Issue HASH-TABLE-TESTS

[Jon L White <jonl@lucid.com>]

Issue: 		HASH-TABLE-TESTS

References: 	CLtL, p382 (third paragraph), and p383
            	Issue EQUAL-STRUCTURE
		Issue: CONTAGION-ON-NUMERICAL-COMPARISONS

Category: 	Addition

Edit history:  	26-Sep-88 Version 1 by JonL


Problem Description:

A great many users try to coalesce two equivalent defstruct instances,
or two equivalent pointer arrays, using hash tables; but they are rudely
awakened when they find out that EQUAL is not an appropriate test for
this case, and that there is no :test argument to MAKE-HASH-TABLE which 
will "hash on non-tree structures".



Proposal: HASH-TABLE-TESTS:ADD-EQUALP

With the advent of the issue CONTAGION-ON-NUMERICAL-COMPARISONS, we
can expect EQUALP to be a true equivalence function, and thus a suitable
candidate for the :test function to MAKE-HASH-TABLE.   Hash-tables will 
come in four kinds, the difference being whether the keys are compared 
with EQ, EQL, EQUAL, or EQUALP.



Examples:

> (defstruct foo a b c)
FOO
> (setq x      (make-foo :a 1 :b 'b :c '(1 . 2))
        x-copy (make-foo :a 1 :b 'b :c '(1 . 2)))
#S(FOO A 1 B B C (1 . 2))
> (setq y      #(1 B (1 . 2))
        y-copy (copy-seq y))
#(1 B (1 . 2))
> (setq ht-equal  (make-hash-table :test 'equal) 
        ht-equalp (make-hash-table :test 'equalp))

#<Hash-Table BB1F7B>
> (progn (setf (gethash x ht-equal) t) (setf (gethash x ht-equalp) t) 
         (setf (gethash y ht-equal) t) (setf (gethash y ht-equalp) t))
T
> (gethash x-copy ht-equal)
NIL
NIL
> (gethash x-copy ht-equalp)
T
T
> (gethash y-copy ht-equal)
NIL
NIL
> (gethash (copy-seq y) ht-equalp)
T
T
> 



Rationale:	

Implementing hash-tables efficiently is not an easy task; it makes more
sense for this to be standardly available (implemented by the wizards at 
the Lisp vendor companies) than for individual programmers to keep trying
to re-invent this obscure part of technology.



Current Practice:

Lucid's release 3.0 implements this proposal [some 2.1-level release
supported it "provisionally"].  Symbolics implementation is reputed
to be robust enough to implement this proposal trivially.



Cost to Implementors:

Moderate.  Implementors have already dealt with EQUAL; the only tricky 
part will be ensuring the implication:
    "If 'a' is EQUALP to 'b', then 'a' and 'b' must lie in the
     same collision chain in any given EQUALP hash table"
It has been suggested that merely linear searching a table is an acceptable
implementation technique for CL's hash-tables  [although no serious 
implementation limits itself thus] and that such tables have no "collision 
chains"; but in fact, this is the degenerate case wherein all entries are 
in the same collision chain, so the implication is trivially satisfied.

Some persons prefer to say that the "reprobe sequence will be the same for
the two items", rather than using the term "collision chain"; the meaning 
is the same. 



Cost to Users:

None.  This is an entirely upwards-compatible addition.



Cost of non-adoption:

Continuing bug reports from CL vendors' customers  about why "hashing 
doesn't work" when said customer tries entering pointer-containing objects
other than cons cells into hash tables.  Continuing delay in same
customers work until they figure out a new strategy for identifying
equivalent structures.  More difficulty in debugging their alternatives.



Benefits:

Addresses one aspect of the difficult equivalence problem.  Makes
hash tables usable with the major, remaining equivalence predicate
of CL.  Also as a "side effect", permits case-insensitive hashing
on strings [tables of type EQUAL are case-sensitive on strings]; 
another "side effect" is the abililty to use the CL numeric comparison
"=" for numbers [tables of type EQUAL use EQL on numbers].



Aesthetics:

Reduces the discontinuity between basic equivalence functions and those
usable as equivalence relations in hash-tables.



Discussion:

With the rejection of all the issues related to EQUAL-STRUCTURE, there is 
little or no hope that EQUAL will be "beefed up" to meet the expectations
of so many of the user community on compound structures.   If one wants
a hash-table with a :test function that has fewer equivalence classes 
(i.e.,  does more "coalescing"), then there is no alternative now except 
to use the function EQUALP.