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.^[1]^[2]

This is more than generic pointer compression. It is a representation-and-decoding convention joining four commitments: Lisp cons semantics, contiguous placement of common successor relations, a tag vocabulary that distinguishes implicit from explicit tails, and primitive operations that hide the physical layout. Normal and coded conses can occur in the same logical list. An exceptional tail, a shared tail, or an improper-list boundary can fall back to an ordinary explicit pointer without changing what Lisp code observes.^[1]

CDR coding survives as a domain-specific abstraction because its roles recur across MIT CADR-derived machines, Symbolics systems, and analyses of compact list encodings. The exact bit assignments and fourth code vary, but the invariant does not: decode the tag and local memory relation into the same logical cdr that a conventional two-word cons would expose.^[3]^[4] It is not a prime abstraction. Its name, recognition test, and hard cases depend constitutively on cons cells, Lisp primitives, tagged memory, and list mutation.

Structural Signature¶

The classical signature is:

logical cons spine + tagged data word + local layout case → decoded cdr relation equivalent to an explicit tail pointer

It has the following mandatory roles:

Logical cons. A Lisp object with a car and a cdr, independent of its physical representation.
Payload word. A tagged word holding the logical car value and a small cdr-code field.
Local successor relation. A placement convention under which the next logical cons can be recovered by address arithmetic when it immediately follows the current word.
Terminal case. A code that makes the logical cdr equal to NIL without storing a separate NIL pointer.
Explicit escape. A code that directs the implementation to an explicit cdr pointer, classically in the next word, for nonlocal, shared, improper, or otherwise uncompressible tails.
Decoder. The cdr primitive or its microcoded/runtime equivalent, which dispatches on the code and returns the logical tail.
Allocator and constructor policy. A facility that forms consecutive coded blocks when enough of a list spine is known together, while retaining ordinary conses when it is not.
Mutation escape. A representation-changing path for RPLACD or equivalent mutation when an implicit case has no physical slot in which to store the replacement tail.

The MIT manual gives three meaningful classical values: CDR-NORMAL, CDR-NEXT, and CDR-NIL.^[1] For a coded word at address (a), an implementation-level sketch is

\[ \operatorname{cdr}(a)= \begin{cases} \operatorname{payload}(a+1), & \text{NORMAL},\\ a+1\ \text{as a list pointer}, & \text{NEXT},\\ \mathrm{NIL}, & \text{NIL}. \end{cases} \]

The notation abstracts away type-tag reconstruction and exact word organization. The invariant is semantic equivalence, not one fixed bit pattern. Some descriptions reserve a fourth combination for an error; Baker uses an EXTENDED case in an illustrative table.^[2] Those are family variants. A representation is CDR coding when the code eliminates predictable cdr pointers while explicit escape and primitive decoding preserve cons behavior.

What It Is Not¶

CDR coding is not ordinary pointer compression. Shortening every pointer changes its bit width but still stores a cdr pointer in each cons. CDR coding suppresses a pointer when the successor relation can be inferred from the code and layout.

It is not merely a contiguous array of list elements. An array has indexed element semantics and does not by itself preserve cons identity, shared tails, dotted pairs, mixed representation, or Lisp RPLACD. Contiguity is an enabling layout relation, not the whole abstraction.

It is not synonymous with a tagged pointer or tagged architecture. Type and cdr tags provide the discriminants, but many tagged systems do not encode list tails this way. Conversely, the abstract scheme could be implemented by software metadata rather than dedicated hardware, although historical Lisp machines made the dispatch efficient.

It is not a promise that a program's memory use will be cut in half. An ideal proper list of (n) conventional two-word conses occupies approximately (2n) words, while an ideal fully coded spine occupies (n). The saving is therefore up to one half of the cons-representation words in that favorable case. Headers, tags, explicit tails, non-list objects, fragmentation, forwarding cells, and allocator policy reduce whole-program savings.

Finally, it is not restricted by definition to immutable data. Mutation is expensive and can destroy compactness, but historical implementations specify how RPLACD of an implicit cons allocates an ordinary cons and installs an invisible or forwarding pointer.^[1] Favoring known, rarely mutated lists is an engineering policy, not a semantic precondition.

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.^[1] CADR-derived and Symbolics documentation treats it as a supported list-storage convention, not as a source-language datatype distinct from a list.^[5]^[3]

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.^[1]^[6] The scope also includes hybrid structures: a coded prefix can end in a normal cons whose explicit cdr points to a distant or shared tail.

It applies less favorably to heavily mutated lists, unpredictable incremental construction, graph-like structures with extensive sharing, or environments where tag dispatch and exceptional representations cost more than the saved word and locality benefit. Garbage collection or copying can sometimes remove forwarding indirections or re-form compact runs, but such restoration is an implementation option rather than a defining requirement.

Contemporary importance is partly architectural and historical. The exact CADR mechanism is not a universal modern Lisp representation. Still, it is a recurring, analyzable answer to a stable representation problem: exploit a dominant local relation while retaining an escape for irregular cases. Engineers can recognize, compare, implement, and reason about that answer independently of any one Lisp-machine model.

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?

