7 ms·

My question is, given the cons pair is not a meaningful primitive datatype to modern CPUs (can't fit in a register unless you're using 32 bit atoms on a 64 bit

My question is, given the cons pair is not a meaningful primitive datatype to modern CPUs (can't fit in a register unless you're using 32 bit atoms on a 64 bit CPU, the individual cells cannot be meaningfully manipulated while packed into a single register even in that case...), is there a good reason to use an unrestricted pair/2-tuple/2 element vector for the sexp representation? Would it be "wrong" to remove dotted pair notation and make sexps a restricted type whose cdr could only be another pair or the empty list? You'd have to give up alists, but those would probably be better served by doing as Clojure does and introducing a hash table syntax. Other than alists, simplifying the implementation[1], and tradition, I can't think of a good reason to keep improper lists and dotted pair notation around. They aren't really that useful, confuse newcomers, and encourage the use of inefficient data structures. I haven't written much Lisp, but when I see a dotted pair (usually in the context of an alist or some hideous approximation of a struct[2]), it comes across as a "code smell" to me, like "this person is taking SICP too literally." [1] You pay for extra reader syntax, but gain uniformity in your treatment of the car and cdr cells. On the other hand, maybe you could optimize the cdr cell a bit if it only needed to address pairs and not arbitrary atoms. [2] ;; barfage (define (make-thing a b c) (cons a (cons b c))) ; barf (define (thing-field-a x) (car x)) (define (thing-field-b x) (cadr x)) (define (thing-field-c x) (cddr x)) ; more barf

Sean-Der 13y ago
I come from a background using Common Lisp for system and web development so I may see things differently than people who were introduced to it academically. Your code looks great, mine just needed to compile :) The cons pair is a a really powerful primitive data structure, it is the linked list of Lisp. You can build a lot of powerful structures given this great base. I really don't it matters what architecture your running on. Do they really confuse people new to Lisp? car+cdr is a pretty simple concept, when talking to new Lispers they usually don't complain about this. Hash Tables are part of the Common Lisp Hyperspec so that is a non issue, they have been first class citizens since before Clojure existed (and are nicely integrated into things like loop)
- anaphor 13y ago
  I think the parent was saying car and cdr are confusing because they don't actually map to registers (i.e. address register and decrement register). On the other hand you don't have to think too hard about the composed versions of them (caddr, cadar, etc...) but they can easily make your code seem obfuscated. Racket offers both that and first/rest anyway so you can choose which style you prefer.
  - ANTSANTS 13y ago
    I don't mind car, cdr, and their composed versions at all. `caddr` is much easier for me to read than `(head (tail (tail ...` I think their usage is sometimes a code smell (the ad-hoc structs I mentioned), but they're really useful when you want to deal with an "unlispy" list of tokens (say, a parser for a language that isn't Lisp).
- ANTSANTS 13y ago
  I mean, it's neat that you can build everything out of cons, in the sense that it's neat that Turing machines and the lambda calculus can perform any computation, but that doesn't mean it's a good idea to so in your code, any more than encoding numbers with Church numerals. Why use alists when you can use hash tables, why use... weird SICP-style struct list things when you could just use structs/vectors, etc. >Hash Tables are part of the Common Lisp Hyperspec so that is a non issue, they have been first class citizens since before Clojure existed (and are nicely integrated into things like loop) I'm not that familiar with Common Lisp, but a quick search didn't reveal a syntax for hash table literals, which I would consider to be a prerequisite for calling them first class citizens. There are other funny uses of lists (not improper ones, but still) in Common Lisp, like named procedure arguments[1]. I guess my point is, why encourage these weird constructs in the first place? Sexps are good at representing recursive structure, tables are good at mapping names to values, why not just have both and let them do what they're good at? Obviously Common Lisp is very old and can't be changed after the fact, I'm just trying to imagine the "ideal Lisp," whatever that is. >Do they really confuse people new to Lisp? car+cdr is a pretty simple concept, when talking to new Lispers they usually don't complain about this. I wasn't, but I've seen it confuse other people. Either way, it's a wart on the syntax that seems out of place in Scheme (not so in Common Lisp, which has lots of other warts ;)) >I come from a background using Common Lisp for system and web development so I may see things differently than people who were introduced to it academically. Well, I was introduced to Scheme through SICP, but my motivation for picking it up was more practical than theoretical; I'd heard all the message board talk, Paul Graham essays, etc. proclaiming Lisp to be the most powerful, productive family of programming languages that will turn you into an expert programmer and so on, and wanted in on that ;) Maybe it's more practical to be Getting Shit Done™ instead of worrying about syntactic warts, but I think choosing to not have dotted pairs runs a bit deeper, by forcing the language to promote at least tables to a first class syntactic citizen. [1] For the unfamiliar, it's something like: (message "Text" :style bold :color red) Reads pretty well, but it still seems wrong to me (ymmv), like it's another spot in the language begging for first class hash tables. In Lua, you'd emulate named arguments by passing a table to the function. I wonder what Clojure programmers do here. This? (message "Text" {style: bold, color: red}) Which doesn't make a big deal for readability, but I bet if you want to use a macro or whatever accepts named arguments, it'd be much easier to deal with the one with the real hash table.
