A(dministrative?)-Normal Form

En Lecture 4, Ben Lerner definió ANF y dio varios ejemplos de como convertir expresiones a ANF.

En clase discutimos alternativas a la funcion anf de Dr. Lerner, en particular que podiamos crear un nuevo tipo para no confundir expresiones con expresiones en ANF. Joe Gibbs presenta una version de ANF que usa unos nuevos tipos, pero me parece un poco complicada. Voy a tratar de hacer una un poco mas sencilla.

Sabemos que queremos distinguir expresiones immediatas de las demas, asi que podemos definir un tipo.

type immexpr =
  | ImmNum of int64
  | ImmId of string

Ahora podemos definir otro tipo aexp de expresiones en ANF. A diferencia de las expr, las aexpr solo pueden construir expresiones en ANF.

type aexpr =
  | AImm of immexpr
  | APrim2 of prim2 * immexpr * immexpr
  | ALet of string * aexpr * aexpr

Normalizando

La funcion anf debe entoces recibir un tag expr y producir un aexpr. Vamos a llamar esta anf. Recibe tag expr y una funcion que recibe immexpr y devuleve aexpr, aqui llamana expr_with_holes esta funcion es como un callback, y va a recibir el inmediato que contiene el resultado de cualquier subexpression complicada. La llamaremos para obtener el valor de la subexpression.

let rec anf (e : tag expr) (expr_with_holes : (immexpr -> aexpr))
 : aexpr =
  match e with
  | ENumber (n, _) -> (expr_with_holes (ImmNum n))
  | EId (b, _) -> (expr_with_holes (ImmId b))

El lio de anf es para poder convertir subexpresiones complicadas en valores inmediatos, para compilar mas facil. Por ejemplo, un EPrim2 puede tener subexpresiones complicadas en left y right, pero las vamos a convertir en inmediatos, e insertarlos en un APrim2:

  | EPrim2 (op, left, right, tag) ->
     anf left (fun limm ->
       anf right (fun rimm ->
           let varname = "foo" ^ (string_of_int tag) in
         ALet (varname,
           APrim2 (op, limm, rimm),
           (expr_with_holes (ImmId varname)))))

Compilando

Nos hara falta una funcion para convertir un inmediato a un arg:

  let imm_to_arg imm env =
    match imm with
    | ImmNum n -> Const n
    | ImmId v -> let slot = lookup v env
                 in RegOffset (RSP, ~-8*slot)

Ahora podemos compilar un inmediato, moviendolo a RAX:

let rec compile_aexpr (e : aexpr) (env : env) : instruction list =
  match e with
  | AImm imm ->
     [ IMov (Reg RAX, imm_to_arg imm env) ]

Y los APrim2 tienen argumentos inmediatos que podemos sumar

  | APrim2 (Plus, left, right) ->
     [ IMov (Reg RAX, imm_to_arg left) ;
       IAdd (Reg RAX, imm_to_arg right) ]

Otro otro ANF

A(dministrative?)-Normal Form

Normalizando

Compilando