[gclist] Re: weak pointer and gc

[William D Clinger]

Let me suggest a very general mechanism that is useful
for gc research, can be used to implement weak pointers,
certain limited forms of finalization, et cetera, and
isn't too hard to implement.  This mechanism was used to
reclaim useless symbols in both MacScheme and in Larceny.

For historical reasons this low-level primitive is named
"sro".  Here is an excerpt from its Larceny documentation.

    (sro pointer-tag type-tag limit) => vector

    SRO ("standing room only") is a system primitive that
    traverses the entire heap and returns a vector that
    contains all live objects in the heap that satisfy the
    constraints imposed by its parameters:

    If pointer-tag is -1, then object type is unconstrained;
    otherwise, the object type is constrained to have a pointer
    tag that matches pointer-tag....
    If type-tag is -1, then object type is unconstrained by
    type-tag; otherwise, only objects with a matching type-tag
    are selected (after selection by pointer tag)....
    Limit constrains the selected objects by the number of
    references. If limit is -1, then no constraints are imposed;
    otherwise, only objects (selected by pointer-tag and type-tag)
    with no more than limit references to them are selected. 

    For example, (sro -1 -1 -1) returns a vector that contains
    all live objects (not including the vector), and (sro 5 2 3)
    returns a vector containing all live flonums (bytevector-like,
    with typetag 2) that are referred to in no more than 3 places.

To reclaim useless symbols, for example, you can use this
sro primitive to find all of the symbols that are referenced
from only one place.  If any of those symbols are in the
symbol table, it's safe to remove them.

The sro operation is very expensive, worse than a full garbage
collection, so you don't want to use it very often.  For things
like weak pointers, that's probably ok.

Will