From Semantics to Garbage Collection

The semantics never mentioned memory. A big-step rule says \rho \vdash e \Downarrow v and a closure is "code plus a captured environment" — clean mathematical objects with no notion of allocation, lifetime, or reclamation. But the moment you run the interpreter, those objects have to live somewhere. Environment frames are allocated as lets and calls push them; closures are allocated as \lambdas are evaluated; and because a returned closure keeps its captured frame alive, these things cannot all live on the stack. They live on the heap — and now the question the semantics quietly ignored becomes unavoidable: when is it safe to reclaim a heap object?

This page connects the runtime structures of the previous pages to the discipline that reclaims them. The central identity is beautiful and exact: the heap that the interpreter builds — frames pointing to parent frames, closures pointing to captured frames, data structures pointing to their fields — is a directed graph, and the roots of that graph are precisely the things the semantics keeps in its hand: the current environment and the evaluation stack (the pending continuations). An object is live exactly when a root can reach it. "Garbage" is not a property of an object in isolation — it is a property of the graph. Garbage collection is applied reachability.

Liveness is reachability, not "still in use"

What does it mean for a heap object to be live? The tempting answer — "the program will use it again" — is uncomputable (it is the halting problem in disguise). So every real collector uses a sound, decidable approximation: an object is live if it is reachable from a root by following pointers. Anything unreachable is definitely dead (the program has no way to name it, so it can never use it); some reachable objects may in fact never be touched again, but reclaiming those would need clairvoyance, so we keep them. Reachability is the conservative, correct-by-construction notion of "live".

Roots are the references the running program holds directly: in an interpreter, the current environment (the frame chain in scope) and the evaluation/continuation stack (values and pending computations), plus any global bindings. These are exactly the \rho and control context of the operational semantics.
Reachable = you can get to it by following pointer edges from some root. A closure edge to its captured frame counts; a frame's parent-pointer counts; a data structure's field pointers count.
Garbage = not reachable from any root — regardless of how many other objects point at it. A cycle with no root pointing in is garbage; a lone object no root can name is garbage.

Formally, if R is the set of roots and \to the "points-to" relation, the live set is the reflexive-transitive closure

\text{Live} \;=\; \{\, o \;:\; \exists r \in R,\; r \to^{*} o \,\}, \qquad \text{Garbage} \;=\; \text{Heap} \setminus \text{Live}.

The interpreter's heap, drawn as an object graph

Here is the heap of a running closure-based interpreter. The roots are the current environment frame and the evaluation stack. From them we can reach a live closure and the environment frame it captured — that frame stays alive because a reachable closure points at it, even though the call that created it has long returned. Off to the side sits an orphaned frame and a stale closure that only point at each other: a cycle no root can reach. Watch the mark trace the live set:

This is the whole bridge from semantics to GC in one figure. The objects are the interpreter's own (frames, closures); the roots are the semantics' own (\rho and the control stack); and "collectable" means "the mark phase, starting from those roots, never colours it". Nothing about garbage collection is separate from the language's runtime — it is the runtime's object graph, swept.

A mark-sweep collector over closures and frames

Below is a mark-and-sweep sketch over a heap whose objects are exactly the interpreter's — number cells, environment frames (with a parent and bindings), and closures (with a captured-frame edge). The roots are the current environment plus the evaluation stack. Mark follows every edge from the roots; sweep frees whatever stayed white. Note that the orphaned closure/frame cycle is collected precisely because reachability — not reference counting — decides. Press Run:

