EQUAL, and hash tables, and value/object distinctions

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

re: For example, one cannot construct a hash-function for #'= unless you limit
    the valid keys to not include both a floating point number and two
    integers that both coerce to that same float.

You must be referring to the bug in CLtL, p194:

  "When rational and floating-point numbers are compared or
   combined by a numerical function, the rule of floating-point
   contagion is followed: ..."

I believe that this should read:

  "When rational and floating-point numbers are 
   combined by a numerical function, the rule of floating-point
   contagion is followed: ..."

Float conversion is an inherently information-losing process; this is,
of course, fine for situations where there will most likely be information
loss anyway ,due to rounding and/or truncation [such as in "combination by 
a numerical function"].  But numerical equality and inequalities are not
information losing, and should in fact be transitive relations.  About 
one year ago, I pointed out this difficulty to Guy Steele with some well-
chosen examples; and he was quite shocked -- indeed it was his intention 
that "=" be a true equivalence predicate.

Lucid's 3.0 release performs "appropriate contagion" in the case of
numerical comparisons, in order to preserve transitivity.


re: Hash tables aren't so complicated that one can't construct them
    yourself.  My guess (and only a guess) is that the only reason they're
    included in the language spec is to give a portable way of hashing on
    %pointer where that might be useful.  SXHASH would have been enough, and
    that allows easy implementation of the common case of EQUAL hash tables,
    too.  

Efficient hash tables are! ["so complicated that one can't construct them ...].
Both Lucid and Symbolics hide a lot of implementation-dependent knowledge
deep within the bowels of CL hash-tables; even if the average Lisp programmer
were "smart enough" to defend his ego on hash-tables, he probably wouldn't
have reasonable access to all the system internals that the vendor wizards do.

In fact, I have heard some C programmers praise Common Lisp for it's inclusion
of hash-tables.  They complain and complain about having to reinvent the
wheel (hash-tables) over and over again.



re:    Date: Thu, 30 Jun 88 12:40:54 PDT
       From: jrose@Sun.COM (John Rose)
       . . . 
       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))
    Yes, but the equality-predicate must be transitive over the domain of
    possible keys in order for a hash-function to work.

This point that you [Greenwald] are making seems not to be generally
appreciated.  The fact that many many experts pored over the Common 
Lisp design, and still thought that numerical equality as defined by 
"="  was an equivalence relation shows how easy it is to miss closure
on transitivity.



-- JonL --