2.4. Lists and Conses

A cons is a record structure containing two components called the car and the cdr. Conses are used primarily to represent lists.

A list is recursively defined to be either the empty list or a cons whose cdr component is a list. A list is therefore a chain of conses linked by their cdr components and terminated by nil, the empty list. The car components of the conses are called the elements of the list. For each element of the list there is a cons. The empty list has no elements at all.

A list is notated by writing the elements of the list in order, separated by blank space (space, tab, or return characters) and surrounded by parentheses.

(a b c)               ;A list of three symbols 
(2.0s0 (a 1) #\*)     ;A list of three things: a short floating-point 
                      ; number, another list, and a character object

The empty list nil therefore can be written as (), because it is a list with no elements.

A dotted list is one whose last cons does not have nil for its cdr, rather some other data object (which is also not a cons, or the first-mentioned cons would not be the last cons of the list). Such a list is called ``dotted’’ because of the special notation used for it: the elements of the list are written between parentheses as before, but after the last element and before the right parenthesis are written a dot (surrounded by blank space) and then the cdr of the last cons. As a special case, a single cons is notated by writing the car and the cdr between parentheses and separated by a space-surrounded dot. For example:

(a . 4)         ;A cons whose car is a symbol 
                ; and whose cdr is an integer 
(a b c . d)     ;A dotted list with three elements whose last cons 
                ; has the symbol d in its cdr

Compatibility note: In MacLisp, the dot in dotted-list notation need not be surrounded by white space or other delimiters. The dot is required to be delimited in Common Lisp, as in Lisp Machine Lisp.

It is legitimate to write something like (a b . (c d)); this means the same as (a b c d). The standard Lisp output routines will never print a list in the first form, however; they will avoid dot notation wherever possible.

Often the term list is used to refer either to true lists or to dotted lists. When the distinction is important, the term ``true list’’ will be used to refer to a list terminated by nil. Most functions advertised to operate on lists expect to be given true lists. Throughout this book, unless otherwise specified, it is an error to pass a dotted list to a function that is specified to require a list as an argument.

Implementation note: Implementors are encouraged to use the equivalent of the predicate endp wherever it is necessary to test for the end of a list. Whenever feasible, this test should explicitly signal an error if a list is found to be terminated by a non-nil atom. However, such an explicit error signal is not required, because some such tests occur in important loops where efficiency is important. In such cases, the predicate atom may be used to test for the end of the list, quietly treating any non-nil list-terminating atom as if it were nil.

Sometimes the term tree is used to refer to some cons and all the other conses transitively accessible to it through car and cdr links until non-conses are reached; these non-conses are called the leaves of the tree.

Lists, dotted lists, and trees are not mutually exclusive data types; they are simply useful points of view about structures of conses. There are yet other terms, such as association list. None of these are true Lisp data types. Conses are a data type, and nil is the sole object of type null. The Lisp data type list is taken to mean the union of the cons and null data types, and therefore encompasses both true lists and dotted lists.

Next: Arrays Up: Data Types Previous: Symbols

AI.Repository@cs.cmu.edu