anaphor 13y ago
It has pedagogical value to define things in terms of a very small kernel language. You will find things like alists in fairly advanced books on lisp (e.g. Lisp In Small Pieces) simply because it reduces the number of extra concepts you need to explain. It's assumed that the reader can figure out how to make the code cleaner and more idiomatic as long as they understand the ideas being presented. Also I have made use of improper lists in my code, usually when I need to do something with multiple values and I don't want to mess with multiple return values, or if I just want to create a list of tuples for some reason and don't feel like defining an actual struct (can't think of a good example right now...)
- ANTSANTS 13y ago
  >Also I have made use of improper lists in my code, usually when I need to do something with multiple values and I don't want to mess with multiple return values, or if I just want to create a list of tuples for some reason and don't feel like defining an actual struct (can't think of a good example right now...) I get what you're saying, but isn't this just a shortcoming of the language? It's pretty common to want to write something like (define (string-lookup-that-might-fail) (if (random) <"string you were trying to look up" nil> <nil "It wasn't there.">)) (define <some-string error-msg> (string-lookup-that-might-fail)) without wanting to destructure a list or use the call-values hack. That's a bad example, just pretend there were multiple reasons the lookup could fail. I totally agree about there being pedagogical value in having a simple core. I'm torn between appreciating minimalism and believing that it's ok to introduce complexity to a language that people will use to get things done every day, so long as it's useful complexity and not just historical accident.
  - anaphor 13y ago
    Okay yeah I agree with you there. The pain of destructuring cons cells is somewhat mitigated by the various forms that allow pattern matching, but it's still basically the same. So I think that is actually a good argument for introducing option types (like Haskell's Either a b) into the language. I think Typed Racket has something like this, but in either case you'd want some nice syntax to handle it as well. Hash tables make this sort of thing fairly easy though (at least in Racket) (define h #hash{["a" . 3] ["b" . 5]}) (hash-ref h k "failed") I think most lisps support this right? I remember seeing something similar in pg's bayesian spam filter code.