If the answer to the first two is no, the representation is not CDR coding. If only shorter addresses are used, it is pointer compression. If adjacency exists but source programs must use array indexes instead of cons operations, it is an array representation. If the structure is immutable by language definition and has no cons identity or explicit-tail escape, it may share the implicit-successor idea without being this Lisp abstraction.

The label NORMAL can be confusing because, in the classical layout, the word tagged normal holds the car, while the following word holds the explicit cdr pointer. It does not mean “the next logical element is in the next word.” That latter case is NEXT. The decisive diagnostic is what the primitive returns, not what the English label appears to suggest.

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.^[4]

This reduces spatial cost and can improve locality because successive traversal visits adjacent words. It also permits a single logical interface over heterogeneous physical layouts. Lisp code calls cdr; the decoder—not the application—decides whether to increment an address, return NIL, or load an explicit pointer. That separation contains representation complexity below the language level.

The complexity is displaced rather than erased. Allocation must choose when a compact run is possible. The collector must interpret tags and any forwarding cells. Mutation needs an escape because NEXT and NIL devote no word to an explicit cdr. Profiling must distinguish the ideal word ratio from realized system savings. CDR coding makes the frequent regular case cheap by accepting a more elaborate exceptional path.

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:

\[ W_{\text{coded}}(n)=n, \qquad \frac{W_{\text{coded}}}{W_{\text{normal}}}=\frac{1}{2}. \]

This is a best-case representation equation, not a benchmark result. If (e) explicit-tail cases each require an additional cdr word, a useful first approximation is (W=n+e), before headers, forwarding cells, alignment, and fragmentation. It predicts why a workload with many shared or edited tails gets less benefit.

The scheme also licenses operational inference. A traversal of a long NEXT run should issue sequential memory accesses and avoid loading explicit cdr words. A NORMAL boundary adds an indirection/load. A mutation of a NEXT or NIL cell cannot simply overwrite a cdr slot because none exists; it must expand or redirect the representation. Thus a high rate of tail mutation predicts increasing normal cells or forwarding indirections and declining compression.

These inferences remain conditional. Caches, tag checks, garbage collection, memory buses, and microcode determine actual time. “More compact” does not mechanically imply “faster” on every architecture.

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. Bobrow and Clark analyze this broader family by considering compact cdr fields and escape representations rather than only one machine's encoding.^[4]

The exact name does not transfer with the skeleton. A compressed tree node, array index, adjacency encoding, or object layout is not thereby “CDR coded.” Without Lisp car/cdr semantics, cons identity, a cdr-case code, and mixed explicit/implicit tails, the relation is analogy and should route to Compression or Encoding and Decoding rather than enlarge this node.

Examples¶

Canonical proper list. Suppose the logical list is (A B C) and the allocator places payload words at consecutive addresses (q_0,q_1,q_2):

(q_0): payload A, code NEXT;
(q_1): payload B, code NEXT;
(q_2): payload C, code NIL.

Then cdr(q0) produces the list pointer for (q_1), cdr(q1) produces (q_2), and cdr(q2) produces NIL. Three words represent a spine that would take six payload-and-pointer words in the simplified conventional representation.

Mixed improper tail. For (A B . T), A may use NEXT, while the word for B uses NORMAL and its following word stores an explicit pointer to T. This is still CDR coding: the compact and escape cases coexist, and decoding preserves the dotted tail.

Mutation. If q0 above receives an RPLACD changing its tail to X, the word has no explicit cdr slot. The MIT scheme can allocate an ordinary two-word cons holding A and X, then replace the old location with an invisible/forwarding pointer.^[1] Existing references continue to denote the logical cons, but access may now cross an indirection and the original compact run is disrupted.

Nonexample: compressed pointers. A runtime stores both car and cdr as 32-bit offsets instead of 64-bit addresses. It saves space, but every cons still contains an explicit cdr and no code means next, nil, or normal. That is pointer compression, not CDR coding.

Nonexample: packed vector. A compiler replaces a private immutable list with a vector and rewrites all consumers to index it. The result may occupy fewer words and traverse sequentially, but it no longer supplies cons-level semantics or mixed explicit tails. It is representation substitution, not an instance.

Structural Tensions¶

Density versus mutation. NEXT and NIL save the cdr word precisely by removing the place that RPLACD would overwrite. More coded cells improve density; more tail updates trigger expansion, forwarding, or normalization. The diagnostic is not simply whether mutation is permitted, but how often it destroys implicit cases and what indirection remains afterward.

Locality versus placement freedom. Consecutive payloads improve spatial locality and make address increment meaningful, but they constrain allocation. A shared or later-discovered tail may be elsewhere. The NORMAL escape protects semantic generality at the price of a word and a pointer load.

Fast common case versus representation dispatch. NEXT can be implemented by incrementing a pointer and NIL by returning a constant, but every cdr must respect the tag vocabulary. Hardware or microcode can make this cheap; a software-only implementation may find the branches and exceptional paths less attractive.

