Consider the version of fil-pos from 2001-11-16, which represents both the stack and the heap explicitly (i.e., as vectors that we update using mutation). As we've seen, the indiscriminate allocation of lists generates garbage that does not automatically disappear. Hence, we write garbage collectors (GC).

In this assignment, you will implement two GCs: a mark-and-sweep collector and a stop-and-copy collector. (If you need more information on garbage collectors, read Wilson's survey, available off the course books page.) Implement the procedures mark-and-sweep and stop-and-copy. Also modify cons/alloc to invoke a single globally-defined procedure, COLLECT, when it needs to trigger a collection (it should do this only when allocation would otherwise fail). That is, we should be able to choose a collection strategy by running

(set! COLLECT mark-and-sweep)

or

(set! COLLECT stop-and-copy)

and making no other changes. Your implementation of the collectors must be independent of the particular function or functions that evaluate (in this case, fil-pos).

To test your GC, you will probably find it useful to

• use a test program like fil-pos, and
• make your heap small, so small tests will trigger collection.

Be sure to include test cases of your GC in action. Be sure to check for boundary cases. Again, some of these checks are easier to perform by varying the size of the heap.