Assignment 3: Data Representation

Due Date: 20th March, 2014

(graded group assignment)

Your task in this assignment is to implement a compiler phase for the CPS data representation transformation. In the new assignment3 branch you will find a template for this compiler phase in class l3.CPSDataRepresenter. You can use the helper methods in class CPSDataRepresenter 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. 

Also, do 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.