[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
EQUAL, and hash tables, and value/object distinctions
- To: firstname.lastname@example.org
- Subject: EQUAL, and hash tables, and value/object distinctions
- From: jrose@Sun.COM (John Rose)
- Date: Wed, 6 Jul 88 13:44:31 PDT
- Cc: email@example.com
- In-reply-to: firstname.lastname@example.org's message of Tue, 05 Jul 88 17:49:37 PDT <8807060049.AA21993@vaxa.isi.edu>
Posted-Date: Tue, 05 Jul 88 17:49:37 PDT
Date: Tue, 05 Jul 88 17:49:37 PDT
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