Garbage Collection FAQ

Notes: This project is a team project to be completed in pairs. Please see the main assignments webpage for more details. Also, you will need to set the language level to CS173 Advanced.

In this assignment, you will implement two garbage collectors: mark & sweep, and stop & copy. As we have seen, garbage collection involves starting from a root set of references, which reside in local variables and stack frames, and searching for reachable values on the heap. Hence, to write a garbage collector, you need a program that exposes this information. For this assignment, we will write such a program for you, so you can focus on implementing the actual garbage-collection algorithms.

Specifically, you should download the source code for the function tree-add1, which consumes a binary tree of numbers and returns a similar tree where each number is incremented by one. This function is written to use low-level routines for memory allocation and an explicit stack. It comes with dummy allocation routines that never collect garbage. You will need to write a replacement allocator that collects garbage when the heap is full. We provide a function called get-stack-roots that returns the current root set as a list of boxed locations (so you can move objects around). We also provide a function called location->tree that returns an S-expression representing the given heap-allocated tree. For each garbage collector, you will need to redefine the following:

alloc/empty-tree : () -> loc allocates an empty tree on the heap
alloc/node : number loc loc -> loc allocates and initializes a node on the heap (each of the three fields must be stored in a separate heap cell)
HEAP-SIZE : number number of cells in the heap (the TAs will change this while grading, so don't hard-code any assumptions about it)

In addition, if you choose to change the representation of values in the heap, you will need to redefine the following:

empty-tree? : loc -> boolean returns true iff loc points to an empty tree
node? : loc -> boolean returns true iff loc points to a tree node
node-val : loc -> number returns the value of a tree node
node-left : loc -> loc returns the left child of a node
node-right : loc -> loc returns the right child of a node

As a part of this conversion, you should maintain a free list in the heap. That is, you should not use any auxiliary data structure; instead, use the available space in the heap to keep track of the free list. (You may use one extra box ("register") to point to the start of the free list.) You may need to adjust your allocation accordingly to have enough space to maintain free list pointers!

You will probably want to use numbers to represent locations, but you may use another representation if it eases your implementation. Also, to help see what is happening, you might want to print a representation of the heap before and after every garbage collection. You can use the Scheme printf function:

(printf "Heap is ~s~n" Heap)

Some final words of advice: