Desugaring

The goal of this first assignment is to properly set up your development environment and to familiarize yourself with the L₃ language and its compiler. Although this assignment is not graded, you should take it seriously as it guides you through the L₃ code base and gives you the information you need to work efficiently on the project.

To work on the project, you first need to install sbt, the Scala build tool that we will use. Depending on how you choose to install sbt, you might have to install Java beforehand, in which case we recommend installing version 21 from the Adoptium web site.

Notice that if you are working on Windows, we strongly recommend that you install the Windows Subsystem for Linux (WSL), as all the instructions for this course assume that you are working in such a Unix-like environment, and we cannot provide support for anything else.

The first task of this assignment consists in completing the desugaring process in the L₃ compiler.

For that, navigate to the compiler subdirectory of your freshly created project and launch sbt in interactive mode. This can be done by entering the following commands in your shell:

$ cd l3-warmup/compiler
$ sbt

Sbt is the standard tool to compile, test and run Scala projects. You can compile the L₃ compiler using the compile command in the sbt shell:

sbt:l3c> compile

Notice that this is an sbt command, not a shell command! This is why the prompt is not $ anymore, but sbt:l3c>, sbt’s default prompt (l3c is the name of the project, and stands for L₃ compiler).

The first time you compile the project, a lot of project-specific dependencies will be downloaded, so be patient! Once compilation succeeds, you can finally run the L₃ compiler using sbt’s run command, to which you should give the path to the input file. For now, you will try to compile a very simple “hello, world!” L₃ program found in ../examples/hello.l3, by entering the following command:

sbt:l3c> run ../examples/hello.l3

You will notice that the compiler fails with a “not implemented” exception. Your next task is to add the missing pieces to the syntactic sugar translation.

For that, navigate to the bottom of file src/l3/L3Parser.scala. You will notice that some methods are implemented in terms of a method called ???, which throws a runtime exception. Implement those methods according to the rewrite rules given in this week’s lecture.

While implementing these methods, you will often have to transform sequences of trees of type Seq[Tree] or similar. The foldRight and reduceRight methods are very useful for that, but if you prefer to do pattern matching, remember that the syntax is as follows:

trees match {
  case Seq(head, tail @ _*) => // … non-empty Seq
  case Seq() =>                // … empty Seq
}

After implementing only the sBegin and sFun methods in src/l3/L3Parser.scala, you should already be able to run the hello.l3 example. Now implement all the other desugaring methods.

As you are developing the desugaring, it would be good to test your implementation. We provide you with a few tests that you can run using sbt’s test command:

sbt:l3c> test

Notice that the test called int-print will fail even if your implementation of desugaring is correct. To make it pass, you will have to implement the int-print function of the standard library, which is your next task.

Once you are done with the desugaring, run the example program called printint.l3 and enter a number when asked to. Notice that this example needs functions from the L₃ standard library, and therefore the name of its module file, lib.l3m, has to be given to the compiler too, as follows:

sbt:l3c> run ../library/lib.l3m ../examples/printint.l3

Alternatively, you can just pass the module file of the above program, which is completely equivalent to the above, but shorter:

sbt:l3c> run ../examples/printint.l3m

As you can see, the program cannot print the number you have entered. This is because the implementation for the L₃ library function int-print is missing, and your next goal is to write it.

For that, open the file library/integers.l3 and look for the int-print function. Complete its definition so that it can properly print the integer it gets as argument, in base 10. Be sure to correctly handle negative numbers too!

We suggest that you implement int-print in terms of two other library functions, both of which are defined in library/characters.l3:

• char-print, which prints a single character, and
• int->char-digit, which returns the character corresponding to the digit given as argument, an integer between 0 and 9.

More information about Scala can be obtained here:

Coursera course

This is a course about functional programming in Scala given by Martin Odersky, the creator of Scala. You can access the course material and exercises by signing up for the course.

Scala API

The API for the Scala standard library.