Teaching Garbage Collection without
Implementing Compilers or Interpreters
Gregory H. Cooper

Arjun Guha

Shriram Krishnamurthi

Google, Inc.

Cornell University

Brown University

arjun@cs.cornell.edu
sk@cs.brown.edu
ghc@google.com
Jay McCarthy
Robert Bruce Findler
Brigham Young University

Northwestern University

jay@cs.byu.edu

robby@northwestern.edu

ABSTRACT
Given the widespread use of memory-safe languages, students must understand garbage collection well. Following
a constructivist philosophy, an effective approach would be
to have them implement garbage collectors. Unfortunately,a full implementation depends on substantial knowledge ofcompilers and runtime systems, which many courses do notcover or cannot assume.
This paper presents an instructive approach to teachinggc, where students implement it atop a simplified stack andheap. Our approach eliminates enormous curricular dependencies while preserving the essence of gc algorithms. We
take pains to enable testability, comprehensibility, and facilitates debugging. Our approach has been successfullyclassroom-tested for several years at several institutions.
Categories and Subject Descriptors K.3.2 [Computers and Education]: Computer and Information Science Education
General Terms Languages
Keywords Garbage collection

1. INTRODUCTION
Many students appear to have a poor grasp of garbage
collection (gc) [8], because it is an automated process thatruns without their control. This makes some students intimidated and untrusting of it (which can result in their using
unsafe programming languages), while others use it without
understanding its impact on performance.
Our antidote is to lay bare the underlying mechanisms byhaving students implement them, in keeping with constructivist educational principles. This approach is consistent
with what many programming languages courses alreadydo, following the venerable tradition of studying languages
through definitional interpreters [11]. A definitional inter-

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SIGCSE’13, March 6–9, 2012, Denver, Colorado, USA.
Copyright 2013 ACM 978-1-4503-1775-7/13/03 ...$15.00.

preter defines a language by a lightweight implementation,in lieu of abstract mathematics. These interpreters allow
students to actually run programs in their languages andexplore the consequences of alternate definitions.
There are several programming language texts and courses
based on definitional interpreters [1, 6, 9], but most of them
do not cover gc within the implementation-oriented tradition. Implementing a gc is taxing because it requires a graspof low-level concepts such as walking the stack, pointer arithmetic, manipulating raw memory, and so on, and most realworld runtime systems—which focus on performance—are
not designed to enable easy modification. The alternative isto provide students with a toy language’s implementation,
but such a language will necessarily be small and hence hard
to write interesting programs in, thereby discouraging testing and experimentation.
Furthermore, even to work with a toy language, students
must first learn about interpreters or compilers, which is asignificant curricular prerequisite. In contrast, many otheruniversity-level courses could and do teach gc, including
runtime systems, operating systems, and even middleware.
Thus, finding a way to implement gc without a heavy language implementation prerequisite could have broad use.
In this paper, we present a framework for building, debugging, and exploring garbage collectors. It meets several
important criteria:• It minimizes curricular dependencies: we enable students to learn and write garbage collection algorithms
in a full-fledged language with an IDE. Students do nothave to master other complex topics, such as compilers
and continuation-passing style, to implement their gc.
This makes the approach fit better as a module in avariety of different courses that might want to teachthis material.
• It is flexible: students can investigate several strategies, including copying collectors, generational collectors, and conservative collectors. We design our framework so that students can trivially change the type ofcollector their program uses (Figure 1).
• It encourages exploration: our framework lets studentwritten collectors manage memory for a regular programming language. Thus, they are not limited to the(much smaller) set of examples and tests they could
write in a toy language. This is especially valuable

Racket's Native
Collector

We provide the infrastructure tocouple these components.

Stop & Copy
Collector

MutatorMark and Sweep
Collector

Mutator

Generational
Collector

MutatorStudents write collectors in a
restricted language.

Students write mutators
in basic Racket.

straightforward provided type-tags are respected; languages
use a combination of static and runtime checks to do so.
The outline above encompasses several kinds of collectors,
including mark-and-sweep, stop-and-copy, and generational
collectors. Advanced techniques such as concurrent collectors are beyond the scope of our gc assignment.

