Common Lisp quote behavior with car and cdr

Question

Beginner with Lisp. I'm working through "Common Lisp: A gentle introduction" and I ran into this behavior that I don't understand. This is in clisp:

[57]> (cdar '((fee fi) '(fo fum)))
(FI)
[58]> (cdar '('(fee fi) '(fo fum)))
((FEE FI))

The first expression (line 57) makes sense to me. It's getting the CDR of the CAR of ((fee fi) (fo fum)), ie the CDR of (fee fi). But what's going in on line 58? I would have expected it to give me the exact same thing, (FI). But instead it gave me a list of a list? Can anyone help me understand what's going on?

Even more surprising, if I do each of these in two expressions, I get an error when the (fee fi) is unquoted:

[72]> (car '((fee fi) '(fo fum)))
(FEE FI)
[73]> (cdr (FEE FI))

*** - EVAL: undefined function FEE

But I get the right result when (fee fi) is quoted, an inversion of my first result:

[77]> (car '('(fee fi) '(fo fum)))
'(FEE FI)
[78]> (cdr '(FEE FI))
(FI)

Any illumination would be greatly appreciated!

Answer 1

The ' character is just an abbreviation: 'something is expanded at read time to (quote something). Therefore:

(cdar '('(fee fi) '(fo fum)))

is actually:

(cdar (quote ((quote (fee fi)) (quote (fo fum)))))

The first quote prevents evaluation of its contents, so the rest of them are just literal lists and symbols, so a more useful representation would be:

(cdar '((quote (fee fi)) (quote (fo fum))))

The CAR is then (quote (fee fi)), and the CDR of that is ((fee fi)).

Answer 2

Before something can be evaluated by a Lisp, it must be read in first. Read operation takes a textual representation of some datum and turns it into a Lisp datum.

[6]> (read)
'a                    ; I typed this
'A                    ; CLISP responded
[7]> (type-of *)      ; * is previous-value
CONS
[8]> (mapcar #'print **) ; ** is value before previous value

QUOTE                 ; first element of the list (code form), (QUOTE A)
A                     ; second element of the list
'A                    ; CLISP translates (QUOTE A) back into 'A, for show

So ' ... is turned into (quote ...), on read. How does this work?

[4]> (get-macro-character #\')
#<SYSTEM-FUNCTION SYSTEM::QUOTE-READER> ;
NIL

So there is something there behind the quote. A quote-reader system function. Lists are also something special:

[5]> (get-macro-character #\()
#<SYSTEM-FUNCTION SYSTEM::LPAR-READER> ;
NIL

When all is read, the result is then evaluated. That's the "read-eval" part of the "read-eval-print loop", the REPL. The result of evaluating a quote form, (quote ...), is whatever is inside it. IOW the top quote disappears, but all the inner quotes remain.

Without the quote, everything is evaluated. So to evaluate (cdr (FEE FI)), the form (FEE FI) must be evaluated, and if it results in a list, that list's cdr will be returned.

---

You could try to define another way of representing literal data, say with [ ... ] brackets standing for (quote ( ... )). The conversion could treat the inner brackets as simple parentheses. Then both

> (cdar [(fee fi) (fo fum)])
> (cdar [[fee fi] [fo fum]])

would behave the same, as you expected.

PS. CLHS is your friend.

---

edit: here's where you've erred. In your last example,

[77]> (car '('(fee fi) '(fo fum)))
'(FEE FI)
[78]> (cdr '(FEE FI))
(FI)

the last call should have been

[1]> (cdr (quote '(FEE FI)))
((FEE FI))

Putting '(FEE FI) inside the quote form prevents its evaluation, so it is passed as is to cdr. Here's how we can be sure about this:

[2]> (car '('(fee fi) '(fo fum)))
'(FEE FI)
[3]> (cdr *)     ; * is the last returned value
((FEE FI))

(cdr (car ...)) really is cdar, no question about it.