You have now written a compiler for a fairly simple language. There are plenty of ways you can improve the compiler or the language it supports. We present some ideas you can build on. You will have to write a small proposal describing what you want to implement and how you plan to do it. This proposal should include:

• 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, and how the improvements will change that behavior
• 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 Dec. 1st and help you prepare your proposal. Please make sure that you have selected a project and submitted a short proposal by Thursday, Dec. 9th, 4pm. 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.

Note that the following list of ideas is not exhaustive. You can (and are encouraged to) submit your own ideas for discussion.

Introduce a form of generics into the compiler. Generics are a way to write functions which 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 = { ... }
}

You will need to learn about type erasure. You can extend this project by adding type covariance and contravariance.

Generate C language source from your programs. Implement rules to ensure safe memory use. You can generate C code and then compile it with, eg. GCC.

Alternatively generate native code, using, for instance LLVM.

Write an alternative to cafebabe which generates bytecodes for the .NET platform. You will need to learn about this platform, read the specs, etc.

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(). Additionally, you could check that such a class exists, by searching in a given classpath at compile-time.

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

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

For this you will need control-flow analysis and some form of abstract interpretation.

Implement support for type inference, so that users do not need to specify all types. You can have inference for fields, local variables, and sometimes return types of methods. You will need to learn some inference algorithm, for instance Hindley-Milner.

Introduce higher-order functions into the compiler, including anonymous function declarations. You will need to extend your type system and learn about lambda lifting. An extension of this project is to support the use of methods as function values.

Add support for implicit type conversions à la Scala.

Add support for optional arguments in methods, that is arguments with a default which is used if not passed:

def foo(a: Int, b = 42: Int) : Int = { ... }
 
...
 
z = this.foo(10,43); // "standard" call
z = this.foo(10);    // same as calling this.foo(10, 42);

Add support for named arguments in method calls. This allows you to call methods with the arguments in a different order, or to omit some arguments, which is particularly useful when you have default values.

def foo(a: Int, b = 42: Int, msg = "none": String) : Int = { ... }
 
z = this.foo(1,2,"3");       // "standard" call
z = this.foo(1,msg="3",b=2); // same as above
z = this.too(1,msg="3");     // uses default value for b, but not for c
...

Introduce throwing and catching exceptions, as well as a way to declare and infer them. You will need to modify the cafebabe library for this.

Shrink your bytecode! (Note that this will in general not make it faster.)

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 check that pattern-matching expressions cover all possible cases, or that all patterns are reachable.

Design natural language-looking procedure calls with optional keywords and mixfix parameters, so you can write

  val str = (concatenation of mylist using ", " as separator)
  (write str on the screen and move to new line)

where you declare e.g.

  mixdef ("concatenation" "of" list : List[String] "using" sep : String "as" "separator") = 
    list match {
      Nil => ""
      one::Nil => one
      more::rest => concat more 
                          (concat sep (concatenation of rest using sep as separator))
    }

Build a partial evaluator for your language.

See here: http://www.dina.kvl.dk/~sestoft/pebook/