Advanced Compiler Construction - Project 4: Closure conversion

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. Please give that 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 (C 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. After creating these symbols, you often need to create corresponding SIdent tree nodes, and attribute them correctly. This is easy to do with method ident of object TreeGenerator.

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.

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 the same test program as for the previous part, bignums.scm, but this time in source form. Notice that this program uses the list library that resides in libraries/lists.scm, which should also be given to the compiler/interpreter.

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/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/Symbol.scala
  compiler/minischeme/Token.scala
  compiler/minischeme/Tree.scala
  compiler/minischeme/TreeGenerator.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.

The archive containing your solution should be attached to an e-mail sent to michel.schinz+acc4@gmail.com, before 23:59, April 17, 2008.

Solution

The file closureconverter.jar contains a compiled version of a working closure conversion phase for the minischeme compiler. To use it, simply apply the ClosureConverter object to your program to get a closure-converted version of it, which you can then hand to the code generator.

Ecole polytechnique fédérale de Lausanne

Laboratoire des méthodes de programmation