More features

If you’d like to continue developing your language after the course, here are some features you may want to add, along with high-level guidance for adding them.

Everything on this page is strictly optional and does not affect your grade.

Indirection

Pointers

A pointer is a value that holds the address of some other value. For instance, saying var x: Int* = &y; means that x shall have type ”int pointer” (Int*) and value ”address of y” (&y).

We can then dereference i.e. use the pointed-to value with a new unary operator *, like this: a = b + *x;.

Example program:

fun square(p: Int*): Unit {
    *p = *p * *p;
}

var x: Int = 3;
square(&x);
print_int(x);  # Prints 9

Requirements:

• For each type T, allow a pointer type T*.
• Implement the ”address of” unary operator &.
• Implement the ”dereference” unary operator *.
• Pointers to pointers (e.g. Int**) should work too.
• Pointers to functions (e.g. ((Int) => Int)*) should work too.

A dangling pointer, is a pointer whose target has been removed from the stack. The compiled program is allowed to have undefined behaviour if a dangling pointer is dereferenced.

Heap allocation

Prerequisite: pointer

Currently our pointers can only point to values on the stack. That means we can’t safely return a pointer to a value we created in a function, since it would become a dangling pointer as soon as the function returns. The solution is to have a different memory region, usually called the heap, where we can store values that aren’t tied to any single function call’s lifetime.

Our goal is to enable two new constructs in the language:

• Creating a value on the heap: var p: Int* = new Int(123) makes p a pointer to an integer value 123 that resides on the heap.
• Destroying a value on the heap: delete p marks the memory occupied by the value pointed to by p as free for reuse. This leaves p (and any copies of p) as dangling pointers.

The operating system can give us a large regions of memory for use as the heap, but we still need a system called a memory allocator to keep track of which parts of the heap are in use and which are free.

A memory allocator consists of two functions:

• malloc(n): reserves a memory range of n bytes and returns a pointer to it
• free(p): takes a pointer p previously returned by malloc, and marks that memory range as available for reuse.

Implementing even a simple memory allocator is a complicated task, so we shall use the allocator in the C standard library.

You can link to the C standard library by passing extra_libraries=['c'] to the assemble function in assembler.py. This will make malloc and free available for calling.

Now you can implement new and delete as unary operators that call malloc and free respectively.

Example program:

fun make_an_int(n: Int): Int* {
    return new Int(n);
}

var p1 = make_an_int(123);
var p2 = make_an_int(456);
print_int(*p1);  # Prints 123
print_int(*p2);  # Prints 456
*p1 = 789;
print_int(*p1);  # Prints 789
print_int(*p2);  # Prints 456
delete p1;
delete p2;

Datastructures

Pointers to structs

Prerequisites: pointers, heap allocation.

Structs are datastructures with named and typed fields. They’re similar to Python classes, except they can’t have methods.

First you need to add struct type definitions to modules. The following defines type Point to mean a struct with two Int-typed fields x and y:

struct Point { x: Int, y: Int };

Until now, all the values in our language have been 8 bytes in size – small enough to fit in a register, which has been very convenient. Structs are about to change this. We can delay this complication a little by initially only permitting structs to appear behind pointers, like Point*. The feature ”direct structs” lifts this restriction.

We’ll change the new operator to support creating structs in heap memory, with syntax like this:

var p: Point* = new Point { x: 123, y: 456 }

Operator new should ask malloc to allocate enough space for the struct’s fields.

We won’t allow dereferencing struct pointers with * yet, but we do need to access their fields. We’ll do this by adding a left-associative highest-precedence operator ., which is used like in Python: e.g. p.a accesses field a of the struct pointed to by pointer p.

Operator . can also be chained, so e.g. p.a.b accesses field b of the struct pointed to by field a of the struct pointed to by p.

The Assembly implementation for operator . should essentially look up the offset of the field from the struct and adds it to the struct’s address. This requires the Assembly generator to know the left hand side’s type. You’ll need to add type information to IR variables.

Note that this decision makes type-checking an essential part of compilation. We can’t just check types and forget about them like before (aside from needing the top-level type).

Next we need to consider operator &. Until now, operator & has only really made sense on variables, but it is reasonable to also support taking the addresses of struct fields, so e.g. &p.a.b should work. This needs some special case code, since expression p.a.b normally returns the value stored in b, not its address.

Finally, the assignemtn operator = needs to be extended so that p.a.b = x works.

In summary, here is a high-level task list for supporting structs behind pointers:

