Re: Hash Tables and GC

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

>     Date: Tue, 6 Sep 88 19:50 PDT
>     From: Gregor.pa@Xerox.COM
> 
> 			This may not be facility we want to add to Common
>     Lisp, but as near as I can tell, weak pointers and finalization are the
>     primitives you need to build these kind of hash tables.
> 
>     In addition, finalization is a useful mechanism to have direct access
>     to.
> 
> Yes.  It's not just useful in hash tables, and it allows multiple
> weak-pointers to the same object. [...]  I'm not sure if there is an
> advantage in having multiple weak-pointers to the same object, but
> still, weak-pointers and finalization provide a lot more flexibility
> than simply implementing temporary hash tables.

Can weak pointers can be implemented using temp-entry tables?  I think
something like the following might work:

(let ((table (make-hash-table :test #'eq :temporary t))
      (inverse (make-hash-table :test #'eq :temporary t)))
  (defun make-weak-pointer (object)
    (let ((wp (gethash object table nil)))
      (when (null wp)
        (setq wp (list "weak pointer"))
	(setf (gethash object table) wp)
        (setf (gethash wp inverse) object))
      wp))
  (defun deref (wp)
    (gethash wp inverse nil))
)

Unfortunately, these weak pointers can't be collected while there are still
references to the corresponding objects.  This suggests that we may want
tables from which entries can be removed when there is no other reference
to the value [or the key?].  Then, if there were no reference to the weak
pointer, the entries in both TABLE and INVERSE could be removed.  Or we
could have tables that hashed both ways.

Oh, well.  Perhaps we *should* look to lower-level primitives.  The reasons
against that approach, though, seem to be the following:

(1) Weak tables are as good as weak pointers for many purposes.

(2) Weak tables are sufficiently useful in their own right that they
    should be provided even if lower-level primitives are also available.

(3) Weak pointers + finalization are insufficient for implementing weak
    tables because one also needs EQ-hashing that is efficient and yet
    doesn't break when used with a GC that moves objects.  [I would be
    pleased to find that I am wrong on this point.]

    [OK, maybe something like this:

       (defun make-weak-table () (make-hash-table))

       (defun weak-gethash (object table)
         (gethash (unique-weak-pointer object) table))

       But when the weak pointer becomes invalid, the table entry
       must still remain.  Enter finalization?]

(4) While it seems possible that weak tables might be accepted as as
    addition to Common Lisp, it seems less likely that finalization
    would be.

-- Jeff