Garbage Collection and Memory

Lisp invented automatic garbage collection (McCarthy, 1959), because cons-heavy programs create lots of short-lived garbage.

Mark everything reachable from roots, sweep the rest Simple; pauses, fragmentation Reference counting Count references, free at zero Incremental; can't free cycles alone Copying (Cheney's algorithm) Copy live objects to a new space

Compacts, fast allocation; needs 2× space Most objects die young: collect the nursery often Used by SBCL, the JVM, Racket CS (Chez) Incremental / concurrent Interleave GC with the program

Low pause times; complexity (write barriers) Tagged pointers: Lisp implementations encode small integers (fixnums), characters, and type tags directly in pointer bits to avoid allocation. That's why fixnum arithmetic is fast and why eq on small numbers usually works (though it isn't guaranteed).

# A minimal mark-and-sweep for cons cells (conceptual)
class Cons:
    def __init__(self, car, cdr):
        self.car, self.cdr, self.marked = car, cdr, False

heap: list[Cons] = []

def mark(obj):
    if isinstance(obj, Cons) and not obj.marked:
        obj.marked = True
        mark(obj.car)
        mark(obj.cdr)

def collect(roots):
    for r in roots:
        mark(r)
    global heap
    heap = [c for c in heap if c.marked]   # "sweep": keep only marked cells
    for c in heap:
        c.marked = False