www.howardism.org
Babblings of an aging geek in love with the Absurd, his family, and his own hubris.... oh, and Lisp.

The Background for CAR and CDR

cars…cdr…cons…mcar…mcdr…mcons…sigh….

im not feeling enlightened

Hey Mike, I feel for you. Learning something new that has a long and rich evolutionary history is usually much more frustrating than a premeditated project. Had a friend from Italy who often complained at learning English and its lack of rules.

On Hoods and Caps

The English language has more than its share of oddities and inconsistencies. Did you know the words cap and hood derive from the same word but through different language families?

The original word, kaput came mostly unchanged into Latin (caput). This is where we get words like capital (head city) and cap as a head covering (originally, capuchon, which came through French with the Norman Invaders in 1066).

That same kaput word, however, changed when it went through the German consonant shift (based on Grimm’s Law) where kh, pf and td, so kaput became heafod in Anglo-Saxon’s influence on Old English (pronounced, I believe, as hefood). The f was dropped and we get head and words like hood as a head covering.

This is also why beheading and decapitation mean the same thing.

My point here is that even when we notice inconsistencies, oddities, and redundancies that make rules impossible, we can’t do much about such traditions. Esperanto is a nice idea, but it will hardly collect the mind-share currently enjoyed by English. However, English with all its quirks, allows this miraculous ability to allow me to communicate with you through time and space.

Assembly Language and the Need for TLAs

Of course, like an old city, an old house, or an old code base, projects that began as conscious design decisions, tend to look more haphazard and evolutionary with time.

Early CPU chips could interpret the number 42 as either a number or an instruction. To ease our minds, we created assembly languages with three-letter mnemonics to refer to these number codes. The assembly language for the 6502 Processor (with which I cut my teeth), LDY was 0xA4 and told the CPU to put the next number into the Y register.

Why only three-letters? I really don’t know, with limitations on space (on both screen and punch cards), inabilities of programmers to use a keyboard, and an engineering love for succinctness, the jump instruction was often JMP.

And Now I Get Back to Lisp

Even though, high-level languages are better at communicating with both the computer and other human readers, some of these machine codes crept in.

For instance, the backbone of Lisp was a very efficient implementation of the list data structure.1 Building and breaking lists are important, but naming things are hard.

Although the exact origins of the names for car and cdr are lost in the mists of time, both probably came from early assembly language codes. CAR stood for contents of address part of a register, and CDR stood for contents of the decrement part of a register. The early lisp was more like a macro system on top of assembly code, but while it changed, these TLAs easily explained their purpose to people who knew the old instructions.

Whew. This is why a twenty-first century language, like Racket, uses archaic, un-helpful fifty year old terms. While Matthew Flatt and team could have changed these terms, they were keeping with a long tradition.

Clojure both Keeps and Breaks Tradition

When Rich Hickey invented Clojure, he kept the gems of the LISP tradition, but jettison much of the muck. This is why Clojure has first instead of car and rest instead of cdr. I really appreciate these changes whenever I program my faithful dog, Emacs.

Sometimes when you build on tradition, you can improve it.

Footnotes:

1

A list is more than just a collection of things, like an array. Technically, a list is a singly-linked list of pairs, where the left-part of the pair holds a value, and right-part of the pair point to next pair in list.

This looks something like this:

origin-of-car-and-cdr.png

Isn’t that pedantically peeking at the implementation? This structure matters. Back in the twentieth century, our computers didn’t have a lot of memory, and this structure is the most memory efficient of the dynamic structures…as you could easily add or remove from the top of the list by simply creating a single new pair:

origin-of-car-and-cdr2.png

So the list and its myriad supporting functions, became fundamental for Lisp. However, this feature of changing a list (from the front only) without actually changing the list, became the inspiration for the immutable function collection in Clojure.

For instance, if one thread referred to our original list as, A, another thread could modify this list as B, without locking or other issues:

origin-of-car-and-cdr3.png

Now that you get what I mean by “list”, click the shiny number 1 to go back to the essay already in progress.