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.