1 Definition and structure
A cons cell is a pair of values, each occupying a fixed-sized field within a single contiguous memory block. It is the primitive compound data type in Lisp-family languages, from which all aggregate structures are built. The two fields are conventionally named car and cdr (pronounced /kɑr/ and /kʊdər/ respectively). Each field can hold any Lisp datum—an integer, a symbol, a string, another cons cell, or the empty list nil.
1.1 Car and cdr fields
The car field holds the first element of a pair; the cdr field holds the second element. These names date from the original IBM 704 implementation (see §6.2). In modern usage, many dialects provide aliases like first and rest for lists, but car and cdr remain the canonical accessors.
1.2 Dotted-pair notation
In textual representation, a cons cell is written as (car . cdr), where the dot separates the two components. For example, (1 . 2) denotes a cons cell whose car is 1 and cdr is 2. The dot is mandatory to distinguish a pair from a list. Dotted-pair notation can nest: (1 . (2 . 3)) is a cons cell with car 1 and cdr another cons cell.
1.3 List notation and proper lists
A chain of cons cells where each cell’s cdr points to the next cell, and the final cdr is nil (the empty list), forms a proper list. Such lists are written without dots: (1 2 3) is syntactic sugar for (1 . (2 . (3 . nil))). Any deviation—such as a final cdr that is not nil—creates an improper list, requiring dotted notation (e.g., (1 2 . 3)).
2 Basic operations
2.1 Constructors: cons
The function cons takes two arguments and returns a new cons cell. Its signature is (cons obj1 obj2). The new cell’s car holds obj1 and its cdr holds obj2. Example: (cons 1 2) → (1 . 2).
2.2 Accessors: car, cdr
car returns the first element of a cons cell; cdr returns the second. Both operate in constant time. Combinations like cadr (equivalent to (car (cdr x))) are standard in many dialects. Accessing the car or cdr of an atom (including nil) is an error in most implementations.
2.3 Mutators: rplaca, rplacd (destructive)
rplaca (replace car) and rplacd (replace cdr) modify the respective field of an existing cons cell. They are destructive: the original cell is changed in place, affecting all references to it. For example:
(setq x (cons 'a 'b)) → (a . b) (rplaca x 'c) → (c . b)
These functions are used for efficiency but can lead to aliasing bugs if used carelessly.
2.4 Predicates: consp, atom, listp
conspreturns true if its argument is a cons cell.atomreturns true if its argument is not a cons cell (including nil and other non‑pair data).listpreturns true if its argument is either nil or a cons cell (i.e., any list‑like object). In Common Lisp,listpis equivalent to(or (null x) (consp x)).
3 Algebraic properties
3.1 Identity and associativity
Cons cells do not form a group; there is no inverse operation. However, the pairing is associative with respect to nesting: (cons a (cons b c)) produces the same structure as (cons (cons a b) c) only when interpreted as binary trees. For proper lists, the “consing” operation is right‑associative—a list is built by repeatedly prepending elements.
3.2 Relationship with nil (empty list)
nil serves dual roles: it is both the empty list and the canonical false value. In proper‑list construction, nil terminates the chain. Any operation expecting a list treats nil as a valid list of length zero. The empty list is its own car and cdr in some dialects? No—accessing car of nil is an error.
3.3 Recursive definitions
Many list operations are defined recursively using car and cdr. For example, the length of a list:
lengthof nil = 0.lengthof a cons cell = 1 +lengthof its cdr.
This recursive pattern is central to functional programming with cons cells.
4 Uses in data structures
4.1 Singly linked lists
4.1.1 Proper lists
The most common use: a sequence of cons cells where each cdr points to the next, and the final cdr is nil. Access is O(n) for arbitrary elements; prepending (cons) is O(1).
4.1.2 Improper (dotted) lists
When the final cdr is not nil, the structure is an improper list (or dotted list). Example: (1 2 . 3). Improper lists are rarely used in modern programming but appear in certain meta‑representations (e.g., association lists with dotted pairs).
4.2 Binary trees and nested structures
Each cons cell can represent a tree node: car holds the left subtree (or data), cdr holds the right subtree. This yields a binary tree where leaves are atoms or nil. S‑expressions (symbolic expressions) are trees built from cons cells and atoms.
4.3 Association lists (alists)
An association list is a list of cons cells, each representing a key‑value pair: ((key1 . value1) (key2 . value2) ...). Functions like assoc search the list linearly. Alists are simple but inefficient for large collections.
4.4 Property lists (plists)
A property list is a flat list of alternating keys and values, stored as a proper list: (key1 value1 key2 value2 ...). Unlike alists, plists are not nested; access uses functions like get and remprop. Many Lisp implementations use plists attached to symbols for attribute storage.
5 Implementation considerations
5.1 Memory layout and tagging
Cons cells are often implemented as two machine words (pointers). To distinguish a cons cell from other objects, Lisp systems use tagging—a few low‑order bits in the pointer or a separate tag field. Tagging allows the runtime to quickly identify the type of an object. Some implementations store type information in the car or cdr field (e.g., fixnum tags).
5.2 Garbage collection implications
Cons cells are heap‑allocated and subject to garbage collection. Because they form linked structures, the collector must traverse chains to mark reachable cells. Generational and copying collectors often handle cons cells efficiently, as they are small and short‑lived in many programs. In some implementations, cons is inlined for speed.
5.3 Efficiency of car/cdr access
Access to car and cdr is typically a single memory load (plus a tag‑mask operation) and is O(1). Destructive updates (rplaca/rplacd) also execute in constant time, but may require write barriers in generational collectors. Overall, cons‑cell operations are among the fastest operations in a Lisp system.
6 Historical context
6.1 Origin in Lisp I and II
The cons cell was introduced by John McCarthy in the late 1950s as the core data structure of Lisp. The first implementation of Lisp I (1958–1960) used cons cells to represent both code (S‑expressions) and data. Lisp II (1962) extended the type system but kept cons cells unchanged.
6.2 The naming convention (Contents of Address/Decrement Register)
The names car and cdr derive from the IBM 704 hardware. That machine had two 15‑bit fields within a 36‑bit word: the address and decrement registers. car stood for “Contents of the Address part of the Register” and cdr for “Contents of the Decrement part of the Register.” The car field held the pointer to the first element; the cdr held the pointer to the rest. These names were carried over into all later Lisp dialects.
6.3 Evolution in modern Lisp dialects (Common Lisp, Scheme, Clojure)
Common Lisp retains car, cdr, and their compound combinations (up to four levels, e.g., cadaddr), plus aliases first and rest. Scheme originally used car and cdr but many implementations provide first and rest as synonyms. Clojure, a modern Lisp on the JVM, uses the same pair metaphor but names the accessors first and rest (or next for the cdr of a seq). Clojure’s core data structures are not built from raw cons cells; instead it uses persistent vectors and linked lists built on abstractions, yet the cons‑cell concept underpins the language’s list‑oriented philosophy.
7 Formal semantics
7.1 Axiomatic definition
Cons cells can be defined axiomatically by three fundamental operations:
conscreates a new pair:∀a,b. (car (cons a b)) = aand(cdr (cons a b)) = b.carandcdrare injective:(cons (car x) (cdr x)) = xfor any cons cellx.- The empty list
nilis an atom:(consp nil)is false.
These axioms suffice to reason about list operations without reference to memory.
7.2 Relation to Church pairs in lambda calculus
In the lambda calculus, a pair is encoded as a function that takes a selector and applies it to the two components. The Church encoding of a pair is:
PAIR = λx y. λf. f x yCAR = λp. p (λx y. x)CDR = λp. p (λx y. y)
This encoding mirrors the behavior of cons cells: CAR (PAIR a b) reduces to a, and CDR (PAIR a b) reduces to b. Pure Lisp’s cons cells are therefore a direct implementation of the Church pair.
7.3 Typed vs. untyped systems
In untyped Lisp (e.g., original Lisp, many Scheme dialects), cons cells can hold any value without type restrictions. In typed functional languages derived from Lisp (e.g., Typed Racket, some extensions of Common Lisp), cons cells are parameterized: a pair (Pairof A B) indicates that the car has type A and the cdr type B. For proper lists, the recursive type (Listof A) is defined as (Rec L (U Null (Pairof A L))). This typed view preserves the recursive structure while enabling static type checking.