Peak compression versus workload reality. The (n)-versus-(2n) formula is exact for its simplified ideal. Real structures contain normal boundaries, shared tails, forwarding cells, unrelated objects, and alignment overhead. Reporting whole-system “50% savings” without measuring those factors turns a structural upper bound into a misleading empirical claim.

Stable logical identity versus moving physical representation. Programs should observe the same cons even when mutation or collection expands it. Forwarding preserves that identity, but adds a second representation and forces the collector and access primitives to cooperate. The abstraction succeeds only when this hidden complexity remains semantically transparent.

Structural–Framed Character¶

CDR coding is strongly structural. Its membership can be tested from representation cases, memory relations, primitive behavior, and mutation handling. The cost model and semantic invariant do not depend on aesthetic preference or institutional endorsement. The structural–framed aggregate is assessed at 0.03.

The small framed component reflects engineering choices: which fourth cdr-code meaning to reserve, which constructors form compact runs, when to normalize or copy, and whether a workload's density/locality trade is worthwhile. These choices tune an instance; they do not make the identity socially framed.

Structural Core vs. Domain Accent¶

The structural core is regular-relation elision with an explicit escape: replace a commonly predictable link by a small discriminator, infer the relation locally, and retain a general representation for exceptions. That skeleton can appear in compact object layouts beyond Lisp.

The domain accent is constitutive here. CDR names the Lisp tail relation; payloads are cons car values; the public invariants are the semantics of car, cdr, and destructive update; tags inhabit a Lisp object representation; and constructors and garbage collectors cooperate with those primitives. Strip those roles away and the remaining skeleton is Compression or Encoding and Decoding, not CDR coding. This is why the candidate is autonomous within Lisp implementation yet fails the prime substrate-independence test.

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. Compression is the minimal proposed DAG parent.

It is related to Encoding and Decoding, because cdr codes form a representation vocabulary and the cdr primitive decodes them, but that relationship is broader than the selected parent. It is related to Locality of Reference, because consecutive list words can improve spatial locality, although locality is a contingent benefit rather than the identity. It interacts with the domain-specific Memory Management node through allocation, garbage collection, forwarding, and fragmentation; memory management is not its genus because CDR coding is one object representation within a larger allocation-and-reclamation discipline.

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

Not to Be Confused With¶

Call detail record (CDR) coding: telecommunications classification or encoding of usage records; unrelated to the Lisp tail operation.
Common Data Representation: an external-data representation associated with RPC systems; unrelated despite the acronym.
Content disarm and reconstruction: a cybersecurity process also abbreviated CDR.
Pointer compression: reduces pointer width but need not eliminate predictable cdr pointers.
Tagged pointer or tagged architecture: infrastructure that can support cdr codes but does not imply this scheme.
Unrolled linked list: stores multiple elements per node but retains a different node-and-link organization.
Array or vector representation: may exploit contiguity but does not necessarily preserve cons identity and mixed tails.
CAR and CDR terminology: the historical Lisp names for head and tail accessors; CDR coding is a physical representation strategy for the latter relation, not the accessor itself.
Lempel–Ziv–Welch or dictionary compression: compresses symbol sequences through dictionary references and does not encode cons topology.

References¶

[1] MIT Artificial Intelligence Laboratory, Lisp Machine Manual, 3^rd ed., March 1981, §5.4, “Cdr-Coding.” https://bitsavers.org/pdf/mit/cadr/chinual_3rdEd_Mar81.pdf registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[2] Henry G. Baker Jr., “List Processing in Real Time on a Serial Computer,” Communications of the ACM 21, no. 4 (1978): 280–294, §5. https://www.plover.com/misc/hbaker-archive/RealTimeGC.html registry ↩a ↩b

[3] Symbolics, 3600 Technical Summary, February 1983. https://www.bitsavers.org/pdf/symbolics/3600_series/3600_TechnicalSummary_Feb83.pdf registry ↩a ↩b

[4] Daniel G. Bobrow and Douglas W. Clark, “Compact Encodings of List Structure,” ACM Transactions on Programming Languages and Systems 1, no. 2 (1979): 266–286. https://doi.org/10.1145/357073.357081 registry ↩a ↩b ↩c

[5] Symbolics, Common Lisp Language Concepts. https://www.bitsavers.org/pdf/symbolics/software/genera_8/Symbolics_Common_Lisp_Language_Concepts.pdf registry ↩

[6] Richard P. Gabriel, Performance and Evaluation of Lisp Systems. https://www.lispmachine.net/books/Performance_And_Evaluation_of_Lisp_Systems.pdf registry ↩

[7] Thomas F. Knight Jr., David Moon, Jack Holloway, and Guy L. Steele Jr., “CADR,” MIT AI Memo 528, May 1979. http://www.bitsavers.org/pdf/mit/cadr/AIM-528_CADR.pdf registry

[8] “CDR coding,” Wikipedia, frozen revision 1369366760, 14 August 2026. https://en.wikipedia.org/wiki/CDR_coding registry