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 download a Zip archive containing our skeleton, and extract it on top of your current project, after making sure that you committed all your work!

After extracting the archive, you will have access to the following new code:

• in CPSTree.scala, you will find a new flavor of the CPS language, FlatCPSTreeModule, that is to be produced by the hoisting phase, and for which there are new “givens” in CPSTreeChecker and CPSTreeFormatter,
• 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 by the type Subst[T], an alias for Map[T,T]. The current substitution should be passed as an additional context parameter to your rewrite methods. Don’t forget to apply that substitution to names as you rewrite the tree!

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

To submit your project, use sbt’s packageSrc command to create an archive containing the sources of your compiler. As a reminder, this archive is called l3c_3-2024-sources.jar and is located in the target/scala-3.3.1 directory. Send us this archive through our submission server before the deadline.

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.