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.

To get started, download the skeleton file from Canvas.

2 Project Structure🔗

Now the project directory has changed a little bit. In the top-level directory, you can see folders compiler, examples and library.

The library folder contains files that define a standard library for our language. The standard library provides some useful functions to manipulate datatypes such as strings, integers, lists, etc. The compiler can take the main MiniScala program along with separate library files as input; see compiler/README.md for more instructions.

The examples folder provides some non-trivial example programs, which you can use to test your implementation.

The source code and test code are in compiler. In compiler/src/main/scala/project4, you can see the source code that are relevant to this project.

3 Your Task🔗

You only need to update the file MiniScalaToCPSTranslator.scala under compiler/src/main/scala/project4 to complete this project.

You will notice that Main.scala from the new project doesn’t directly run an interpreter anymore (which was the case before). Instead, it first runs the CPS translator (which you will build) and then an interpreter over the CPS IR program generated from the translator.

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.

Your task is to implement the methods nonTail, tail and cond in MiniScalaToCPSTranslator.scala, which directly correspond to the optimized translations that we discussed in the lecture. The transformation for let is already given to you as an example. Your task is to complete these methods by adding the missing cases.

4 Syntactic Sugar and New Types🔗

The skeleton code already handles a richer MiniScala language and provides a comprehensive frontend for you. You do not need to change any code for the parser or semantic analyzer, but you should be aware of what they provide for you when implementing the CPS translation.

The frontend implements some syntactic sugar, including:

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 these skeleton also provides solutions for previous assignments, you may want to look over MiniScalaParser and MiniScalaAnalyzer. Please post questions on Piazza if you have any questions about the implementation of these functions.

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.

5 Implementation Hints🔗

• Try implementing the non-optimized translations in nonTail first (there are the rules shown in week4-2.pdf and week5-1.pdf). This represents roughly 80% of the work. Once this is done, you can implement the optimized version using all three functions available (nonTail, tail, and cond discussed in week5-2.pdf).

• Take the time to understand the comments and helper methods that are provided, and use them as frequently as possible! It will save you time and help you avoid common errors. The comments in MiniScalaToCPSTranslator.scala also explains some Scala features used in the project.

6 Testing🔗

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

The skeleton has already provided a suite of blackbox tests in src/test/scala/project4/ok, which you should take advantage of to check the correctness of your implementation.

You should at least write 5 tests by yourself, otherwise points will be deducted.

7 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.

See General Submission Guidelines for more information.