car, cdr, cons: Fundamental Functions
In Lisp, car, cdr, and cons are fundamental
functions. The cons function is used to construct lists, and
the car and cdr functions are used to take them apart.
In the walk through of the copy-region-as-kill function, we
will see cons as well as two variants on cdr,
namely, setcdr and nthcdr. (See section copy-region-as-kill.)
cdr repeatedly.
The name of the cons function is not unreasonable: it is an
abbreviation of the word `construct'. The origins of the names for
car and cdr, on the other hand, are esoteric: car
is an acronym from the phrase `Contents of the Address part of the
Register'; and cdr (pronounced `could-er') is an acronym from
the phrase `Contents of the Decrement part of the Register'. These
phrases refer to specific pieces of hardware on the very early
computer on which the original Lisp was developed. Besides being
obsolete, the phrases have been completely irrelevant for more than 25
years to anyone thinking about Lisp. Nonetheless, although a few
brave scholars have begun to use more reasonable names for these
functions, the old terms are still in use. In particular, since the
terms are used in the Emacs Lisp source code, we will use them in this
introduction.
car and cdr
The car of a list is, quite simply, the first item in the list.
Thus the car of the list (rose violet daisy buttercup) is
rose.
If you are reading this in Info in GNU Emacs, you can see this by evaluating the following:
(car '(rose violet daisy buttercup))
After evaluating the expression, rose will appear in the echo
area.
Clearly, a more reasonable name for the car function would be
first and this is often suggested.
car does not remove the first item from the list; it only reports
what it is. After car has been applied to a list, the list is
still the same as it was. In the jargon, car is
`non-destructive'. This feature turns out to be important.
The cdr of a list is the rest of the list, that is, the
cdr function returns the part of the list that follows the first
item. Thus, while the car of the list '(rose violet daisy
buttercup) is rose, the rest of the list, the value returned by
cdr, is (violet daisy buttercup).
You can see this by evaluating the following in the usual way:
(cdr '(rose violet daisy buttercup))
When you evaluate this, (violet daisy buttercup) will appear in
the echo area.
Like car, cdr does not remove any elements form the
list--it just returns a report of what the second and subsequent
elements are.
Incidentally, in the example, the list of flowers is quoted. If it were
not, the Lisp interpreter would try to evaluate the list by calling
rose as a function. In this example, we do not want to do that.
Clearly, a more reasonable name for cdr would be rest.
(There is a lesson here: when you name new functions, consider very carefully about what you are doing, since you may be stuck with the names for far longer than you expect. The reason this document perpetuates these names is that the Emacs Lisp source code uses them, and if I did not use them, you would have a hard time reading the code; but do please try to avoid using these terms yourself. The people who come after you will be grateful to you.)
When car and cdr are applied to a list made up of symbols,
such as the list (pine fir oak maple), the element of the list
returned by the function car is the symbol pine without
any parentheses around it. pine is the first element in the
list. However, the cdr of the list is a list itself, (fir
oak maple), as you can see by evaluating the following expressions in
the usual way:
(car '(pine fir oak maple)) (cdr '(pine fir oak maple))
On the other hand, in a list of lists, the first element is itself a
list. car returns this first element as a list. For example,
the following list contains three sub-lists, a list of carnivores, a
list of herbivores and a list of sea mammals:
(car '((lion tiger cheetah)
(gazelle antelope zebra)
(whale dolphin seal)))
In this case, the first element or car of the list is the list of
carnivores, (lion tiger cheetah), and the rest of the list is
((gazelle antelope zebra) (whale dolphin seal)).
(cdr '((lion tiger cheetah)
(gazelle antelope zebra)
(whale dolphin seal)))
It is worth saying again that car and cdr are
non-destructive--that is, they do not modify or change lists to which
they are applied. This is very important for how they are used.
Also, in the first chapter, in the discussion about atoms, I said that
in Lisp, "certain kinds of atom, such as an array, can be separated
into parts; but the mechanism for doing this is different from the
mechanism for splitting a list. As far as Lisp is concerned, the
atoms of a list are unsplittable." (See section Lisp Atoms.) The
car and cdr functions are used for splitting lists and
are considered fundamental to Lisp. Since they cannot split or gain
access to the parts of an array, an array is considered an atom.
Conversely, the other fundamental function, cons, can put
together or construct a list, but not an array. (Arrays are handled
by array-specific functions. See section `Arrays' in The GNU Emacs Lisp Reference Manual.)
cons
The cons function constructs lists; it is the inverse of
car and cdr. For example, cons can be used to make
a four element list from the three element list, (fir oak maple):
(cons 'pine '(fir oak maple))
After evaluating this list, you will see
(pine fir oak maple)
appear in the echo area. cons puts a new element at the
beginning of a list; it attaches or pushes elements onto the list.
cons must have a list to attach to.(2) You
cannot start from absolutely nothing. If you are building a list, you
need to provide at least an empty list at the beginning. Here is a
series of cons's that build up a list of flowers. If you are
reading this in Info in GNU Emacs, you can evaluate each of the
expressions in the usual way; the value is printed in this text after
`=>', which you may read as `evaluates to'.
(cons 'buttercup ())
=> (buttercup)
(cons 'daisy '(buttercup))
=> (daisy buttercup)
(cons 'violet '(daisy buttercup))
=> (violet daisy buttercup)
(cons 'rose '(violet daisy buttercup))
=> (rose violet daisy buttercup)
In the first example, the empty list is shown as () and a list
made up of buttercup followed by the empty list is constructed.
As you can see, the empty list is not shown in the list that was
constructed. All that you see is (buttercup). The empty list is
not counted as an element of a list because there is nothing in an empty
list. Generally speaking, an empty list is invisible.
The second example, (cons 'daisy '(buttercup)) constructs a new,
two element list by putting daisy in front of buttercup;
and the third example constructs a three element list by putting
violet in front of daisy and buttercup.
length
You can find out how many elements there are in a list by using the Lisp
function length, as in the following examples:
(length '(buttercup))
=> 1
(length '(daisy buttercup))
=> 2
(length (cons 'violet '(daisy buttercup)))
=> 3
In the third example, the cons function is used to construct a
three element list which is then passed to the length function as
its argument.
We can also use length to count the number of elements in an
empty list:
(length ())
=> 0
As you would expect, the number of elements in an empty list is zero.
An interesting experiment is to find out what happens if you try to find
the length of no list at all; that is, if you try to call length
without giving it an argument, not even an empty list:
(length )
What you see, if you evaluate this, is the error message
Wrong number of arguments: #<subr length>, 0
This means is that the function receives the wrong number of arguments, zero, when it expects some other number of arguments. In this case, one argument is expected, the argument being a list whose length the function is measuring. (Note that one list is one argument, even if the list has many elements inside it.)
The part of the error message that says `#<subr length>' is the
name of the function. This is written with a special notation,
`#<subr', that indicates that the function length is one
of the primitive functions written in C rather than in Emacs Lisp.
(`subr' is an abbreviation for `subroutine'.) See section `What Is a Function?' in The GNU Emacs Lisp Reference Manual, for more about subroutines.
nthcdr
The nthcdr function is associated with the cdr function.
What it does is take the cdr of a list repeatedly.
If you take the cdr of the list (pine fir
oak maple), you will be returned the list (fir oak maple). If you
repeat this on what was returned, you will be returned the list
(oak maple). (Of course, repeated cdring on the original
list will just give you the original cdr since the function does
not change the list. You need to evaluate the cdr of the
cdr and so on.) If you continue this, eventually you will be
returned an empty list, which in this case, instead of being shown as
() is shown as nil.
For review, here is a series of repeated cdrs, the text following
the `=>' shows what is returned.
(cdr '(pine fir oak maple))
=>(fir oak maple)
(cdr '(fir oak maple))
=> (oak maple)
(cdr '(oak maple))
=>(maple)
(cdr '(maple))
=> nil
(cdr 'nil)
=> nil
(cdr ())
=> nil
You can also do several cdrs without printing the values in
between, like this:
(cdr (cdr '(pine fir oak maple)))
=> (oak maple)
In this case, the Lisp interpreter evaluates the innermost list first.
The innermost list is quoted, so it just passes the list as it is to the
innermost cdr. This cdr passes a list made up of the
second and subsequent elements of the list to the outermost cdr,
which produces a list composed of the third and subsequent elements of
the original list. In this example, the cdr function is repeated
twice and returns a list that consists of the original list without its
first two elements.
The nthcdr function does the same as repeating the call to
cdr. In the following example, the argument 2 is passed to the
function nthcdr, along with the list, and the value returned is
the list without its first two items, which is exactly the same
as repeating cdr twice on the list:
(nthcdr 2 '(pine fir oak maple))
=> (oak maple)
Using the original four element list, we can see what happens when
various numeric arguments are passed to nthcdr, including 0, 1,
and 5:
;; Leave the list as it was.
(nthcdr 0 '(pine fir oak maple))
=> (pine fir oak maple)
;; Return a copy without the first element.
(nthcdr 1 '(pine fir oak maple))
=> (fir oak maple)
;; Return a copy of the list without three elements.
(nthcdr 3 '(pine fir oak maple))
=> (maple)
;; Return a copy lacking all four elements.
(nthcdr 4 '(pine fir oak maple))
=> nil
;; Return a copy lacking all elements.
(nthcdr 5 '(pine fir oak maple))
=> nil
It is worth mentioning that nthcdr, like cdr, does not
change the original list--the function is non-destructive. This is
in sharp contrast to the setcar and setcdr functions.
setcar
As you might guess from their names, the setcar and setcdr
functions set the car or the cdr of a list to a new value.
They actually change the original list, unlike car and cdr
which leave the original list as it was. One way to find out how this
works is to experiment. We will start with the setcar function.
First, we can make a list and then set the value of a variable to the
list, using the setq function. Here is a list of animals:
(setq animals '(giraffe antelope tiger lion))
If you are reading this in Info inside of GNU Emacs, you can evaluate this expression in the usual fashion, by positioning the cursor after the expression and typing C-x C-e. (I'm doing this right here as I write this. This is one of the advantages of having the interpreter built into the computing environment.)
When we evaluate the variable animals, we see that it is bound to
the list (giraffe antelope tiger lion):
animals
=> (giraffe antelope tiger lion)
Put another way, the variable animals points to the list
(giraffe antelope tiger lion).
Next, evaluate the function setcar while passing it two
arguments, the variable animals and the quoted symbol
hippopotamus; this is done by writing the three element list
(setcar animals 'hippopotamus) and then evaluating it in the
usual fashion:
(setcar animals 'hippopotamus)
After evaluating this expression, evaluate the variable animals
again. You will see that the list of animals has changed:
animals
=> (hippopotamus antelope tiger lion)
The first element on the list, giraffe is changed to
hippopotamus.
So we can see that setcar did not add a new element to the list
as cons would have; it replaced giraffe with
hippopotamus; it changed the first element of the list.
setcdr
The setcdr function is similar to the setcar function,
except that the function changes the second and subsequent elements of a
list rather than the first element.
To see how this works, set the value of the variable to a list of domesticated animals by evaluating the following expression:
(setq domesticated-animals '(horse cow sheep goat))
If you now evaluate the list, you will be returned the list
(horse cow sheep goat):
domesticated-animals
=> (horse cow sheep goat)
Next, evaluate setcdr with two arguments, the name of the
variable which has a list as its value, and the list to which the
cdr of the first list will be set;
(setcdr domesticated-animals '(cat dog))
If you evaluate this expression, the list (cat dog) will appear
in the echo area. This is the value returned by the function. The
result we are interested in is the "side effect", which we can see by
evaluating the variable domesticated-animals:
domesticated-animals
=> (horse cat dog)
Indeed, the list is changed from (horse cow sheep goat) to
(horse cat dog). The cdr of the list is changed from
(cow sheep goat) to (cat dog).
Construct a list of four birds by evaluating several expressions with
cons. Find out what happens when you cons a list onto
itself. Replace the first element of the list of four birds with a
fish. Replace the rest of that list with a list of other fish.