# EQUAL, and hash tables, and value/object distinctions

• To: Greenwald@stony-brook.scrc.symbolics.com
• Subject: EQUAL, and hash tables, and value/object distinctions
• From: Jon L White <edsel!jonl@labrea.stanford.edu>
• Date: Tue, 19 Jul 88 00:05:31 PDT
• Cc: jrose@sun.com, goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu
• In-reply-to: Michael Greenwald's message of Thu, 30 Jun 88 16:36 EDT <19880630203650.3.GREENWALD@SWALLOW.SCRC.Symbolics.COM>

```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 --

```