Dotted pair notation is a syntactic construct in Lisp programming languages used to represent a cons cell, the fundamental building block of lists and data structures. It is written as (a . b), where a is the first element (car) and b is the second element (cdr). This notation explicitly distinguishes between a pair of two values and a proper list, which is a chain of cons cells ending with nil. Dotted pairs are essential for understanding Lisp's S-expression grammar and are commonly used in association lists, property lists, and function argument handling.

1.1 John McCarthy and Lisp's Early Development

Dotted pair notation originated with John McCarthy's development of Lisp at the Massachusetts Institute of Technology in the late 1950s. McCarthy introduced the cons cell as the primitive data structure for representing symbolic expressions (S-expressions). The dot notation (a . b) appeared in the Lisp 1.0 and 1.5 manuals as a way to write a cons cell explicitly, allowing programmers to construct and examine pairs without relying solely on function calls.

1.2 Relationship to S‑expressions

S-expressions (symbolic expressions) are the textual representation of data in Lisp. A dotted pair is one form of S-expression, distinct from atoms and proper lists. The notation (a . b) directly maps to the internal representation of a cons cell, whereas a proper list like (a b c) is a shorthand for nested dotted pairs: (a . (b . (c . nil))). The dot serves as a syntactic marker that separates the car and cdr fields.

1.3 Adoption in Common Lisp and Scheme

Both Common Lisp and Scheme, the two major Lisp dialects, inherit dotted pair notation from early Lisp. Common Lisp uses it in the language standard (ANSI X3J13) for explicit cons cell notation and in lambda list syntax. Scheme also supports dotted pairs, though its use of proper lists is more predominant in idiomatic code. The notation remains largely unchanged across dialects, ensuring backward compatibility.

2.1 Basic Syntax ((a . b))

A dotted pair is written as (a . b), where a and b are any S-expressions (atoms or lists). The parentheses enclose the pair, and a single dot separates the two components. No spaces are required around the dot, but most style guides recommend a space before and after for clarity. For example, (42 . (foo . bar)) is a valid nested dotted pair.

2.2 Proper Lists vs. Dotted Pairs

2.2.1 End-of-list marker (nil)

A proper list is a chain of cons cells where the cdr of the last cell is nil (also represented as the empty list ()). For instance, (a b c) is shorthand for (a . (b . (c . nil))). If the final cdr is not nil, the structure is an improper list. Dotted pair notation is required to write such structures explicitly.

2.2.2 Improper lists

An improper list is a chain of cons cells whose final cdr is an atom (other than nil). For example, (a b . c) represents three cons cells: the first cell has car a and cdr pointing to a second cell; the second cell has car b and cdr pointing to a third cell; the third cell has car c and cdr that is an atom (here c is the final cdr). This is written as (a . (b . (c . c))) in fully dotted form, but the Lisp reader allows the shorthand (a b . c).

2.3 Nested Dotted Pairs

2.3.1 Multiple dots and associativity

Dotted pair notation can nest arbitrarily, but only one dot per level is allowed because a pair has exactly two slots. Nested pairs are written as (a . (b . c)) or ((a . b) . c). The Lisp reader resolves the structure left-associatively: (a . b . c) is not syntactically valid (multiple dots at the same level) and would signal a read error. Proper nesting requires explicit parentheses.

2.4 Reader Macros and Literal Notation

