Naming expressions with let: Compiler Edition

We are in the midst of adding support for names. Recall that our language will support OCaml-style variable binding: variables are immutable, and are bound in expressions using let. Some examples:

(let ((x 1)) x) ; => 1                                                                                 
(let ((x 3)) (let ((y (+ x 2)) (+ x y))) ; => 8                                                        
(let ((x 3)) (let ((x (+ x 2)) (+ x x))) ; => 10

Names in the compiler

In the compiler, we’ll start with let:

Listing 1: compile.ml

let rec compile_exp (stack_index : int) (exp : s_exp) : directive list =
  match exp with
  | Lst [Sym "let"; Lst [Lst [Sym var; e]]; body] ->
    compile_exp stack_index e @ ...

Once we’ve compiled e, what should we do with it? We know we want to compile body, and somehow have references to x in body be able to “find” the value of e. We definitely can’t leave that value in rax–as we saw last time, it will get overwritten right away. We’ll need to “remember” this value for later use. Let’s put it in memory!

Listing 2: compile.ml

let stack_address (stack_index : int) = MemOffset (Reg Rsp, Imm stack_index)

let rec compile_exp (stack_index : int) (exp : s_exp) : directive list =
  match exp with
  | Lst [Sym "let"; Lst [Lst [Sym var; e]]; body] ->
    compile_exp stack_index e @ [Mov (stack_address stack_index, Reg Rax)] @ ...

(The stack_address helper function lets us avoid a little repetition; we’ll want to rewrite the stack code from last time to use it as well).

Now we want to compile body, but make sure our compiler knows to get the right value from memory if it runs into Sym var. Just like in the interpreter, we can do this with a symbol table. In the interpreter, our table mapped variables to values; here, we’ll need to map variables to stack indexes.

Listing 3: compile.ml

let stack_address (stack_index : int) = MemOffset (Reg Rsp, Imm stack_index)

let rec compile_exp (tab : int symtab) (stack_index : int) (exp : s_exp) : directive list =
  match exp with
  | Lst [Sym "let"; Lst [Lst [Sym var; e]]; body] ->
    compile_exp tab stack_index e @ [Mov (stack_address stack_index, Reg Rax)] @
    compile_exp (Symtab.add var stack_index tab) (stack_index - 8) body
  | Sym var when Symtab.mem var tab ->
    [Mov (Reg Rax, stack_address (Symtab.find var tab))]

Here’s what the compiler produces for (let ((x 1)) (+ x 2)):

entry:
        mov rax, 4
        mov [rsp + -8], rax
        mov rax, [rsp + -8]
        mov [rsp + -16], rax
        mov rax, 8
        mov r8, [rsp + -16]
        add rax, r8
        ret

Homework 3

We spent some time talking about Homework 3; see the lecture capture for details.