Re: what happened to hash-tables

From: Christopher C. Stacy (cstacy_at_news.dtpq.com)
Date: 09/20/04 

Date: Mon, 20 Sep 2004 03:46:57 GMT

Vassil Nikolov <vnikolov@poboxes.com> writes:

> Pascal Costanza <costanza@web.de> 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.

Relevant Pages

  • Re: What could J4 (or WG4) do (was: INSPECT and TRAILING syntax
    ... my intent was "The reports of the demise of the COBOL *standards ... of time or resources to tackle what you suggest right now. ... If I was on this committee, ... Was the 2002 standard later than anybody wanted it to be? ...
    (comp.lang.cobol)
  • Re: Function designator implicit conversion
    ... If the Committee had meant for the parameter list to be part of the ... it's not the intent. ... Standard says which is what my comment accurately reflected. ... This response seems to support the position I have presented. ...
    (comp.std.c)
  • Re: What could J4 (or WG4) do (was: INSPECT and TRAILING syntax
    ... the National Body representation to WG4, have the resources to carry out ... Then the first priority of the committee should be to get properly resourced ... COBOL standardization process, much less anyone whose primary financial ... So, given that you cannot produce a yardstick for the proposed standard, why ...
    (comp.lang.cobol)
  • Re: OO syntax
    ... You have a few people who are proud of their OO implementations giving good reasons why their particular model should be adopted as a standard. ... I am pointing out that the Lua language doesn't offer objects as a primitive type. ... What Lua does instead is to provide meta-mechanisms and some minor syntactic sugar that allows programmers to create and use objects with whatever kinds of semantics make sense for the programmer and application. ... I am saying that I believe that if the people who advocate the various OO systems for Forth would stop thinking in terms of why their OO system is the best and instead focus on factoring what is common between their systems, the result would be a set of primitives that they could layer their OO system on top of. ...
    (comp.lang.forth)
  • Re: Cohens paper on byte order
    ... A normal user (a programmer working with a common ... the program of the recipient. ... transmission of the AES block. ... defined 'standard' functions for doing the conversion ...
    (sci.crypt)