Advanced Compiler Construction

Introduction

The goal of this second graded assignment is to add a closure conversion phase to your minischeme compiler. As explained in the course, closure conversion transforms all functions to close them. This is done by replacing all references to free variables by references to fields of an environment that gets passed as an additional argument to closed functions.

Free variables computation

Before implementing closure conversion itself, write (and test) a function to compute the set of free variables of a lambda expression. This amounts to translating the F function presented in the course to Scala code. Make sure that the free variables are represented as symbols (not as compiler trees), and please give the function a more expressive name than simply F.

Closure conversion

Closure conversion should be implemented as a transformation phase that gets as argument a list of trees with possibly open functions, and returns an equivalent list of trees containing only closed functions. Once again, this amounts to translating a function presented in the course (⟦⋅⟧ in this case) to Scala code.

During closure conversion, you will need to create new identifiers for the various environments and closures. Since closure conversion takes place after name analysis, you should create new symbols, not simply new strings. The method freshLocal in object Symbol does precisely that.

Notice that the interpreter can deal with open functions, so it doesn't need the closure conversion phase. Therefore, you should only invoke closure conversion from the MainCompiler function.

Finally, notice that you don't need to do anything about recursive closures since in minischeme, they are always global. This implies that they are never free.

Tips and tricks

As explained above, the interpreter does not need a closure conversion phase. However, it should be able to interpret a program transformed by your closure conversion phase. Therefore, to debug your closure conversion phase, simply feed its output to the interpreter and see what comes out of it. The interpreter has a big advantage over the VM: it produces meaningful error messages instead of crashing.

Another useful trick to debug the closure conversion phase is to print the program after transformation, using the TreePrinter object.

As always, it is important to test your program as thoroughly as possible. To help you, we provide you with two test programs: incr.scm is a small program which contains the adder seen in the course; you can use queens.scm to test if your transformation works on larger programs (note that it requires both libraries/predefined.scm and libraries/lists.scm), this program creates some closures when calling the method for-all.

Solution submission

Your solution must be submitted as a ZIP archive containing exactly the following files - not one more, not one less:

  README  (short description of your solution)
  compiler/minischeme/ClosureConverter.scala  (your closure conversion phase)
  compiler/minischeme/Code.scala
  compiler/minischeme/EtaExpander.scala
  compiler/minischeme/FileReader.scala
  compiler/minischeme/Generator.scala
  compiler/minischeme/Instruction.scala
  compiler/minischeme/Interpreter.scala
  compiler/minischeme/Label.scala
  compiler/minischeme/Main.scala
  compiler/minischeme/NameAnalyzer.scala
  compiler/minischeme/Opcode.scala
  compiler/minischeme/Parser.scala
  compiler/minischeme/Primitives.scala
  compiler/minischeme/Register.scala
  compiler/minischeme/Report.scala
  compiler/minischeme/Representable.scala
  compiler/minischeme/Scanner.scala
  compiler/minischeme/SeqReader.scala
  compiler/minischeme/Symbol.scala
  compiler/minischeme/Token.scala
  compiler/minischeme/Tree.scala
  compiler/minischeme/TreePrinter.scala

The README file should contain a short description of your solution and its peculiarities, as well as the name of all its authors. With the exception of ClosureConverter.scala and Main.scala, the files you submit should be identical to the ones you were given. If they are not, explain why in the README file.

To help you check the contents of the archive, we provide you with a Scala script called SubCheck4.scala. When run with your archive as argument, this script should not report any problem.

Remember that according to our submission regulations, we do not accept solutions which fail to compile.

The archive containing your solution should be submitted on Moodle before 23:55, April 2, 2009.

Ecole polytechnique fédérale de Lausanne

Programming Methods Laboratory