Re: Hash Tables and GC

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

> Also, the think the proposal should explicitly state that
> IT IS AN ERROR to apply MAPHASH or HASH-TABLE-COUNT to
> a TEMPORARY hash table. (Alternatively, the proposal could state what
> useful behavior can be relied on for these functions with
> temporary hash tables.  For instance, they could map over / count all
> the non-garbage entries as well as whatever garbage entries had
> not yet been collected.  But would that be useful?)

This question is tied to that of whether temporary tables should be a
variety of hash table or a tables of a new type.  If they are hash
tables, I think it should be possible to apply MAPHASH and HASH-TABLE-
COUNT (with the understanding that some entries might vanish without
an explicit REMHASH).  It would be too great an inconsistency to
disallow these operations.

Moreover, if we feel the operations *are* useful, that would be an
additional reason to make temporary tables be hash tables.  (This is
the "they would be so like hash tables that they might as well *be*
hash tables" argument.)

However, suppose temporary tables are not hash tables.  Then we might
omit operations like MAPHASH and HASH-TABLE-COUNT, for simplicity, but
also because removability would then follow automatically: there would
be no way to determine that *any* entries had been removed unless there
was some independent reference to the keys, and so entries without such
an independent reference could be removed.  There would be no need to
mention garbage collection in the description of the tables.

[BTW, this suggests that the keyword argument to MAKE-HASH-TABLE might
be :MAPPABLE rather than :TEMPORARY.  Tables that were not mappable
could have entries secretly removed.  Of course, another choice would
be to have :PERMANENT, defaulting to T, instead of :TEMPORARY,
defaulting to NIL.]

The reason I have not advocated this approach is that I suspect that
mapping over temporary tables is useful.  For example, a table where
the values are meant only to be "true" would be a "weak set", presence
in the table indicating membership in the set.  It makes sense to ask
what objects are (still) in the set.

Moreover, implementation of such tables tend to provide mapping
operations.  T, which has weak sets but not the general tables,
provides a WALK-WEAK-SET to map over the set as well as WEAK-SET->LIST
to give a list of the members.  Pop11, which has tables with temporary
entries, also provides a mapping operation.

-- Jeff