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
F given in the course
to Scala code, and check that it works as expected.
-
Write a function to close a term, by translating the
function
C given in the course. In a first
version, you can ignore the problem of recursive closures to
simplify your job. Check that it works as expected on a
simple example like the make-adder function
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-adder function.
-
Modify your code so that it handles recursive closures
correctly, if it doesn't already.
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.
|