EQUAL, and hash tables, and value/object distinctions

[Jon L White <edsel!jonl@labrea.stanford.edu>]

[have been out of town for some time, and under other time constraints,
so apologies in advance for replying to "old mail"]

re: First, if EQUAL is going to descend structures and arrays to test
    for isomorphism, it should compare hash tables for equality
    according to their contents.  That is, it should verify
    that two possibly-equal hash tables have the same set of
    keys, and that for each key the two stored values are EQUAL.
    Key equality testing must be done using each table's
    key comparison function.

That's a lot of very strong words for what must be considered an
opinion on how EQUAL could be extended to the case of hash-tables.
The difficulty is that EQUAL has, until now, been a very low-level
simple-minded component-wise equivalence test.  What you are proposing 
is something that looks much more grandiose than even EQUALP.  While
I might see some partial utility in these relations that equated
more things (e.g., 3/2 and 1.5 are EQUALP), and those that refined
EQUAL (e.g., "graph-isomorphism" equates fewer things than EQUAL),  I 
don't see why EQUAL should bear the burden of being anything more than 
a "simple-minded component-wise equivalence test."

re:    Date: Wed, 29 Jun 88 18:57:09 PDT
       From: Jon L White <edsel!jonl@labrea.stanford.edu>

       . . .  At one time, there was a suggestion that hash tables admit 
       a user-supplied equivalence predicate; but it never got very far for  
       just this reason, that the equivalence predicate must be *** paired up**
       with an appropriate "numericalizer" function, and many implementors felt
       that users wouldn't understand these issues and wouldn't be able to 
       construct up their own versions of sxhash to go with their alleged 
       equivalence predicates. 

    Yuck.  Who are these brilliant Implementors, that we may all worship
    at their feet?  For they are the curators of such profound knowledge as
	   (EQUALITY-PREDICATE X Y)   ==>   (= (HASH-FN X) (HASH-FN Y))
    If we mere Users cannot be trusted with such wisdom, how are we to
    navigate the Streams of Extensibility, or handle the Objects of
    Genericity?  Oh great Implementors, save us, we pray, from overmuch
    functionality.
    Seriously, I hear an alarming amount of condescension in the above 
    reasoning.
    The above logical implication is ALL THAT IS NEEDED to construct an
    appropriate hash function.  It is the sole and fundamental insight which
    makes hash tables work; I have relied on it for years, building many a
    hash table in various extensible frameworks.  What's the problem of
    requiring a hash-table builder from promising that his hash and equality
    functions bear the simple relation to each other?  And if he can't

There is no :HASH-FN argument to make-hash-table in CL; and I presume you
mean the :TEST argument when you say :EQUALITY-PREDICATE?  The last time
on this mailing list that I suggested having user-suppled equivalence
predicates for hash-tables, there was:
   (1) a lot of argumentation over what to call the replacement for SXHASH
       [a ":test" argument isn't enough, if you give an equivalence relation
       for which the system-supplied SXHASH function isn't "good enough" in 
       the sense I spoke about before]
   (2) comments from Symbolics folks that they had discussed these ideas
       internally, and rejected them because of the potential for confusion
       over the SXHASH correlation issue.
You might try asking Dave Moon what the issues were, if you are really
interested.  It may be that the close link between methods on EQUAL and
methods on SXHASH is one reason that CLOS doesn't say much about EQUAL.


-- JonL --