Linguistic Dependence.

Figure 1: High-Level Assignment Architecture

when students believe they have a working collector
and now want to stress-test it on non-trivial inputs.
• It facilitates testing and debugging: our framework canuse a native garbage collector instead of a studentwritten collector. This allows the student to validate
behavior and to isolate errors. In addition, students
have powerful debugging tools as their disposal. We
include a heap visualizer, and engineer our system sothat the IDE’s debugger allows students to single-step
between collector and program.
In end-of-semester surveys, students indicate that whereas
they had been apprehensive before, they are now much more
likely to trust and rely on garbage collection as a result of
their implementation experience. Beyond the pure pedagogic value, this could have a salutary impact on the software students write in their careers.
The solution described in this paper has already been implemented in actual courses at several institutions. Before
adopting this solution, some of them used a more conventional approach that depended on compiling to continuationpassing style. Since switching to the new framework, all havenoticed a marked improvement in the quality of students’solutions and the extent of their testing and exploration.

Background and Terminology.
We use standard terminology from the garbage collection literature. A language runtime’s memory subsystem,or collector, has two principal duties. (1) It allocates andde-allocates values on the heap on behalf of programs, ormutators. (2) It provides facilities for reading and writing
values and inspecting their types at runtime.
When allocating a new value, the collector first searches
for a free slot of appropriate size on the heap. If found, it
stores the value along with metadata, e.g., a type-tag for
runtime type-inspection. Garbage collection usually starts
if there are no free slots. gc de-allocates values that are
not reachable by following references from local variables on
the stack and in registers; these variables are called the root
set. To follow references through arbitrary values, the gc
inspects their type-tags. Accessing and mutating values is

The work in this paper is done for Racket [3], a descendant of Scheme. We use Racket for two reasons. Historically, Scheme and Racket are widely used in definitional interpreter courses (thanks to several influential textbooks [1,6, 9]). Much more importantly, Racket (but not Scheme)
provides us with the linguistic mechanisms needed to implement this solution seamlessly from the student’s perspective, through its cutting-edge ability to treat languages aslibraries [5, 13]; other languages lack the module systems
needed to enable such a solution. Readers who would prefer
our solution in a different linguistic context can regard thispaper as a technical challenge for the module mechanismsof their preferred language.

2.

PROBLEM CONTEXTOur garbage collection assignment, along with classroom
discussions contrasting garbage collection with the cost of
manual memory management and the impact of garbage collection on programming style, constitutes about one fifth ofa roughly 13-week programming languages course for upperlevel undergraduates and beginning graduate (master’s andPhD) students. We ask students to implement memory allocation and garbage collection algorithms for a small numberof Racket primitives. We assign multiple algorithms to avoid
the risk of presenting too narrow a perspective: traditionally, mark-and-sweep (which later also provides a starting
point for discussing conservative collection) and semispace
swapping (because it confronts the challenge of moving objects in memory). Students are given about two weeks tocomplete these implementations.
We often grade the assignment by code inspection, in which
students present their collectors to the course staff and answer questions about their design decisions. We discuss code
inspection for gc in more detail in Section 6.

3.

WRITING COLLECTORS

We provide a general framework that allows students toimplement several kinds of collectors. The framework exposes essential concepts such as memory layout and rootson the stack. However, we hide lower-level machine details,
including registers and the binary representation of data.
A student-written collector is a module that implements
the interface in Figure 2a. These functions allocate values, query type-tags, and read values. The depicted functions only manipulate lists and flat values (i.e., numbers
and booleans), though it is trivial to add support for otherdatatypes. For example, we also require students to allocate
closures for higher-order functions.
These student-written functions determine the location,layout, and size of values on the heap. Therefore, students
can experiment with collectors that add metadata (e.g., lifetimes for generational collectors) or don’t (e.g., conservativecollectors). Students can also explore simple optimizations,such as reusing allocated constants.

addr
flat

∈ 0 ≤ n < (heap-size)≡ num | bool | empty

