3 ms·

CAR, CDR, and Lisp...

55 points by parenthesis 16y ago

gigamonkey 16y ago
Regarding the "hunks" he mentioned, here's what Guy Steele had to say about them when I interviewed him for Coders at Work: "I implemented a new data type called a 'hunk,' which was probably the biggest disaster in language design we ever put in. It was essentially a cons cell with more than two pointers. It was a desperation move because we were running out of address space on the PDP-10. Recall that the -10 only had an 18-bit address space. In a list, 50 percent of the pointers were dedicated to just maintaining the structure of the list, whereas with a threaded set of hunks, maybe only one-eighth of the pointers were dedicated to the threading of the chunks so you’d get better memory usage that way."
gruseom 16y ago
car and cdr must have something going for them that first and rest don't, or else people would have abandoned them decades ago. The author mentions one point in their favor: generality. I'd add another two: brevity, and symmetry. It's also worth noting that the primary disadvantage of car and cdr, their arbitrariness, fades as one becomes familiar with the language.
- kunjaan 16y ago
  >car and cdr must have something going for them In most implementations , I can do (cadar (list (list 1 2 3))) -> 2 vs (first (rest (first (list (list 1 2 3))))) -> 2 I find the car and cdrs in Racket very very convenient. Reference: http://docs.racket-lang.org/reference/pairs.html?q=pair%20accessor#(part._.Pair_.Accessor_.Shorthands) http://docs.racket-lang.org/reference/pairs.html?q=pair%20ac...
bhrgunatha 16y ago
Why are people so offended by syntax? So many people complain about parentheses or names like car and cdr. Is it the programming equivalent of being shallow or judging by appearance? When I first started learning scheme I was much more challenged by the rest of the cognitive assault - tail recursion is "free", call/cc or continuations, the shift to thinking in "higher order" mode, macros, being able to effectively define your own syntax.
- petercooper 16y ago
  It's disingenuous to split people into those who whine about syntax and those who enjoy deeper challenges. It's possible to be in both camps. Syntax isn't any more important than the other things you mention, but it's certainly as important. Syntax is not mere window dressing. Like punctuation in written language, there's good and bad, confusing and obvious, opaque and transparent, and it will be judged and analyzed like anything else.
- SkyMarshal 16y ago
  Agreed, you should flesh that out into a blog post, a reminder to people to stop losing sight of the forest for the trees.
- p_nathan 16y ago
  Syntax helps frame thought. I wrote a comment on this topic over on the StackExchange just the other day. http://programmers.stackexchange.com/questions/30135/does-syntax-really-matter-in-a-programming-language/30156#30156 http://programmers.stackexchange.com/questions/30135/does-sy...
swannodette 16y ago
Of course since Clojure is built upon abstractions, and because it's simple to introduce your own protocols and extend them to existing types w/o conflicts - it's straightforward to reintroduce the concept of a "pair" where the right-hand side is not a sequence. I recently encountered this challenge working on a Clojure port of miniKanren (the relational programming system described in the The Reasoned Schemer). In miniKanren the concept of a "pair" is useful because the right hand side of a sequence in miniKanren might be a logic variable and not a sequence. What's lovely is how simple this is. I can define a custom iteration protocol (LogicSeq) which define two functions - lfirst, lnext. Then I create a custom sequence type that returns a legitimate Sequence or logic variable for lnext. To bring all the other collections into this protocols is 4 lines of code: (extend-protocol LConsSeq clojure.lang.IPersistentCollection (lfirst [this] (clojure.core/first this)) (lnext [this] (clojure.core/next this))) Voila! Custom iteration! What's even more amazing is that there's hardly a perf hit. The JVM sees it's just a pass through call for real Clojure collections. Fun stuff :)
techiferous 16y ago
I'm surprised cadr, caddr, cddr, etc. were not mentioned when comparing car/cdr with first/rest. See http://www.franz.com/support/documentation/8.2/ansicl/dictentr/carcdrca.htm http://www.franz.com/support/documentation/8.2/ansicl/dicten...
- masklinn 16y ago
  Indeed, so was I: the cºr indirections strike me as a very good reason to not switch to `first` and `rest` (or `head` and `tail`) in Lisp: they provide an unambiguous and readable way to quickly traverse multiple levels of datastructures (as long as they're not abused too much) which is not as easy to generally replicate using more meaningful names.
  - kaylarose 16y ago
    Maybe it's just my mental model, or being new to the language. But while going through SICP - 'cdadadr', 'cddaadr', etc. never really "clicked" in my mind. Really anything past 3 levels (cadar, cddar, etc.) always slowed down reading code, like hitting a speed bump. I would have to stop and really try to grok what list item it was referring to. Not saying that that is a bad thing, just an observation. Is there a common way of thinking that makes it easier to comprehend, or is it just something that comes with experience?
    - techiferous 16y ago
      I worked with Scheme (a type of Lisp) professionally for over a year and even after heavy usage there were still lots of syntax "speed bumps" like this that slowed me down. I really enjoyed a lot of the concepts of Scheme but the syntax was a bummer and I'm so glad I'm not programming with it anymore. :)
      - kaylarose 16y ago
        Yep Scheme was what I was using with SICP. I've heard of Common Lisp in passing, does it have a more friendly syntax?

