Garbage Collection: Mark-and-Sweep

Writing a Compiler/Interpreter: Advanced

Chapter 8 · Garbage Collection: Mark-and-Sweep

Chapter 7 gave objects a way to outlive the call that created them — a closure keeps its captured upvalues alive indefinitely, for as long as anything still needs them. Nothing so far has ever gotten rid of one. Closure and Upvalue objects have been piling up in memory since Chapter 6, with nothing ever asking whether a given one is still needed. This chapter builds a real collector to answer that question — and along the way, finds a genuinely surprising reason it's needed at all, in a VM hosted inside a language that already has its own garbage collector.

An Honest Framing, First

Python already manages memory automatically — say so plainly before building anything

A real bytecode VM written in C (the design this course has followed throughout) has no garbage collector unless it builds one — a malloc'd Closure stays allocated forever unless something explicitly frees it. This course's own VM is written in Python, which already reference-counts every object and reclaims it automatically the instant nothing points to it anymore. Building a mark-and-sweep collector here is a genuine, correctly-working algorithm — not a simulation — but it's worth being direct about why: it's the real mechanism a systems language needs, demonstrated faithfully, even though Python's own memory management would keep this specific VM safe with or without it. Whether that makes this chapter's own collector purely redundant turns out to have a more interesting answer than "yes" — see below.

What's on the Heap

Only two kinds of object get created dynamically, during execution, potentially many times, with a genuine question of whether each one is still needed later: Closure and Upvalue. Both allocation points from Chapter 7 now record into an explicit self.heap list.

def alloc_closure(self, function, upvalues):
    c = Closure(function, upvalues)
    self.heap.append(c)          # NEW -- every closure gets tracked
    return c

def capture_upvalue(self, abs_slot):
    if abs_slot in self.open_upvalues:
        return self.open_upvalues[abs_slot]
    upv = Upvalue(self.stack, abs_slot)
    self.heap.append(upv)        # NEW -- every upvalue gets tracked
    self.open_upvalues[abs_slot] = upv
    return upv
    

Roots: Where Reachability Starts

An object is garbage only if nothing reachable from the program's own currently-live state points to it, directly or indirectly. That live state — the roots — is everything currently on the value stack, every value stored in globals, the closure each active call frame is running, and any upvalue still open (backing a live stack slot right now).

def mark_roots(self):
    for value in self.stack:
        if isinstance(value, (Closure, Upvalue)): self.mark_object(value)
    for value in self.globals.values():
        if isinstance(value, (Closure, Upvalue)): self.mark_object(value)
    for frame in self.frames:
        self.mark_object(frame.closure)
    for upv in self.open_upvalues.values():
        self.mark_object(upv)
    

Mark: Following References Transitively

A root is only the start. A closure can hold upvalues; a closed upvalue can hold a value that's itself a closure (a closure captured by another closure, stored as its own upvalue's frozen value). Marking has to follow those references outward, not just mark the roots themselves.

def mark_object(self, obj):
    if obj is None or obj.marked:
        return                          # already visited -- stop, don't loop forever
    obj.marked = True
    if isinstance(obj, Closure):
        for upv in obj.upvalues:
            self.mark_object(upv)          # a closure keeps its own upvalues alive
    elif isinstance(obj, Upvalue):
        if obj.closed and isinstance(obj.value, Closure):
            self.mark_object(obj.value)    # a closed upvalue might be HOLDING a closure
        # if OPEN, its value lives on the stack -- already a root, nothing more to do
    

Sweep: Discarding What Isn't Marked

def collect_garbage(self):
    self.mark_roots()
    survivors = [obj for obj in self.heap if obj.marked]
    collected = len(self.heap) - len(survivors)
    for obj in self.heap:
        obj.marked = False       # reset every mark for the NEXT cycle
    self.heap = survivors
    return collected
    

Verified: a Real Collection Cycle

fun makeAdder(x) {
    fun adder(y) { return x + y; }
    return adder;
}
var keep = makeAdder(10);   // kept -- reachable via the global 'keep'
makeAdder(20);              // discarded immediately -- garbage
makeAdder(30);              // discarded immediately -- garbage
print keep(5);              // 15
    

Verified directly — exactly 5 of 8 allocated objects are correctly identified and removed

Before collect_garbage(): 8 objects on the heap — the top-level script's own closure, makeAdder's closure, and one [Closure, Upvalue] pair for each of the three calls. After: 3 survive — makeAdder's own closure, keep's closure, and keep's captured upvalue. 5 collected: the two throwaway adder closures from makeAdder(20) and makeAdder(30) (each immediately discarded by the very next OP_POP, per Chapter 4's own expression-statement rule), their two upvalues, and — genuinely unexpected until checked — the top-level script's own closure, which nothing references anymore once the program has finished running.

