[WantonQuantum]

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.

[JonChesterfield]

The idea is to move variables from the body of the function to the argument list and rewrite the call sites to match.

That decreases the size of the closure (and increases the size of the code, and of however you're passing arguments).

Do it repeatedly though and you end up with no free variables, i.e. no closure to allocate. Hence the name, the lambda (closure) has been lifted (through the call tree) to the top level, where it is now a function (and not a lambda, if following the usual conflating of anonymous function with allocated closure).

Doesn't work in the general case because you can't find all the call sites.

[zozbot234]

I think the "no closure to allocate" is not quite right because the captured parameters of a first-class function still need to be stored somewhere. It just happens as part of the calling code, e.g. consider how a "function object" in C++/Java works: the operator() or .call() code does not need to allocate anything, but the allocation might occur as part of constructing the object itself.

[mrkeen]

Once they've been converted from free variables to formal parameters then it's assumed you can just stack allocate them, and roll them off when you return from your lambda (which is no longer a closure)

[MangoToupe]

> Using the quote form, lists, vectors, and strings can be turned into constants as well.

So all of these forms will transformed to bss?

[JonChesterfield]

bss stores zeros but sure, this lot could end up in rodata if you were careful about the runtime representation, or data if you were a little less careful. Treat the elf (ro)data section as the longest lived region in the garbage collector and/or don't decrement refcounts found there. Good thing to do to the language standard library.