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

The Origin of CAR and CDR in Lisp (2005)

iwriteiam.nl

84 pointstosh40 comments

To cut to the chase and save reading though all the unnecessary speculation, this is the relevant part of this article...

>"The 704 family (704, 709, 7090) had "Address" and "Decrement" fields that were 15 bits long in some of the looping instructions. There were also special load and store instructions that moved these 15-bit addresses between memory and the index regiseters ( 3 on the 704, 7 on the others )

We had devised a representation for list structure that took advantage of these instructions.

Because of an unfortunate temporary lapse of inspiration, we couldn't think of any other names for the 2 pointers in a list node than "address" and "decrement", so we called the functions CAR for "Contents of Address of Register" and CDR for "Contents of Decrement of Register".

After several months and giving a few classes in LISP, we realized that "first" and "rest" were better names, and we (John McCarthy, I and some of the rest of the AI Project) tried to get people to use them instead.

Alas, it was too late! We couldn't make it stick at all. So we have CAR and CDR."

Well, after all we've always used CAR and CDR! If it was good enough then, why shouldn't it be good enough now?

Also, the proposed new keywords were on average 50% longer. Just too much typing! With FST and RST they would have stood a chance. HD and TL would have been clear winners!

And fst and rst allow for composition too:

    caar -> ffst
    cddar -> rrfst

But that doesn't look as nice.

It would need to have a pronunciation convention before it could catch on.

https://people.eecs.berkeley.edu/~bh/pronounce.scm

Instead of (f)irst/(r)est we could use (h)ead _or_ (f)irst and (r)est. Then the pronunciation is just exactly as it is spelled - https://www.youtube.com/watch?v=spefM2OjKp4

I am disproportionally moved by this elegance.

That's right, but I would go one step further and have F(irst) and R(est), with obvious composition as follows: (using kruhft's examples from another thread)

    (ff  x) == (caar  x) == (car (car x))
    (rrf x) == (cddar x) == (cdr (cdr (car x)))

I would argue that it's worth sacrificing the 'f' and 'r' symbols for such a common construct.

If not, a common prefix (lacking in HD and TL) could be used:

    (.ff  x) == (caar  x) == (car (car x))
    (.rrf x) == (cddar x) == (cdr (cdr (car x)))

Yes, I realize I'm 55 years late to the party.

Steve Russell wrote that. In case people don't know, he also co-wrote 'Spacewar!', one of the first video games. According to Wikipedia he also invented continuations and mentored Bill Gates and Paul Allen while they were teenagers: https://en.wikipedia.org/wiki/Steve_Russell_(computer_scient...

Didn't know the person who wrote the first Lisp compiler also wrote Spacewar!, two impressive achievements!

However, whilst I respect it's open for interpretation, I would say the first video game was Tennis for Two.

https://en.m.wikipedia.org/wiki/Tennis_for_Two

There's also OXO, which predates both Spacewar! and Tennis for Two:

https://en.m.wikipedia.org/wiki/OXO

Good point! I edited my comment to say "one of".

Yeah, certainly one of the first, I'd agree with that. First I'd ever heard about it was in the documentary Thumb Candy, at the beginning Steve Russell gives an introduction to Spacewar!, which is quite fun to see:

http://youtu.be/UAo4CZTGFQQ

Digging around, I found even more early examples of computer-based games that appear to have been largely overlooked, I certainly don't remember hearing about them before, seems like the first video games may have emerged in the early 50s (between 1950 to 1951, depending on whether it needed to be on a general purpose computer):

https://videogamehistorian.wordpress.com/2014/01/

One interesting thing here is that the attempt to get people to stop using the 'bad' names car and cdr is only a few months younger than car and cdr themselves. This is analogous to the plan (which lasted a few years) to replace s-expressions with m-expressions. In both cases the 'bad' construct stuck around because it's easier to program with.

I think people might still start new s-expression based languages, whereas any respectable new language will use head/tail rather than car/cdr.

First and rest make more sense if you're only going one level down, true. Long-term Lisp fans will argue that the composability shorthand of caddar, cddddr, cadadar, etc. is just too useful to give up.

I think needing to use such operators is already indicative of inadequate tools to express structure.

And if I did need to use something as complex as `cadadar` frequently for some reason, I'd much rather give it a name (and a type) that expresses what I'm actually doing with it.

Well, the point is not that you use cadadar all the time as such, but that you also use cdddar, caadr, and so on, and that having these shorthand forms available means that you don't have to define a whole bunch of one-off functions.

I think saying you can use `cadadar` to operate on a data structure instead of defining an accessor is like saying you can use pointer arithmetic to work with data structures in C instead of using structs.

EDIT: And as other people have mentioned, most serious lisps already have proper tools for building data-structures, so I'm inclined to think that if you're using `cadadar` you're probably doing something wrong.

"I'm inclined to think that if you're using `cadadar` you're probably doing something wrong."

