EQUAL, and hash tables, and value/object distinctions

[jrose@Sun.COM (John Rose)]

   Posted-Date: Tue, 05 Jul 88 17:49:37 PDT
   From: goldman@vaxa.isi.edu
   Date: Tue, 05 Jul 88 17:49:37 PDT
   Sender: 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.
Good rationale.  OK, the "hash"-ness is abstracted away when
thinking about hash table semantics, and the equivalence class
structure should remain, abstracting away from the specific
keys.  So a hash table is "really" a finite map over a set
of equivalence classes.

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

There's one sticky problem when we concentrate on equivalence
classes rather than exemplars:  Equivalence classes are defined
via equivalence predicates, which in Lisp are algorithms.
So, if user-defined hash tables are ever supported,
we need to carefully design a notion of "same equivalence
predicate".  Equivalence of algorithms is undecidable,
and so we need a narrower notion predicate equivalence.
(That's why I was trying to ignore the predicates altogether;
it finesses this problem.)

This isn't an issue yet, of course.  EQ can distinguish
#'EQ, #'EQL, and #EQUAL.

Incidentally, what should happen to user-defined hash tables
when their predicates or hash functions are redefined?
There is a CLOS hook MAKE-INSTANCES-OBSOLETE which could
be used to re-construct all instances of the affected
table type.

   Neil
				-- John