Re: Hash Tables and GC

[Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>]

>    Add a keyword parameter :TEMPORARY to MAKE-HASH-TABLE.  If this
>    argument is specified and not NIL, and if :TEST is #'EQ or #'EQL,
>    entries in the table may be removed by the GC if the key (i.e.,
>    an object EQ or EQL to the key) IS ACCESSIBLE ONLY THROUGH THE
>    TABLE.  Entries in EQUAL tables are never so removed, nor are
>    numbers in EQL tables.  [Explanation: in these cases, it is
>    generally possible to construct new objects that are respectively
>    EQUAL or EQL to the key.]
> 
> Numbers and Characters could never be removed from EQL tables, because
> they ARE always accessible in other ways.  But what is the rationale for
> PROHIBITING the removal of an entry from an EQUAL hash table if its
> key is in fact accessible ONLY through the table?  E.g., defstruct
> instances and symbols can be legitimately used as keys in an EQUAL hash
> table, so an implementation that removed them from EQ hash tables
> would be able to remove them from EQUAL tables as well.

You are quite correct; I neglected to include characters with numbers
as objects that could not be removed from EQL tables and also to
consider the cases where EQUAL was equivalent to EQL (for EQUAL hash
tables).  The latter point is important because it makes EQUAL tables
less of a special case.  Thank you for bringing it up.

> Note that
> all discussions of this topic have considered an implementation correct
> even if it NEVER removed entries, and I don't recall anyone implying
> that an implementation that did remove entries was required to remove
> ALL removable entries.

I agree.  Moreover, there will be times when removable entries have
not yet been removed even if they will be removed eventually.

Or, consider lists in EQUAL tables.  I would not expect list-key
entries to be removed even though some might be removable in principle
when they contain EQ-unique objects accessable only through the table
entry.

-- Jeff