That's nice. I'm inclined to think that you haven't written very much Lisp code.

I don't know about respectable, but I prefer car/cdr even in a new Lisp. In addition to the composability of the notation, which others have cited, there's the clear lexical symmetry between the two; their compactness, which adds value when writing and reading concise programs; and how easy they are to say out loud. There's something also about their precision: when you say 'car' or 'cdr' in a Lisp context it's immediately clear that there's a linked list at hand and you're talking about it.

The main disadvantage is that they're words with no immediate connection to their meaning, but that's true of many words we're all familiar with. It really only costs anything in the learning stage—which admittedly is a critically important stage. But I think it's fair for a programming language to use specialized idioms for a small number of their most fundamental constructs.

CAR and CDR are also good names because they are part of the Lisp tradition. Also due to this tradition, they have a clear meaning in the context of Lisp. If the "new Lisp" keeps conses (and some may argue that if it doesn't, it shouldn't really fall under "a Lisp"...), perhaps it should also keep these names.

Conses are arbitrary pairs, not necessarily lists. car and cdr are what eg OCaml and Haskell call fst and snd.

When I made my own Schemes back in the 90s, I included the ca/dr primitives, because yes, they were handy -- but coming back to this recently I didn't bother, because I built in pattern matching instead. I imagine that'll finally kill off the caaddars in most new Lisps.

What did you do recently?

To add to that question ... how did you use pattern matching to replace the composability of car/cdr?

My new Lisp dialect is https://github.com/darius/squeam (and as it says, I'm not wishing it on anyone else).

Pattern matching would replace a call like cadar with a pattern like ((_ x @_) @_). Using cadar is sort of like point-free style in Haskell: they both invite you to mentally run a chain of operations to understand the meaning, in contrast to patterns and expressions with named variables, which are more like a picture of the input and output.

Of course pattern matching goes way back, but I used to think of it as less settled -- people might want to extend the kernel language with pattern matching in many different ways. Now I'd be more surprised by a new Lisp without some sensible default; plus if it is absent, you can add it in under a page of code, like http://okmij.org/ftp/Scheme/macros.html#match-case-simple

Thank you for sharing your work. I could see some good use out of it.

I hope it does become useful, thanks! So far it's more of a hobby.

Think of them as tools or symbols, like Sigma or Pi. Make peace and move on.

car and cdr may not be the best names, but they allowed for composition, like:

    (caar x) == (car (car x))
    (cddar x) == (cdr (cdr (car (x)))

Something which you can't do with first and rest. This has (AFAIK) always been one of the arguments for car and cdr.

I dunno, as a latecomer lisp-enthusiast, that cadaddaaadr stuff seems heinous to me.

I've grown to like it, and implemented it in TXR Lisp one level deeper than CL, all the way to cddddr.

http://www.nongnu.org/txr/txr-manpage.html#N-03E5CED9

The code for them is generated textually: http://www.kylheku.com/cgit/txr/tree/gencadr.txr

It's not pretty, but it has a consistency to it that includes a lot of compact information in a digestable manner. It takes no longer to decode what the instructions say, but it saves a lot of time parsing, for the human reader of the program.

Compare:

    (caadar x) => (car (car (car (cdr (car x)))))

Saves parens too.

You can make it even easier on human readers by defining accessors (even if they're just wrappers over car/cdr) and giving them meaningful names. Asking for the car of the car of the cdr of the car of an ad-hoc data structure is pretty hostile toward human readers regardless of whether or not you use caadar.

That's why you actually won't find many instances of such patterns in practice. Either you refactor to have structures/classes, or you define your own accessors. Besides, if you are using CL, FIRST, SECOND, THIRD, ... , TENTH, NTH and REST are defined by the spec (http://clhs.lisp.se/Body/f_firstc.htm).

I've always like FST and RST (FirST and ReST) because they're more mnemonic but they still compose like CAR and CDR (e.g. FFRRFST == CAADDAR).

Good point. Haven't seen that example before.

Are you kidding? cdar would be the second element, cddar the third, and so on. And they're harder to misread on a scan through the code.

As a general rule, I assume that I read most lines of the code not when I'm writing it, nor fixing a bug, but while I'm trying to locate a bug of unknown location. The complexity or trickiness of a function that you are actively modifying can be pretty high and you'll still grasp it. But a function not even involved with a problem needs to be even more legible if you don't want to repeatedly waste time contemplating it to determine if you should move on.

Keep calm and read the Common Lisp specification (http://clhs.lisp.se/Body/f_firstc.htm)

There are first, etc... accessors (other Lisps might define them too, it is so easy to implement). People are encouraged to use them, especially for lists, and are even encouraged to not use them but prefer objects with named slots.

The general advice is to reserve C..R functions for trees, but this is actually rarely needed, especially when using pattern matching.

I prefer car/cdr over first/rest since a list is an implicit type and cdr/car are actually operating on pairs that are not necessary part of a list.

Reply on news.ycombinator.com