Complete this assignment with the same team you worked with for Continuations (Written). You and your partner must each understand the answers to all the problems, so don't just split up the work.

Garbage Collection

In this assignment, you will implement two garbage collectors: mark-and-sweep, and stop-and-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.

Writing your Garbage Collectors

Your garbage collectors must be written in the GC Collector Scheme language level. This language defines an interface to a program's stack and heap that you will use to implement garbage collection.

Consult the PLAI manual for more information on the interface provided by GC Collector Scheme and the functions you must define to write a garbage collector.

Memory Layout

Your allocator must use the following cell sizes when allocating blocks:

Dealing with Closures

One or both of your garbage collectors will need to occasionally move around cells in memory. If that cell is referenced by a closure, then the pointer in the closure will need to be updated to point to the new location in memory. We've given you the function procedure-roots, which returns all the cells referenced by the given closure as root objects; they are returned as roots not because they are necessarily roots of the reference hierarchy, but because that is a convienient data structure allowing you to update the closure without explicit access to its internal representation.

Testing your Garbage Collectors

You may write programs that exercise your garbage collectors using the GC Mutator Scheme language. This language is a subset of Scheme that uses a garbage collector that you specify. Consult the PLAI manual for more information.

Debugging your Garbage Collectors

Because of certain peculiarities in the GC language level, to debug your collector you must follow the following steps:
  1. Open your collector and your mutator side-by-side in tabs in a DrScheme window.
  2. In both files, select the Module language level.
  3. Add the following line to the top of your collector file:
    #lang plai/collector
  4. Add the following line to the top of your mutator file:
    #lang plai/mutator
You can now set breakpoints in your code, and use the regular DrScheme debugger to step through your program.

Sample Code

To get you started, we've provided a sample mutator and a trivial collector that signals an error when the heap fills up. (In fact, our collector does signal an error with the mutator we've provided, if you don't increase the size of the heap.)

Notes

You must store bookkeeping data on the heap provided by GC Collector Scheme. You may store 2-3 atomic values, such as addresses into the heap as variables in your garbage collector. We will assume they represent machine registers. However, all compound data structures must be on the heap.

In particular, in the mark-and-sweep collector, 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!

Some final words of advice:

Handin

Turn in the following files:

  1. copy.ss, your stop-and-copy collector.
  2. ms.ss, your mark-and-sweep collector.
  3. You will need to write multiple mutators to test your collectors. Include as many as you need to test your code thoroughly.