1. Add struct type definitions to the language. As with functions, their order in the input shouldn’t matter.
2. Implement syntax new <structname> { <fields> } to create correctly sized structs on the heap.
3. Attach type information to IR variables.
4. Implement operator . so that a .-separated sequence like p.a.b.c where p is an expression for a pointer. (This is generalized in direct structs.)
5. Extend operator & to support .-separated sequences.
6. Extend the assignment operator = to support a .-separated sequence on its left.

Example program:

struct Point { x: Int, y: Int };
struct Line { start: Point*, end: Point* };

fun manhattan_len(line: Line*): Int {
    return abs(line.start.x - line.end.x) +
           abs(line.start.y - line.end.y);
}
fun abs(x: Int): Int { return if x >= 0 then x else -x; }

var line1: Line* = new Line {
    start: new Point { x: 1, y: 2 },
    end: new Point { x: 5, y: 9 },
};
line1.end.y = 10;
var end_x = &line1.end.x;
*end_x = 7;
print_int(manhattan_len(line1));

These features are not as commonly seen in languages as the previous ones, and many of these are more difficult too.

Direct structs

Prerequisite: functions, pointers to structs.

Currently our structs resemble Python objects in that they are always allocated on the heap and always accessed through a pointer. Our next goal is to allow placing structs directly on the stack or in the fields of other structs. We want to be able to copy whole structs between variables and pass them as function arguments (example).

Note that structs don’t necessarily fit in a register, so we can’t pass copies of whole structs around as easily as we’ve done with integers and booleans so far.

Even if we could magically fit large structs into registers, copying them around at every turn would be very inefficient. Consider e.g. the expression a.b + a.c + .... If it made a full copy of a potentially large struct a every time a is mentioned, that would be quite wasteful.

This suggests the following design: we can internally pass around hidden pointers to structs. We’ll call references. When a copy really must to be made, e.g. when passing a struct as a parameter, we make that copy on the stack and pass on a reference to that copy.

Here is a high-level task list for supporting direct structs:

1. Allow creating a struct on the stack like this: var p = Point { x: 1, y: 2 }; (no new). In the Assembly generator, Locals should reserve enough stack space for the entire struct.
2. For each type T, allow an internal reference type Ref(T). (The programmer need not ever see this type.)
3. Whenever a struct-typed IR variable is read, return a reference to it i.e. a Ref(T)-typed IR variable.
4. Make operator . work on struct pointers T* as well as struct references Ref(T). Accessing a field a.b should result in a reference to that field. Assignments a.b = c should assign to the field pointed to by the reference on the left.
5. Ensure that assigning to a struct (b = a) makes a copy of the struct instead of copying the reference.
6. Ensure that structs can be passed to and returned from functions. The x86-64 calling convention is complicated when it comes to structs, so for simplicity, always pass structs via the stack. To return structs, let the caller reserve stack space for the return value and pass the address of that space in register %rdi (so it takes the place of the first argument).
7. Ensure that structs can contain other structs directly (not just via pointers like before), e.g. struct Line { start: Point, end: Point }. (Note that recursively nested structs should be forbidden, as their size would be infinite.)
8. Make == and != work for structs. Given two struct references, they should compare the contents of the structs.
9. Ensure that struct pointers like p: Point* can be dereferenced explicitly too (e.g. (*p).x = 123).

Arrays

Prerequisites: functions, pointers, heap allocation.

Add the following built-in functions and operators:

• int_array_create(n) allocates zero-initialized memory for storing n integers and returns a pointer to it.
• int_array_delete(a) deallocates a previously allocated array a.
• int_array_get(a, i) returns array a element i.
• int_array_set(a, i, x) sets array a element i to value x.

Better syntax

You may prefer to allocate array memory with the C function calloc, which guarantees the allocated memory is initialized with zeroes. Note that unlike malloc, it takes two parameters.

Note the following possible mistakes by the programmer:

• an array is accessed out-of-bounds
• an array is deleted twice
• an uninitialized array pointer is deleted

You can choose to implement run-time checks to crash with a clear error message (as most languages do), or leave them as undefined behaviour (like in C/C++).

Functional programming

Lambdas and closures

Prerequisite: pointers to structs.

Add inline anonymous functions i.e. ”lambdas” to the language.

Basic example:

var f = new fun(x: Int): Int { return x * x; };
print_int(f(5));  # Prints 25

Lambdas must be able to access variables declared outside of them. These variables form the lambda’s closure.

Example:

var k = 10;
var f = new fun(x: Int): Int { return x * k; }
print_int(f(5));  # Prints 50
delete f;

Closures should contain the variables by reference i.e. modifying a closure variable in the function should modify the original, not a copy.

Example:

var k = 10;
var set_k = new fun(x: Int): Int { k = x; }
set_k(123);
print_int(k);  # Prints 123
delete set_k;