brudgers 13y ago
Going a little Abelson&Sussman, the utility of cons persists because it is a powerful abstraction. Fitting into registers was, as a scholastic might say, an as accidental feature as the input line voltage of a toaster [110 @ 60Hz makes things easier in this part of the world but isn't intrinsic to making crisp English muffins]. cons is useful for dealing with linked memory structures, including singlely linked lists and particularly singly linked lists where the stored value in each list element is a pointer because it abstracts over all the pointers. Writing code to process and manipulate and pass pointers is idiomatic in C. Using pointers is idiomatic Lisp. Your barfing code shows why cdr and car persist. They are also powerful abstractions due to their rules of combination and probably because their rules of combination aren't constrained by a bias toward English language. There ain't no synonyms for "caddr" and "cdddr" in English or Python. The idea that lists should be everywhere replaced by structs is assembly in any language thinking (also known as C). Lists provide a standard interface. Each struct definition creates a new data type. It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. Alan J. Perlis, Epigram 9.
- munificent 13y ago
  > There ain't no synonyms for "caddr" and "cdddr" in English or Python. In Python: x[1][1][0] # caddr x[1][1][1] # cdddr
- chc 13y ago
  I think the question is more along the lines of "Should the core data type be the cons cell rather than the list?" Clojure takes the approach the GP was talking about. It has lists with heads and tails, but it does not have dotted pairs. The tail of a list is always a list.

Sean-Der 13y ago

I come from a background using Common Lisp for system and web development so I may see things differently than people who were introduced to it academically. Your code looks great, mine just needed to compile :) The cons pair is a a really powerful primitive data structure, it is the linked list of Lisp. You can build a lot of powerful structures given this great base. I really don't it matters what architecture your running on. Do they really confuse people new to Lisp? car+cdr is a pretty simple concept, when talking to new Lispers they usually don't complain about this. Hash Tables are part of the Common Lisp Hyperspec so that is a non issue, they have been first class citizens since before Clojure existed (and are nicely integrated into things like loop)

anaphor 13y ago
I think the parent was saying car and cdr are confusing because they don't actually map to registers (i.e. address register and decrement register). On the other hand you don't have to think too hard about the composed versions of them (caddr, cadar, etc...) but they can easily make your code seem obfuscated. Racket offers both that and first/rest anyway so you can choose which style you prefer.
- ANTSANTS 13y ago
  I don't mind car, cdr, and their composed versions at all. `caddr` is much easier for me to read than `(head (tail (tail ...` I think their usage is sometimes a code smell (the ad-hoc structs I mentioned), but they're really useful when you want to deal with an "unlispy" list of tokens (say, a parser for a language that isn't Lisp).
ANTSANTS 13y ago
I mean, it's neat that you can build everything out of cons, in the sense that it's neat that Turing machines and the lambda calculus can perform any computation, but that doesn't mean it's a good idea to so in your code, any more than encoding numbers with Church numerals. Why use alists when you can use hash tables, why use... weird SICP-style struct list things when you could just use structs/vectors, etc. >Hash Tables are part of the Common Lisp Hyperspec so that is a non issue, they have been first class citizens since before Clojure existed (and are nicely integrated into things like loop) I'm not that familiar with Common Lisp, but a quick search didn't reveal a syntax for hash table literals, which I would consider to be a prerequisite for calling them first class citizens. There are other funny uses of lists (not improper ones, but still) in Common Lisp, like named procedure arguments[1]. I guess my point is, why encourage these weird constructs in the first place? Sexps are good at representing recursive structure, tables are good at mapping names to values, why not just have both and let them do what they're good at? Obviously Common Lisp is very old and can't be changed after the fact, I'm just trying to imagine the "ideal Lisp," whatever that is. >Do they really confuse people new to Lisp? car+cdr is a pretty simple concept, when talking to new Lispers they usually don't complain about this. I wasn't, but I've seen it confuse other people. Either way, it's a wart on the syntax that seems out of place in Scheme (not so in Common Lisp, which has lots of other warts ;)) >I come from a background using Common Lisp for system and web development so I may see things differently than people who were introduced to it academically. Well, I was introduced to Scheme through SICP, but my motivation for picking it up was more practical than theoretical; I'd heard all the message board talk, Paul Graham essays, etc. proclaiming Lisp to be the most powerful, productive family of programming languages that will turn you into an expert programmer and so on, and wanted in on that ;) Maybe it's more practical to be Getting Shit Done™ instead of worrying about syntactic warts, but I think choosing to not have dotted pairs runs a bit deeper, by forcing the language to promote at least tables to a first class syntactic citizen. [1] For the unfamiliar, it's something like: (message "Text" :style bold :color red) Reads pretty well, but it still seems wrong to me (ymmv), like it's another spot in the language begging for first class hash tables. In Lua, you'd emulate named arguments by passing a table to the function. I wonder what Clojure programmers do here. This? (message "Text" {style: bold, color: red}) Which doesn't make a big deal for readability, but I bet if you want to use a macro or whatever accepts named arguments, it'd be much easier to deal with the one with the real hash table.

