[R6RS] Table proposal

Marc Feeley feeley
Sun Apr 24 07:56:48 EDT 2005

On 24-Apr-05, at 4:53 AM, Michael Sperber wrote:

> Marc Feeley <feeley at iro.umontreal.ca> writes:
>> A feature of Emacs Lisp not supported by this proposal is the
>> key-and-value weakness.  This type of weakness means that a key/value
>> binding can only be removed by the system when the key **and** the
>> value are only reachable from the roots through weak references.  I
>> don't think this case is particularly useful (none of the packages
>> distributed with Emacs uses this type of weakness).
> I agree key-and-value weakness is not worthwhile.  Can you cite an
> example where value weakness is useful?
> -- 
> Cheers =8-} Mike
> Friede, V?lkerverst?ndigung und ?berhaupt blabla

Yes.  A simple example is attaching serial numbers to arbitrary
objects.  This is a real example taken from the Gambit runtime
library.  What is needed is a pair of procedures

     (object->serial-number obj)
     (serial-number->object num [default])

to respectively map an object to its serial number (an exact integer),
and to map a serial number to the object it is associated with (default
is returned when the serial number is not currently associated with an
object).  We want the serial numbers to be generated lazily.  Moreover,
we want objects with a serial number to be reclaimed by the garbage 
in a normal way (if an object with serial number is only reachable
weakly then it should be reclaimed).

These procedures can be implemented with two global tables.  Each one
implements the mapping in one of the two directions.  When an object
is passed to object->serial-number for the first time it is added to
both tables.  This way mapping between objects and serial numbers is
fast in both directions.  For the object to serial number direction,
the table is created like this

     (make-table test: eq? weak-keys: #t)

so that the objects (the keys of the table) are held weakly.  For the
serial number to object direction, the table is created like this

     (make-table test: eqv? weak-values: #t)

so that the objects (the values of the table) are held weakly.

Another example is for implementing memoized functions.  The table
maps the function's argument to the result.  You may wish to keep an
argument/result association in the memoization table only for as long
as the result is strongly reachable (perhaps because you know results
take up a lot of space and you are only willing to maintain a
argument/result binding for as long as the program is using the
result).  Of course, if the table uses eq? as the key comparison
procedure, it would make sense to also specify weak-keys = #t.


More information about the R6RS mailing list