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: v2 · 2026-09-19 · History
Domain-specific #: 1446
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Lisp Implementation → Computer Science & Software Engineering
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.

How would you explain it like I'm…

The Next-Box Sticker

Imagine a list of toys, each in its own box, and each box usually has a note saying where the next box is. If the boxes are lined up in a row, you don't need a whole note — just a tiny sticker that says "next one is right beside me" or "this is the last one." CDR coding does this for lists inside certain old computers, saving lots of space.

Lists Without All the Pointers

In the Lisp programming language, a list is built from pieces called conses; each has a value (the car) and a pointer to the rest of the list (the cdr). Storing all those pointers takes up memory. CDR coding stores list items in a row and adds a tiny code to each one saying where the rest of the list is: in the very next slot, nowhere (the list ends), or at a pointer stored in the next word. Programs still use car and cdr exactly as usual; they don't notice the trick. When a list can't be stored in a neat row, the computer can fall back to an ordinary pointer.

Tagged Compact Lisp Lists

CDR coding is a compact memory representation for Lisp lists. Normally each cons cell uses two words: one for the car (the element) and one for the cdr (a pointer to the rest). With CDR coding, a word holds the car plus a small cdr code saying the cdr is either the next sequential word, NIL (end of list), or stored explicitly in the following word. A proper list laid out consecutively then takes one word per element: every word says "next" except the last, which says "nil." Lisp's car and cdr operations hide this layout, so programs behave the same. Coded and ordinary cells can mix in one list, so shared tails or unusual list endings just fall back to explicit pointers. It was used on Lisp machines such as MIT CADR-derived and Symbolics systems.

CDR coding is a compact representation of Lisp cons-based lists in which a small code attached to a memory word replaces many explicit tail pointers. In the classical Lisp-machine scheme, each word holds the logical car together with a cdr code indicating that the logical cdr is the next sequential address, is NIL, or is stored explicitly in the following word; a proper list laid out consecutively thus takes one word per element, with every word marked 'next' except the last, marked 'nil'. It is more than generic pointer compression, combining four commitments: Lisp cons semantics, contiguous placement of common successor relations, a tag vocabulary distinguishing implicit from explicit tails, and primitive operations (car, cdr) that hide the physical layout. Coded and ordinary conses can coexist in one logical list, so an exceptional tail, a shared tail, or an improper-list boundary can use an explicit pointer without changing what Lisp code observes. The scheme recurs across MIT CADR-derived machines and Symbolics systems; bit assignments and the fourth code vary, but the invariant is that decoding tag plus local memory relation yields the same logical cdr a conventional two-word cons would expose. Because it is defined by cons cells, tagged memory, Lisp primitives and list mutation, it is domain-specific.

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:

Does a word-level code distinguish at least an implicit adjacent tail, a terminal tail, and an explicit tail?
Does cdr decode those cases to the same logical relation an ordinary cons would expose?
Can coded and ordinary conses coexist, so exceptional topology has an escape?
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) — outgoing typed relations

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 → is a kind of Compression → is a kind of 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 (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25