CDR Coding

Replace predictable tail pointers in contiguous Lisp conses with small per-word codes that decode the cdr as the next address, NIL, or an explicit pointer.

Version

v1 · 2026-08-30 · History

Domain-specific #

1446

Origin domain

computer science

Subdomain

lisp implementation

Aliases

CDR-coding, Cdr coding, Cdr-coded list representation

Core Idea

CDR coding is a compact representation of Lisp cons-based lists in which a small code attached to a word replaces many explicit tail pointers. In the classical Lisp-machine scheme, a word contains the logical car value and a cdr code. The code says that the logical cdr is either stored explicitly in the following word, implicitly equal to the next sequential address, or NIL. A proper list laid out consecutively can therefore use one word for each element: every word except the last says “next,” and the last says “nil.” The representation preserves ordinary Lisp-level car and cdr behavior while exploiting the predictable topology of list spines.

Scope of Application

The home domain is Lisp implementation, especially machines and runtimes with tagged words and primitive-aware memory layouts. The MIT Lisp Machine Manual describes CDR coding as part of the object representation visible to low-level primitives but normally hidden from Lisp programs. CADR-derived and Symbolics documentation treats it as a supported list-storage convention, not as a source-language datatype distinct from a list.

The scheme is most effective for proper list spines that a constructor can allocate as a block. Historical constructors such as LIST, MAKE-LIST, and APPEND could form coded lists because they knew a run of elements together, whereas an incremental CONS generally had to create a normal cons before it knew what object, if any, would become physically adjacent.

Clarity

A practical recognition test asks four questions:

1. Does a word-level code distinguish at least an implicit adjacent tail, a terminal tail, and an explicit tail?
2. Does cdr decode those cases to the same logical relation an ordinary cons would expose?
3. Can coded and ordinary conses coexist, so exceptional topology has an escape?
4. Does mutation or relocation have a defined way to preserve logical references when a coded cell cannot hold a new explicit cdr?

Manages Complexity

Conventional conses give every node the full generality of two independent pointers even though proper-list spines repeatedly use only two cdr patterns: continue with the physically next element, or terminate with NIL. CDR coding moves that regularity into the representation. A two-bit local discriminator stands in for a full-width pointer in common cases, while the normal case preserves generality where needed.

Abstract Reasoning

Let (n) be the number of conses in a proper, unshared list spine. Under the simplified historical word model, an ordinary cons uses one word for car and one for cdr, so

\[ W_{\text{normal}}(n)=2n. \]

If the allocator places all (n) payloads consecutively and cdr codes occupy bits already present in each tagged word, the first (n-1) words can use NEXT and the last can use NIL:

Knowledge Transfer

Within the Lisp domain, the abstraction transfers across machine models and runtime designs whenever logical cons operations can mask multiple physical encodings. A designer can reuse the role structure without copying MIT bit assignments: identify a frequent local successor relation, assign compact cases for adjacency and termination, retain an explicit exception, and make primitives representation-aware.

Outside Lisp, that pattern resembles implicit links, offset elision, tagged unions, and escape-coded compact fields. The lesson is portable: do not pay full generality in every record when a small set of relations dominates and an escape can preserve the uncommon case.

Relationships to Other Abstractions

Current abstraction CDR Coding Domain-specific

Parents (1) — more general patterns this builds on

• CDR Coding is a kind of Compression Prime

  CDR coding instantiates Compression: it removes repeated explicit cdr pointers by encoding the common successor relations in fewer bits and reconstructing the logical relation on access.

Hierarchy paths (3) — routes to 3 parentless roots

• CDR Coding → Compression → Abstraction

Show alternative paths (2)

Neighborhood in Abstraction Space

CDR Coding sits in a sparse region of the domain-specific corpus (95^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Far Pointer — 0.78
• Conditioned Disjunction — 0.77
• Language of Temporal Ordering Specification — 0.76
• Supposition theory — 0.76
• Proof-theoretic semantics — 0.76

Computed from structural-signature embeddings · 2026-09-08