You have now written a compiler for a simple language. The final mini-project of the course is to research, design an implement an extension for the compiler and/or the language it supports. This page gives a list of ideas, but you should also feel free to submit your own by email. All groups will rank the mini-projects in order of preference on the repository server (“Mini Projects” tab), and we will then apply a matching algorithm to assign them.

When the bidding phase is over and a mini-project has been assigned to your group, you should prepare a short report describing:

• a basic description of the features you want to add to the compiler and/or to the language
• some (short) programs highlighting the use of these features, with a description of how your compiler currently behaves on them (if it supports them at all), and how the improvements will change that behaviour
• a sketch of the changes you will make to each compiler phase and of the potential new phases you'll have
• ideas for further extensions

The third point should not be a complete implementation plan, but it should demonstrate that you understand how to tackle the problem you chose. You will (in principle) not have to implement what you describe in the fourth point. You will only be keeping this in mind so as to avoid running out of work in case the project turns out to be simpler that expected (or for extra credit, if you happened to solve the hard problems too quickly).

We will discuss the ideas with the groups during the lab session of Nov. 30th and help you prepare your proposal. Please make sure that you have selected a project and submitted a short proposal by Tuesday, Dec. 6th, 11.59pm. At the end of the project you will have to write a report on your compiler extension, and (part of) this proposal will serve as its introduction. The proposal and the report are to be submitted through Git and using the usual repository server.

Remember that the following list of ideas is not exhaustive. You can (and are encouraged to) submit your own ideas for discussion. You can even propose something and set it as your second best choice in case your preferred mini project cannot be assigned to you.

The great idea you proposed and discussed with us.

Allow multiple return locations within methods. Implement tail-call elimination so that tail-recursive methods can be implemented efficiently without using too much stack space.

class Helper {
  def last(a: List) = {
    if (a.hasNext()) {
       return last(a.next());
    } else {
       return a;
    }
  }
}

Write a pretty printer to output C code and accompany it with a garbage collector. That way you will be able to generate code that can be compiled with any C compiler into binaries that will be memory-efficient.

You can implement the kind of GC you want, like mark-and-sweep or copying. It does not need to run in parallel.

Introduce a form of generics into the language. Generics are a way to write functions that are reusable with different types. You could write code such as:

class LinkedList[T1] {
  var next: LinkedList[T1];
 
  ...
 
  def addElement(elem: T1): Bool = { ... }
 
  def at(index: Int): T1 = { ... }
}

LLVM is a fast-developing compiler platform. At is core is an intermediate representation language and a suite of compilers from that language to, e.g., native code. The goal of this project is to target LLVM as a new backend for your Tool compiler.

Implement support for traits, as in Scala, and add support for abstract methods. Traits allow programmers to use multiple inheritance and have a clear mechanism for resolving conflicts that typically arise in diamond-shaped inheritance graphs.

Add support for “foreign” class and function declarations, so that you can use arbitrary Java classes in your code. For instance, you could write:

foreign class java.util.Random as JRandom {
  def nextInt() : Int;
}

…to introduce the class JRandom with the method nextInt(). You will have to search the classpath at compile-time for classes exist that match the interface, for instance using BCEL.

Prevent errors from happening in the compiler, e.g.

• variables are always initialized (makes the JVM happier)
• null dereference
• out of bounds array accesses
• division by zero

For this you will need to implement a control-flow analysis and understand abstract interpretation.

Implement support for type inference, so that users do not need to specify (all) types. Because the language is simpler, you can go beyond what Scala supports: infer types for method arguments, return types, fields, local variables. Issue warnings or errors when types could not be inferred.

class TypeUser {
  def run(a: Int) = {
     val b = this.identity(a);
     return b;
  }
 
  def identity(a) = { return a; }
}

Introduce higher-order functions into the language, including anonymous function declarations. Allow functions to be passed as arguments, stored in variables, etc. You will need to extend your type system and learn about lambda lifting.

class List {
  // ...
 
  def forall(t: Int => Bool): Bool = {
     var c = this;
     var res = true;
     while(c.hasNext() && res) {
       if (!t(c.value()) {
         res = false;
       }
       c = c.next();
     }
     return res;
  }
 
  def test() = {
     this.forall( (x: Int) => { return x > 2; });
  }
 
  def identity(a) = { return a; }
}

Implement support for method overloading by argument count and type and for multi-methods.

Introduce throwing and catching exceptions, as well as a way to declare and infer them. Among other things, you will need to (slightly) modify the cafebabe library for this. We'll help you.

Introduce algebraic data types (ADTs, similar to Scala case classes) and pattern matching into the compiler. You can start with lists and extend it to user-defined recursive types (like your ASTs).

You will need to add support for the declaration of ADTs, so that you can write, for instance:

  type List = Nil | Cons(head: Int, tail: List)
  type Tree = Leaf | Node(left: Tree, value: Int, right: Tree)

ADTs are immutable tree structures that are the core data types of most functional programming languages. Typically, you program with them by using pattern-matching:

def size(t: Tree) : Int = {
  return (tree match {
    case Leaf => 0
    case Node(left, _, right) => 1 + size(left) + size(right)
  });
}

For the optional part, you can implement an optimal matching algorithm, check that pattern-matching expressions cover all possible cases, or that all patterns are reachable.

Extend the syntax to allow:

• Semicolon inference
• Methods as infix operators
• Expressions as statements
• Operators as methods

This will allow you to rewrite code that looks like

def matrixLinearCombination(xa : Int, ma : Matrix, xb : Int, mb : Matrix) : Matrix = {
  var result : Matrix;
  result = ma.times(xa).plus(mb.times(xb));
  return result;
}

into

def matrixLinearCombination(xa : Int, ma : Matrix, xb : Int, mb : Matrix) : Matrix = {
  var result : Matrix
  result = ma * xa + mb * xb
  return result
}