Info Catalog elisp: Lists elisp: List-related Predicates

elisp: Cons Cells

 
 5.1 Lists and Cons Cells
 ========================
 
 Lists in Lisp are not a primitive data type; they are built up from
 “cons cells” (Cons Cell Type).  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 (this asymmetry
 between CAR and CDR is entirely a matter of convention; at the level of
 cons cells, the CAR and CDR slots have similar properties).  Hence, the
 CDR slot of each cons cell in a list refers to the following cons cell.
 
    Also by convention, the CDR of the last cons cell in a list is ‘nil’.
 We call such a ‘nil’-terminated structure a “true list”.  In Emacs Lisp,
 the symbol ‘nil’ is both a symbol and a list with no elements.  For
 convenience, the symbol ‘nil’ is considered to have ‘nil’ as its CDR
 (and also as its CAR).
 
    Hence, the CDR of a true list is always a true list.  The CDR of a
 nonempty true list is a true list containing all the elements except the
 first.
 
    If the CDR of a list’s last cons cell is some value other than ‘nil’,
 we call the structure a “dotted list”, since its printed representation
 would use dotted pair notation (Dotted Pair Notation).  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 a 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, we refer to any
 structure made out of cons cells as a “list structure”.
 

Info Catalog elisp: Lists elisp: List-related Predicates