55 points by parenthesis 16y ago

Regarding the "hunks" he mentioned, here's what Guy Steele had to say about them when I interviewed him for Coders at Work: "I implemented a new data type called a 'hunk,' which was probably the biggest disaster in language design we ever put in. It was essentially a cons cell with more than two pointers. It was a desperation move because we were running out of address space on the PDP-10. Recall that the -10 only had an 18-bit address space. In a list, 50 percent of the pointers were dedicated to just maintaining the structure of the list, whereas with a threaded set of hunks, maybe only one-eighth of the pointers were dedicated to the threading of the chunks so you’d get better memory usage that way."

gruseom 16y ago

car and cdr must have something going for them that first and rest don't, or else people would have abandoned them decades ago. The author mentions one point in their favor: generality. I'd add another two: brevity, and symmetry. It's also worth noting that the primary disadvantage of car and cdr, their arbitrariness, fades as one becomes familiar with the language.

kunjaan 16y ago
>car and cdr must have something going for them In most implementations , I can do (cadar (list (list 1 2 3))) -> 2 vs (first (rest (first (list (list 1 2 3))))) -> 2 I find the car and cdrs in Racket very very convenient. Reference: http://docs.racket-lang.org/reference/pairs.html?q=pair%20accessor#(part._.Pair_.Accessor_.Shorthands) http://docs.racket-lang.org/reference/pairs.html?q=pair%20ac...

bhrgunatha 16y ago

Why are people so offended by syntax? So many people complain about parentheses or names like car and cdr. Is it the programming equivalent of being shallow or judging by appearance? When I first started learning scheme I was much more challenged by the rest of the cognitive assault - tail recursion is "free", call/cc or continuations, the shift to thinking in "higher order" mode, macros, being able to effectively define your own syntax.

petercooper 16y ago
It's disingenuous to split people into those who whine about syntax and those who enjoy deeper challenges. It's possible to be in both camps. Syntax isn't any more important than the other things you mention, but it's certainly as important. Syntax is not mere window dressing. Like punctuation in written language, there's good and bad, confusing and obvious, opaque and transparent, and it will be judged and analyzed like anything else.
SkyMarshal 16y ago
Agreed, you should flesh that out into a blog post, a reminder to people to stop losing sight of the forest for the trees.
p_nathan 16y ago
Syntax helps frame thought. I wrote a comment on this topic over on the StackExchange just the other day. http://programmers.stackexchange.com/questions/30135/does-syntax-really-matter-in-a-programming-language/30156#30156 http://programmers.stackexchange.com/questions/30135/does-sy...

swannodette 16y ago

Of course since Clojure is built upon abstractions, and because it's simple to introduce your own protocols and extend them to existing types w/o conflicts - it's straightforward to reintroduce the concept of a "pair" where the right-hand side is not a sequence. I recently encountered this challenge working on a Clojure port of miniKanren (the relational programming system described in the The Reasoned Schemer). In miniKanren the concept of a "pair" is useful because the right hand side of a sequence in miniKanren might be a logic variable and not a sequence. What's lovely is how simple this is. I can define a custom iteration protocol (LogicSeq) which define two functions - lfirst, lnext. Then I create a custom sequence type that returns a legitimate Sequence or logic variable for lnext. To bring all the other collections into this protocols is 4 lines of code: (extend-protocol LConsSeq clojure.lang.IPersistentCollection (lfirst [this] (clojure.core/first this)) (lnext [this] (clojure.core/next this))) Voila! Custom iteration! What's even more amazing is that there's hardly a perf hit. The JVM sees it's just a pass through call for real Clojure collections. Fun stuff :)

techiferous 16y ago

I'm surprised cadr, caddr, cddr, etc. were not mentioned when comparing car/cdr with first/rest. See http://www.franz.com/support/documentation/8.2/ansicl/dictentr/carcdrca.htm http://www.franz.com/support/documentation/8.2/ansicl/dicten...

masklinn 16y ago
Indeed, so was I: the cºr indirections strike me as a very good reason to not switch to `first` and `rest` (or `head` and `tail`) in Lisp: they provide an unambiguous and readable way to quickly traverse multiple levels of datastructures (as long as they're not abused too much) which is not as easy to generally replicate using more meaningful names.
- kaylarose 16y ago
  Maybe it's just my mental model, or being new to the language. But while going through SICP - 'cdadadr', 'cddaadr', etc. never really "clicked" in my mind. Really anything past 3 levels (cadar, cddar, etc.) always slowed down reading code, like hitting a speed bump. I would have to stop and really try to grok what list item it was referring to. Not saying that that is a bad thing, just an observation. Is there a common way of thinking that makes it easier to comprehend, or is it just something that comes with experience?
  - techiferous 16y ago
    I worked with Scheme (a type of Lisp) professionally for over a year and even after heavy usage there were still lots of syntax "speed bumps" like this that slowed me down. I really enjoyed a lot of the concepts of Scheme but the syntax was a bummer and I'm so glad I'm not programming with it anymore. :)
    - kaylarose 16y ago
      Yep Scheme was what I was using with SICP. I've heard of Common Lisp in passing, does it have a more friendly syntax?