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 this assignment, you should download the Zip archive containing our skeleton.

If you are using git, or some equivalent tool, we recommend that you first make sure that the repository containing your project is clean, and then unzip the skeleton archive directly in it. Then, you should look at the changes introduced by this skeleton, and finally commit them. When working in group, only one group member should do this, while the other should simply pull these changes.

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

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 LowCPSInterpreter)

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.

To submit your project, use sbt’s packageSrc command to create an archive containing the sources of your compiler. As a reminder, this archive is called l3c_3-2024-sources.jar and is located in the target/scala-3.3.1 directory. Send us this archive through our submission server before the deadline.

Remember that we do not accept late submissions, and that only the last accepted submission will be graded. So submit often, and never ever wait until the last minute to do your first submission!

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!