Closure Conversion

For this third graded assignment, you have to complete the implementation of the values representation phase of the L₃ compiler, by adding closure conversion.

To start working on the assignment, you should once again fetch the new code from our git repository, and then rebase your branch on ours. As a reminder, this can be done using the following two commands:

$ git fetch origin
$ git rebase origin/master

After rebasing your branch on ours, you will have access to the following new code:

• in CPSHoister.scala you will find an empty definition of the hoisting phase, which you will have to complete,
• in L3Tester.scala you will find a new definition of backEnd3 that includes the hoisting phase and uses the version of the CPS interpreter that assumes that closure conversion has been done.

To complete this assignment, you must first implement closure conversion by fixing the way function abstraction and application are handled in CPSValueRepresenter. Once this is done, you have to write the hoisting phase that brings all the functions to the top level of the program. This is possible since after closure conversion they are all closed, i.e. they do not have free variables.

One operation you will have to perform during closure conversion is substitution of symbols, to replace the free variables of functions that you close by the fresh variables containing their value, extracted from the environment. To do this, you can use the functions available in package.scala to create substitutions (represented as maps), and then write a helper function to apply such a substitution. That function is pretty straightforward to write, and could look as follows:

private def substitute(tree: L.Tree, s: Subst[Symbol]): L.Tree = {
  def substT(tree: L.Tree): L.Tree = tree match {
    case L.LetP(name, prim, args, body) =>
      L.LetP(name, prim, args map substA, substT(body))
    // ... other cases
  }
  def substC(cnt: L.Cnt): L.Cnt =
    ??? // code for continuation definitions
  def substF(fun: L.Fun): L.Fun =
    ??? // code for function definitions
  def substA(atom: L.Atom): L.Atom =
    ??? // code for atoms
  substT(tree)
}

You can test your phase as usual, using sbt's test command.

To submit it, use sbt's packageSrc command to create an archive containing the sources of your compiler. As a reminder, this archive is called l3c_2.13-2020-sources.jar and is located in the target/scala-2.13 directory. Submit this archive to our submission server.

A total of 80 points are assigned to this project part, out of a total of 500 for the whole semester.

You can choose to implement either the "simple" version of closure conversion, or the optimized one. Notice however that only doing the former will cost you 10 points.

Be careful, though, as an incorrect implementation of the optimized version could give you less points than a correct implementation of the simple one. We therefore strongly recommend that you start by implementing the simple translation and, if it passes all tests and you still have time, work on the optimized one. And to be on the safe side, submit a version of your code as soon as the simple translation works.

Your submission will be graded based on:

1. its correctness, i.e. whether it passes all the functional tests that were made available to you, and additional ones that we might have,
2. the version of the closure conversion you implemented: as explained above, only implementing the simple one will cost you 10 points,
3. its style, which will be worth 4 points for this assignment, so please pay attention to the feedback you received for the previous assignments.