re: EQUAL, and hash tables, and value/object distinctions

[goldman@vaxa.isi.edu]

      Proposal:  EQUAL should check for isomorphism of hash tables.
I think that's fine;  the issue is what properties define, and thus derive
from, two hash tables being isomorphic.

      An interesting question arises when two hash tables have
      different key equality predicates, and (suppose) we've already
      decided to treat equality predicates as implementation details,
      and ignore them directly.  Here's one answer:  Declare two
      hash tables EQUAL if they include each other.  That is, for
      every key K in hash table A, require that
	      (EQUAL (GETHASH A K) (GETHASH B K *UNIQUE-UNKNOWN-VALUE*))
      and the same for every key in table B.

I definitely do not like that definition.  I don't think that two
hash tables with different equality predicates should be considered
EQUAL unless they are both EMPTY.  
Rationale:  A hash table is best though of as a mapping from (a subset of) the
EQUIVALENCE CLASSES of an equivalence predicate to associated values.
The fact the CommonLisp's functions for dealing with hash tables
(GETHASH, MAPHASH) deal with an equivalence class through an exemplary
member of the class should not lead us astray.  The suggested semantics, as
I read it, makes the issue of whether two hash tables are EQUAL dependent
on which exemplars happen to be stored.
For example, suppose HEQ and HEQUAL are hash tables, with equivalence 
predicates EQ and EQUAL, respectively.  Further suppose
	   (EQUAL xxx '(a b c))  and  (EQUAL yyy '(a b c)) , but
			    (NOT (EQ xxx yyy))
if I do (setf (gethash xxx HEQ) 1  (gethash yyy HEQUAL) 1)
then, by my reading of the above definition,
   (NOT (EQUAL HEQ HEQUAL))
because the key yyy, in HEQUAL, is not a key in HEQ.  But if I do
 (setf (gethash xxx HEQ) 1  (gethash xxx HEQUAL) 1)
then they are EQUAL.  I claim that the choice between two different
exemplars of an E equivalence class should be transparent for a
hash table with equivalence predicate E.  

I would define EQUALity of hash tables H1 and H2 in the following
manner:

either H1 and H2 are both empty, or 

the suggested mutual inclusion definition, with the added requirment
that H1 and H2 have the same equivalence predicate.

Note that this does not imply that MAPHASH applied to the two tables will
generate the same sequence of key/value pairs -- the ordering used by
maphash is an implementation detail, and could even change from one
invocation to another on the same, unaltered, hash table.

Also, "it is an error" to destructively modify a value that has been used
as a key for a hashtable of equivalence E (or obtained via a MAPHASH
over such a hashtable) in a manner that changes the E-class to which it
belongs.  I.e., the following is an incorrect program:

(setf h (make-hash-table :test 'equal)
      xxx '(a b c))
(setf (gethash xxx h) 1)
(setf (second xxx) nil)

Neil