Assignment 2

In the last assignment, we got our infrastructure up and running. We also implemented constants, primitive functions, locals, and conditionals. That’s nice, but it’s a very limited set of objects. To do more advanced work, we will need to also work with objects such as cons cells (pairs), strings, and vectors. These structures are often allocated on the heap, so we will implement a heap for our compiler and runtime.

The heap will be a disjoint region of memory from our stack: stack frames are ephemeral, but heap objects are expected to live past the end of the frame. Therefore we now track another pointer in our compiler and runtime state: a heap pointer.

Each program starts off given a fixed-size region of memory. The runtime knows where it starts (the heap pointer, which will be moved as objects are allocated) and how big it is. Our allocator will be simple: it will not reclaim objects and it will abort the program if it runs out of memory while attempting to allocate.

We will also tag pointers exactly like the Ghuloum paper does. Note that we are using 64-bit words/pointers instead of 32-bit, though!

Pairs

• Implement cons
• car
• cdr

Strings

• string
• string-ref (get a character at index)
• string-set! (set a character at index)
• string-append (join two strings into a new string)

A thought experiment: small strings

Vectors

• vector
• vector-ref
• vector-set!
• vector-append (join two vectors into a new vector)

Side-effects… how to observe

• begin

Submitting your homework