Closure Conversion in Python
This article discusses the process of converting closures into assembly code using Python. The author starts by explaining that this is a conversion of "closure conversion" (not lambda lifting) and provides an example implementation in Python.
The process involves three main steps: binding, analysis, and compilation. Binding refers to the process of recognizing variable names in special expressions like let and lambda, while analysis is concerned with identifying free variables in each expression. Compilation involves converting these variables into assembly code.
Binding Variables
The author introduces a class called labels, and updates it as needed during the recursive traversal of the program.
The author then explains that they do not need to consider variable names when dealing with simple constants. However, if a variable is bound by a let or lambda expression, they are left alone, while otherwise, they need to be marked as free variables.
The author also notes an irritating special case where certain language primitives, such as the addition operator (+), should not be considered free variables.
Converting Lambda Expressions
To convert lambda expressions, the author must reason about all three key components: the lambda binds its parameters as new names, those are the only bound variables in a lambda, and they want to keep track of the set of variables that are free inside the lambda.
The author explains that they pass in a new set for the lambda body's free set and update the global environment accordingly. They also create a code form and a closure form by appending the code to the global list with a new label, threading the label through to the closure, and handling any variables that are bound inside the lambda but not within its scope.
Converting Let Expressions
The author then explains how they convert let expressions, which have two wolves: one is bound inside the let, while the other is free inside the let. This happens because let evaluates all of its bindings without access to the bindings as they are being built up.
The author notes that this conversion can be done by treating the variables in the binding expression as always-bound, and then simply updating the global environment accordingly.
Converting Function Calls
The author explains how they convert function calls, including handling always-bound primitive operators like +, which should not be treated as a function call.
They also explain how they compile closure forms into assembly code, including storing pointers to the corresponding labels, writing those labels to the heap, finding and writing pointers to the definitions of free variables, and tagging the closures with the necessary information.
Converting Closures
The author provides an example of how they convert a closure expression into assembly code. They show that ((lambda (x) x) 3) compiles to an assembly instruction.
Conclusion
The author concludes by noting that this is not the end of their compiler, as there are still many features and optimizations to implement. However, they are pleased with what has been accomplished so far.