The Origin of CAR and CDR in Lisp (2005) | Hacker News Reader

The Origin of CAR and CDR in Lisp (2005)

iwriteiam.nl

102 pointstosh95 comments

I've programmed a lot in various dialects of Lisp, and I like car and cdr. Using names like first and rest might make a language more attractive to new users, but there is something to be said for designing at least some languages for experienced users rather than new ones, and it doesn't take much experience (a week?) for the words car and cdr to mean the left and right halves of a cons cell to you. And once they do, they're better than first and rest, because

1. They're shorter.

2. They're the same length, which means in practice that a lot of code lines up in a way that's easier to read.

3. They look similar to one another, which telegraphs that they're part of the same set of list access tools. Code that munges lists looks like it munges lists.

4. Their meaning is precise: car just takes the first element of a list. Whereas something called first might reasonably be expected to also give you the first element of a vector, or a string.

5. When you're operating on lists as trees, the names first and rest are actively misleading. The car and cdr are the left and right subtrees, not the first and rest of something.

When you see car and cdr in code, it is usually a loud and clear signal that this module is doing something very concrete and explicit, with conses as a structuring material.

I agree. The argument against car/cdr reminds me of the adage 'in theory theory and practice are the same and in practice they're different'. car and cdr may have begun as a historical accident but they stuck around because they hold up in practice.

As other commenters have pointed out, we could add to your list the classical point that car and cadr are composable, so cadr, cdar, etc. This creates a simple DSL for list manipulation which sometimes is just what's needed.

> When you're operating on lists as trees, the names first and rest are actively misleading. The car and cdr are the left and right subtrees, not the first and rest of something.

If by trees you mean 2-ary trees, sure. For any other n, #'first and #'rest are probably the correct generalisation.

> Using names like first and rest might make a language more attractive to new users, but there is something to be said for designing at least some languages for experienced users rather than new ones, and it doesn't take much experience (a week?) for the words car and cdr to mean the left and right halves of a cons cell to you.

When designing Rust, we quickly learned that the idea of picking short names to satisfy experienced users at the cost of new ones doesn't work in practice. Too many users complain that the language is too hard to learn and ugly; it took years for "Rust is so ugly, it's the resurrection of Perl" to finally stop being a meme. If we had stuck to our guns with short keywords, Rust might have been dead by now.

Choosing unfamiliar syntax such as car and cdr worked for Lisp because, during the '70s, Lisp as a whole was novel enough to gain a sizable following. It doesn't work today. (And note that, even then, Lisp lost a lot of potential users due to the S-expression based syntax.) I'm firmly in the "first" and "rest" camp, because history has shown that readable languages much more frequently go on to be successful than languages with idiosyncratic syntactic choices.

> car and cdr worked for Lisp because, during the '70s, Lisp as a whole was novel enough to gain a sizable following. It doesn't work today. (And note that, even then, Lisp lost a lot of potential users due to the S-expression based syntax.) I'm firmly in the "first" and "rest" camp

first and rest are bad names for what car and cdr do, in the general case. If you have "Jenny" mapped to "867-5309" in a dictionary, then getting the "Jenny" part of that binding with first and the "867-5309" part with rest doesn't really make any sense. Similarly, if you have a node in a binary search tree, getting the subtree with the lesser elements with first and the subtree with the greater elements with rest also doesn't make any sense.

Lisp, even in the 70s, uses first and rest as synonyms for car and cdr for the case where you are operating on a list. first and rest do not make sense as replacements for car and cdr in the general case, however, and if all you want is to have them as synonyms for when they do make sense, then Lisp has been providing that since the 70s.

If you want precise names to offer as aliases to "first" and "rest", then I think ML-style "head" and "tail" are better names than "car" and "cdr".

Head and tail make more sense in ML because data gets the stream abstraction. The semantics of car/cdr make sense in the context of Von Neumann memory. It's no accident that car/cdr came from machine code...and that's what Lisp was mostly competing with.

I don't see how head and tail make less sense as names for generic elements of a pair than abbreviations derived from idiosyncrasies of a long-dead computer from the 1950s.

Sorry for not being clear. Specific terms make more or less sense depending on the context for which a language was designed. The ML family of languages comes out of telecom where the stream abstraction expresses a primary aspect of the principle input. Production versions of Lisp developed as a substitute for machine code. Even today, Common Lisp is useful for abstracting over operations best understood in terms of places where values mutate. Functional programming ideology aside, Common Lisp provides a good tool for "close to the metal thinking". It's not as close as C. It's closer than Java on top of the JVM.

