cmpt 440/821
Advanced Topics in Programming Languages
Assignment 4
Christopher Dutchyn
November 25, 2019
Due: 23:55, December 2, 2019
This assignment deepens your understanding of continuations and our model
of memory, by having you implement generational garbage collection in ourlanguage. You can explore and use the various routines in the gc implementations presented in class:
• gc=bump+sweep.rkt – a bump allocator, with a moving collector sweeeping into a second semispace
• gc=freelist+collect.rkt – a free-list allocator, with a non-moving collector
Your implementation must use two spaces:
1. a young memory-space where all mutator allocation (i.e. calls to alloc-sto!
occurs, and
2. an old memory-space into which the young generation collected (a minor
gc).
Note that
• collecting (moving) a live young-generation value to the old-generation is
an allocation into the old-generation: the pre-existing values in the oldgeneration must remain, and the young-generation is emptied.
• if the old-generation fills up and needs a collection (a major gc), then that
collection must be in-place. It is your choice whether to use a compacting
(mark-and-sweep) collector on the old-space or a simpler collector. Your
choice of a allocator (bump versus freelist) for the old-space will influence
this decision.
1
You can choose to use one vector of cells to contain both spaces, or employ separate vectors; regardless, you will need to recognize and correctly handle inter-generational pointers (which can be in both directions). Both design
choices have inherent complexity. Deploying a single vector of cells allows pointers into either space to simply be locations (i.e. numbers), but then you need to
compare the location to the bounds of each space to recognize what kind they
are. Two vectors means that pointer values need to know which space they
point into, but are easily distinguished from each other.
If you need a new cell-type, for example, forwarding pointers, then you
can add them (as done in the semispace collector in class). You should not
need to alter any of the code for the interpreter, including the storeinterface (alloc-sto!, get-sto, and set-sto!, except as necessary to
accommodate pointers into both memory-spaces. In particular, you must
not change the memory layout for tuples.
Start with the initial interpreter for the assignment, copying it to abc123-gc.rkt
in the A4 directory of your gitlab project. Ensure that you include a number of
programs that exercise all aspects of your garbage collector.
Submission Instructions
In the A4 directory of your git course workspace, deposit 1 file:
• abc123 -gc.rkt – your generational garbac-collected CPS interpreter with
tuples.
Then, tag your repository as A4 (by the due-date), to designate the version
we will download for marking.
• Nov. 25, 2019: initial release