View the Project on GitHub TiarkRompf/cs352

Project 4: CMScala to CPS Translation

Due: Feb 14, 11:59PM


In this assignment, we are asking you to implement the optimized CPS transformations you have seen in the course.

In previous assignments, we have focused on building up frontend of our compiler pipeline (i.e., our parser and semantic analyzer), and have made due with a relatively simple backend. As many students have noticed, this has resulted in suboptimal assembly code being generated. As such, we will now shift gears and focus more heavily on creating an optimized backend.

For this project, we have provided you with a more complex frontend than we've seen thus far. Some of the new pieces of syntactic sugar of which you should be aware are as follows:

You can find all code dealing with syntactic sugar in MiniScalaParser.scala, though you will not need to make any modifications there.

Similarly, the code for desugaring can be found in CMScalaAnalyzer.scala. Again, no modifications are necessary in this file.

As we will not be providing solutions for previous assignments, you may want to look over MiniScalaParser and CMScalaAnalyzer if you have any questions about how these function. We are also happy to provide further clarification on Piazza as needed.

In addition to these pieces of syntactic sugar, we also have some new types, with corresponding literals and operators. Below is a list of some of the types available in our language:

And some corresponding operators:

Other types include Array[T], function types, Pairs, and List[T]. Take a look at the library files to see how to use them.

Step 1: Getting Started

The project has been designed and tested for Linux/Mac OS. If you only have Windows installed on your personal laptop, consider running Linux in a VM or using the lab machines for the project.

If you use remote access to work on your project, please use one of the lab machines pod1-1 to pod1-20 with the suffix cs.purdue.edu (e.g. pod1-1.cs.purdue.edu)

Download the skeleton file here.

Step 2: Project Structure

Browse the Files

All files with the prefix MiniScala are handling the parsing. All files with prefix CMScala are handling the semantic analyzer pass.

You only need to update the file CMScalaToCPSTranslator.

You will notice that MiniScala.Main from the new project doesn't run the CMScalaInterpreter anymore (it was the interpreter we were using before), but first runs the CPS translator and then an interpreter for your CPS representation.

Also, you may notice that between translation and interpretation, there is an additional step called SymbolicCPSTreeChecker. The purpose of this module is to go through your generated CPS tree, check that all names used are defined exactly once, and emit useful warnings in case they are not. Take advantage of this output to track any bugs you may have in the translation. Notice that, since SymbolicCPSTreeChecker.apply returns Unit, we have to pass it to the passThrough function to integrate it in the pipeline.

You will find that methods nonTail, tail and cond in MiniScala.CMScalaToCPSTranslator directly correspond to translations that were explained during the lecture. Transformation for let is already given to you as an example. Your task is to complete these methods by adding the missing cases. Important: take the time to understand the helper methods that are provided, and use them as frequently as possible! It will save you time and help you avoid common errors.

Note that there are two different kinds of tests: Whitebox and Blackbox. Whitebox tests check that the entire output (i.e., the IR post-translation) is correct. Blackbox tests only ensure that the value generated is correct (e.g., def f(x: Int) = x*x; 0 will only check that the program returns 0).

Implementation Hint

Try implementing the non-optimized translations in nonTail (there are the rules shown in the beginning of the lecture). This represents 80% of the work. Once this is done, you can implement the optimized version using all three functions available (nonTail, tail, and cond).


You should turn in the proj4 directory. Please run an 'sbt clean' before submitting. You can also remove the target/.

To turn in your project, make sure that you are in the directory that contains the proj4 directory. Then, type the following:

        turnin -c cs352 -p proj4 proj4

To verify your turned-in work, do:

        turnin -c cs352 -p proj4 -v


Unlike for the previous assignment, very few test cases are given to you. You should fill in the tests, as they guide you through the implementation. The tests that you write may also get you small bonuses while grading.