gc:cons :: addr × addr → addr
gc:cons? :: addr → bool
gc:first :: addr → addr
gc:rest :: addr → addr
gc:set-first! :: addr × addr → void
gc:set-rest! :: addr × addr → void
gc:flat :: flat → addr
gc:flat? :: addr → bool
gc:deref :: addr → flat(a) Garbage Collector Interface (student-implemented)(define (incr-list lst)
(if (empty? lst)
empty
(cons (+ 1 (first lst)) (incr-list (rest lst)))))
Use students' GC primitives(define (incr-list lst)
(if (and (gc:flat? lst) (empty? (gc:deref lst)))(gc:flat empty)(gc:cons (gc:alloc-flat (+ (gc:deref (gc:flat 1))(gc:deref (gc:first lst))))(incr-list (gc:rest lst)))))

heap-size :: → int
heap-set! :: addr × flat → voidheap-ref :: addr → flat(b) Heap manipulation (provided)

get-root-set :: → listof root
read-root :: root → addr
set-root! :: root × addr → void(c) Root manipulation (provided)

Figure 2: Generic Allocator Interface

Name intermediate results(A-normal form)(define (incr-list lst)
(if (and (gc:flat? lst) (empty? (gc:deref lst)))(gc:flat empty)(let* ([t0 (gc:flat 1)][t1 (gc:first lst)][t2 (gc:flat (+ (gc:deref t0) (gc:deref t1)))])[t3 (incr-list (gc:rest lst))])(gc:cons t2 t3))))Figure 3: Sketch of Program Transformations
Our framework provides functions to manipulate the heap
as an array of cells (Figure 2b). The collector can store(heap-set! ) and retrieve (heap-ref ) flat values in heap cells—
storing structured-data in a single cell would violate the intent of the assignment. The heap-size function returns thesize of the heap, which is set by each mutator (Section 4).
Our framework provides functions to manipulate the rootson the stack (Figure 2c). A root is an updatable reference tothe heap: updates are needed by moving collectors, such as
stop-and-copy or compacting mark-and-sweep. We do not
require students to walk the mutator’s stack to find roots
themselves; the get-root-set function provides this functionality. The next section explains why having students
implement root-finding is neither essential nor desirable.

4. TESTING AND CALCULATING ROOTS
To truly exercise a collector we must use it to allocate
memory for a program. In traditional courses, students
test collectors by writing mutators in small, toy, classroomonly languages. It is difficult to write substantial tests inthese toy languages. However, in our framework students
write mutators in Racket itself. This enables students towrite much more rigorous tests: student submissions haveincluded non-trivial programs such as entire interpreters forother languages, and complex graph algorithms. In addition, by automating stack-walking, our approach eliminatesa curricular dependency on program transformations.

The Traditional Approach.
In a traditional setting, such as a compilers course, writing a collector requires mastery of semantics-preserving program transformations. We sketch these transformations fora simple mutator that increments the numbers in a list (topof Figure 3).
Given a mutator, such as incr-list, students have to first
instrument it to call their collector at memory-manipulation
points. Although this first transformation is conceptuallysimple, it is orthogonal to gc algorithms and quickly becomes complex for non-toy languages. In addition, the collector must save the state of the mutator, collect garbage ifnecessary, perform the memory operation, and then restore
the state of the mutator. Implementing these steps in a lowlevel language requires considerable effort and knowledge.
Students must then transform the mutator to an intermediate form that names all sub-expressions. Such representations (e.g., continuation-passing style, static single assignment, or A-normal form) are advanced topics, tricky toimplement, and tedious for even modestly-sized languages.
As a result, a traditional approach incurs several curricular dependencies and is only realistic for a toy, classroomonly mutator language.

Our Approach.
Our framework automates the transformations in Figure 3
for a large subset of the Racket language, eliminating thecurricular dependencies described above, and allowing students to test and explore their collectors by writing mutatorsin ordinary Racket. Our students are familiar with Racket,
since it is the language they use to write the collector itself!
Mutators do have one non-standard line, which specifies thecollector to use and the size of the heap:(collector-setup hcollector-filenamei hheap-sizei)

