Re: hash tables and GC

[David L. Andre <DLA@JASPER.SCRC.Symbolics.COM>]

    Date: Sat, 27 Aug 88 21:25:34 BST
    From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>

    ...

    It's probably best to have a concrete proposal, so I'll make one:

       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.]

       (*) Actually, I think this should be "accessible only through
       such tables", because something might be in more than one.

    Current practice:

       Pop11 has a similar capability as "temporary properties".
       (For this purpose, we can think of Pop as Lisp with a different
       syntax.)

       T has "weak sets".  T also has OBJECT-HASH and OBJECT-UNHASH,
       which use "weak pointers".  If (OBJECT-HASH object) => i, then
       (OBJECT-UNHASH i) => object if the object is still accessible
       and false if it is not.  i is an integer.

       R2RS Scheme also has OBJECT-HASH and OBJECT-UNHASH, but they
       were not "essential" and have since been removed.

    Issues:

    0. Can such tables be implemented?

Proof by existence:  We have had such tables prototyped internally at
Symbolics for a year or so, but have not had the resources to qualify
them for release to customers.  They can be quite efficient, and of
course can significantly improve the efficiency of some kinds of
programs.