anaphor 13y ago

It has pedagogical value to define things in terms of a very small kernel language. You will find things like alists in fairly advanced books on lisp (e.g. Lisp In Small Pieces) simply because it reduces the number of extra concepts you need to explain. It's assumed that the reader can figure out how to make the code cleaner and more idiomatic as long as they understand the ideas being presented. Also I have made use of improper lists in my code, usually when I need to do something with multiple values and I don't want to mess with multiple return values, or if I just want to create a list of tuples for some reason and don't feel like defining an actual struct (can't think of a good example right now...)

ANTSANTS 13y ago
>Also I have made use of improper lists in my code, usually when I need to do something with multiple values and I don't want to mess with multiple return values, or if I just want to create a list of tuples for some reason and don't feel like defining an actual struct (can't think of a good example right now...) I get what you're saying, but isn't this just a shortcoming of the language? It's pretty common to want to write something like (define (string-lookup-that-might-fail) (if (random) <"string you were trying to look up" nil> <nil "It wasn't there.">)) (define <some-string error-msg> (string-lookup-that-might-fail)) without wanting to destructure a list or use the call-values hack. That's a bad example, just pretend there were multiple reasons the lookup could fail. I totally agree about there being pedagogical value in having a simple core. I'm torn between appreciating minimalism and believing that it's ok to introduce complexity to a language that people will use to get things done every day, so long as it's useful complexity and not just historical accident.
- anaphor 13y ago
  Okay yeah I agree with you there. The pain of destructuring cons cells is somewhat mitigated by the various forms that allow pattern matching, but it's still basically the same. So I think that is actually a good argument for introducing option types (like Haskell's Either a b) into the language. I think Typed Racket has something like this, but in either case you'd want some nice syntax to handle it as well. Hash tables make this sort of thing fairly easy though (at least in Racket) (define h #hash{["a" . 3] ["b" . 5]}) (hash-ref h k "failed") I think most lisps support this right? I remember seeing something similar in pg's bayesian spam filter code.

brudgers 13y ago

Going a little Abelson&Sussman, the utility of cons persists because it is a powerful abstraction. Fitting into registers was, as a scholastic might say, an as accidental feature as the input line voltage of a toaster [110 @ 60Hz makes things easier in this part of the world but isn't intrinsic to making crisp English muffins]. cons is useful for dealing with linked memory structures, including singlely linked lists and particularly singly linked lists where the stored value in each list element is a pointer because it abstracts over all the pointers. Writing code to process and manipulate and pass pointers is idiomatic in C. Using pointers is idiomatic Lisp. Your barfing code shows why cdr and car persist. They are also powerful abstractions due to their rules of combination and probably because their rules of combination aren't constrained by a bias toward English language. There ain't no synonyms for "caddr" and "cdddr" in English or Python. The idea that lists should be everywhere replaced by structs is assembly in any language thinking (also known as C). Lists provide a standard interface. Each struct definition creates a new data type. It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures. Alan J. Perlis, Epigram 9.

munificent 13y ago
> There ain't no synonyms for "caddr" and "cdddr" in English or Python. In Python: x[1][1][0] # caddr x[1][1][1] # cdddr
chc 13y ago
I think the question is more along the lines of "Should the core data type be the cons cell rather than the list?" Clojure takes the approach the GP was talking about. It has lists with heads and tails, but it does not have dotted pairs. The tail of a list is always a list.