srt@aerospace.aero.org (Scott "TCB" Turner) (08/16/90)
Is there a mechanism in Common Lisp (specifically AKCL) for weak reference? By weak reference I mean a reference that won't prevent garbage collection if no other references exist. -- Scott Turner
mayer@hplabsz.HPL.HP.COM (Niels Mayer) (08/17/90)
In article <81084@aerospace.AERO.ORG> srt@aero.org (Scott "TCB" Turner) writes: >Is there a mechanism in Common Lisp (specifically AKCL) for weak >reference? By weak reference I mean a reference that won't prevent >garbage collection if no other references exist. > > -- Scott Turner Sorry, I don't know, infact I'd like to find out more about weak references. Does anybody have any pointers to articles on this subject? What do weak references buy you? How do they affect performance? Why do you want them? How do you use them? Thanks. ------------------------------------------------------------------------------- Niels Mayer -- hplabs!mayer -- mayer@hplabs.hp.com Human-Computer Interaction Department Hewlett-Packard Laboratories Palo Alto, CA. *
murthy@algron.cs.cornell.edu (Chet Murthy) (08/17/90)
mayer@hplabsz.HPL.HP.COM (Niels Mayer) writes: >In article <81084@aerospace.AERO.ORG> srt@aero.org (Scott "TCB" Turner) writes: >>Is there a mechanism in Common Lisp (specifically AKCL) for weak >>reference? By weak reference I mean a reference that won't prevent >>garbage collection if no other references exist. >> >> -- Scott Turner >Sorry, I don't know, infact I'd like to find out more about weak >references. >Does anybody have any pointers to articles on this subject? What do weak >references buy you? How do they affect performance? Why do you want them? >How do you use them? I know that there is such a facility (weak pointers) in the SML-NJ (Standard ML of New Jersey) system. --chet--
barmar@think.com (Barry Margolin) (08/18/90)
In article <81084@aerospace.AERO.ORG> srt@aero.org (Scott "TCB" Turner) writes: >Is there a mechanism in Common Lisp (specifically AKCL) for weak >reference? By weak reference I mean a reference that won't prevent >garbage collection if no other references exist. No, there is no such thing in Common Lisp. Some Common Lisp implementations (Symbolics Genera 8.0 and Lucid, I believe) have an extension to hash tables that implements weak references to the keys. If the only reference to an object is as the key in such a hash table it may be removed from the hash table (along with the value) and may then be GCed. The implication is that MAPHASH won't necessarily see all the associations that were installed into a weak hash table. I haven't heard of any other types of weak references being implemented. I think they're only feasible in cells that are allowed to reference nothing. Hash table entries meet this requirement because entries may be removed; symbol value cells and CLOS slots can be "unbound", so weak references are possible there. But it wouldn't make sense to have a weak reference from a cons cell -- what does CAR return if the object had been GCed (I suppose you could wimp out and say that cells that aren't allowed to be unbound must be set to NIL)? -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
wright@utopia.rice.edu (Andrew Wright) (08/19/90)
In article <44659@cornell.UUCP> murthy@algron.cs.cornell.edu (Chet Murthy) writes: >>In article <81084@aerospace.AERO.ORG> srt@aero.org (Scott "TCB" Turner) writes: >>>Is there a mechanism in Common Lisp (specifically AKCL) for weak >>>reference? By weak reference I mean a reference that won't prevent >>>garbage collection if no other references exist. >I know that there is such a facility (weak pointers) in the SML-NJ >(Standard ML of New Jersey) system. I think Chet must be referring to "weak types" of standard ML. SML's weak types have nothing to do with what the original poster intended. SML may be thot of, loosely, as lisp with a static polymorphic type system. Reference cells are given a "weak" or "imperative" type in order that they interact properly with polymorphism. The semantics of imperative types are presented in "The Definition of Standard ML", by Milner, Tofte and Harper, MIT Press 1990, and are explained in more detail in Tofte's Phd thesis (Edinburgh). The term "weak" refers to an extension of "imperative" as implemented by Appel and MacQueen in Standard ML of New Jersey, and described only very briefly in the release documentation. Andrew K. Wright Computer Science, Rice University wright@rice.edu Houston Texas 77251-1892
wright@utopia.rice.edu (Andrew Wright) (08/21/90)
In article <1990Aug18.190312.25603@rice.edu> I wrote: >In article <44659@cornell.UUCP> murthy@algron.cs.cornell.edu (Chet Murthy) writes: >>>In article <81084@aerospace.AERO.ORG> srt@aero.org (Scott "TCB" Turner) writes: >>>>Is there a mechanism in Common Lisp (specifically AKCL) for weak >>>>reference? By weak reference I mean a reference that won't prevent >>>>garbage collection if no other references exist. > >>I know that there is such a facility (weak pointers) in the SML-NJ >>(Standard ML of New Jersey) system. > >I think Chet must be referring to "weak types" of standard ML. >SML's weak types have nothing to do with what the original poster intended. It seems that buried in the debugger source that comes with the New Jersey implementation there is an abstraction that implements weak pointers like the original poster was seeking, but this module is not available to programmers. So while I may have leapt too far to the conclusion that Chet was thinking of weak types, weak pointers are not really in the New Jersey implementation, and are definitely not in the standard. Andrew K. Wright Computer Science, Rice University wright@rice.edu Houston Texas 77251-1892
krulwich@ils.nwu.edu (Bruce Krulwich) (08/21/90)
Regarding weak reference: In article <41670@think.Think.COM>, barmar@think (Barry Margolin) writes: >I think they're only feasible in cells that are allowed to reference >nothing. Hash table entries meet this requirement because entries may be >removed; symbol value cells and CLOS slots can be "unbound", so weak >references are possible there. But it wouldn't make sense to have a weak >reference from a cons cell -- what does CAR return if the object had been >GCed (I suppose you could wimp out and say that cells that aren't allowed >to be unbound must be set to NIL)? This problem becomes easier to manage if dereferencing a weak pointer had to be done explicitly, similar to T's OBJECT-HASH and OBJECT-UNHASH. Abstracting away from T's version for a minute, you could have: (MAKE-WP <obj>) -- return a weak pointer to <obj> (WP-DEREF <wp>) -- return the value pointed to (weakly) by <wp> Then the question would not be "what should be done to <wp> when its <obj> is GC'ed," as barmar seems to say above, but rather "what should WP-DEREF return when <wp>'s <obj> has been GC'ed." One answer to this question is to model WP-DEREF after GETHASH, and in the case where <wp>'s <obj> has been GC'ed have it return NIL or a user-specified DEFAULT. Bruce Krulwich krulwich@ils.nwu.edu
sfk@otter.hpl.hp.com (Steve Knight) (08/22/90)
Niels Mayer asks: > Does anybody have any pointers to articles on this subject? What do weak > references buy you? How do they affect performance? Why do you want them? > How do you use them? Although Common Lisp does not provide a standard mechanism for implementing weak references, some implementations provide hash-tables in which the entries can be garbage collected when the key or value or either becomes garbage. These can be used to implement weak references. In Pop11 they are called "temporary" properties. I believe they are called "populations" in Scheme. They have a number of uses. The simplest use is attaching information to data structures without having to declare extra fields in the data structure. Temporary properties allow you to do this without making the data structures permanent. Another typical use is for sparse information, such as sparse arrays, in which considerable memory savings might be made. Sometimes they are useful to provide ways of iterating over all members of a set without making the members of the set permanent. For implementations (such as Poplog Common Lisp) in which it is possible to mark entries as garbage collectable if either key or value becomes garbage, it is convenient to represent two-way relations without nasty store implications. The cost of temporary properties is to make the garbage collection algorithm slightly more complicated & to necessitate rehashing after GC. These are typically small costs. I hope these quick comments are useful. Steve Knight
gjc@paradigm.com (08/23/90)
In article <41670@think.Think.COM>, barmar@think.com (Barry Margolin) writes: > > Some Common Lisp implementations ... > If the only reference to an object is as the key in such a > hash table it may be removed from the hash table (along with the value) and > may then be GCed. You *have* to mention that that would only be reasonable for EQ hash tables. Not for EQUAL hash tables, or any other predicate you can think of. -gjc
sfk@otter.hpl.hp.com (Steve Knight) (08/23/90)
>> Some Common Lisp implementations ... If the only reference to an object >> is as the key in such a hash table it may be removed from the hash table >> (along with the value) and may then be GCed. > You *have* to mention that that would only be reasonable for EQ hash tables. > Not for EQUAL hash tables, or any other predicate you can think of. 99.9% true. You can use EQUAL "temporary" hash-tables to implement uniquely allocated datatypes (ie. values for which EQ implies EQUAL). Steve
krulwich@ils.nwu.edu (Bruce Krulwich) (08/23/90)
In article <276@paradigm.com>, gjc@paradigm writes: >In article <41670@think.Think.COM>, barmar@think.com (Barry Margolin) writes: >> Some Common Lisp implementations ... >> If the only reference to an object is as the key in such a >> hash table it may be removed from the hash table (along with the value) >> and may then be GCed. > >You *have* to mention that that would only be reasonable for EQ hash tables. > >Not for EQUAL hash tables, or any other predicate you can think of. Not necessarily. First of all, the behavior being discussed is only an option and is not correct default behavior in any case. Given this, it's clear that a user may decide that he/she wants this behavior for EQUAL tables as well as for EQ ones. For example, if someone was using EQUAL hash tables to cache computation results in a backward-chaining system (say, mapping propositions onto the leaves of a proof tree that need to be true for the proposition to be true) then the programmer may decide that the savings in computation is only worthwhile in cases when there is no memory tradeoff (i.e., when the structures have to be kept in memory for other reasons already), but when they can be GC'ed then it's worth redoing the computation to keep memory size down. Regardless of whether you agree with my example here (which was a bit off the cuff), it seems clear that this is a feature which would be an option, and not the default behavior, and which a programmer may very well want as an option for non-EQ-based hash tables. Bruce Krulwich Institute for the Learning Sciences
jeff@aiai.ed.ac.uk (Jeff Dalton) (08/27/90)
In article <1350026@otter.hpl.hp.com> sfk@otter.hpl.hp.com (Steve Knight) writes: > >Although Common Lisp does not provide a standard mechanism for implementing >weak references, some implementations provide hash-tables in which the >entries can be garbage collected when the key or value or either becomes >garbage. These can be used to implement weak references. In Pop11 they >are called "temporary" properties. I believe they are called "populations" >in Scheme. T (A dialect of Scheme) has populations. I don't know of any other Scheme that does. A polulation is what is sometimes known as a "weak set". It's isn't a mapping from keys to values, just from objects to true or false (depending on whether or not the object is in the population). T, and perhaps some other dialects of Scheme, have an operation called object-hash that returns a weak pointer, plus object-unhash for going back from a weak pointer to the corresponding object. Lisp/VM had hash tables that were weak for (I think) one of either keys or values (I forget which). I happen to prefer the hash table approach over that of explicit weak pointers. I also think Pop11 is right to allow hash tables (called "properties") to be used as functions and to allow programmers to specify their own test and hash functions. Moreover, I think hash tables in Common Lisp are much less useful than they ought to be, because putting something in a hash table prevents it from being garbage collected. -- Jeff
net@tub.UUCP (Oliver Laumann) (08/28/90)
In article <3289@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: > T (A dialect of Scheme) has populations. I don't know of any other > Scheme that does. C-Scheme release 7 (and probably earlier releases as well) has populations and weak conses, too (see runtime/hash.scm). Regards, -- Oliver Laumann net@TUB.BITNET net@tub.cs.tu-berlin.de net@tub.UUCP
lgm@cbnewsc.att.com (lawrence.g.mayka) (08/29/90)
In article <3289@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >Moreover, I think hash tables in Common Lisp are much less useful than >they ought to be, because putting something in a hash table prevents >it from being garbage collected. Symbolics Genera 8.0 offers a keyword option to MAKE-HASH-TABLE called :GC-PROTECT-VALUES. If NIL, table entries are automatically deleted if a value becomes unreachable other than through the table. I urge Common Lisp vendors to standardize on something like this. Lawrence G. Mayka AT&T Bell Laboratories lgm@iexist.att.com Standard disclaimer.
stephen@estragon.uchicago.edu (Stephen P Spackman) (09/04/90)
In article <1350026@otter.hpl.hp.com> sfk@otter.hpl.hp.com (Steve Knight) writes:
The cost of temporary properties is to make the garbage collection
algorithm slightly more complicated & to necessitate rehashing after GC.
These are typically small costs.
Depending on how you do things, the necessity of rehashing after GC is
quite possibly there anyway. And you can always defer rehash until
first reference.
The biggest cost in *my* implementation was the manhours tracking down
the bug where having an object that was the key of an object that was
its key made the two objects get their first cells mixed up.... :-)
stephen "Well I *had* a correctness proof, I guess I left it in the
caf, and it's really a very simple algorithm anyway, what could go
wrong?" p spackman stephen@estragon.uchicago.edu 312.702.3982