3 ms·

It's difficult to gauge how serious this proposal slash thought experiment is. The nice thing about a pair is the way it naturally lends itself to iterative pro

by edw 15y ago

It's difficult to gauge how serious this proposal slash thought experiment is. 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. (Are the keys in these maps ordered?) Not all data is complex enough to merit a map: modeling e.g. a list using lists is perverse in that you're using degenerate single-item maps to model what is a simpler data structure. And what does a lisp based on maps look like, if this language preserves the homoiconic nature of lisp? The argument by analogy that a lisp "should" have a "better" data structure than a cons cell because lisp lambdas support multiple arguments, unlike pure lambda calculus, doesn't hold water. Lisps--and even Scheme, which is often incorrectly taken to have as a design goal to be minimalistic to the point of consisting of axiomatic primitives--do not deal in pedantic adherence to theory. Limiting lambdas to a single argument is pointless whereas a cell happens to be minimal yet extremely useful in practice. Other have written lisps atop vectors as the primitive data type. That's an idea that makes more sense: it's a generalization of the pair to arbitrary length.

slewis 15y ago
From the article: "Thus the result is not a language for real-world use but one that I hope embodies many different unique and novel design decisions in a way that triggers thoughts and ideas in those that take the time to play with it." So its meant to be more thought-experimental than realistic (not saying your points are incorrect though).
- edw 15y ago
  I agree that sometimes pursuing prima facie "ridiculous" ideas to their logic conclusions can sometimes provide insights into problems that have far more real-world utility than you might ever expect when you start down the path.
jasonwatkinspdx 15y ago
" 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 15y 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 15y 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 15y 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 15y 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.

by edw 15y ago

slewis 15y ago

From the article: "Thus the result is not a language for real-world use but one that I hope embodies many different unique and novel design decisions in a way that triggers thoughts and ideas in those that take the time to play with it." So its meant to be more thought-experimental than realistic (not saying your points are incorrect though).

edw 15y ago
I agree that sometimes pursuing prima facie "ridiculous" ideas to their logic conclusions can sometimes provide insights into problems that have far more real-world utility than you might ever expect when you start down the path.

jasonwatkinspdx 15y ago

" 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 15y 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 15y 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 15y 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 15y 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.