The Lisp reader recognizes the dot as a special character. When the reader encounters a dot after an opening parenthesis, it reads the next form as the car, then the dot (if followed by whitespace), then the cdr, then a closing parenthesis. Reader macros cannot alter this fundamental behavior; the dot is part of the base syntax. Some dialects provide literal notation for cons cells (e.g., Common Lisp's #1=(a . #1#) for circular structures), but these are extensions.

3.1 Association Lists (alists)

An association list is a list of dotted pairs, each representing a key-value mapping. For example, ((name . "Alice") (age . 30) (city . NY)). Functions like assoc and assq search such lists by key, retrieving the associated value via the cdr of the matching dotted pair. Alists are mutable and allow multiple entries with the same key.

3.2 Property Lists (plists)

A property list is a flat list alternating property names and values, e.g., (name "Alice" age 30 city "NY"). Though not using dotted pairs directly, plists can be implemented as a chain of dotted pairs where each pair's car is the name and cdr the remainder list. However, plists are typically proper lists, not dotted pairs.

3.2.1 Difference from alists

Alists use a collection of dotted pairs, making key lookup straightforward: each pair is a single cons cell. Plists use a flat list where keys and values are interleaved at even and odd positions; accessing a value requires traversing the list in steps of two. Alists are more flexible for dynamic addition, while plists are more compact for fixed sets of properties.

3.3 Function Arguments and Destructuring

Dotted pairs appear in lambda lists for handling rest arguments. In Common Lisp, a lambda list can include a dotted pair, e.g., (lambda (a &rest b) ...). However, the actual notation lambda (a . rest) is not standard; the dotted pair is used conceptually when destructuring a rest list: after binding the first parameters, the remaining arguments form a dotted pair with the last parameter as the cdr. Destructuring bind in Scheme often uses dotted pairs: (lambda (x . y) y) returns the list of trailing arguments.

3.4 Dotted Lambda Lists (e.g., lambda (a &rest b) expanded)

The Common Lisp standard allows a lambda list of the form (var1 var2 ... . rest-var). This is a dotted lambda list, where the symbol after the dot receives the list of remaining arguments. For example, (lambda (x y . z) (list x y z)) will bind z to the rest of the argument list. This syntactic sugar is equivalent to using &rest, but the dotted form mirrors the underlying cons-cell structure.

3.5 Influence on Other Data Formats (e.g., EDN, JSON)

Dotted pair notation has influenced the Extensible Data Notation (EDN), which uses [a b] for vectors and {:key value} for maps rather than dotted pairs. JSON uses key-value pairs in maps but with a different syntax. However, the concept of pairing two items with a separator appears in many Lisp-derived languages (e.g., Clojure's (a . b) for cons cells, though Clojure discourages improper lists). Dotted pairs remain distinct due to their explicit cons-cell representation.

4.1 Basic Cons Cell

The expression (cons 1 2) returns a cons cell that is printed as (1 . 2). The car is 1 and the cdr is 2.

4.2 Pair Representing a Key-Value Entry

(setq entry (cons 'name "Alice"))
;; entry => (NAME . "Alice")
(car entry) ; Returns NAME
(cdr entry) ; Returns "Alice"

4.3 Converting Between Dotted and List Notation

4.3.1 Using list and cons functions

  • (list 'a 'b 'c) produces (a b c), which is equivalent to (cons 'a (cons 'b (cons 'c nil))).
  • To create an improper list, use cons with a non-nil final cdr: (cons 'a (cons 'b 'c)) yields (a b . c), printed as (A B . C).

4.3.2 Quasiquoting with dotted pairs

Quasiquoting allows mixing literal and computed values: ` (a . ,(+ 1 2)) ` evaluates to (a . 3)`. This is useful for constructing dotted pairs with computed components.

5.1 Memory Model of Cons Cells

5.1.1 car and cdr pointers

A cons cell is typically implemented as a pair of pointers in memory: one for the car and one for the cdr. Each pointer can reference any Lisp object, including atoms, other cons cells, or nil. The sizes of these pointers depend on the architecture (e.g., 64-bit systems use 8 bytes per pointer). The dot notation is purely syntactic; in memory there is no dot—only two fields.

5.2 Garbage Collection Impact

5.2.1 Consing and memory fragmentation

Frequent creation of cons cells (consing) can lead to memory fragmentation and increased garbage collection overhead. Dotted pairs, being the same structure as proper list nodes, contribute equally to the heap. Optimizing Lisp systems use generational garbage collectors to reduce the cost of short-lived cons cells. Dotted pairs in particular are often used in temporary structures, such as alists during search, and thus may be short-lived.

5.3 Type Tags and Optimization

Some Lisp implementations use tagged pointers to distinguish cons cells from other types. For example, the least significant bit might be set to indicate a cons cell, allowing fast dispatch. Dotted pairs are not a separate type; they are just cons cells. Optimizations such as immediate pairing of small integers (fixnums) or bypassing consing for certain operations (e.g., cons of two fixnums) can improve performance.

6.1 Cons Cells

A cons cell is the primitive pair structure that underlies both proper lists and dotted pairs. It provides the car and cdr operations.

6.2 S-expressions

S-expressions include atoms, dotted pairs, and proper lists. The dot notation is one of several syntactic forms for S-expressions.

6.3 Proper and Improper Lists

Proper lists end with nil; improper lists end with an atom. Dotted pair notation is required to write improper lists.

6.4 Tree Representations (binary trees via nested pairs)

Nested dotted pairs can represent binary trees: each cons cell is a node with left and right subtrees stored in car and cdr. For example, ((a . b) . (c . d)) is a binary tree with root node having (a . b) as left child and (c . d) as right child.

7.1 Lisp (programming language)

7.2 CAR and CDR

7.3 List (abstract data type)

8.1 Primary Sources (Lisp 1.5 Manual, Common Lisp Standard)

  • McCarthy, J. et al. (1962). *Lisp 1.5 Programmer's Manual*. MIT Press.
  • ANSI X3J13 (1994). *Common Lisp Standard*.

8.2 Academic Papers and Tutorials