begin quoting Andrew P. Lentvorski, Jr. as of Wed, Feb 02, 2005 at 08:14:55PM -0800: > > On Feb 2, 2005, at 3:14 PM, Stewart Stremler wrote: > > >>As one would expect, Common Lisp supplies vectors, arrays, hash > >>tables, strings, structures, classes, and, with library support, just > >>about any other data structure one can imagine. > > > >Aren't they all built out of cons-cells? Or it's just that they *can* > >be? > > Ack! Absolutely not!
Sorry. Didn't mean to cause distress. :) > Sure, they all *can* be built out of cons-cells, but that's a crappy > way to do it. Granted -- optimization would want to tackle that first thing. > And, now that I think about it, it probably explains the > persistent implication that Lisp is slow. For example, (length a) and > (elt a 4) are O(n) operations on cons-cells; they have to be as > cons-cells are effectively a singly-linked list. When your accessor is > O(n), any data structure built on top of that is going to suck. Well, trees fall naturally out of cons-cells as collections of n-item lists, so you can get at least O(logn) access time... :) > Anything other than a toy lisp implements those structures exactly as > you would expect with the O() guarantees you would also expect. Weren't the first lisp implementations built that way? Or do those count as "toy implementations" as well? > >I was trying to define what I see to be the defining feature of > >Lisp-like languages, namely, that the cons-cell / list is the key > >abstraction upon which the language is built. This is amazingly > >elegant and powerful. > > I disagree. A singly linked list is a *crappy* basic abstraction. Performance-wise, yes. Conceptually, it seems rather elegant. Then again, I find C's 1-1 correspondence with ASM to be elegant, as well as TCL's attitude that everything is just a string, or Smalltalk's approach of treating everything as an object. . . > However, it very friendly in an environment where memory is one-to-one > in frequency with the processor and the processor has few registers. > If that is not the case, then there are better abstractions. Indeed. > Amortized > vectors allocated from a data specific memory area are really friendly > to modern processors (4-8 element vectors get sucked into processor > cache lines whenever *any* element gets accessed). Surely that doesn't have to be visible to the programmer? > I find myself using vectors in lisp much more often than cons-cells. I > generally want O(1) element access more often than I want O(1) > insertion-deletion. And, if insertion-deletion was causing problems, > I'd still probably go use a tree or a deque instead. Do these have different accessors in CL? That is, if I write a generic function that, oh, sums the elements of a collection, would I need an implementation for each sort of data-structure (list, tree, vector, etc.) or would the same code handle all types? [snip] > I won't argue about the SmugLispWeenies. Of which Paul Graham is one > of the grand poobahs. Heh. > There are better voices with more rational decision making processes. > Erann Gat is a good choice: > http://groups-beta.google.com/group/comp.lang.lisp/msg/6f75cfb5a289d3f6?rnum=1 Nice! You're quite right, I think. He is a good choice to listen to. -Stewart "Had the most fun with Prime's CPL" Stremler -- KPLUG-List mailing list [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