// A heap object is one of the interpreter's runtime shapes. `refs` lists the ids it points at. type HObj = | { id: number; kind: "num"; n: number; refs: number[] } | { id: number; kind: "frame"; refs: number[] } // parent frame + bound values | { id: number; kind: "closure"; refs: number[] }; // captured frame (+ maybe more) // The heap the interpreter has built up. const heap: HObj[] = [ { id: 0, kind: "frame", refs: [] }, // F1: a captured environment frame { id: 1, kind: "closure", refs: [0] }, // C1: closure capturing F1 ← reachable { id: 2, kind: "num", n: 42, refs: [] }, // a live value on the eval stack { id: 3, kind: "frame", refs: [4] }, // F2: orphaned frame → C2 { id: 4, kind: "closure", refs: [3] }, // C2: stale closure → F2 (a cycle) ]; // Roots = current environment frame + evaluation stack. Here: C1 (in scope) and the num 42. const roots: number[] = [1, 2]; const byId = (id: number) => heap.find((o) => o.id === id)!; function markSweep(): { live: number[]; collected: number[] } { const marked = new Set<number>(); const grey = [...roots]; // worklist of reachable-but-unscanned ids while (grey.length > 0) { const id = grey.pop()!; if (marked.has(id)) continue; // already black — this tames cycles marked.add(id); // colour it black for (const r of byId(id).refs) grey.push(r); // follow every out-edge } const live = heap.filter((o) => marked.has(o.id)).map((o) => o.id); const collected = heap.filter((o) => !marked.has(o.id)).map((o) => o.id); return { live, collected }; } const { live, collected } = markSweep(); console.log("roots :", roots); console.log("LIVE (kept) :", live); // [0,1,2] — F1 survives BECAUSE C1 captured it console.log("COLLECTED :", collected); // [3,4] — the F2⇄C2 cycle, unreachable console.log("=> F1 (id 0) is live only via the closure C1's capture edge;"); console.log(" the C2⇄F2 cycle is freed because no ROOT can reach it.");

Frame F1 (id 0) is kept although the call that built it is gone — a reachable closure holds it. The F2/C2 cycle is reclaimed although each still points at the other, because reachability, not reference count, is the verdict. This is the same reason reference counting leaks cycles: it asks "how many point at me?", the collector asks "can a root reach me?".

Three ways to act on reachability

Every tracing collector computes the same live set; they differ in what they do with it and how they lay memory out. At a high level:

Mark-sweep. Mark the reachable set from the roots, then sweep the heap freeing the unmarked. Simple and non-moving (object addresses never change, so it suits C interop), but it fragments the heap and its sweep cost is proportional to the whole heap.
Copying (semi-space / Cheney). Split the heap in two. Trace the live objects and copy them compactly into the other half; then flip. Cost is proportional to the live data only (dead objects are never touched), and it compacts as it goes — at the price of using half the memory and moving objects (so pointers must be forwarded).
Generational. Exploit the generational hypothesis — most objects die young. Allocate into a small nursery collected often (usually by copying, since survivors are few); promote survivors to an old space collected rarely. Nursery collection needs a remembered set to track old→young pointers so it can treat them as extra roots without scanning the whole old space. This is how the JVM, .NET and V8 keep pauses short.

A subtle point the semantics-to-GC view makes clear: a copying or generational collector moves objects, so it must fix up every pointer to a moved object — including the capture edges inside closures and the parent pointers inside frames. The collector must understand the interpreter's object layout exactly, because it is rewriting the very graph the interpreter walks. GC and the runtime are not neighbours; they share one data structure.

C. J. Cheney's 1970 algorithm copies a live graph breadth-first using the to-space itself as the queue — no explicit stack, no recursion. Two pointers walk the to-space: scan trails behind, free races ahead. You copy the roots' targets to the front; then scan advances object by object, and for each pointer it finds, if the target hasn't moved yet you copy it to free (leaving a forwarding pointer behind so you never copy it twice) and bump free. When scan catches up to free, every live object has been copied and compacted, and the old space can be wiped wholesale. It is one of those algorithms that feels like a magic trick the first time you trace it: an entire graph traversal, in constant auxiliary space, falling out of two integers chasing each other across a block of memory.

Reachable ≠ will-be-used; unreachable = definitely dead. GC keeps every reachable object even if the program will never touch it again (deciding otherwise is the halting problem). So a "leak" in a managed language is almost always an accidental root or edge — a global cache, a closure captured in a long-lived listener, a stale frame still referenced — keeping garbage reachable. To fix a managed-language leak, find what still points at the object, not the collector.
Closures are sneaky roots. A closure keeps its entire captured environment alive, not just the variables it uses — if the frame binds a huge structure the body never mentions, a naïve capture can pin megabytes. This is why some compilers do closure conversion that captures only the free variables actually referenced. Capturing a whole frame is correct but can be costly.
Moving collectors must forward every pointer. Copying and generational GC relocate objects, so every reference — including a closure's capture edge and a frame's parent pointer — must be updated to the new address (via forwarding pointers). Miss one and you have a dangling pointer into freed space. A non-moving mark-sweep sidesteps this but pays in fragmentation.