There are no memory safety requirements. The program is allowed to have undefined behaviour if a lambda is called when variables in its closure no longer exist.

Recommended design: the easiest approach is to represent lambdas internally as pointers to heap-allocated structs that contain:

• a pointer to the function’s code
• pointers to every closure variable

The function can take the pointer to the lambda’s representation as a hidden parameter.

Read-only types

Prerequisite: pointers

For every type T, allow a new read-only type readonly T. During type-checking, check that no value of type readonly T is overwritten.

Example:

var x: readonly Int = 123;  # OK: can initialize readonly
x = 456;  # Error: can't overwrite readonly
var y: Int = x;  # OK: can copy from readonly to non-readonly

Type readonly T* means ”a pointer to a readonly T” while type readonly (T*) would mean ”a readonly pointer to a non-readonly T”.

Interactions of pointers and readonly require care.

• You must not allow a value to be overwritten through a read-only pointer.
• You must not allow converting a pointer to a readonly into a non-readonly pointer, i.e. you must not allow giving a readonly T* where a T* is expected.
• The other way is OK: a T* can be given where a readonly T* is expected.

Example:

var x: Int = 123;
var p1: readonly Int* = &x;  # OK: converting Int* to readonly Int*
var p2: Int* = p1;  # Error: can't convert readonly Int* to Int*

*p1 = 456;  # Error: can't overwrite dereferenced readonly

The rules outlined above can be understood through the intuition ”if I have something marked readonly, then I’ve promised not to modify it (but some other code might modify it)”. This is not the only possible design.

Analyses and optimizations

Dataflow framework

Implement the dataflow framework, reaching definitions and live variables analysis by doing the exercises in chapter 8.

You may want to implement break and continue before doing dataflow analysis, because they make it more convenient to construct interesting dataflow graphs.

Report useless writes

Prerequisite: dataflow framework.

Using the dataflow framework and a suitable analysis, have the compiler print warnings for places where a stack-allocated variable is written but the written value is never read.

Example: in the following code, writing 3 to x is useless.

x = 3;
x = 4;
f(x);

An intraprocedural analysis is enough.

Constant propagation

Prerequisite: dataflow framework.

Using the dataflow framework, find situations where a variable’s value is a known constant and replace uses of the variable with loads of the constant into a new temporary variable.

Doing constant propagation may open up new opportunities for more constant propagation, so you should repeat it iteratively until no more opportunities are found. However, because our IR requires using constants through Load...Const instructions, don’t do constant propagation on variables that are already only set in a single Load...Const or you’ll end up in an infinite loop.

Finally, remove all Load...Const and Copy that write to the variables that you just removed.

An intraprocedural analysis is enough.

Constant folding

Prerequisite: functions.

Constant folding means evaluating expressions using only constant values, such as 1 + 2 at compile-time.

Let’s define a function or operator to be pure if it only uses its parameters, constants, and other pure functions or operators. (The built-in operators are all pure, but the builtin print_... and read_... functions are not.)

Recursively find AST subtrees that only use constants and pure functions or operators, and use the interpreter to evaluate these subtrees and replace them with literals. It is enough to limit constant folding to AST subtrees that only use base language features and function calls.

If you intend to combine this with constant propagation, read the following note first, as the recommended approach there is to do constant folding at the IR level instead of on the AST.

Combining with constant propagation

Inlining

Prerequisite: functions.

Inlining means replacing a function call with the implementation of the function. That is, it transforms a program like

fun f(x: Int) { return x + x; }
print_int(f(123));

into

print_int(123 + 123);

Inlining by itself removes function call overhead at the cost of enlarging the program. This is a worthwhile trade if the called function is quite small.

Often the greater benefit of inlining is that it enables more optimizations e.g. making the resulting program more amenable to intraprocedural analyses.

Make your compiler inline functions whose bodies are smaller than e.g. 20 IR instructions.

Things to remember:

• Rename the inlined IR variables to avoid clashes with the caller’s existing IR variables.
• After inlining f into g, the size of g has changed, which may change whether it’s worth inlining g into something else. You can inline e.g. in depth-first order or in breadth-first order, but neither strategy is universally superior.
• Remember to test that your inliner doesn’t crash when it sees a recursive or mutually recursive function.

Dead code elimination

Removing code that does useless work is an optimization that is not very useful directly, but it’s a good cleanup after other optimizations such as constant folding and inlining that may leave useless code behind.

Let’s define dead code as code that only does useless writes and only calls pure operations.

Write an optimization that iteratively removes dead code until it can’t find more.

Other ideas

Here are some other language features you could consider implementing:

• extension methods
• generics
• type inference
• overloading
• traits/interfaces
• garbage collection
• IDE support