[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: goldman@vaxa.isi.edu*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*: common-lisp@sail.stanford.edu*In-reply-to*: goldman@vaxa.isi.edu'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 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

**References**:**re: EQUAL, and hash tables, and value/object distinctions***From:*goldman@vaxa.isi.edu

- Prev by Date:
**re: EQUAL, and hash tables, and value/object distinctions** - Next by Date:
**[Re: EQUAL]** - Previous by thread:
**re: EQUAL, and hash tables, and value/object distinctions** - Next by thread:
**[no subject]** - Index(es):