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

Write your garbage collector using #lang plai/collector. This language defines an interface to a program's stack and heap that you will use to implement garbage collection. The PLAI manual specifies the functions that your collectors must define.

Memory Layout

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

Dealing with Closures

Your collectors will allocate closures on the heap, and closure environments contain pointers to heap-allocated values. The function procedure-roots returns all pointers in the closure's environment as a list of roots. If your collector moves objects in memory, do update these roots accordingly.

Testing your Garbage Collectors

To test your collector, write programs using #lang plai/mutator, which is a subet of Racket that uses a custom garbage collector (i.e., yours) instead of Racket's own collector.

Debugging your Garbage Collectors

If both a mutator and its collector are open in adjacent tabs, you can use breakpoints and DrRacket's debugger to step between them.

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. (With the sample mutator, it does signal an error.)

Notes

You may store 2-3 atomic values, such as addresses, as global variables in your collector. We will assume they represent machine registers. However, all compound data structures and allocated values must be on the heap.

For example, in the mark-and-sweep collector, the free list must be on the heap, since its size is indeterminate and cannot fit in registers. You can variables to point to the beginning/end of the free list, but the list itself cannot legitimately reside in variables (registers).

Some final words of advice:

Handin

Turn in the following files:

  1. copy.rkt, your stop-and-copy collector.
  2. ms.rkt, 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.