LISP II Garbage Collector

✨ Summary

The memo proposes a relocating garbage collector for LISP II. The existing LISP storage-control mechanism is described as adequate mainly for list structures, whereas LISP II is intended to support arrays, binary programs, and other quantities that may require contiguous blocks of storage. The proposed collector therefore both reclaims unreachable storage and relocates surviving objects to consolidate free space.

The design operates in four phases. First, marking traces all active LISP structures and records live words in a bit table. Each LISP quantity has a tracing routine that determines how its references should be followed and whether its addresses or decrements are relocatable. This type-specific tracing permits different kinds of LISP quantities to coexist in free storage.

Second, collection performs a linear sweep of the bit table. It identifies reclaimable words and builds a free-storage list while recording, for each location, the number of collected words below it. This value represents the local relocation distance for objects located above the reclaimed region. Third, relocation scans for relocatable addresses and decrements, determines their corresponding relocation distances, and subtracts those distances from the original values. Finally, moving performs a linear sweep that packs all retained items downward into the available free words, leaving the remaining storage as one contiguous free block.

The paper is an early description of a mark-and-compact-style collector: reachability marking is combined with address adjustment and compaction rather than merely rebuilding a fragmented free list. Historical garbage-collection bibliographies identify the memo as an early mark-compact design and preserve it as part of the development history of automatic memory management. (argonavis.com.br) However, the search found no strong evidence that this particular two-page memo was directly cited as a primary influence by later garbage-collection algorithms or industrial implementations. Later LISP II documentation continued to specify garbage collection, but that documents continuation within the LISP II project rather than demonstrated influence from this memo. (softwarepreservation.computerhistory.org)