News for hackers. Stuff that matters.
Re:The Origin of CAR and CDR in Lisp (2005) by ZenoArrow on Monday December 26, 2016 @11:49AM (#13258815)
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."

Re:The Origin of CAR and CDR in Lisp (2005) by dang on Monday December 26, 2016 @01:10PM (#13259122)
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...
Re:The Origin of CAR and CDR in Lisp (2005) by ZenoArrow on Monday December 26, 2016 @03:09PM (#13259547)
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

Re:The Origin of CAR and CDR in Lisp (2005) by dang on Monday December 26, 2016 @04:16PM (#13259805)
Good point! I edited my comment to say "one of".
Re:The Origin of CAR and CDR in Lisp (2005) by ZenoArrow on Monday December 26, 2016 @05:29PM (#13260117)
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/

Re:The Origin of CAR and CDR in Lisp (2005) by _0ffh on Monday December 26, 2016 @12:50PM (#13259051)
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!

Re:The Origin of CAR and CDR in Lisp (2005) by AlbertoGP on Monday December 26, 2016 @02:06PM (#13259344)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by tspiteri on Monday December 26, 2016 @01:18PM (#13259157)
And fst and rst allow for composition too:

    caar -> ffst
    cddar -> rrfst
Re:The Origin of CAR and CDR in Lisp (2005) by nothrabannosir on Monday December 26, 2016 @01:34PM (#13259230)
I am disproportionally moved by this elegance.
Re:The Origin of CAR and CDR in Lisp (2005) by qwertyuiop924 on Monday December 26, 2016 @01:32PM (#13259218)
But that doesn't look as nice.
Re:The Origin of CAR and CDR in Lisp (2005) by Turing_Machine on Monday December 26, 2016 @06:06PM (#13260257)
It would need to have a pronunciation convention before it could catch on.

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

Re:The Origin of CAR and CDR in Lisp (2005) by bhrgunatha on Monday December 26, 2016 @09:07PM (#13260838)
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
Re:The Origin of CAR and CDR in Lisp (2005) by dang on Monday December 26, 2016 @01:11PM (#13259129)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by abecedarius on Monday December 26, 2016 @06:34PM (#13260342)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by dang on Monday December 26, 2016 @06:43PM (#13260374)
What did you do recently?
Re:The Origin of CAR and CDR in Lisp (2005) by metaobject on Monday December 26, 2016 @06:53PM (#13260407)
To add to that question ... how did you use pattern matching to replace the composability of car/cdr?
Re:The Origin of CAR and CDR in Lisp (2005) by abecedarius on Monday December 26, 2016 @07:53PM (#13260609)
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

Re:The Origin of CAR and CDR in Lisp (2005) by kruhft on Monday December 26, 2016 @10:03PM (#13261022)
Thank you for sharing your work. I could see some good use out of it.
Re:The Origin of CAR and CDR in Lisp (2005) by abecedarius on Tuesday December 27, 2016 @05:51PM (#13266937)
I hope it does become useful, thanks! So far it's more of a hobby.
Re:The Origin of CAR and CDR in Lisp (2005) by lmm on Monday December 26, 2016 @05:29PM (#13260118)
I think people might still start new s-expression based languages, whereas any respectable new language will use head/tail rather than car/cdr.
Re:The Origin of CAR and CDR in Lisp (2005) by dang on Monday December 26, 2016 @06:39PM (#13260355)
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.

Re:The Origin of CAR and CDR in Lisp (2005) by bluefox on Monday December 26, 2016 @07:34PM (#13260549)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by Turing_Machine on Monday December 26, 2016 @06:03PM (#13260241)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by aninhumer on Tuesday December 27, 2016 @09:21AM (#13263241)
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.

Re:The Origin of CAR and CDR in Lisp (2005) by Turing_Machine on Wednesday December 28, 2016 @03:03AM (#13269138)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by aninhumer on Wednesday December 28, 2016 @05:28AM (#13269670)
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.

Re:The Origin of CAR and CDR in Lisp (2005) by Turing_Machine on Thursday December 29, 2016 @01:17AM (#13275950)
"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.

Re:The Origin of CAR and CDR in Lisp (2005) by kbp on Monday December 26, 2016 @07:05PM (#13260444)
Conses are arbitrary pairs, not necessarily lists. car and cdr are what eg OCaml and Haskell call fst and snd.
Re:The Origin of CAR and CDR in Lisp (2005) by chj on Monday December 26, 2016 @11:01PM (#13261202)
Think of them as tools or symbols, like Sigma or Pi. Make peace and move on.
Re:The Origin of CAR and CDR in Lisp (2005) by kruhft on Monday December 26, 2016 @12:51PM (#13259056)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by s_kilk on Monday December 26, 2016 @01:58PM (#13259313)
I dunno, as a latecomer lisp-enthusiast, that cadaddaaadr stuff seems heinous to me.
Re:The Origin of CAR and CDR in Lisp (2005) by kazinator on Monday December 26, 2016 @02:29PM (#13259425)
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

Re:The Origin of CAR and CDR in Lisp (2005) by kruhft on Monday December 26, 2016 @09:44PM (#13260951)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by kbp on Monday December 26, 2016 @11:53PM (#13261343)
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.
Re:The Origin of CAR and CDR in Lisp (2005) by junke on Tuesday December 27, 2016 @02:55AM (#13261890)
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).
Re:The Origin of CAR and CDR in Lisp (2005) by hinkley on Tuesday December 27, 2016 @12:15AM (#13261416)
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.

Re:The Origin of CAR and CDR in Lisp (2005) by junke on Tuesday December 27, 2016 @02:51AM (#13261868)
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.

Re:The Origin of CAR and CDR in Lisp (2005) by lisper on Monday December 26, 2016 @05:00PM (#13260008)
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).
Re:The Origin of CAR and CDR in Lisp (2005) by kruhft on Monday December 26, 2016 @09:42PM (#13260946)
Good point. Haven't seen that example before.
Re:The Origin of CAR and CDR in Lisp (2005) by topkekz on Tuesday December 27, 2016 @07:48AM (#13262777)
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.