CS352

View the Project on GitHub TiarkRompf/cs352

Project 4: CMScala to CPS Translation

Due: Sept 28, 11:59PM

Introduction

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

Open Project in Your Favorite Scala IDE

You can use your editor or IDE of choice. The Scala website has instructions for a range of alternatives. If you are using Eclipse, you first need to generate an Eclipse project. Execute:

        sbt eclipse
        
and then import the Project into Eclipse: File > Import > Existing project into Workspace. Select the root folder proj4 and hit Finish.

Browse the Files

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

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.

Turnin

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
        

Testing

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.