EQUAL, and hash tables, and value/object distinctions

[Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Fri, 1 Jul 88 15:15 EDT
    From: Barry Margolin <barmar@Think.COM>

	Date: Thu, 30 Jun 88 16:36 EDT
	From: Michael Greenwald <Greenwald@stony-brook.scrc.symbolics.com>

	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.

	(i.e. 
	  (let* ((a (expt 2 56))
		 (b (1+ a))
		 (c (float a)))
	    (values (= a b) (= a c) (= b c)))
	 => NIL T T
	)

    Actually, it's not that difficult to construct such a hash function.
    All it has to do is coerce its argument before hashing, e.g.

I think you are confused.  The problem isn't in having a valid
hash-function ( (DEFUN TRIVIAL-=-HASH (NUMBER) 1) is legal and valid,
but inefficient), the problem is which bucket you put a, b, and c in my
example above.

In other words, what does 
(DEFUN TEST-BARMAR-HASH ()
  (SETF (GETHASH a TABLE) 0) 
  (SETF (GETHASH b TABLE) 1)
  (SETF (GETHASH c TABLE) 2)
  (VALUES (GETHASH a TABLE) (GETHASH b TABLE) (GETHASH c TABLE)))
return?)

Unless you restrict the domain as specified above, you are in a
quandary.   If you coerce them all to long-floats, then 
(TEST-BARMAR-HASH) => 2,2,2
If you coerce them all to integers then (depending on the
implementation) you can get
(TEST-BARMAR-HASH) => 0,1,2 or 0,2,2 or 2,1,2

    (defun =-hash (number)
      (let ((real (realpart number))
	    (imag (imagpart number)))
	(setq number (complex (coerce real 'long-float)
			      (coerce imag 'long-float))))
      <compute the hash>)

    I admit that this isn't a great hash function if you expect your keys to
    include many bignums that are near each other.  But it is guaranteed to
    be a correct hash (assuming <compute the hash> is well behaved).

The hash isn't a problem.  It's the fact that #'= isn't transitive.

						    barmar