By varying the gc algorithm and heap size, students cantest for more corner-case behaviors.
Finally, our framework allows students to easily run sequences of collector functions on hand-crafted heaps. This
allows them to unit-test with complex heaps without crafting complex mutators. To help students further, we provide
a program that generates mutators that allocate and traverse random graphs.

5. DEBUGGING
Despite the efforts described above, building a collector remains subtle and error-prone. Bugs often corrupt the heap,
and heap corruption may only cause errors and incorrect answers several steps later. Students thus need good debugging
support. Building a debugger in this context is a challenge,
because bugs manifest in the interaction between collectors
and mutators. We thus need to co-debug the mutator andcollector, set breakpoints in either piece, and single-step between them.

The Traditional Approach.
In a traditional setting, the mutator is first compiled toa low-level, intermediate representation, and then coupledwith the collector, which is also written in a low-level language, such as C. A debugger for this low-level language(GDB) can debug both components. However, without extensive tooling, the debugger can only show the mutator’sintermediate form, so students have to fully absorb the very
program transformations we were trying to hide.

Our Approach.
Figure 4 shows our framework co-debugging a mutatorand collector. The collector has a breakpoint at the startof gc. We are paused a few steps beyond this breakpoint,
which we reached because the heap filled up after a few
recursive calls in the mutator. Note that the stack shows
both mutator and collector stack frames. Most significantly,
we can debug both in their original source language.
Our approach reuses Racket’s native debugger [10] by
carefully transforming the mutator using Racket’s macros.
The debugger works at the original source level, and does
not step into intermediate expressions introduced by macros.
This is possible because macros can attach original source
locations and variable names to generated code. Simple
macros can track names and locations automatically, but ourmore complex, whole-program transformations require more
careful engineering. In particular, we are careful to leave theshape of the control stack unmolested by our macros.

Heap Visualization.
Debugging is not enough. Not surprisingly, we noticed
that in practice, students have as much difficulty interpreting their data as they do debugging the flow of control.
Specifically, we found that they repeatedly printed the entire
heap, often as frequently as before and after every allocation(to answer questions like, What exactly is at location 14? ).
They then had to pore over the output to reconstruct its
meaning as a heap of values.
While such activity builds character, it may not fit theconstraints of some teaching schedules. Fortunately, we canprovide a much better interface for this domain. Keeping
the heap data structure under the control of our code—adecision made to guard the size of and kinds of values stored

in the heap—has a (perhaps unexpected) advantage: we canfind the heap without difficulty (whereas otherwise it would
be just another datum in the collector code) and employ thestudent’s heap-inspection routines to display it.
Figure 5 shows the heap at the point shown in Figure 4.
From this, it is relatively easy to reconstruct what datum is
at location 27.
Naturally, the visualizer and debugger are especially useful in conjunction. For instance, it is often convenient toavoid stepping through code that sets up initial data structures in the mutator. The student can thus set a breakpointin the mutator past this stage. Upon control arriving there,
the student can then enable breakpoints in the collector,
or use single-stepping, to proceed methodically through theprogram’s execution—using the visualizer to avoid having
to manually inspect the heap at each point along the way.

6.

PEDAGOGY

Implementing collectors forces students to confront intricacies of the problem that would be difficult to convey
through an abstract verbal treatment alone. To evaluate
student understanding we often augment the implementation assignment with a code inspection, in which students
explain their programs to the course staff, then answer questions about their design decisions and how they might handle
potential extensions. Our questions include:
basic concepts How did they represent data on the heap,
and why? Did they inline the free list in mark-and-sweep?
What are forwarding pointers in stop-and-copy, and what
purpose do they serve? Is their collector realistic, or havethey over-simplified the problem by exploiting high-level features, or even cheated (e.g., ignoring the provided heap interface and relying instead on Racket’s collector)?
representations What representations did they choose forflat values? Did every mention of a flat value result in freshallocation? Did they reuse existing allocated values (and if
so, what are the time-space tradeoffs)? Did they pre-allocate
any values? Did they make intelligent use of addresses to
encode some values in the address itself and, if so, how did
this affect their ability to address all of the heap?
cycles How does the collector handle cyclic data? How doesit avoid getting stuck in an infinite loop if it traverses datawith cycles? Do we need to check for sharing even in programs that do not create cyclic data, and what impact does
this have on a copying collector?
subtleties What happens if the collector needs to run in
the middle of a recursive procedure? Could the collector
run out of memory in the middle of allocating an object? Is
the collector idempotent?
testing Did they have test cases to exercise salient featuresof the language? Did they try nested data structures, suchas lists of lists? The assignment does not provide a canonicalmutator, so students are forced to exercise their imagination.
extensions What would it take to add support for coalescing adjacent free blocks in the mark-and-sweep collector?
How difficult would it be to support other kinds of objects?
invariants What invariants hold for the mark-and-sweep
collector? What about semispace swapping?

