Lists in Lisp are not a primitive data type; they are built up from cons cells. A cons cell is a data object that represents an ordered pair. That is, it has two slots, and each slot holds, or refers to, some Lisp object. One slot is known as the car, and the other is known as the cdr. (These names are traditional; see Cons Cell Type.) cdr is pronounced “could-er.”
We say that “the car of this cons cell is” whatever object its car slot currently holds, and likewise for the cdr.
A list is a series of cons cells “chained together,” so that each
cell refers to the next one. There is one cons cell for each element of
the list. By convention, the cars of the cons cells hold the
elements of the list, and the cdrs are used to chain the list: the
cdr slot of each cons cell refers to the following cons cell. The
cdr of the last cons cell is
nil. This asymmetry between
the car and the cdr is entirely a matter of convention; at the
level of cons cells, the car and cdr slots have the same
nil is the conventional value to put in the cdr of
the last cons cell in the list, we call that case a true list.
In Lisp, we consider the symbol
nil a list as well as a
symbol; it is the list with no elements. For convenience, the symbol
nil is considered to have
nil as its cdr (and also
as its car). Therefore, the cdr of a true list is always a
If the cdr of a list's last cons cell is some other value,
nil nor another cons cell, we call the structure a
dotted list, since its printed representation would use
‘.’. There is one other possibility: some cons cell's cdr
could point to one of the previous cons cells in the list. We call
that structure a circular list.
For some purposes, it does not matter whether a list is true, circular or dotted. If the program doesn't look far enough down the list to see the cdr of the final cons cell, it won't care. However, some functions that operate on lists demand true lists and signal errors if given a dotted list. Most functions that try to find the end of a list enter infinite loops if given a circular list.
Because most cons cells are used as part of lists, the phrase list structure has come to mean any structure made out of cons cells.
The cdr of any nonempty true list l is a list containing all the elements of l except the first.
See Cons Cell Type, for the read and print syntax of cons cells and lists, and for “box and arrow” illustrations of lists.blog comments powered by Disqus