Writing GNU Emacs Extensions

List Details

This section explains the inner workings of Lisp lists. Since most Lisp programs employ lists to some degree or other, it is beneficial to understand why they work the way they do. This will help you to understand what Lisp lists are and aren't good at.

Lists are composed of smaller data structures called cons cells. A cons cell is a structure that contains two Lisp expressions, referred to, you may not be surprised to learn, as the cell's car and cdr.

The function cons creates a new cons cell from its two arguments. Contrary to the implication in the preceding section, both arguments to cons may be arbitrary Lisp expressions. The second one need not be an existing list.

(cons 'a 'b) ⇒ a cons cell with car a and cdr b
(car (cons 'a 'b)) ⇒ a
(cdr (cons 'a 'b)) ⇒ b

The resulting cons cell is usually depicted as in Figure 6-1.

Figure 6-1. The result of (cons ' a ' b)

When you cons something onto a list, as in

(cons 'a '(b c))

the result is (a b c), which is merely a cons cell whose car is a and whose cdr is (b c). More about this below.

There's a special syntax for cons cells whose cdrs aren't lists. It's called dotted pair notation, and cons cells themselves are sometimes referred to as dotted pairs:

(cons 'a 'b) ⇒ (a . b)
(cons '(1 2) 3) ⇒ ((1 2) . 3)

When the cdr of a cons cell is nil, as in Figure 6-2, the dotted pair notation can be abbreviated to omit the dot and ...