collector stack frames
breakpoint inallocator
mutator stack frames

single-step
debugging

Figure 4: Co-debugging a collector and a mutator
Collector The collector language provides a heap abstraction to students. The language itself ensures that students
do not store structured data directly on the heap using contracts [4]. In addition, the collector language itself starts
the graphical heap visualizer.

Figure 5: Heap visualization: a filled semi-space

By having a concrete implementation in front of us (thatthe student has hopefully thought long and hard about),
we can ask specific, detailed questions that would otherwise
be difficult to frame. Code inspection thus gives us a verystrong sense of the student’s understanding of the concepts.

Student Feedback.
Many faculty have reported success using this framework.
For example, one author, Jay McCarthy, surveyed 258 students over 4 years. Before doing the assignment, 40 students
agreed with the statement, “Manual memory management
is usually preferable to gc,” but only 10 agreed after the assignment. Before the assignment, 80% believed that manual
memory management is always faster than gc, but only 40%
agree after; the others answer that gc is as fast or faster,
given enough memory. The students were also asked whatpart of the class they learned from and enjoyed the most.
Of the 258, only 15 mentioned anything other than gc.

7. IMPLEMENTATIONOur gc framework could be built for any programming
language, but Racket provides a combination of several technologies that ease its implementation [13]. Whereas syntactic extensions are part of the Scheme tradition, a Racket
language can have entirely different syntax and semantics.
Our gc framework is an extreme example of the latter: thesemantics of the mutator language changes as students fix
bugs in their collectors. The implementation is a separate
research contribution beyond the scope of this paper. But,
we note some key techniques below.

Mutator The mutator language implements the transformations that students have to learn in traditional gc courses(Section 4). Throughout these transformations, we ensurethat generated code is carefully tagged with the sourcelocation of original code. This ensures that runtime errors have correct locations and that the transformations aretransparent to the debugger [10].
The mutator language uses students’ collectors insteadof Racket to manipulate memory (e.g., it rewrites cons to
gc:cons). If done naively, e.g., with macros, we would haveto instrument all syntactic forms (that we remember). Instead, we use Racket’s ability to precisely control macro expansion: we first transform mutators to primitive syntax
and then instrument code. This ensures that students canwrite mutators with convenient syntax.
Mutators must expose their root set to collectors, which
we do with an internal roots variable at each program point.
To calculate roots, we first name all intermediate expressions
and then calculate free variables at each program point. By
doing so, as Figure 6 illustrates, the set of free variables andthe root set coincide for a single stack frame. We also augment all functions with an additional caller-roots parameter.
Thus at each point, the root set is the union of caller-roots
and the local roots.1

8.

RELATED WORK

We surveyed faculty who teach implementation-based languages courses, as well as experts in the field of garbage
collection, and none of them appear to use an infrastructure similar to ours. The only assignments we found involving implementation of garbage collection were in courses oncompilers and run-time systems.
At the University of Victoria, Nigel Horspool’s course on
virtual machines treats gc in depth [7]. Students study the
1
N.B., we use continuation marks to obviate parts of thistransformation and preserve tail-calls [2].

execution
2

Heap

3

5

7

35

