Garbage Collection

Memory lifetime is bookkeeping, and humans are bad at bookkeeping. In C you malloc a block and you must free it exactly once: never (a leak), twice (corruption), or too early (use-after-free). Whole categories of the worst, hardest-to-find bugs live in that one obligation.

The person who saw it first

John McCarthy was at MIT around 1959, building Lisp to chase a wild goal: a program that could reason with common sense, his “Advice Taker”. That meant code endlessly building and discarding little pieces of list structure, at a pace and in patterns no human could track. Asking the programmer to free each cell by hand was hopeless when you could not even say when a cell had stopped mattering.

His answer was to stop asking. Let the machine, every so often, walk over what is still reachable and reclaim everything else. It was the first garbage collector, running on an IBM 704 whose entire memory would be a rounding error today. The idea was so far ahead of its hardware that GC was written off as an academic luxury for years, until memory grew and the rest of the field caught up to McCarthy’s quiet gift.

Two philosophies, side by side

• C — you hold the ledger. Every allocation is a promise to free. Fast and total control, but safety rests entirely on the programmer never slipping, not once, across a whole codebase.
• Lisp / Clojure — the runtime holds it. Allocate as freely as you think. When you stop referencing something, it becomes unreachable, and the collector reclaims it later. You trade a little control and some pause time for the deletion of an entire bug class.

Why it endures

This is the value versus place distinction again: you care about values, not the addresses they happen to sit at. Managed runtimes (the JVM, Go, .NET, every browser’s JavaScript) all descend from McCarthy’s move. Even Rust’s borrow checker is an answer to the exact question he asked in 1959 — who owns this memory, and when is it safe to reclaim? — reached by a different route: proven at compile time instead of tracked at runtime.

Try it

Run the Clojure first (make a heap of garbage, watch nothing bad happen), then the C (notice the ceremony, and imagine forgetting the free).

;; Allocate 100k maps on purpose. No free(), no leak - stop referencing
;; them and the runtime reclaims them for you.
(let [xs (doall (map (fn [i] {:i i :sq (* i i)}) (range 100000)))]
  (println "made" (count xs) "maps; last one:" (last xs)))
(println "the other 99999 are unreachable now - GC's problem, not yours")

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int *xs = malloc(5 * sizeof(int));   /* you asked for it... */
    for (int i = 0; i < 5; i++) xs[i] = i * i;
    printf("xs[4] = %d\n", xs[4]);
    free(xs);                            /* ...you must give it back, once */
    return 0;
}

[!recall] What does garbage collection free you from, and what does it cost? It frees you from manual lifetime bookkeeping, and with it the whole family of leaks, double-frees, and use-after-free bugs. The cost is runtime overhead and giving up precise control over when memory is reclaimed (collector pauses). For the vast majority of programs that is a trade well worth making, which is why most modern languages take it by default.

Sources

• McCarthy, “Recursive Functions of Symbolic Expressions and Their Computation by Machine” (1960) — the paper that introduced Lisp, and with it the first garbage collector.

See also: Lisp, C, Clojure.