In ML, head/tail are a bit of training wheels anyway. Most interesting ML code relies on [x1::x2::x3::[y::ys]] pattern matching. Erlang (another telecom language but without ML's academic pedigree) foregos a formal head/tail and just relies on idiomatic {H|T} pattern matching. In ML head/tail make it easier to teach students the concept of car/cdr, but not much else.

> If you want precise names to offer as aliases to "first" and "rest", then I think ML-style "head" and "tail" are better names than "car" and "cdr".

I don't know what you mean by ML-style, as most ML-derived languages call car and cdr fst and snd; I don't know any that call them head and tail.

But aside from that: really? I think of head and tail as being basically synonymous with first and rest (every language I know of that has built-in head and tail functions, or that idiomatically uses head and tail or abbreviations for variable names, uses them to mean the first element, and the list beyond that element. I don't know any that use them for two parts of a 2-tuple). The left child of a binary tree node being the head and the right side being the tail makes no sense at all to me. Not that car and cdr shouldn't be aliased when they're being used that way, but reading as "element a" and "element b" is better to me than "head" and "tail" which are equally meaningless, but by having English names imply meaning.

Lisp offers (since the 70s) the aliases first and rest for when conses are being used as lists, and I think those are fine and should be used when you are operating on lists. Conses can be used as other things than lists, though, and first/rest (or head/tail) don't work as meaningful names for any usecase aside from lists. Head/tail are totally equivalent to first/rest to me and I don't really care which pair is used for naming the list-handling functions, but they're both bad sets of names for the cons handling functions.

> first and rest do not make sense as replacements for car and cdr in the general case, however, and if all you want is to have them as synonyms for when they do make sense, then Lisp has been providing that since the 70s.

And were it so that one really felt that LISP were incomplete without `first` and `rest`, wouldn't it be trivial to wrap them in custom functions (ie alias them)?

Don't get me wrong, but of all the things that will make learning LISP a bit of work, adding a couple of utility functions isn't on the radar...

A sometimes overlooked feature of car and cdr is composibility, e.g. caadr, cddr, etc. Though I don't think it is useful to go ten deep as the spec requires if people are reading the code, deep composition may make some sense for machine written code.

Car and cdr also reflect a sometimes misunderstood aspect of Lisp: lists are an abstraction for sequential memory addresses in the Von Neumann architecture. The sense in which Lisp was designed for functional programming only goes about as far as one can pragmatically throw the lambda calculus. Practically and historically speaking Lisp programming was only slightly less about mutation than any other language. Design for current state of the art (in the 70's, 80's and 90's) is why Common Lisp has destructive versions of everything useful. Heck, Lisp even mutates its source code.

At the end of the work week, the major language design choice is not so much between car/cdr and first/rest it's between the language having a concept of first/rest and not having one: e.g. Python, Javscript, Go[?], C, and so on.

Finally, car/cdr is not that much worse than first/rest for all those programmers who are not fluent in English. Naming things is hard mostly because names are arbitrary. Both car/cdr and first/rest require the harder concept of fixed order data...and next makes more sense than first if one applies the stream abstraction.

> A sometimes overlooked feature of car and cdr is composibility, e.g. caadr, cddr, etc. Though I don't think it is useful to go ten deep as the spec requires if people are reading the code, deep composition may make some sense for machine written code.

The 90% case here is "second", "third", etc. For more exotic cases, surely there are other naming conventions that would be more readable. You could use "h" and "t" for head and tail, or "l" and "r" for left and right...

> At the end of the work week, the major language design choice is not so much between car/cdr and first/rest it's between the language having a concept of first/rest and not having one: e.g. Python, Javscript, Go[?], C, and so on.

The "concept of first/rest" is just the concept of pairs, which are a special case of tuples, which Python and JS certainly have.

Erlang uses a {H|T} pattern matching convention in lieu of language keywords. For what it is worth (limit x | x -> 0), I think Erlang is an exceptionally elegant piece of engineering as engineering. But it's not the 90% use case. Then again, neither is Lisp, ML, or Rust. The 90% use case these days is Javascript. Which I would hesitate to associate with the phrase "elegant piece of engineering" without an "in" prefix.

Python and Javascript may have pairs. They just live at the bottom of a Turing Tarpit.

I rarely used Python before the last few months, but I've already stumbled upon a great tragedy in the 3.x migration.

Although few know it, and fewer use it, Python 2.x allowed tuples to be unpacked in function heads, like Erlang. Since my last job was 100% Erlang, I stumbled into using it without knowing any better.

I decided a couple of months later that since it was a new project, I really should convert to Python 3, whereupon I discovered that feature had been removed due to parsing complexity and "because no one uses it."

Sigh.

This feature is still good to know about for use on legacy projects. Thanks for sharing!

With Python 2 due to be EOL'd in a couple of years, I'm not sure I should feel good about encouraging more use of it!

> The 90% case here is "second", "third", etc.

In addition to first and rest, Lisp has provided second, third, fourth, etc since the 70s, as well as the more general nth/elt which just takes the index as an argument.

> there are other naming conventions that would be more readable. You could use "h" and "t" for head and tail, or "l" and "r" for left and right

Why would you bother replacing names with 60 years of precedent with h and t so that instead of cdaddr you could write thtt? I think cdaddr nonsense is illegible and very bad style, but I don't see how someone could seriously suggest writing thtt as a good solution to that readability problem. The real solution is to use named accessors instead of ad-hoc pointer chains.

> The 90% case here is "second", "third", etc.

Unfortunately, those cases exhibit poor style if they are mixed with cddr. For instance, I would never write this:

  (when (and (consp (cdr x)) (consp (cddr x)))
    (do-something (third x)) ;; ouch!
    )

If we checked that cddr is a cons, we then want to access caddr (its car) or cdddr (its cdr).

Those first, second, rest and whatnot are really geared toward when the structure is a (proper!) list. If it really is just a proper list and we just want to be sure it has a third element, it would be more consistent to just do

   (when (>= (length x) 3)
     (do-something (third x))

Basically stick to one way or the other.

> It doesn't take much experience (a week?) for the words car and cdr to mean the left and right halves of a cons cell to you.

A long forgotten five minutes sometime in Y2000 in my case.

> They look similar to one another, which telegraphs that they're part of the same set of list access tools.

…and probably allows for more typos and misreads during code review or something else. Luckily 'a' is distinct enough from 'd' visually so the difference between them is more noticable; imagine functions ending up with unfortunate names like cbr/cdr or car/cer…

> 4. Their meaning is precise: car just takes the first element of a list. Whereas something called first might reasonably be expected to also give you the first element of a vector, or a string.

That may be true in LISP, but it's not true in Clojure (which I assume is a fair paragon for the first/rest camp), where first works just fine on strings and vectors:

  => (first "abc")
  \a
  => (first [1 2 3])
  1

> 5. When you're operating on lists as trees, the names first and rest are actively misleading. The car and cdr are the left and right subtrees, not the first and rest of something.

Firstly, trees can clearly branch out more than n=2. Then, nth becomes a much cleaner term than "left" and "right" which immediately limit you to 2 cases. But, let's say we're talking about n=2 trees. Consider:

  headmarc.core=> (second [1 2 3])
  2

And, of course, if that still seems unreasonable:

  (def left first)
  (def right second)

... but maybe what you really want is a zipper, which has everything you're asking for and more: https://clojure.github.io/clojure/clojure.zip-api.html#cloju...

TXR Lisp, a dialect with true conses:

  1> (car "abc")
  #\a
  2> (cdr "abc")
  "bc"
  3> (cddr "abc")
  "c"
  4> (cdddr "abc")
  nil
  5> (caddr "abc")
  #\c

I'm not sure if that's what you meant, but the point I was addressing was that "first" is bad because you could reasonably expect it to work on anything sequentialish not just on conses (agreed), and car/cdr is explicitly about conses (agreed). But first, in some Lisps, works just fine on everything sequentialish, including vectors and strings, so I don't consider that a particularly strong argument.

cl, cr I could live with, maybe. (consleft, consright). Other suggestions, head and tail, fst and snd, which have some of the other touted advantages. (I don't necessarily agree with them, but they also don't hurt, so...)

car and cdr is not necessarily about conses. I made them the basis for iterating over any list-like sequences in TXR Lisp. To participate in the protocol, an object can implement methods called cdr, car and nullify. This latter nullify should return nil if the object considers itself as representing "empty". Otherwise it can return the object itself, or possibly something else, like an ordinary list.

CAR and CDR can possibly work very well in Japanese, I have discovered:

https://www.reddit.com/r/lisp_ja/comments/78i4ws/

CAR -> karu -> 借る　(to borrow)

CDR -> kudaru -> 下る (to descend)

"Borrow" the first value/reference, or "descend" to the next cell.

The usual readings are カー/クダー (kaa/kudaa); these have to be altered to have a final ル (ru) rather than "aa".

The world isn't all English; someone's Anglo-centric quibble about how "cdr" doesn't mean anything means nothing to someone speaking another language.

By the way, descend starts with D:

C(Ante-, Ascend)R

C(Descend)R

I myself seem to be carrying the vestiges of a poorly articulated, subconscious connection to anno domini (A.D.).

"The world isn't all English"

But the history of computing largely is (not totally of course, but largely).

If we were discussing sushi, or katanas, or bushido, or netsuke, would you complain about the language being "Japanese-centric"?

If we were discussing grand opera (or, for that matter, having a technical discussion of almost any kind of music), would you complain about the language being "Italian-centric"?

> would you complain

I'm not complaining that programming languages use words based on English; my point is about English speakers having bikeshedding quibbles about those words that don't mean anything to non-English-speakers.

Suppose some Italian, due to some Italian reasons, doesn't like something about the music term dal segno or any other term. Why would I care, know what I mean.

Hmm... if you didn't care, why would you be reading the Italian quibble on a history site written in Italian?

I mean, this was quite clearly a page about the history of the terms, right?

You're turning a note about a happy coincidence into something very personal. Why?

> ... would you complain about the language being ..

I'm not sure there was a complaint there. To me, it read more like an interesting side note.

My favorite pair of silly LISP function names derived from CAR and CDR is RPLACA and RPLACD.

Then of course there's the whole family of derived function names CAAR, CADR, CDAR, CADADR, CADDDDR, CAAAAR, etc.

I wonder if that's what inspired Oliver Steele's "The Aargh Page":

http://osteele.com/words/aargh

http://blog.osteele.com/2005/12/aargh/

Even sillier is LOGO's alternative to CAR and CDR: FIRST and BUTFIRST. As in "BUTFIRST recursion" (giggle).

https://en.wikipedia.org/wiki/List_of_MicroWorlds_Logo_comma...

> Even sillier is LOGO's alternative to CAR and CDR: FIRST and BUTFIRST. As in "BUTFIRST recursion" (giggle).

Frosh-level CS classes may introduce linked lists as classes in some OO programming language -- often with the accessor methods getHead() and getTail(). Huh huh huh huh huh.

You'd think CAR and CDR, being abstruse acronyms steeped in technical language, would be immune from this sort of unfortunate double entendre, but no: my AI class professor had an Eastern European accent and pronounced CDR like "cooter".

> 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

Rich Hickey did not invent 'first' and 'rest'. LISP has those since the end of the 70s in language standards.

From Common Lisp the Language, published 1984, chapter on lists:

    [Function]
    first list 
    second list 
    third list 
    fourth list 
    fifth list 
    sixth list 
    seventh list 
    eighth list 
    ninth list 
    tenth list

    These functions are sometimes convenient for
    accessing particular elements of a list. first
    is the same as car, second is the same as cadr,
    third is the same as caddr, and so on.
    Note that the ordinal numbering used here is
    one-origin, as opposed to the zero-origin
    numbering used by nth:

    (fifth x) == (nth 4 x)

    setf may be used with each of these functions
    to store into the indicated position of a list.


    [Function]
    rest list

    rest means the same as cdr but mnemonically
    complements first. setf may be used with rest
    to replace the cdr of a list with a new value.

Lisp Machine Lisp had FIRST, SECOND, ... REST1, ..., REST4 at least in 1979. They are documented in the 2nd edition Lisp Machine manual.

Paraphrasing Mr Adams - “The story so far: In the beginning LISP was created, .... and then Guy wrote the Common LISP Bible. This made a lot of people very angry and been widely regarded as a bad move.” - or, Common Lisp - the LISP communities attempt at a non-proliferation treaty with itself. :-)

> > 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

> Rich Hickey did not invent 'first' and 'rest'.

Rather than the names 'car' and 'cdr', the "muck" that Rich Hickey jettisoned here was conses as a core language feature. Since Lisp already used first and rest for operating on lists, Clojure borrowed those names, and since Clojure doesn't have conses (in the Lisp sense of the term; Clojure has a cons function, but it just adds elements to sequences rather than constructing pairs), it didn't have any need for car and cdr, which operate on conses.

It reminds me of a section from Kent Pitman's article 'More Than Words, or: Lambda, the Ultimate Political Party':

> Some years ago, when I was first becoming involved with language standards, I did a personal study of languages in the Lisp family to determine whether there was a common core of operators that were present throughout the family with the same name and semantics.

Then after going through several basic operators which differ in behaviour or name across dialects, he concludes:

> I did find that CONS was present in every Lisp I looked at with pretty much the same meaning, but that seemed to be an isolated case

Those who do not understand the history of Clojure are doomed to assert Rich Hickey invented Common Lisp.

Too bad we couldn't just have "nth" and call it a day.

We do have it, it is called "elt" in Lisp.

> We do have it, it is called "elt" in Lisp.

In Common Lisp, ELT is generic over sequences, so it also works on arrays. CL also has a function actually called NTH which is specific to lists; NTH was also in Maclisp, Lisp Machine Lisp, etc with the same meaning (Interlisp had an NTH function but it's what Common Lisp calls NTHCDR (except that Interlisp NTH used 1-based indexing whereas CL NTHCDR uses 0-based)). Emacs Lisp uses the same nth/elt distinction as Common Lisp. Islisp has elt which is generic over sequences, but I believe that it discarded nth.

> Rich Hickey did not invent 'first' and 'rest'.

No one claimed Hickey invented first and rest, or even implied it. The point is not that first and rest didn't exist, but that car and cdr DID. Clojure deliberately left them out, as a design choice. For good or ill, that's the point.

> No one claimed Hickey invented first and rest, or even implied it.

I think that saying "This is why Clojure has first instead of car and rest instead of cdr" is a very odd way of saying "this is why Clojure doesn't have car and cdr" if you don't mean to imply that it added first and rest.

I also think the originally linked article was rather poorly written and seemed to put all of the focus on "car and cdr sure are weird names" without examining that they are operations on cons cells, which Clojure doesn't have. Clojure leaving out the names car and cdr doesn't really have anything to do with those names; it left out the data structure they operate on. A language without numbers proably wouldn't have a sqrt function either, but that has little to do with the clarity of the name sqrt.

Discussing the differences and tradeoffs between how Lisps and Schemes all represent lists compared to how Clojure does (and the tradeoffs with how Clojure makes up for the other things that conses are used for in Lisp) might have made for a more interesting point, but it would have been a harder one to make than just pointing at two not immediately obvious symbol names (without even mentioning that it did keep the equally archaic and unhelpful name "cons" but changed its behaviour).

> but that car and cdr DID. Clojure deliberately left them out, as a design choice.

Clojure doesn't have the concept of Lisp's linked lists, thus it does not have its operators.

Note that where the link now points to is something different. Originally this was the link: http://www.howardism.org/Technical/Clojure/origin-of-car-and...

> Clojure deliberately left them out, as a design choice.

I don't think they were 'left out'. That's not how Clojure was designed, IIRC. Clojure is not first Lisp minus the arcane names, plus second then the new stuff. It's a new language from start, not Lisp with names left out. Hickey did not start with Lisp and redesigned it. He started with a new language, based on ideas like immutable persistent lazy sequences, host language integration with easy interoperation, some Lisp ideas like s-expressions and macros, ... I don't think he thought, 'I leave CAR and CDR out'. There was no place for them, since he designed the language Clojure around different data structure concepts.

I use FST and RST (for FIRST and REST). I like them because they are short, mnemonic, and can be composed like CAR and CDR, e.g. CADADDR = FRFRRST (though I also believe that if you find yourself doing this you're almost certainly doing something wrong).

I think I prefer this as well. I think the importance of the mnemonic aspect can’t be overstated.. even though I did get _used_ to CAR and CDR, I feel like I was never immediately able to comprehend code that used them.. I had to always perform a mental translation as if I were somewhat bad at French or something and didn’t intuitively know the words.

It’s the same thing when I see test code that uses foo, bar, and baz as variables / strings instead of something more memorable like apple, banana, and cherry (or preferably something even more relevant to the code being tested). I feel like I have to work harder to understand what the tests are actually testing when I don’t have a good mental association with the variables under test. I get that it’s something programmers just do, but I’m really not a fan.

Maybe I’m an odd one though.

Another possibility is LHS and RHS for Left Hand Side and Right Hand Side (if you want to emphasize the use of a cons cell as a pair rather than a linked list).

    Date: 5 March 1980 08:54-EST
    From: Mark L. Miller <MILLER at MIT-AI>
    To:   Dave.Touretzky at CMU-10A, RWK
    cc:   KMP, HIC, BUG-LISP
    Re:   CAR and CDR
    
    Of course, you could rename them to, e.g., "LHS" and "RHS" for "Left Hand
    Side" and "Right Hand Side".  This would address the composition argument
    in favor of CAR and CDR: CADR -> LRHS (left-hand-side of right-hand-side),
    CDADADR -> RLRLRHS, and so on.   It's easy to provide these as macros.
    
    Later, you can explain that the original names are CAR and CDR, and isn't
    that silly, etc.
         Regards, Mark

Shows you how resilient car and cdr have been against decades of complaining and bikeshedding. That just reaffirms them.

I would accept that if Lisp were a runaway success, but it's not. It is very nearly a dead language [1]. It is entirely possible that the unwillingness of the Lisp community to give up in this obscure terminology in favor of something more user friendly contributed to its demise.

[1] Look at e.g. https://madnight.github.io/githut/. The most popular Lisp is Clojure, with a whopping 0.33% market share. Scheme and Common Lisp don't even make it to the top 50.

CL was #45 in the car quarter of 2017; by cadr, it slipped into the long(er) tail.

> It is entirely possible that the unwillingness of the Lisp community to give up in this obscure terminology in favor of something more user friendly contributed to its demise.

What more-user-friendly terminology do you suggest?

Did you not read the upstream comments? FST and RST, or LHS and RHS depending on whether the intent is to access the cons as a linked list or a pair.

The D in CDR already corresponds to "dexter-" (right); we just need "L" for "levo-":

CLR: cell levo/left reference.

CDR: cell dexter reference.

Organic chemistry uses these letters and prefixes. E.g. "L-glutamine", "D-glucose" (a.k.a "dextrose").

The H and S (hand side) don't really contribute anything. (Yes, left is side and a hand).

The whole point of this exercise (if it has a point at all) is not to come up with acronyms with justifiable expansions, but to come up with something that is less newbie-bostile. I'm not sure CLR/CDR fits the bill any better than CAR/CDR. Part of the problem with CAR/CDR is that CAR is an English word that means automobile, and people get a little hung up on that when they first see it. Likewise, CLR is usually a shortened form of the word "clear". So I'm not sure that CLR/CDR is any better than CAR/CDR. One of the advantages of LHS/RHS and FST/RST is that none of those trigrams have any semantic baggage associated with them other than their intended meaning.

Why trigrams: (cl x) (cr x). cell left, cell right.

I don't think car and cdr are newbie hostile; they are rather troll-fertile.

You're not the first person I've heard of that doesn't like foo,bar,baz nonce variable names. But it's the first I've heard of someone preferring meaningful but irrelevant words over meaningless words.

In any case, I think it makes sense, even if it's not common within programming culture.

You'd have to really sneak this under the cadar if I were reviewing code.

The LISP people should have changed those names way back when. Not 79, 59. McCarthy himself said then that this representation is independent of the IBM 704 computer, or of any other electronic computer [1]. So why stick with the names of 704 registers? Was there a purpose to this?

[1] https://courses.engr.illinois.edu/cs421/sp2012/project/mccar...

Lisp has both CAR/CDR and FIRST/REST.

It's usual programming style to use CAR/CDR when working with CONS trees/graphs and FIRST/REST when working with lists.

OK, but isn't CalChris's point still valid? Something other than CAR/CDR would have been a better choice for working with CONS cells, even back in 1959.

Do I think it's a big problem? Not really. Are the names less than optimal? Yes.

> Something other than CAR/CDR would have been a better choice for working with CONS cells, even back in 1959.

> Are the names less than optimal? Yes.

I don't think that's self-evident. The only better alternatives I've ever heard suggested are something like left and right, which I think are probably slightly clearer names for what the functions do, but not significantly so (I don't think "a cons is a thing with a left and right side" is that much more intuitive than "a cons is a thing with two parts called a car and a cdr").

Further, I think in 1959 when most everyone using Lisp was hacking on the implementation itself, names that are mnemonic for what the machine they were actually using is actually doing make sense; I don't think they're clearly sub-optimal now, but I think they were even less so in 1959.

I assert that naming the interface for the implementation is almost always the wrong thing to do.

(And then you ask me what would be a better name, and I don't have a perfect answer. "left" and "right" are the best I know of...)

> I assert that naming the interface for the implementation is almost always the wrong thing to do.

I think it's perfectly acceptable if there aren't really any better names for the abstraction you're creating. car and cdr work just fine as made-up arbitrary names for an abstraction that doesn't really have any more natural names for them; the fact that 60 years ago they weren't actually entirely arbitrary doesn't really change that.

These names were very well thought out. They were part of a larger vocabulary in fact; most of that vocabulary died out and only car and cdr remained. There were things like cwr, ctr and others. MacCarthy and gang were well aware (of all people!) that the language is machine-independent and not something that will be forever stuck to the particular IBM machine; they used these names anyway because there was nothing wrong with them.

By the way, the C and R are not machine specific; any machine can have a "register" and any register can have "contents". On any machine where we implement cons cells, we can just call the two fields registers, understood as being A and D.

These, in turn, can be "ante" and "de", if someone desperately needs mnemonics:

https://en.wiktionary.org/wiki/ante

https://www.etymonline.com/word/de-

"active word-forming element in English and in many words inherited from French and Latin, from Latin de "down, down from, from, off; concerning."

In addition to car and cdr, there were cpr (Contents of the Prefix part of Register) and ctr (Contents of the Tag part of Register).

> By the way, the C and R are not machine specific; any machine can have a "register"

Slight nitpick: the first machine on which I had a decent Lisp to use (Portable Standard Lisp) was a Burroughs 6800, a stack machine with no general purpose registers, or indeed any registers directly accessible by the programmer.

Vi has "registers" and so do TeX and troff. I think once upon a time, it was more common to use the word for things beside CPU registers and I/O ports.

If a cons cell is a context with two registers (R) whose contents we can access (C), the only vestiges of that IBM machine are the A and D letters sandwiched in between to distinguish them.

Compared to how option letters change meaning between Unix commands, it's nothing. -h help? Nope, h)uman readable sizes.

^ to anchor regex at beginning; $ for end. Because on common keyboards, ^ is on the right, and $ on the left!

> So why stick with the names of 704 registers? Was there a purpose to this?

Are there other, much better names for the two parts of a pair? First and second aren't great because they're not clear that it's a pair and not a larger sequence (and the difference is important in Lisp; since lists are built on conses, it would be odd to get the tail of a list by calling 'second'). The only other names I can think of would be something like left and right, but I don't think those would be substantially easier to understand for beginners than car and cdr.

When working with lists, many people prefer to use the functions first and rest, which behave identically to car and cdr but are more meaningfully named for list applications. They would be terrible names for the general cons-handling functions, though.

Would it be silly to use 'head' and 'tail' then?

I learned car/cdr in school so that's what I use.

Left and Right are really commonly used in this situation in ML-descended languages. It’s not the worst thing.

I don’t mind car and cdr though. I kind of wish they were in Clojure tbh. It feels nice to pay tribute to a half-century of computing history.

> Left and Right are really commonly used in this situation in ML-descended languages. It’s not the worst thing.

Are you talking about Either types? OCaml and Haskell at least both call car and cdr fst and snd respectively, but they're rarely used.

As for left and right as names, I don't think they're any worse than car and cdr, I just don't think they're substantially better.

In C++, I often use LHS and RHS (left hand side / right hand side). I know other people who like fst, eat (first, rest). Both seem better to me, as they have some meaning other than random made up strings (for people who don't use 704).

> Both seem better to me, as they have some meaning other than random made up strings (for people who don't use 704).

Calling the lefthand child of a node in a binary tree the "first" and the righthand child the "rest" seems like a markedly worse naming system than random made-up names, to me, because the use of English names seems to be implying meaning that it doesn't really offer.

The idea of a thing with two values, one on the left side and one on the right side is probably a bit more intuitive, but I really doubt it's that much moreso than just saying it has two parts called the car and the cdr. People who've never touched a 704 have been learning about conses as a data structure with two parts, a car and a cdr, for almost 60 years; to most of them, it's just vocabulary you learn now, the same way that numerator and denominator are just arbitrary names to people learning fractions.

I also think it's interesting how much people complain about car and cdr yet it's very rare that people complain about cons, which is just as badly named. It should probably have been called make-pair or something, which I think is a much bigger improvement than car vs lhs. But really, it's 3 words of vocabulary, whose definitions can be completely understood by

    (car (cons x y)) = x
    (cdr (cons x y)) = y

That's not very much to ask someone to wrap their head around, it was meaningful to the original implementors, and for people now there's about 60 years of precedent for using that terminology.

I feel the better question, and I don't know the answer, is does this kind of thing stop people taking up lisp. Honestly I think it does, for so many languages, the first view, the first 15 minutes of reading, and the first 10 hours are super important, that is when you lose many possible users. It is certainly the points where I often drop languages.

While lisp is old, it's never picked up many users. This is the kind of little thing which makes me not want to teach it (not just this, but just lots of little ways it seems stuck in history).

I think that's more attributable to the fact that for most people, their first 10 hours with Lisp are spent writing recursive functions that explicitly cdr down lists, rather than the names car and cdr. I think it would make a much bigger difference if more people's first exposure to Lisp was something like:

    (with-open-file (input "foo.txt")
      (loop for line = (read-line input nil)
            while line
            do (write-line line)))

But instead most schools only use Lisp as a vehicle for teaching the basics of recursion and functional programming, rather than as an immediately useful tool, so most students go away with the idea that that's what Lisp is used for, and attribute their difficulty understanding The Little Schemer to difficulty understanding Lisp.

>But instead most schools only use Lisp as a vehicle for teaching the basics of recursion and functional programming, rather than as an immediately useful tool, so most students go away

This was my experience too. In university, Lisp seemed like an awkward, limited language for doing some CS algorithms. So i totally overlooked it.

Fast forward 12 years later, reading in depth about Common Lisp and using it as a general purpose programming language, it's totally awesome.

Wanting to optimize my path through school, I asked some senior people if that programming languages course based on Scheme was useful. I was informed that it's a toy language based on Lisp for teaching. I correctly assumed that this is something other than the real Lisp, a legendary language which can't be a toy. It being a university for grown up children and all, I didn't want to have anything to do with toys. The course was a prerequisite for a senior level compiler course, but I talked the prof into letting me skip the prerequisite and go straight to that compiler course.

Man, I sure dodged a bullet there. Some decade later, I got into Lisp in a big way (the real one); the rest is history.

Nothing that was based on garbage collection picked up a lot of users before 1999 or so.

Basically when the world "rebooted" into garbage collected, managed languages, it was amid a sort of Lisp amnesia. A lot of that was due to new people who had no such memory to recall.

Prior to this general movement, there were severe barriers in place against anything memory-managed.

And anyway, even if everyone who had already been programming in 1980 switched to Lisp today, it would be a drop in the bucket.

I think the original Lisp people didn't persevere enough. They peaked early. By the time Java and whatnot came around, the presence wasn't there.

Url changed from http://www.howardism.org/Technical/Clojure/origin-of-car-and..., which points to this, which is far more informative.

The link in that previous article is a little weird, since the text says "lost in the mists of time". That of course isn't true; if you read through to Steve Russell's explanation the mists clear up quickly.

>When Rich Hickey invented Clojure, he kept the gems of the LISP tradition, but jettison much of the muck.

That's the myth that Hickey loves to pass around, but is a totally baseless claim.

>This is why Clojure has first instead of car and rest instead of cdr.

Just as Common Lisp also has "first" and "rest" if one feels like using them instead of "car" and "cdr".

These days `first` and `rest` is used in Racket to indicate the input is a list. Since `cons` can build non-lists, the traditional `car` and `cdr` are used when working on trees.

Well - actually most Racket programmers use pattern matching when working on trees.

Note that `first` throws an error in modern Racket when used on a non-list.

As noted earlier, the names first and rest date from the 70s and were already around in Lisp Machine Lisp. Also, to nitpick: in Racket, first (car) will sometimes throw when used on lists, too, if the list happens to be the empty list (which has been true for decades in Scheme). It's more correct to say that it throws when used on non-pairs/conses (aka atoms).

Get best conversion services at one place. We convert your designed PSDs to HTML, HTML5, WordPress, WooCommerce, Magento, BuddyPress Themes. All our code is hand-written, W3C Validated, Google Page-Load Optimized, Cross-Browser, Clean & Commented. Details Here: http://www.thehtmlcoder.com/

TXR is a new Lisp dialect (project started in 2009) with real conses, car and cdr. Plus some little embellishments in that area:

  This is the TXR Lisp interactive listener of TXR 188.
  Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet.
  1> (defstruct kar nil
       kar kdr
       (:method car (me) me.kar)
       (:method cdr (me) me.kdr))
  #<struct-type kar>
  2> (new kar kar 1 kdr 2)
  #S(kar kar 1 kdr 2)
  3> (car *2)
  1
  4> (cdr *2)
  2

TXR Lisp has the cadr accessors down to depth five (caar to cddddr).

This stuff is not "muck" to be jettisoned; it is part of the essence without which we don't have Lisp.

For nonenglish speaker KAR and KUDER were of course as good as any other foreign symbols. First derivatives were KA-AR, KADER and KUD-DER (for CAAR, CADR and CDDR).

TIL that the guy who invented these names, Steve Russell, was the guy who 9 years later mentored Bill Gates and Paul Allen on the PDP-10. History's cool.

That is cool, but I was wondering if you had a citation for Steve Russell coining the names? I don't believe that's true.

Scroll down on the parent. He talks about the 704 instructions and not having a better idea at the time.

Oh, sorry, the linked story used to be different. I hadn't noticed it was changed.

i don't like first/rest; car and cdr are about pairs, not about lists which is an implicit type (like strings in C).

Contents of Address Register and Contents of Decriment Register.

Two instructions on the original IBM that the first LISP imterpreter was written on.

I heard.

Why don't you read the linked text to learn that you're wrong? There is no address register and no decrement register on the IBM 704, and no instructions CAR and CDR either. An instruction had an address part and a decrement part. The LISP functions CAR and CDR return the the address part and decrement part of a given register and both were implemented with more than one machine instruction.

I stand corrrected. Thanks.

So why did I remember it the that way?

It must be part of history somehow, I didn't make it up.

Reply on news.ycombinator.com