View the Project on GitHub TiarkRompf/cs502

Project 3: Value Representation

Due: Oct 6, 11:59PM

This project will be done individually, as with the previous two projects.

Your task in this assignment is to implement a compiler phase for the CPS value representation transformation, including closure conversion. In the skeleton code, you will find a template for this compiler phase in class l3.CPSValueRepresenter. You can use the helper methods in class CPSValueRepresenter and object BitTwiddling. Additionally, you are also required to implement the hoisting phase that brings all function bodies to the top level (CPSHoister.scala). Please note that the the following aspects will taken in to consideration while grading:

For instance, transforming a primitive operation x op y by naively decoding the arguments (x,y) and encoding the result back will fetch you lesser points if there exists a better translation that avoids, completely or partially, some encodings/decodings. Note: To that end, make sure to use Left shift ( << ) and right shift ( >> ) operations to implement multiplication and division by 2 as descibed in the lectures.

For the closure conversion part, you can choose to either implement the "simple" or the optimized version. Correctly implementing the simplified one will give you 90% of the grade for this assignment, while a correct implementation of the optimized transformation will give you 110% of the grade.

Notice however that by submitting an incorrect version of the optimized transformation you may loose a lot of points depending on the mistakes. Therefore, we recommend that you start by implementing the basic closure conversion procedure and, if you are successful and still have time, to extend it to the optimized procedure.

The skeleton code for the assignment is available here.

This assignment relies on the correct implementation of the previous one (the CL3ToCPSTranslator class). If you are confident that your implementation of CL3ToCPSTranslator is correct, feel free to use your implementation. You are also free to use the reference implementation that is part of the skeleton for Project 3.


From this assignment on, you will choose the shapes for the trees you generate. You should inspect them visually and decide whether or not they are correct and optimal. The application in the given skeleon code will not have whitebox tests, but it will still have an extensive blackbox test suite to ensure the correctness of the programs you generate.

Although we will not test tree shapes, we still encourage you to do so for every transformation rule you write. You have the necessary infrastructure in l3.test.CPSValueRepresentation_Whitebox so it's a matter of just writing the source code and the resulting tree. It is usually an effort that pays off.

Turning In

The project is due by October 6, 11:59PM. To turn in your project, go to the same directory that your proj3 directory lives in (you do not have to name it proj3, but it must contain all of the project files) and type:

turnin -c cs502 -p project3 proj3 

You can verify the status of your turned in project by running:

turnin -c cs502 -p project3 -v