Design a Mark-and-Sweep Garbage Collector

Design the heap and a tracing mark-and-sweep collector for a small single-threaded interpreter, covering roots, cycles, the allocation trigger, and out-of-memory.

For this exercise, assume you are building the memory manager for the runtime of a small interpreted language that runs on one thread. The interpreter creates every object through a managed heap.

Each object has a type, a size in bytes, and a fixed number of reference fields set when it is created; each field points to another object or to nothing. Memory is simulated: the heap only counts bytes against a fixed budget, and there are no real addresses or calls to the operating system.

The roots are the global variables and the local variables in every frame on the interpreter's call stack, and the runtime must be able to tell the collector what the current roots are.

The interpreter needs to allocate an object, set or clear a reference field, run a full collection, and read simple stats: live bytes and how many objects the last collection freed.

When an allocation would go over the budget, a collection runs first; if there is still not enough room, the allocation fails with an out-of-memory error. The collector must use tracing mark-and-sweep.

It never frees an object that a root can reach, it frees every unreachable object, including groups of objects that only point to each other in a cycle, it pauses the interpreter for the whole collection (stop-the-world), and it leaves no leftover marking state, so the next collection starts clean.

Design the objects, responsibilities, interfaces, and interactions. Two follow-ups compare your design with reference counting and shorten pauses with incremental marking.

Moving or compacting collectors, generations, several interpreter threads, finalizers, weak references, and real operating-system memory are outside scope.