Overview
The aim of this part is to add a closure conversion phase to your minischeme compiler.
As explained in the course, closure conversion is a translation phase which transforms a program potentially containing nested functions with free variables into one where all functions are at the top-level (and, hence, closed). This translation can be split in two parts:
- the closing of functions,
- the hoisting of nested functions to the top-level.
Two representations for closures were presented in the course, and for this project we ask you to use the flat (or one-block) representation.
To add closure conversion to your minischeme compiler, we suggest you proceed roughly as follows:
-
Define a function to compute the set of free
variables of a term (i.e. a tree), by simply
translating the function
Fgiven in the course to Scala code, and check that it works as expected. -
Write a function to close a term, by translating the
function
Cgiven in the course. Check that it works as expected on a simple example like themake-adderfunction used in the course. -
Write a function to hoist nested functions to the top-level.
Check that it works as expected, e.g. on the
closed version of the
make-adderfunction.
Notes
- One problem you will encounter is that of creating the symbols corresponding to the various identifiers generated during closure conversion (e.g. the parameter referencing the environment, or the hoisted functions). To keep things simple, we suggest that you ensure that you always use unique identifiers, and simply re-run name analysis after closure conversion. You are of course free to use another solution if you prefer.
-
Recursive closures need not be treated specially, although the
lectures suggest otherwise. The reason is that minischeme does
not allow one to
definenamed non-top-level functions, therefore there can't be recursive functions. The other binding construct,let, allows naming functions, but does not allow recursive definitions. If the language permitted such recursive nested functions, they would need to be treated specially, as described in the course.