Compiling a Lisp: Lambda lifting

If you like Ghuloum's paper, there are three fairly recent compiler books that are inspired by it:

https://nostarch.com/writing-c-compiler - Writing a C Compiler by Nora Sandler, language agnostic for the implementation.

https://mitpress.mit.edu/9780262047760/essentials-of-compila... - Essentials of Compilation (using Racket) by Jeremy Siek

https://mitpress.mit.edu/9780262048248/essentials-of-compila... - Essentials of Compilation (using Python) by Jeremy Siek

Those last two both have open access versions.

The "lambda lifting" seems to be referring to section 3.11 "Complex Constants" in the linked Ghuloum PDF:

Scheme’s constants are not limited to the immediate objects. Using the quote form, lists, vectors, and strings can be turned into constants as well. The formal semantics of Scheme require that quoted constants always evaluate to the same object. The following example must always evaluate to true:

    (let ((f (lambda () (quote (1 . "H")))))
      (eq? (f) (f)))

So, in general, we cannot transform a quoted constant into an unquoted series of constructions as the following incorrect transformation demonstrates:

    (let ((f (lambda () (cons 1 (string #\H)))))
      (eq? (f) (f)))

One way of implementing complex constants is by lifting their construction to the top of the program. The example program can be transformed to an equivalent program containing no complex constants as follows:

    (let ((tmp0 (cons 1 (string #\H))))
      (let ((f (lambda () tmp0)))
        (eq? (f) (f))))

Performing this transformation before closure conversion makes the introduced temporaries occur as free variables in the enclosing lambdas. This increases the size of many closures, increasing heap consumption and slowing down the compiled programs. Another approach for implementing complex constants is by introducing global memory locations to hold the values of these constants. Every complex constant is assigned a label, denoting its location. All the complex constants are initialized at the start of the program. Our running example would be transformed to:

    (labels ((f0 (code () () (constant-ref t1)))
             (t1 (datum)))
      (constant-init t1 (cons 1 (string #\H)))
      (let ((f (closure f0)))
        (eq? (f) (f))))

The code generator should now be modified to handle the data labels as well as the two internal forms constant-ref and constant-init.

Off topic, but anybody have a quick take why LISP isn't the primary language of all of these AI models, and why everybody defaulted to using Python.

I just remember 30 years ago everyone thought LISP would be the language of AI.

Was it just that some nice easy Python Libraries came out, and that was enough to win the mindshare market.? More people can use Python Glue?

In the TXR Lisp compiler, I did lambda lifiting simply: lambda expressions that don't capture variables can move to the top via a code transformation that inserts them into a load-time form (very similar to ANSI Common Lisp's load-time-value).

E.g.

  (let ((fun (lambda (x) (+ x x))))
    ...)

That can just be turned into:

  (let ((fun (load-time (lambda (x) (+ x x)))))
    ...)

Then the compilation strategy for load-time takes care of it. I had load-time working and debugged at the time I started thinking about optimizing lambdas in this way, so it was obvious.

load-time creates a kind of pseudo-constant. The compiler arranges for the enclosed expression to be evaluated just once. The object is captured and it becomes a de-facto constant after that; each time the expression is evaluated it just refers to that object.

At the VM level, constants are represented by D registers. The only reason D registers are writable is to support load-time: load time will store a value into a D register, where it becomes indistinguishable from a constant. If I were so inclined, I could put in a vm feature that will write-protect the D register file after the static time has done executing.

If we compile the following expression, the d0 register is initially nil. The d1 register holds 3, which comes from the (+ 3 x ) expression:

  1> (compile-toplevel '(lambda () (lambda (x) (+ 3 x))))
  #<sys:vm-desc: a32a150>
  2> (disassemble *1)
  data:
      0: nil
      1: 3
  syms:
      0: sys:b+
  code:
      0: 8C000009 close d0 0 4 9 1 1 nil t2
      1: 00000400
      2: 00010001
      3: 00000004
      4: 00000002
      5: 20020003 gcall t3 0 d1 t2
      6: 04010000
      7: 00000002
      8: 10000003 end t3
      9: 8C00000E close t2 0 2 14 0 0 nil
     10: 00000002
     11: 00000000
     12: 00000002
     13: 10000400 end d0
     14: 10000002 end t2
  instruction count:
      6
  #<sys:vm-desc: a32a150>

The close instruction has d0 as its destination register "close d0 ...". The 9 argument in it indicates the instruction offset where to jump to after the closure is created: offset 9, where another "close ..." instruction is found: that represents the outer (lambda () ...)

We have only compiled this top-level form and not yet executed any of the code. To execute it we can call it as if it were a function, with no arguments:

  3> [*1]
  #<vm fun: 0 param>

It returns the outer lambda produced at instruction 9: as expected. When we dissassemble the compiled form again, register d0 is filled in, because the close instruction at 0 executed:

  4> (disassemble *1)
  data:
      0: #<vm fun: 1 param>
      1: 3
  syms:
      0: sys:b+
  code:
      0: 8C000009 close d0 0 4 9 1 1 nil t2
  [... SNIP; all same]

d0 now holds a #<vm fun: 1 param>, which is the compiled (lambda (x) ...). We can call the #<fm fun: 0 param> returned at prompt 3 to get that inner lambda:

  5> [*3]
  #<vm fun: 1 param>
  6> [*5 4]
  7

We can disassemble the functions 3 and 5; we get the same assembly code, but different entry points. I.e. the lambdas reference this same VM description for their code and static data:

  7> (disassemble *3)   ; <-- outer (lambda () ...)
  data:
      0: #<vm fun: 1 param>
      1: 3
  [ SNIP same disassembly ]
      9: 8C00000E close t2 0 2 14 0 0 nil
     10: 00000002
     11: 00000000
     12: 00000002
     13: 10000400 end d0    <---
     14: 10000002 end t2
  instruction count:
      6
  entry point:
     13                     <---
  #<vm fun: 0 param>

The entry point for the outer-lambda is offset 13. And that just executes "end d0": terminate and return d0, which holds the compiled inner lambda.

If we disassemble that inner lambda:

  8> (disassemble *5) ; <--- inner lambda (lambda (x) (+ 3 x)) 
  data:
      0: #<vm fun: 1 param>  <--- also in here 
      1: 3
  syms:
      0: sys:b+
  code:
      0: 8C000009 close d0 0 4 9 1 1 nil t2
      1: 00000400
      2: 00010001
      3: 00000004
      4: 00000002    <---
      5: 20020003 gcall t3 0 d1 t2.    <-- sys:b+ 3 x
      6: 04010000
      7: 00000002
      8: 10000003 end t3
  [ SNIP ... ]
  entry point:
      4             <---
  #<vm fun: 1 param>

The entry point is 4, referencing into the lifted lambda that got placed into d0. Entry point 4 is in part of the close instruction which indicates the parameter mapping. The word there indicates that the argument value is to be put into register t2. Function 0 is called with the t2 argument and d1 (which is 3). Function 0 is in the syms table: sys:b+, a binary add. When it returns, its value is put into t3 and execution terminates with "end t3".