3 ms·

" The nice thing about a pair is the way it naturally lends itself to iterative processing: There's the CAR and the CDR, the first and the rest." While elegant

" The nice thing about a pair is the way it naturally lends itself to iterative processing: There's the CAR and the CDR, the first and the rest." While elegant, the convention of cons cells as lists is increasingly going to be a flaw, because using linear recursion to process a list often obscures parallelism vs using a binary divide/conquer description of algorithms. See recent talks by Guy Steel on lisps organized as concatenation trees. Also, I think Lua is a good existential example that organizing a language on top of a single MAP data structure can be quite sensible.

cema 16y ago
Thanks for the tip on Guy Steele's talks! And I agree that the cons based model of a list hides important properties (parallelism being perhaps the most important one).
edw 16y ago
I don't disagree that the pair is far free the be-all end-all of primitive data structures. On the contrary, when I'm programming in Clojure, most of my data structures are made out of hashes and vectors. And most definitely, the need to walk a linked list inhibits parallel thinking (and, just as importantly parallel execution) and so we shouldn't avoid baking richer data structures into lisps. Again, Clojure does this and even Scheme does too, with R6RS with hashes as well as the more established vectors, because, again, Scheme is not about axiomatic minimalism. But to make a hash the fundamental data structure out of which everything else is constructed would be crazy. There's plenty of room on the world for atoms, pairs, vectors, hashes, and maybe even primitive sets. What I don't know is if this proliferation of primitive types would cause other problems because we'd wind up dedicating so many bits in a pointer to tags to signal a type that we'd restrict the range of atoms too much. But hey, we're living in a 64 bit world now, right?
- jasonwatkinspdx 16y ago
  "But to make a hash the fundamental data structure out of which everything else is constructed would be crazy." A hash can easily model a vector, including sparse vectors. There are efficient functional implementations such as Clojure's which is based on Bagwell's Array Mapped Tries. Functional vectors/arrays are an open research problem. So I would say maps might be very reasonable as the single structure in a functional language. Also, there are many ways to cope with tagging more types than are practically fit within the low bits of a pointer. The simplest dates all the way back to MACLISP (no relation to macintosh). The idea is to tag regions of memory that hold uniform values. This fits very well with modern memory allocators based on the slab allocator.
danssig 16y ago
>While elegant, the convention of cons cells as lists is increasingly going to be a flaw, because using linear recursion to process a list often obscures parallelism I disagree that it's a flaw. I think the problem here is this idea that we can only have one data type. For me, the main thing C++ got right was the STL. It didn't have one collection type, it had several. Each with its own set of trade offs. That's what we need in Lisp. You want instant insert but don't care as much about traversal? List. Fast random index-based access? Vector. And so on.

cema 16y ago

Thanks for the tip on Guy Steele's talks! And I agree that the cons based model of a list hides important properties (parallelism being perhaps the most important one).

edw 16y ago

I don't disagree that the pair is far free the be-all end-all of primitive data structures. On the contrary, when I'm programming in Clojure, most of my data structures are made out of hashes and vectors. And most definitely, the need to walk a linked list inhibits parallel thinking (and, just as importantly parallel execution) and so we shouldn't avoid baking richer data structures into lisps. Again, Clojure does this and even Scheme does too, with R6RS with hashes as well as the more established vectors, because, again, Scheme is not about axiomatic minimalism. But to make a hash the fundamental data structure out of which everything else is constructed would be crazy. There's plenty of room on the world for atoms, pairs, vectors, hashes, and maybe even primitive sets. What I don't know is if this proliferation of primitive types would cause other problems because we'd wind up dedicating so many bits in a pointer to tags to signal a type that we'd restrict the range of atoms too much. But hey, we're living in a 64 bit world now, right?

jasonwatkinspdx 16y ago
"But to make a hash the fundamental data structure out of which everything else is constructed would be crazy." A hash can easily model a vector, including sparse vectors. There are efficient functional implementations such as Clojure's which is based on Bagwell's Array Mapped Tries. Functional vectors/arrays are an open research problem. So I would say maps might be very reasonable as the single structure in a functional language. Also, there are many ways to cope with tagging more types than are practically fit within the low bits of a pointer. The simplest dates all the way back to MACLISP (no relation to macintosh). The idea is to tag regions of memory that hold uniform values. This fits very well with modern memory allocators based on the slab allocator.

danssig 16y ago

>While elegant, the convention of cons cells as lists is increasingly going to be a flaw, because using linear recursion to process a list often obscures parallelism I disagree that it's a flaw. I think the problem here is this idea that we can only have one data type. For me, the main thing C++ got right was the STL. It didn't have one collection type, it had several. Each with its own set of trade offs. That's what we need in Lisp. You want instant insert but don't care as much about traversal? List. Fast random index-based access? Vector. And so on.