1 Introduction🔗

In this assignment, you will implement the optimized CPS transformations we have seen in the lecture.

In previous assignments, we have focused on building up a frontend of our compiler pipeline (i.e., our parser and semantic analyzer), and have build a relatively simple backend. 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 comprehensive frontend. Some of the new pieces of syntactic sugar of which you should be aware are as follows:

e1 && e2 ⟹ if (e1) e2 else false
e1 || e2 ⟹ if (e1) true else e2
!e1 ⟹ if (e1) false else true
"c1...cn" ⟹ val s = new Array[Char](200); s(0) = ’c1’; ...; s
(n1: T1, ...) => b1 ⟹ def anon1(n1: T1, ...) = b1; anon1

You can find all code dealing with syntactic sugar in compiler/src/main/scala/project4/MiniScalaParser.scala, though you will not need to make any modifications there. Similarly, the code for desugaring during semantic analysis can be found in compiler/src/main/scala/project4/MiniScalaAnalyzer.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 MiniScalaAnalyzer if you have any questions about how these functions are implemented. Further clarification can be discussed 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:

• Integer: Now available in base 16 with 0x prefix.

• Char: All character literals are supported (e.g., ’c’, ’s’, ’3’, ’5’, ’2’, ’\n’, etc.).

• Boolean: As before, Boolean literals are true and false.

• Unit: As before, the Unit literal is ().

• String: Strings are now supported in our language, with string literals appearing as expected (e.g. "this is a string", "help, I’m stuck in compiler class", "let me out", "\n\\compiler gives an error: \"unable to escape\"\n", etc.).

And some operators for these types:

• + - * << >> & | ^ / % : (Int, Int) => Int

• < <= > >= : (Int, Int) => Boolean

• == != : (T1, T2) => Boolean

• id : T => T

• toChar : Int => Char. Note: Int must be valid Unicode code-point

• toInt : Char => Int

• isInt isChar isBoolean isUnit : T => Boolean

• getchar : () => Int. Note: return value between 0 and 255, or -1

• putchar : Int => Unit. Note: input between 0 and 255

Other types include Array[T], function types, Pairs, and List[T]. Take a look at the files in library as well as the README file under compiler folder to see how to use them.

2 Getting Started🔗

Download the skeleton file here.

3 Project Structure🔗

Now the project directory has changed a little bit. In the top dir, you can see folders compiler, examples and library. The source code and test codes are in compiler. The examples folder provides some example programs, similar to previous projects. The library folder contains files that define a standard library for our language. In compiler/src/main/scala/project4, you can see the source code that are relevant to this project.

You only need to update the file MiniScalaToCPSTranslator.scala.

You will notice that Main.scala from the new project doesn’t run the CMScalaInterpreter anymore (which was the interpreter used before). Instead, it 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 MiniScalaToCPSTranslator.scala directly correspond to translations that we discussed in 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.

4 Submission🔗

You should turn in the proj4 directory. Please run an sbt clean before packaging and submitting.

To submit your project, create a ZIP file named proj4.zip of the proj4 directory and upload it to the corresponding assignment on Canvas.

Verify your submission by downloading the ZIP file you uploaded on Canvas and extracting its content. The uncompressed content should be the proj4 folder containing the code. Your submission ZIP file should have the exact same structure as the skeleton ZIP file.

Your submitted code must compile, i.e. running sbt compile gives no errors. If your code does not compile, your submission will not be graded and you will receive 0 points for the whole project.

Late Submission Policy: Projects are due at 11:59pm on the due date. Succeeding projects build upon previous ones and will reveal solutions of preceding projects, so late submissions will not be accepted. Submitted after the deadline will receive 0 points.