Ecole Polytechnique Fédérale de Lausanne
Part Three: Closure conversion
English only

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:

  1. the closing of functions,
  2. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.