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!
Sure, they all *can* be built out of cons-cells, but that's a crappy way to do it. 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.
Anything other than a toy lisp implements those structures exactly as you would expect with the O() guarantees you would also expect.
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. 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. 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).
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.
When I dismiss Lisp-like languages, it is because the language is utterly
insane, and the advocates are wont to take credit for absolutely everything
useful in computer science, and fail to claim that FORTRAN is lisp-like
due only to the distressing fact that FORTRAN came first.
I won't argue about the SmugLispWeenies. Of which Paul Graham is one of the grand poobahs.
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
"So I can't really go into many specifics about what happened at Google
because of confidentiality, but the upshot was this: I saw, pretty much
for the first time in my life, people being as productive and more in
other languages as I was in Lisp. What's more, once I got knocked off my
high horse (they had to knock me more than once -- if anyone from Google
is reading this, I'm sorry) and actually bothered to really study some of
these other languges I found *myself* suddenly becoming more productive in
other languages than I was in Lisp. For example, my language of choice
for doing Web development now is Python.
I also saw Peter Norvig come to Google and leave Lisp behind with no apparent regrets. (Actually, Peter and I had talked about this while we were both still at NASA, and he was already leaving Lisp behind, which I found very distressing at the time.)"
-a
--
KPLUG-List mailing list [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
