The Essentials of Compilation (using Racket) by Jeremy Siek links to this[0] which when downloaded says "An Incremental Approach in Python" and is in Python.
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:
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:
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:
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.
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.
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.
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:
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:
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:
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".
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 paper itself has been discussed a few times:
An Incremental Approach to Compiler Construction (2006) [pdf] - https://news.ycombinator.com/item?id=29123715 - Nov 2021 (10 comments)
An Incremental Approach to Compiler Construction (2006) [pdf] - https://news.ycombinator.com/item?id=20577660 - July 2019 (5 comments)
An Incremental Approach to Compiler Construction (2006) [pdf] - https://news.ycombinator.com/item?id=13207441 - Dec 2016 (19 comments)
An Incremental Approach to Compiler Construction (2006) [pdf] - https://news.ycombinator.com/item?id=10785164 - Dec 2015 (13 comments)
Writing a Compiler in 24 Small Steps [pdf] - https://news.ycombinator.com/item?id=1652623 - Sept 2010 (16 comments)
An Incremental Approach to Compiler Construction - https://news.ycombinator.com/item?id=1408241 - June 2010 (18 comments)
(and also in comments: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...)
The Essentials of Compilation (using Racket) by Jeremy Siek links to this[0] which when downloaded says "An Incremental Approach in Python" and is in Python.
[0]: https://github.com/IUCompilerCourse/Essentials-of-Compilatio...
https://github.com/IUCompilerCourse/Essentials-of-Compilatio...
My man. I appreciate you, and your kindness to me.
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:
So, in general, we cannot transform a quoted constant into an unquoted series of constructions as the following incorrect transformation demonstrates: 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: 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: The code generator should now be modified to handle the data labels as well as the two internal forms constant-ref and constant-init.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.
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.
> Using the quote form, lists, vectors, and strings can be turned into constants as well.
So all of these forms will transformed to bss?
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.
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.
That can just be turned into: 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:
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:
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: 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: 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: 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:
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".