# LEARNING LISP

## Lists, CAR and CDR

We are going to direct our attention towards the structure of data in the Lisp language. All expressions in Lisp are in the form of a list. Even functions that we will define in a later chapter will be in the form of a list. Lists are so important that the next several chapters will be devoted to developing your facility in using lists.

And now, meet the list.

A list is a linear arrangement of objects separated by blanks and surrounded by parentheses. The obkects which make up a list are either atoms or other lists. An atom is the basic unit of data understood by the Lisp language.

Here are some atoms.

```carbon
eve
1
bananastand
```
Here are some lists:
```(1 2 3 4)
((i hate) (peanut butter) (and jelly))
(you (walrus (hurt) the (one you) love))
(add 3 (mult 4 5))
(garbage (garbage) out)
(car ((in the garage) park))
(deeper and (deeper and (deeper and (deeper we went))))
```
Please note several things.
• Some of the atoms in the above lists are: "i", "()", "4", and "deeper". An atom is a word or number or the pair of parentheses "()" which will be referred to as "NIL".
• The parentheses in a list will always be balanced because every list is surrounded by a left and right parenthesis, and the only things inside which have parentheses are other lists.
• The definition given above permits us to nest lists within other lists to any arbitrary depth.
You should note that the parentheses are used to denote the list; they are not actually part of the list.

"you" is an atom.
"(walrus (hurt) the (one you) love)" is a list.

The parts of that list are

"walrus" is an atom.
"(hurt)" is a list with one element: the atom "hurt".
"the" is an atom.
"(one you)" is a list with the elements: "one" and "you", each of these is an atom.
"love" is an atom.

What does Lisp do with lists? Well, whenever you type a list into Lisp it tries to evaluate that list.

Rules for lists being evaluated:

• The first element of the list should be a Lisp function [like ADD].
• The rest of the list should be the arguments to the Lisp function, that is, it should contain the data to be acted upon.
Evaluation takes place if Lisp can apply the function to the arguments.

Thus,

```:(ADD 8 3)

11
```
is a list which is evaluated and has its value printed.

If the first element is not a Lisp function, then an error occurs:

```:(1 2 3 4)

** ERROR: BAD ATOMIC ARG **
EVAL :: NIL

+()

NIL
```
What if we try to add all the numbers in a list?
```:(ADD (1 2))

** ERROR: BAD ATOMIC ARG **
EVAL :: NIL

+()

NIL
```
Compare the expressions (ADD 1 2) and (ADD (1 2)). In the first one, the ADD function acts on two separate atoms [not a list--no surrounding parentheses] while in the second one ADD acts [or at least tries to act] on a list: (1 2). Remember that Lisp first evaluates the arguments before applying the function.

When Lisp encounters (ADD (1 2)), it first tries to evaluate the argument to ADD, namely the list (1 2). Note that "1" is not a Lisp function. [Remember, if Lisp is trying to evaluate a lista, the first element in the list had better be the name of a Lisp function and the rest of the list had better be the arguments to that function or else TROUBLE!!]

Here, again, NIL ["()"] is used to get back to the normal Lisp prompt ":".

We would like to be able to use lists like "(A B C)", to represent data in Lisp. Unfortunately Lisp seems to want to evaluate everything that we enter. Since there is likely no "A" function, the evaluation of the list will cause an error. This leaves us in a bit of a quagmire!

