[PATCH] Add user-facing weak pair API

[Peter Bex]

Dear hackers,

At the Village CHICKENs event, I gave a presentation about how we could
add "proper" support for weak pairs, so that they can be exposed to the
user.  Right now we have half-baked support for weak pairs as a hidden
implementation detail of the symbol table.

This would be useful for users, but also for core: this would make it
easier to support line numbers in the interpreter without unbounded
memory usage - the expression in source code would be the key, the line
number where it occurs would be the value in the database.  When an
expression gets discarded because nothing hangs on to it, we can drop
the corresponding entry from the database.

Slides of the talk are here:
https://code.more-magic.net/weak-refs-for-chicken/tree/weak-refs.org

I also expect to publish a more accessible writeup of this on my blog,
but don't hold your breath - it may take a while.

Attached are 5 patches to add the weak pair support.  I've also pushed
this to the git repo under the "user-facing-weak-pairs" branch.

The patches contain more information about the specific approach.
Especially of interest is the trick to build a linked list in the
"dead space" of the old cdr that is still allocated behind forwarding
pointers of weak pairs that makes this efficient.  I've taking this
idea from MIT Scheme, see "src/microcode/gcloop.c" in their source
code repository for more info.  Viewable online at:
https://git.savannah.gnu.org/cgit/mit-scheme.git/tree/src/microcode/gcloop.c?id=545efe9dcaac695d4d5c34de7497543b8dd4f2b0#n789

Even though we take this neat trick from MIT Scheme, I decided not to
use their API as it is a bit awkward.  It may be more Schemely as
weak pairs are completely distinct from regular pairs in MIT Scheme,
but there's an issue with the way you can detect broken weak pairs;
you have to follow the pattern in the manual where you access the
pair to make sure it wasn't actually storing #f.  See here:
https://web.mit.edu/scheme_v9.2/doc/mit-scheme-ref/Weak-Pairs.html

Instead, this set of patches follows the Chez Scheme API: it adds
only three procedures: weak-cons, weak-pair? and the
broken-weak-pointer? predicate, whilst all the regular pair operations
transparently accept either regular or weak pairs.  It is much more
expedient as it means you get to use all the list operators, and you
get printing of weak pairs for free, since they get serialized like
regular pairs.  And it's extensible - if we ever decide to support
"ephemerons", we could also go with the ephemerons API from Chez.

See the following page for more info about Chez's API:
https://cisco.github.io/ChezScheme/csug9.5/smgmt.html#./smgmt:h2

NOTE: Changing locatives to use the "chain of forwarding pointers to
weak container objects" trick (so we can drop the locative table) is
still to be done.

NOTE 2: I wasn't 100% sure if (chicken base) is the best place to put
these new procedures.  We could also add them to a new module, e.g.
(chicken weak-pair) or (chicken weak-pointer) or some such, or add
them to the extant (chicken gc) module (although that's a bit odd
since locatives are in their own rather than under (chicken gc))...
However, it's only three procedures, they sort of "match" cons, pair?
etc in (scheme base), and finally Chez also puts them in their
(chezscheme) module (which kind of makes sense in that it holds the
"core" data types).  This is great bikeshed discussion fodder, of
course.

NOTE 3: I tried to keep the commits bite-sized and form a narrative
of sorts so that it should be easy to understand even if you haven't
seen my talk at the Village CHICKEN event.

Cheers,
Peter

0001-Replace-special-casing-of-weak-symbol-GC-with-generi.patch
Description: Text document

0002-Introduce-a-new-special-value-for-broken-weak-pointe.patch
Description: Text document

0003-Add-new-user-facing-API-procedures-for-weak-pairs-to.patch
Description: Text document

0004-Tweak-list-operations-to-work-for-weak-pairs-too-and.patch
Description: Text document

0005-Add-new-weak-pair-procedures-to-types-database-and-a.patch
Description: Text document

signature.asc
Description: PGP signature