Garbage
McCarthy described this in April 1960, in the paper that also described LISP. The part usually left out is when it happens. Collection is not a tidy-up running quietly in the background: nothing happens until the program runs out of free storage. You ask for a register, there are none, and only then does anything get collected. What follows allocates until it stalls, then collects, and counts what came back.
Memory becomes garbage when nobody can reach it
1 A list, built one register at a time
Cells are taken from the free list one at a time. Two of them are held by base registers; the rest are reachable only through the ones in front of them. Drop a base register and a whole chain becomes unreachable without moving anything.
2 The free-storage list runs out, which is when anything happens at all
Nothing is collected while there is anything left to hand out. Keep allocating and the free list shortens until a request cannot be met, and that request is what starts a cycle.
3 Marking, from the base registers outward
Marking starts at the base registers and follows every chain. A cell already marked is left alone, which is what stops a loop going round forever. Nothing is freed in this pass; it only decides what is still reachable.
4 Sweeping, and how many registers came back
The sweep walks the whole heap once, puts back everything unmarked, and clears the marks it set. Its cost does not depend on how much was garbage: it is the size of the heap either way, which is the reason McCarthy's own rule is about what the cycle returns rather than what it frees.
| after the cycle | value |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| garbage sitting in the heap does not start a collection | yes | 1 unreachable cell(s) and 0 cycles so far |
| the allocation that cannot be met is what starts one | yes | one request returned 1 cell(s) and then succeeded |
| a cell you can still reach is never collected | yes | 12 reachable before, 12 after |
| a list that points back at itself is walked once, not forever | yes | 3 cell(s) reached in a heap holding a loop |
| the sweep walks the whole heap however much was garbage | yes | walked 20 cell(s) to return 20 |
What is real here, and what is not
The paper does not use the words
McCarthy calls it the reclamation process throughout. A footnote in his own later copy explains the absence: “We already called this process “garbage collection”, but I guess I chickened out of using it in the paper—or else the Research Laboratory of Electronics grammar ladies wouldn’t let me.” The name on this page is the one the field settled on, and the paper’s own word is reclamation.
Cells, not registers, and far fewer of them
The original free-storage list held about fifteen thousand registers. This heap holds a few dozen, because the point is to watch the list run out, and fifteen thousand squares is not a thing anyone can watch. Every count on this page is of the small heap in front of you.
Mark and sweep only, and the simplest kind
No generations, no compaction, no copying collector, no reference counting, no concurrent or incremental marking, none of which existed yet in the form the word implies now. The sign bit in the original is a boolean here. Nothing moves during a collection, so no address ever changes, which is exactly why this family of collector was easy to add to a language that hands out raw pointers.
The efficiency rule is the paper's, not this page's
McCarthy writes that the cycle takes several seconds and must therefore return at least several thousand registers or the program spends most of its time collecting. That is a statement about a machine from 1960 and the numbers do not carry over. What does carry over is the shape of it: a collector is worth running when it returns a lot, and the cost of the sweep is the heap rather than the garbage.
No sound
Nothing here has a duration to hear.
Sources
- John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, CACM 3(4), April 1960, pages 184-195. Read for this page, in McCarthy's own copy at Stanford: section 4c is where the free-storage list, the base registers, the sign-bit marking and the sweep are described, and where the footnote about the name sits.
- The same paper in the ACM's own record, for the citation: volume 3, issue 4, April 1960.
- Logical Art, the studio this belongs to.