Good fortune has fallen upon you. There is a way to stop Lisp from trying to evaluate a list. The quote character ['] causes Lisp to take the expression as written rather than to try to evaluate it. We're going to begin applying the quote quite liberally from now on. Be very careful to watch what does and does not get evaluated.

```:'(DO NOT (EAT ANYTHING) NOW))

( DO NOT (EAT  ( ANYTHING ) NOW  ) )

:'(MULT (ADD 1 2) 4)

( MULT (ADD 1  2 ) 4 )
```
Let's introduce some Lisp functions which manipulate lists. Manipulating involves taking apart, putting together, and checking the values of lists. The two functions CAR and CDR are used to get parts out of lists. The CAR function returns the first element in a list.
```:(CAR '(1 2 3 4))

1

:(CAR '((I HATE) (PEANUT BUTTER) (AND JELLY)))

( I HATE )

:(CAR 1)

** ERROR: BAD ATOMIC ARG **
CAR :: (1       )

+()

NIL
```
Note that the result of a CAR need not be an atom [in the second case above, it is a list of two atoms], but that CAR is only designed to take arguments which are lists, not atoms.

CDR [pronounced "could-er"] is the complement of CAR in that the result of CDR is the "rest" of the list:

```:(CDR '(1 2 3 4))

( 2 3 4 )

:(CDR '(FUN FROG))

( FROG )

:(CDR '((THREE BLIND) MACE))

( MACE )

:(CDR '(HELLO))

NIL

:(CDR '())

NIL
```
Like CAR, CDR is defined only to operate on lists. Unlike CAR, however, the value of CDR is ALWAYS a list. Note that the CDR of a list with only one element is an empty list [written as () or NIL].

We have, in the previous pages, listed the following seemingly contradictory characteristics of NIL:

• NIL is an atom.
• NIL is a list (as a result of the CDR operation).
• NIL means "false" in predicates.
• NIL, by name, means "nothing."

NIL is certainly making a lot of trouble for such an empty concept. Why should we make so much ado about nothing? NIL is in fact the most important entity in the Lisp language. It is both an atom and a list, depending upon who is doing the asking. It can be returned by functions whose value is defined to be an atom, such as a predicate, or by functions whose value is defined to be a list, such as CDR. NIL is an empty list [a list with no elements]. The use of NIL will become clearer when we begin studying user defined functions in a later chapter.

Back to the business at hand: CAR and CDR.

We saw in the first chapter that subexpressions can be used in place of the arguments of any function. In the same way, the list processing functions can be combined to do various list operations.

```:(CDR '(SAND WITCH))

( WITCH )

:(CDR (CDR '(SAND WITCH)))

NIL

:(CDR (CDR (CDR '(SAND WITCH))))

NIL

:(CAR (CDR '(SAND WITCH)))

WITCH

:(CAR (CAR (CDR '(() ((BOZO) ( NO NO))))))

( BOZO )

:(CDR (CAR (CDR '(() ((BOZO)  (NO NO))))))

( (NO NO ) )

:(CAR (CAR (CDR (CAR (CDR '(() ((BOZO) (NO NO))))))))

NO

:(CDR (CAR '((CAR CDR) CAR)))

( CDR )

:(CAR '(ADD 1 2))

ADD

:(CDR '(ADD 1 2))

( 1 2 )
```
As we mentioned a little earlier in this chapter, the expressions that we are typing into Lisp are lists, just as "(1 2 3 4)" is a list. Remember functions and arguments? Well, the CAR of an expression-list is its function name and the CDR of that expression-list is the list of the arguments to that function!

There are standard abbreviations for up to four successive applications of CAR/CDR combinations: take the letter "A" from every CAR and "D" from every CDR and place them next to each other sandwiched between a "C" and an "R" [NOTE: Lisp aficionados claim to be able to pronounce all 28 combinations of CAR and CDR]. For example, the expression (CADDR ANYLIST) is the same as the longer expression (CAR (CDR (CDR ANYLIST))). This book will not use these too much, but you should be familiar with them since many things written in Lisp do use them. The above example

```:(cdr (car (cdr '() ((bozo) (no no))))))
```
could have been written
```:(CDADR ' (() ((BOZO) (NO NO))))

( (NO NO ) )
```

### Exercises: Car For Yourself

We still aren't deep enough into Lisp to do any entertaining or interesting exercises so your task is to make up some exercises for this chapter and do them.