254: Ephemerons and Guardians254: Ephemerons and Guardiansby Marc Nieper-Wißkirchen
This SRFI is currently in draft status. Here
is an
explanation of each status that a SRFI can hold. To provide
input on this SRFI, please send email
to srfi-254@nospamsrfi.schemers.org.
To subscribe to the list,
follow these
instructions. You can access previous messages via the
mailing
list archive.
This SRFI was forked from SRFI 246 on that date.
This SRFI describes three concepts associated with the storage management of a Scheme system, ephemerons, guardians, and transport cell guardians.
An ephemeron is a record structure with a key and a value field.
An ephemeron can be broken. Breaking an ephemeron replaces the
key and value with #f. An implementation of this SRFI
breaks an ephemeron when it proves that the storage occupied by
the key could be reclaimed if the ephemeron were broken.
A guardian is a structure containing objects as guarded or resurrected elements. Initially, guardians are empty. Objects can be added in guarded elements to the guardian by the programmer. An implementation of this SRFI resurrects an element when it proves that the storage occupied by the object could be reclaimed if all guardians in the system were empty. Objects from resurrected elements can be queried and removed from the guardian by the programmer. Instead of the object itself, a representative can be returned.
A transport cell guardian is a structure containing transport cells, similar to a guardian. Whenever an object in a guarded transport cell in the transport cell guardian is moved by the garbage collector, the transport cell is resurrected so that it can be queried by the programmer.
Neither ephemerons nor guardians can be implemented portably in existing standard Scheme, so incorporating them as a standard features in Scheme implementations makes Scheme more expressive, and more portable programs possible.
Ephemerons and guardians have been implemented in many Scheme systems and are incorporated in other programming languages as well, so there is sufficient experience both in terms of use cases and implementability with those features.
Transport cell guardians are trivial to implement in Scheme systems with non-moving garbage collectors. In Scheme systems with moving garbage collections, transport cell guardians or an equally powerful concept are needed to when hash values are to be derived from object addresses.
Use cases for ephemerons are portable implementations of hash tables that hold the keys or the associated values or both weakly.
A use case for guardians is the management of externally allocated resources that need to be eventually freed when all Scheme objects referencing them have been conceptually destroyed by the garbage collector.
Use cases for transport cell guardians are efficient portable
implementations of eq?-based hashing data structures.
This SRFI supersedes SRFI 246. It is recommended that it supersede SRFI 124 as well, and that SRFI 124 be withdrawn. This SRFI renames the datum field of SRFI 124's ephemerons to value field because a datum in Scheme is a particular type of value.
This SRFI extends the reports on Scheme by stipulating that locations can be strongly holding and weakly holding. Except as noted, all newly chosen locations are strongly holding.
As specified in the reports on Scheme, implementations of Scheme are required to be properly tail-recursive. The formal definition of proper tail-recursion can be found in [2]. This SRFI extends the property tail recursive semantics in [2] by replacing the last line
and β, … do not occur within v, ρ, κ, σ
in the garbage collection rule with
and β, … do not occur within v, ρ, κ, σ' where σ = σ'[β', … ↦ v'', …] and β' are weakly holding.
Comment: This extension of the proper tail recursive semantics says that the values stored in weakly holding locations are ignored when the garbage collector determines the locations that can be reclaimed.
This SRFI further stipulates that locations and sequences of locations can be kept alive in the course of a computation.
Finally, it stipulates that objects may be moved in
the course of a computation with the following restriction: If
an object obj1 is moved, every
object obj2 such that eq?
returns #t when applied
to obj1 and obj2 is moved as well.
The procedures in this section are exported by the (srfi
:254 ephemerons-and-guardians ephemerons) library. The
procedure reference-barrier is also exported by
the (srfi :254 ephemerons-and-guardians guardians)
library.
An ephemeron is a record structure with two fields called the key and value fields. The content of the key field is stored in a weakly holding location.
Ephemerons can be broken. When an ephemeron is
broken, the contents of its value field are replaced
with #f.
If the content of an ephemeron's key field denotes a location or a sequence of locations, the ephemeron is broken in the course of the computation if the garbage collector would reclaim the location or sequence of locations if the location denoted by the ephemeron's value field were weakly holding. The ephemeron may be broken in the course of a computation if the Scheme implementation can prove that the location or sequence of locations will not be kept alive in the future of the computation if the ephemeron is broken.
Procedure: reference-barrier obj
If obj is an object such as a pair, string, vector, or bytevector that denotes a location or a sequence of locations, the location or the sequence of locations is kept alive.
Comment: Other procedures may keep locations alive as well.
Procedure: make-ephemeron key value
The make-ephemeron procedure returns a newly
allocated ephemeron with fields key, which should
denote a location or a sequence of locations,
and value.
Procedure: ephemeron? object
The ephemeron? procedure returns #t
if its argument is an ephemeron, and #f otherwise.
Procedure: ephemeron-key ephemeron
The ephemeron-key procedure returns the contents
of the key field of ephemeron if the ephemeron hasn't
been broken, and #f otherwise.
Procedure: ephemeron-value ephemeron
The ephemeron-value procedure returns the contents
of the value field of ephemeron.
Procedure: ephemeron-broken? ephemeron
The ephemeron-broken? procedure
returns #t if ephemeron has been broken,
and #f otherwise.
The procedures of this section are exported by the (srfi
:254 ephemerons-and-guardians guardians) library.
Guardians first appeared in [3].
A guardian is a heterogenous structure with two types of elements, guarded elements and resurrected elements. A guarded element is a record structure with two fields called the object and the representative field. A resurrected element contains a single value.
A guarded element of a guardian can be resurrected. When a guarded element is resurrected, the guarded element is removed from the guardian and a resurrected element containing the content of the representative field of the removed guarded element is added to the guardian.
If the content of a guarded element denotes a location or a sequence of locations, the element is resurrected in the course of the computation when the garbage collector would reclaim the location or sequence of locations if all locations denoted by the fields of guarded elements or by resurrected elements of all guardians were weakly resurrected. The element may be resurrected in the course of a computation if the Scheme implementation can prove that the location or sequence of locations will not be kept alive in the future of the computation if the element is resurrected.
Guardians are represented by a Scheme
procedures guardian. When guardian is
invoked on two Scheme values obj and rep,
where obj should denote a location or a sequence of
locations and rep should not be #f, a
guarded element whose object field contains obj
and whose representative field contains rep is added
to the guardian.
When guardian is invoked on no
arguments, a resurrected element, if available, is removed from
the guardian and its contents returned. If no resurrected
element is available, #f is returned.
Procedure: make-guardian
The make-guardian procedure returns a newly
allocated guardian, initially with no elements.
Procedure: guardian? obj
The guardian? procedure returns #t if
its argument is a guardian, and #f otherwise.
The procedures of this section are exported by the (srfi
:254 ephemerons-and-guardians transport-cell-guardians) library.
Transport (link) cells first appeared in [1].
A transport cell is a record structure with two fields called the key and value fields. The content of the key field is stored in a weakly holding location.
Transport cells can be broken. If the content of its key field denotes a location or a sequence of locations, the transport cell is broken in the course of the computation when the garbage collector reclaims the location or sequence of locations. The transport cell may be broken in the course of a computation if the Scheme implementation can prove that the location or sequence of locations will not be kept alive in the future of the computation if the ephemeron is broken.
A transport cell guardian is a homogeneous structure contain transport cells.
Transport cell guardians are represented by Scheme procedures guardian. When guardian is invoked on two Scheme values key and value, a transport cell with fields key and value is added to guardian and returned to the caller of guardian.
When guardian is invoked on no arguments and it
contains a transport cell whose key may have been moved since
the transport cell was added to guardian, such a
transport cell is removed from guardian and returned
to the caller of guardian. If guardian
contains no such transport cell, #f is returned.
Procedure: current-hash obj
The current-hash procedure returns an exact
integer. If objects obj1
and obj2 such that eq?
returns #t when applied to these objects are not
moved between an invocation of current-hash
to obj1 and an invocation
of current-hash to obj2, both
calls to current-hash return the same exact integer.
Procedure: make-transport-cell-guardian
The make-transport-cell-guardian procedure returns
a newly allocated transport cell guardian, initially containing
no transport cells.
Procedure: transport-cell-guardian? obj
The transport-cell-guardian? procedure returns #t
if its argument is a transport cell guardian, and #f otherwise.
Procedure: transport-cell? obj
The transport-cell? procedure returns #t
if its argument is a transport cell, and #f otherwise.
Procedure: transport-cell-key transport-cell
The transport-cell-key procedure returns the contents
of the key field of transport-cell if the transport-cell hasn't
been broken, and #f otherwise.
Procedure: transport-cell-value transport-cell
The transport-cell-value procedure returns the contents
of the value field of transport-cell.
Procedure: transport-cell-broken? transport-cell
The transport-cell-broken? procedure
returns #t if transport-cell has been broken,
and #f otherwise.
The (srfi :254) and (srfi :254
ephemerons-and-guardians) libraries are a composite of the
libraries described above.
The libraries exports all procedures and syntactic forms provided by the component libraries.
An implementation for Chez Scheme is provided.
Thanks to the members of the SRFI discussion group, to John Cowan for writing SRFI 124 and SRFI 246, and to Kent Dybvig and his collaborators for creating Chez Scheme, its documentation, and the papers on guardians.
© 2024 Marc Nieper-Wißkirchen.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.