Assignment 3: Value Representation

Due Date: 24th March, 2016, 13:00

(graded group assignment) 

Important: This is the first group assignment (for groups of 2 members). Before you start it, you need to find a partner to work together with for the rest of the course. After you form your group, you will need to decide on whose work you are going to base the rest of the compiler on. Please send a message to Manos ( with the group members, former group numbers, and which group’s repository you wish to keep. The other member will be moved to this group. If you cannot find a partner or want to work alone (the latter is strongly discouraged), also send a message to Manos. 

You won’t have access to the repository you abandon after this assignment, and the person whom it belonged to will need to clone the common one. Of course you will have the local copy of your code, so if you feel like using some parts of the code later, you can always transfer them manually.


Your task in this assignment is to implement a compiler phase for the CPS value representation transformation. In the new assignment3 branch 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. Please note that the the following aspects will taken in to consideration while grading:

a) Correctness of the implementation, b) The time and memory efficiency of the implementation.

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.

This assignment relies on the correct implementation of the previous one (the CL3ToCPSTranslator class), and the reference implementation will not be revealed. You will have to merge the changes you made for assignment 2 into the new source tree. To do so, use:

 git commit -a git fetch  git merge origin/Assignment3 cd l3/compiler sbt clean update compile test 

To commit your changes use

 git add ...                  # files modified, as shown by "git status" git commit git push origin master 

You should be able to do this without merge conflicts or compilation errors. If you get into trouble with git, ask the TAs.


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 Repository application 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.CPSDataRepresentation_Whitebox so it’s a matter of just writing the source code and the resulting tree. It is usually an effort that pays off.