Re: what happened to hash-tables
From: Christopher C. Stacy (cstacy_at_news.dtpq.com)
Date: Mon, 20 Sep 2004 03:46:57 GMT
Vassil Nikolov <email@example.com> writes:
> Pascal Costanza <firstname.lastname@example.org> writes:
> > Tayssir John Gabbour wrote:
> >> I wonder if the standards guys felt really decadent about putting in a
> >> hashtable, since CL was already huge by the standards of the day (ha
> >> ha, how times change), so it wasn't bulked up.
> > You already need hashtables anyway internally for implementing Common
> > Lisp (-> package system), so it doesn't cost that much to standardize
> > them. EQUALP already works well with structures, so the current state
> > of affairs is probably just because noone put energy into integrating
> > CLOS and hashtables.
> Or maybe because the people on the committee were not quite sure how
> exactly to standardize this (using any user-supplied function as the
> equality test of an ANSI Common Lisp hash table), and they did not
> want to set anything in stone that might turn out to be half-baked.
> As it has been pointed out many times, designing library interfaces
> (including the constraints that apply) requires lots of effort as
> well as sufficient experience with prototype library designs.
The above is not consistent with the reality of the state
of the art of the day, and is a naive analysis of how
standards committees work.
Many of the people on the committee had much more experience
with Lisp than you seem to imagine. The state of the art of
the period is not really reflected in ANSI Common Lisp;
only a small, minimally greeable subset is in there.
The ANSI standard is about memorializing the "Common" practice
of the existing vendors, not necessarily about good practice.
Suppose there had been a well-thought out protocol, with years
of experience, and it solved the problem nicely. But also suppose
that only some dominant vendor had this particular feature.
Now imagine that you are one of the various competing vendors;
your main goal is to create an ANSI standard that you will be
complaint with. (That is, you want a standard that describes the
product that you already have, and you very much do not want to
add extra work for yourself,) Further suppose that you might be
rather sick and tired of the community telling you that the
dominant vendor's product is the gold standard, (of which this
functionality this might be small example), while your product
is at best, a second fiddle. How do you vote?
Suppose that the winning extensible hash table protocol is based
on object-oriented programming, and that there is disagreement on
which OO extensions to Lisp are best. It is not clear if there
will be any OO in the standard - the CLOS committee is working
in parallel with your committee. Maybe CLOS will not be be adopted.
And maybem,while hash table performance is critical to you, OO
performance is a general problem, or at least in your implementation,
and that you don't want to be forced to reimplement your hash tables
and at the same time slow it down (and things dependant on it) down
in the process. Maybe the dominant vendor does not even propose
their winning hash table protocols, and maybe nobody else suggests
that it's even a problem. Maybe everyone has much bigger fish to fry.
The above is a hypothetical thought experiment, but illustrative.
People were motivated at various times by exactly those factors.
(I don't know anything about proposals for this particular feature.)
I do not mean to cast any aspersions or make any specific suggestion
here about any particular vendor. Everybody who was on the committee
worked very hard to come up with something "good". But whether one
is "adopting a common practice" or "innovating" is a judgement call.
Technical abstractions might not be the deciding factor of "goodness".
Also, committee work is extremely expensive, taking critical resources
away from struggling companies. (By which I mean All of the companies.)
And the committe is on some deadlines. (To some degree, at least some
of the vendors - maybe most - didn't even really want any ANSI standard
at all at the time, but were forced into it by politics!)
If someone wants to propose a hash table extension protocol, I recommend
a careful study of the extension protocols used by the past and current
vendors. . (I strongly suggest including the Symbolics hash and "table"
system circa 1998 in this study.) Also, consider how you may and may not
extend the ANSI standard hash table functions, whether some "generic table"
system might be a better way of providing the functionality to applications,
and the performance implications and other features and implementation
constraints (GC, locking, etc.) involved in these. And, of course, look to
see what protocols are available in recently invented programming languages
so we can steal any good ideas that might have been missed.