[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: hash tables and GC
- To: jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK
- Subject: Re: hash tables and GC
- From: David L. Andre <DLA@JASPER.SCRC.Symbolics.COM>
- Date: Mon, 29 Aug 88 12:06 EDT
- Cc: barmar@THINK.COM, email@example.com, DLA@JASPER.SCRC.Symbolics.COM
- In-reply-to: <firstname.lastname@example.org>
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.
Pop11 has a similar capability as "temporary properties".
(For this purpose, we can think of Pop as Lisp with a different
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.
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