hash tables and GC

[Jon L White <edsel!jonl@labrea.stanford.edu>]

re: Interlisp-10 does this for all hash tables, although certain cases of
    keys involving "permanent" objects like SMALLP numbers are never
    automatically removed.  It also looks like pretty complicated code to
    implement it.  At first blush, it seems like it would be much harder
    to do in some incremental GC scheme as it requires scanning all such
    hash tables before recycling objects they contain.

Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented).  The 
clever trick was that the incremental Reference Counting garbage collector 
could be counted upon to tell you a likely candidate: if an entry for the 
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it 
is removeable; because the count of 1 means that that table entry points 
to it and no one else does.  A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).


But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable.  And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.

At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly  to implement the backwards-compatiblity feature of 
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector.   But then, the GC for  Vax/NIL never got done.  The best-laid 
plans of mice and men go oftimes a-garbage-collecting.



-- JonL --