This was a group project using Scala in the 2nd year of Computing at Imperial.¹

We designed a compiler for the WACC programming language in Scala using the Parsley parser combinator library. Our parser was highly efficient, with helpful error messages, type checking, and peephole optimisation.

Testing was done using generation-based fuzzing tests, unit tests and 1000+ integration tests. We also had a CI pipeline which verified code style and automatically ran the tests on each commit.

Here’s a sample WACC program that recursively calculates Fibonacci numbers, to give an idea of the challenges this included:

begin
  int fibonacci(int n) is
    if n <= 1 then
        return n
    else
        skip
    fi;
    int f1 = call fibonacci(n - 1);
    int f2 = call fibonacci(n - 2);
    return f1 + f2
  end

  int n = 0;
  read n;
  print "The input n is ";
  println n;
  print "The nth fibonacci number is ";
  int result = call fibonacci(n);
  println result
end

As you can see, there are typed variables, I/O, function calls. We also had to support arrays and pair types, type erasure, and more.

Extensions

The project included a 2-week part where we were able to extend the functionality of the compiler in any way we pleased.

We decided to extend it to include efficient monomorphic type inference², and cross-compiler support for three CPU architectures (x86, ARM64, ARM32). We also added support for peephole optimisation, bitwise operators and loop control flow (i.e. break/continue).

Outcome

We achieved an excellent mark of 93.3% overall, and I was very proud of our project. Personally, I learned Scala from the beginning and became a big fan of it due to its powerful type system and mutable & immutable collections library. We used advanced features new to the language (at the time) such as deferred givens in an attempt to make our code as generic, reusable and non-repeating as possible.

Based on my performance on this project, I was invited to serve as a teaching assistant for the next cohort.