Values Representation

For this second graded assignment, you have to implement the phase that takes care of the representation of values in the L₃ compiler.

To start working on the assignment, you should fetch the new code from our git repository, and then rebase your branch on ours. This can be done using the following two commands:

$ git fetch origin
$ git rebase origin/master

Your task is to write the CPSValueRepresenter phase, which is currently completely empty.

As a reminder, the goal of this phase is to simplify the code that is produced by the translation to CPS, by representing all L₃ values using values of the target architecture (the L₃ virtual machine). These are basically bit vectors of size 32 containing either a pointer to a heap-allocated block, or some tagged atomic value.

The phase therefore consists mostly in converting all atomic L₃ values (unit, booleans, characters and integers) to tagged values, and translating all the L₃ primitives to primitives of the target architecture. Remember that L₃ primitives are described by the L3Primitive type, while the primitives of the target architecture are described by the CPSValuePrimitive and CPSTestPrimitive types.

The output of the values representation phase is a new variant of the CPS language, which can be interpreted by an interpreter that has been given to you, called CPSInterpreterLowNoCC. The NoCC suffix means that it assumes that closure conversion has not been done yet, which is correct as it will be the subject of the next assignment.

Writing the values representation phase should not be too challenging technically, but please pay attention to two important points:

1. you must translate all primitives as efficiently as you can, e.g. translate integer addition to one addition followed by one subtraction (or something equivalent) as done in the lecture,
2. you should define helper methods to factor out common code, as well as use the methods we give you — in particular, have a look at the method bitsToIntMSBF in package.scala, which might be useful.

As usual, we will start working on this assignment together at the beginning of the lab session, so it is strongly recommended that you attend it!

You can test your phase as usual, using sbt's test command.

Notice that the test framework that we give you has been augmented for this assignment, and the L3Tester object now defines a new back-end phase called backEnd3:

val backEnd3 = (
  CL3ToCPSTranslator
    andThen CPSValueRepresenter
    andThen CPSInterpreterLowNoCC
)

This new back-end is the one that tests your phase, by feeding its output to the interpreter. It is used both by "synthetic" tests — see object SyntheticTests3 in SyntheticTests.scala — and tests based on example programs — see object ExamplesTests3 in ExamplesTest.scala.

This assignment will not be submitted individually, but along with the next one about closure conversion, which will start in a week (on 2020-03-19). Submission instructions will therefore be given at the end of that assignment.

Make sure that you are done with this part of your project by the time the closure conversion part starts! This will give you enough time to work on the closure converter, which is quite challenging.

A total of 40 points are assigned to this project part, out of a total of 500 for the whole semester. Your submission will be graded based on:

1. its correctness, i.e. whether it passes all the functional tests that were made available to you,
2. its completeness, i.e. whether you covered all the cases as required, and translated all the primitives efficiently, that is using the optimized translations presented in the lecture, and similar ones for the cases not covered there,
3. its style, which will be worth 2 points for this assignment, so make sure to write clean code!