Lisp with maps instead of lists
will.thimbleby.net
will.thimbleby.net
It's a similar idea, in many ways, to the way Javascript does objects: run some code get a map back. Where it gets interesting is that you can choose to use the evaluated value and the scope that was generated in evaluating it. Objects, maps, code, scope, closures and lazy evaluation become the same thing: you declare a block of code, you evaluate it into a closure (with scope and a stack) you query it for results, rinse-repeat.
A for-loop becomes a function that takes two blocks: one that lazily generates values in and one that lazily consumes them. It is the two closures that remember their state - not the for-loop function. The 'for-function' just passes the current value to the second block to use it.
Javascript, REBOL and Lua do have these capabilities but none have the elegance (nor simplicity) of Lisp. I'd love to see a language that does.
On my project we ended up adding a JS-style property operator to CL and using JS-style maps wherever we wanted this flexibility, which was nearly everywhere. It just compiles to CL hashtables under the hood. This is so valuable, it's natural to wonder what a Lisp with the map as its organizing principle would look like.
http://stackoverflow.com/questions/323346/what-can-lisp-do-t...
Records (which are objects with a user defined types) are maps too so the upgrade is easy (and yes you can add you own fields to an object).
It's an important question because maps are flexible and flexibility is important for exploratory programming, which is nearly all programming. If there exists a language that is as regular and programmable as Lisp but organized around maps rather than lists, that would be a big deal.
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.
So its meant to be more thought-experimental than realistic (not saying your points are incorrect though).
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.
And I agree that the cons based model of a list hides important properties (parallelism being perhaps the most important one).
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?
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.
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.
Maybe we should all team up or something...