Verified directly — the surviving closure remains fully functional after collection

Calling keep(100) again, after collect_garbage() has already run: 110, correct. Removing an object from self.heap is bookkeeping only — the real Python object keep refers to was never touched.

Verified directly — a program with nothing genuinely unreachable collects almost nothing

Storing all three makeAdder results in separate globals (a, b, c) instead of discarding two of them: collect_garbage() removes exactly 1 object — again, only the now-unreferenced top-level script closure. Every closure and upvalue the program itself created stays reachable through globals, and none of it is touched.

The Twist: This Collector Isn't Actually Redundant

The honest framing at the top of this chapter said Python would keep this VM memory-safe with or without a collector of its own. Checking that directly turns up something worth correcting.

Verified directly — the VM's own heap list holds a real, counted Python reference to every object it tracks

Inspecting sys.getrefcount() on one of the two discarded adder closures before collect_garbage() runs shows a live reference count greater than zero — self.heap itself is holding a genuine, counted Python reference to an object nothing in the running Wisp program cares about anymore. Only after collect_garbage() removes it from self.heap does that reference actually go away.

The append-only bookkeeping list is the real leak — this chapter's own collector is what fixes it

self.heap only ever grows via append() in alloc_closure/capture_upvalue; nothing removes anything from it except collect_garbage() itself. Without ever calling it, every closure and upvalue a Wisp program has ever created — including every one immediately discarded, like the two adder closures above — would stay referenced by self.heap forever, growing without bound for the entire life of the program. Python's own reference counting was never the obstacle; the VM's own tracking structure, built specifically so a mark-and-sweep collector would have something to sweep, is what turns out to need exactly the collector this chapter built to fix it.

Where This Connects

This chapter's finding	What it connects to
Roots include every active frame's own closure, and every open upvalue	Chapter 6's own `CallFrame` and Chapter 7's own `open_upvalues` dict — this chapter reuses both structures directly as sources of truth for reachability, adding nothing new to track
A closed upvalue can hold a closure, which mark_object follows transitively	Chapter 7's own closure-capturing-a-closure scenarios (Exercise 3's nested forwarding) — the same shapes that made closures hard to compile make them non-trivial to trace for reachability too
The VM's own `self.heap` list is itself a real reference, not neutral bookkeeping	A general lesson about instrumentation: adding a tracking structure to observe a system can change that system's own behavior — here, literally introducing the memory leak this chapter's own collector then fixes
A no-garbage program collects almost nothing (just the finished top-level script)	Confirms the collector is conservative and correct in the boring case, not just the dramatic one — a collector that swept something still reachable would be a far worse bug than one that's merely unnecessary

Hands-On Exercises

Exercise 1

Before running this chapter's own makeAdder example, predict by hand exactly how many objects will be on vm.heap once the program finishes (counting every Closure and Upvalue allocated by name), and which specific ones will survive a collect_garbage() call. Then run it and check your prediction against the actual heap contents.

📄 View solution

Exercise 2

Using sys.getrefcount(), confirm directly that one of the two discarded adder closures from this chapter's own example still has a positive Python reference count immediately before collect_garbage() runs, and explain specifically which line of code is responsible for that reference existing at all.

📄 View solution

Exercise 3

Rewrite this chapter's own makeAdder example so that all three calls' own results are stored in separate globals (a, b, and c) instead of two being discarded, then call all three. Run collect_garbage() and confirm how many objects it actually removes. Explain why the number isn't zero, even though nothing the program created is unreachable.

📄 View solution

Chapter 8 Quick Reference

Heap: every Closure and Upvalue ever allocated, tracked in self.heap from the moment each is created
Roots: the value stack, globals, each active frame's own closure, and every currently open upvalue
Mark: transitive — a closure marks its own upvalues; a closed upvalue marks a closure it happens to hold
Sweep: anything on the heap left unmarked after mark_roots() is removed; every mark resets for the next cycle
Verified: a real program with genuine garbage — 8 objects, exactly 5 correctly collected, exactly 3 correctly kept and still functional afterward
Verified: a program with nothing genuinely unreachable collects almost nothing (just the finished top-level script's own closure)
The twist, verified: self.heap itself holds a real, counted Python reference — without this chapter's own collector, that append-only list would leak every discarded closure and upvalue for the life of the program, regardless of Python's own reference counting
Next chapter: Classes, Instances & Method Dispatch in Bytecode — the last major feature, verified against Course 1's own tree-walking dispatch