Teaching Garbage Collection without Implementing Compilers or Interpreters
📜 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 of compilers and runtime systems, which many courses do not cover or cannot assume. This paper presents an instructive approach to teaching gc, where students implement it atop a simplified stack and heap. 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 successfully classroom-tested for several years at several institutions.
✨ Summary
The paper presents a Racket-based framework for teaching garbage collection through implementation, while avoiding the need for students to first build or understand compilers, interpreters, continuation-passing-style transformations, or low-level runtime systems. Students implement collectors over a simplified heap and stack interface, while the framework automatically performs the program transformations needed to expose roots and route allocation through student code.
The framework supports multiple collector designs, including mark-and-sweep, stop-and-copy, generational, and conservative approaches. Students write mutator programs in ordinary Racket, allowing them to test collectors with substantially more complex workloads than would be practical in a toy language. The infrastructure also provides automated root-set calculation, interchangeable native and student-written collectors, randomized graph-generating tests, source-level co-debugging, and graphical heap visualization.
The authors report classroom use at several institutions and describe assessment through implementation, testing, and code-inspection activities. A survey of 258 students over four years found changes in students’ attitudes toward manual memory management and garbage collection: fewer students preferred manual management, and fewer believed it was always faster. The assignment was also reported by students as the most educationally valuable and enjoyable part of the course.
The approach appears to have had continuing influence in computing education and the Racket ecosystem. A contemporaneous Brown PLT account states that the framework was used at several universities and included with Racket, while current Racket documentation provides a GC2 collector language with an interface closely matching the pedagogical allocator model described in the paper. (blog.brownplt.org) A later programming-languages education paper cites this work as part of the prior literature on experimental and adversarial approaches to teaching programming languages, indicating influence beyond garbage-collection instruction itself. (drops.dagstuhl.de) The search found evidence of educational and tooling influence, but no verified industry deployment directly attributable to this paper. The paper’s bibliographic details and author ordering are corroborated by the authors’ publication pages and bibliographic records. (cs.brown.edu)