CAR represent *right* subtree of a cons?

Question

I am reading "ANSI Common Lisp" by Paul Graham, in $3.8 (page 40) it goes:

"Conses can also be considered as binary trees, with the car representing the right subtree and the cdr representing the left."

To me it sounds like the "right" and "left" were used wrongly at opposite positions....then I took a look of the online errata but it's not one of the items listed there...

http://www.paulgraham.com/ancomliser.html

Can anyone help to clarify this?

Btw, on the next page (p41), Paul said that "Binary trees without interior nodes are not useful for much." I don't fully understand it either. what does it mean by "without interior nodes"? A deeply nested list can have as many internal/interior nodes (i.e., conses) as you want, why he said "without"? or probably he just meant that these interior nodes, if present, does not contain atom values?

Thanks, /bruin

Answer 1

In Lisp syntax, car is indeed the left half of a pair cdr the right half.

As for interior nodes, I suppose Graham means unlabeled interior nodes. E.g. you will much more often encounter trees like

(+ (* x y) z)

which should be thought of as trees built out of triples, even though implemented in terms of pairs, than trees of the form

((a . b) . (c . d))