Roots
Original
SourceA-normalform
Free
Variables(let ([x (* (+ 2 3) 7)])x)(let ([x (* (+ 2 3) 7)])x)(let ([x (* (+ 2 3) 7)])x)(let ([t0 2] [t1 3])(let ([t2 (+ t0 t1)] [t3 7])(let ([x (* t2 t3)])x)))(let ([t0 2] [t1 3])(let ([t2 (+ t0 t1)] [t3 7])(let ([x (* t2 t3)])x)))(let ([t0 2] [t1 3])(let ([t2 (+ t0 t1)] [t3 7])(let ([x (* t2 t3)])x))){t0, t1}{t2, t3}{x}

identical to roots in stack frame

Figure 6: Naming intermediate results allows us to track roots
implementation of a conservative mark-and-sweep collector
inside a JVM, then answer questions pertaining to design
decisions. Students do not implement collection algorithms,
but they instrument the collector to obtain statistics.
At Cornell, Greg Morrisett’s course on data structures andfunctional programming [12] included an assignment to implement parts of a compiler and runtime system for a subset
of ML, including generational gc. Programs are first compiled to lambda terms, which are evaluated by an abstract
machine. The course framework specifies the heap layout
and handles allocation; students only implement collection.
At Princeton, David Walker assigned a similar project that
had students write a semispace collector for a simple, functional language interpreter [14]. All the interfaces between
the elements of the system (memory layout, stack, heap,
collector) are spelled out explicitly in the module system.
Abelson and Sussman detail the implementation of anothersemispace collector for a register-based Scheme evaluator [1].
The main difference between all these assignments andours is their use of explicit compilers, interpreters, and abstract machines, which expose a lower-level model of theruntime system, encouraging a more systems-oriented viewof garbage collection. Our approach involves fewer curriculardependencies and allows the students to focus on the collection algorithms. Our unobtrusive transformation strategy
allows students to write mutators in a full-fledged language
and exploit graphical debugging and testing features in the
DrRacket IDE. These variations reflect a difference in course
content and philosophy; our approach seems advantageousfor instructors interested in covering garbage collection without assuming much low-level background or context.

Acknowledgments
We thank our students for enduring gc, Matthew Flatt formaking Racket awesome, and the NSF for partially supporting this work.

9. REFERENCES[1] H. Abelson and G. J. Sussman. Structure andInterpretation of Computer Programs. MIT Press,
Cambridge, MA, 1985.

[2] J. Clements and M. Felleisen. A tail-recursive
semantics for stack inspection. In ESOP, 2003.
[3] R. B. Findler, J. Clements, C. Flanagan, M. Flatt,
S. Krishnamurthi, P. Steckler, and M. Felleisen.
DrScheme: A programming environment for Scheme.
JFP, 12(2):159–182, 2002.
[4] R. B. Findler and M. Felleisen. Contracts forhigher-order functions. In ICFP, 2002.
[5] M. Flatt. Composable and compilable macros. In
ICFP, 2002.
[6] D. P. Friedman, M. Wand, and C. T. Haynes.
Essentials of Programming Languages. MIT Press,
second edition, 2001.
[7] N. Horspool. Topics in virtual machine
implementation. http://www.cs.uvic.ca/~nigelh/
Courses/csc586a-2008/.
[8] R. Jones and R. Lins. Garbage Collection: Algorithms
for Automatic Dynamic Memory Management. John
Wiley & Sons, 1996.
[9] S. Krishnamurthi. Programming Languages:
Application and Interpretation. 2006. http://www.cs.
brown.edu/~sk/Publications/Books/ProgLangs/.
[10] G. Marceau, G. H. Cooper, J. P. Spiro,
S. Krishnamurthi, and S. P. Reiss. The design andimplementation of a dataflow language for scriptabledebugging. ASE Journal, 14(1):59–86, 2007.
[11] J. McCarthy. Recursive functions of symbolic
expressions and their computation by machine.
CACM, 3(3):184–185, 1960.
[12] J. G. Morrisett. Mini-ML Compiler. http://www.cs.
cornell.edu/Courses/cs312/2002fa/hw/ps5/ps5.
html.
[13] S. Tobin-Hochstadt, V. St-Amour, R. Culpepper,
M. Flatt, and M. Felleisen. Languages as libraries. In
PLDI, 2011.
[14] D. Walker. Garbage collection programming
assignment. http://www.cs.princeton.edu/courses/
archive/spr05/cos320.