Issue: HASH-TABLE-KEY-MODIFICATION (Version 1)

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

Issue:         HASH-TABLE-KEY-MODIFICATION

References:    CLtL page 282, page 168 (last paragraph in 10.2)

Category:      CLARIFICATION

Edit history:  Version 1, 12-Sep-88, Moon, for discussion

Problem description:

CLtL is silent about what happens if you modify a component of an object
that is used as a hash-table key.

Proposal (HASH-TABLE-KEY-MODIFICATION:SPECIFY):
	  
In EQ and EQL hash tables, components of a key may be freely modified
with no effect on the table.

In EQUAL hash tables, it is an error to modify a component of a key.

If implementations define additional acceptable values for the :TEST
argument to MAKE-HASH-TABLE, the rule is that it is an error to modify
a component of a key if and only if that component affects the test
function.  If that component cannot affect the test function, the hash
table's operation must not be affected by modifying the component.

Test Cases/Examples:

(setq ht (make-hash-table :test #'eq))
(setq a (cons 1 2))
(setf (gethash a ht) 'win)
(setf (cdr a) 3)
(gethash a ht 'lose) => win t

The same example with :test #'equal in the first line would be an
error.

The following example is not an error, because EQUAL does not examine
the components of general vectors:

(setq ht (make-hash-table :test #'equal))
(setq a (vector 1 2))
(setf (gethash a ht) 'win)
(setf (aref a 1) 3)
(gethash a ht 'lose) => win t

Rationale:

EQ and EQL hash tables use the identity of the object as the key, while
EQUAL hash tables use the structure of the object as the key.  Component
modification changes the structure of an object, while the identity of
an object cannot be changed in Common Lisp.

Making component modification of a key of an EQUAL hash table be an error,
rather than requiring it to signal an error, requiring the table to behave
like ASSOC :TEST #'EQUAL, or requiring SETF of GETHASH to copy the key so
that the table is not affected, minimizes the impact on implementations.

This is a generalization of the warning on p.168 of CLtL.

Note that this proposal implies that it is invalid to use an overly
general hash function, such as SXHASH, as the hash function for EQ or
EQL hash tables.  The value of SXHASH can be affected by component
modifications, and this is likely to cause hash table entries to become
inaccessible.

Current practice:

I am not aware of any implementations that do not conform to the proposal.

Cost to Implementors:

Most implementations probably already conform.  It is possible that some
implementations might have to use a different hash function in their
implementation of some hash tables in order to conform.

Cost to Users:

None.

Cost of non-adoption:

Users would not be sure whether they were allowed to perform side effects
on objects that might have been used as keys of hash tables.

Benefits:

More specific language semantics.

Esthetics:

More specific language semantics.

Discussion:

Discussion on the Common-Lisp mailing list was in favor of this.