Skip to content
KN-86 Deckline

Baker — List Processing in Real Time on a Serial Computer (1978)

What it is

Section titled “What it is”

The paper that made Lisp garbage collection real-time. Baker’s thesis: the elementary list operations — CONS, CAR, CDR, RPLACA, EQ, ATOM — can each be bounded by a small constant time, by doing GC work incrementally (a little per allocation) instead of stop-the-world. His incremental copying collector interleaves reclamation with mutation so no single operation ever stalls. The later “Treadmill” (1992) refines the same idea against a fixed cell pool. This is the canonical literature on not stuttering when a single- threaded machine has to collect garbage mid-workload.

Key takeaways for KN-86

Section titled “Key takeaways for KN-86”
  • Bounded GC latency is a hard constraint here, and this is its founding text. The runtime runs “mark-sweep GC over a fixed object pool (no heap growth, no unbounded pause),” and the event loop budgets “Lisp handlers ~50 ms of latency headroom per event” while the PSG audio callback runs at 44.1 kHz independent of redraw (parent CLAUDE.md; runtime notes). A multi-ms stop-the-world collect would stutter the 20 fps redraw or starve audio — exactly the failure Baker’s incremental scheme exists to prevent.
  • Same class of machine. Baker solved this for memory-constrained, single-threaded 1970s hardware with no parallelism. A Pi Zero 2 W driving one global SystemState over a 32 KB Fe arena is the same problem rhymed forward.
  • Relevant as a design lens, not a drop-in. KN-86’s collector is mark- sweep, not Baker’s copying collector, and the arena resets at cart-load / mission-instance boundaries (parent CLAUDE.md) deliberately sidestep most steady-state collection. So Baker is the reference for if/when bounded-pause behavior is ever measured as a problem on-device — the read-counter / barrier technique and the Treadmill’s fixed-pool discipline are the named prior art.

Notes

Section titled “Notes”
  • Cite candidate in ADR-0004 (VM selection)‘s memory-budget / arena-discipline section — the “why bounded pauses matter and who proved they’re achievable” reference.
  • Cross-link McCarthy 1960 (where GC was first described) and game-programming-patterns (object-pool / fixed-allocation patterns the runtime already leans on).