-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsrfi-124.html
317 lines (263 loc) · 14.2 KB
/
srfi-124.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<title>SRFI 124: Ephemerons</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet" href="/srfi.css" type="text/css" />
<style>#content > #right > .dose > .dosesingle,
#content > #center > .dose > .dosesingle
{display:none !important;}</style></head>
<body>
<h1>Title</h1>
Ephemerons
<h1>Author</h1>
John Cowan
<h1>Status</h1>
<p>This SRFI is currently in <em>final</em> status. Here is <a
href="https://srfi.schemers.org/srfi-process.html">an explanation</a>
of each status that a SRFI can hold.</p>
<p>To provide input on this SRFI, please send email to <code><a href="mailto:srfi minus 124 at srfi dot
schemers dot org">srfi-124@<span
class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="https://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-124">archive</a>.</p>
<ul>
<li>Received: 2015-09-06</li>
<li>Draft #1 published: 2015-09-06</li>
<li>Draft #2 published: 2015-10-26</li>
<li>Draft #3 published: 2015-10-29</li>
<li>Draft #4 published: 2015-11-02</li>
<li>Draft #5 published: 2015-11-04</li>
<li>Finalized: 2015-11-06</li>
<li>Revised to fix errata:
<ul>
<li>2020-11-30 (Made <code><a href="#reference-barrier">reference-barrier</a></code> mandatory.)</li>
</ul>
</li>
</ul>
<h1>Abstract</h1>
<p>
An ephemeron is an object with two components called its <em>key</em> and its <em>datum</em>. It differs from an ordinary pair as follows: if the garbage collector (GC) can prove that there are no references to the key except from the ephemeron itself and possibly from the datum, then it is free to <em>break</em> the ephemeron, dropping its reference to both key and datum. In other words, an ephemeron can be broken when nobody else cares about its key. Ephemerons can be used to construct weak vectors or lists and (possibly in combination with finalizers) weak hash tables.
</p>
<p>Much of this specification is derived with thanks from the MIT Scheme Reference Manual.</p>
<h1>Issues</h1>
None at present.
<h1>Rationale</h1>
<p>Weak references are a mechanism for building data structures that point at objects without protecting them from garbage collection. An example of such a data structure might be an entry in a lookup table that should be removed if the rest of the program does not reference its key. Such an entry must still point at its key to carry out comparisons, but should not in itself prevent its key from being garbage collected.</p>
<p>A weak reference is a reference that points at an object without preventing it from being garbage collected. The term strong reference is used to distinguish normal references from weak ones. If there is no path of strong references to some object, the garbage collector will reclaim that object and mark any weak references to it to indicate that it has been reclaimed.</p>
<p>If there is a path of strong references from an object A to an object B, A is said to hold B strongly. If there is a path of references from an object A to an object B, but every such path traverses at least one weak reference, A is said to hold B weakly.</p>
<p>Ephemerons, unlike simple weak pairs, allow the correct handling of
data structures in which the value points to the key. For example, a
record may have a single field holding the key; if it's desired to
use these records as values in a weak hash table using this internal
key, ephemerons are necessary or the table will not really be weak.
</p>
<p>
Ephemerons are considerably heavier-weight than simple weak pairs, because garbage-collecting ephemerons is more complicated than garbage-collecting weak pairs. In MIT Scheme, each ephemeron needs five words of storage rather than the two words needed by a weak pair. However, while the GC needs to spend more time on ephemerons than on other objects, the amount of time it spends on ephemerons can be made to scale linearly with the number of live ephemerons, which is how a copying GC's running time scales with the total number of live objects anyway.
</p>
<h1>Specification</h1>
<p>
<tt>(ephemeron? </tt><em>object</em><tt>)</tt>
</p>
<p>
Returns <tt>#t</tt> if <em>object</em> is an ephemeron; otherwise returns <tt>#f</tt>.
</p>
<p>
<tt>(make-ephemeron </tt><em>key datum</em><tt>)</tt>
</p>
<p>
Returns a newly allocated ephemeron, with components <em>key</em> and <em>datum</em>. Note that if <em>key</em> and <em>datum</em> are the same in the sense of <tt>eq?</tt>, the ephemeron is effectively a weak reference to the object.
</p>
<p>
<tt>(ephemeron-broken? </tt><em>ephemeron</em><tt>)</tt>
</p>
<p>
Returns #t if <em>ephemeron</em> has been broken; otherwise returns #f.
</p>
<p>
This procedure must be used with care. If it returns <tt>#f</tt>, that guarantees only that prior evaluations of <tt>ephemeron-key</tt> or <tt>ephemeron-datum</tt> yielded the key or datum that was stored in <em>ephemeron</em>. However, it makes no guarantees about subsequent calls to <tt>ephemeron-key</tt> or <tt>ephemeron-datum</tt>, because the GC may run and break the ephemeron immediately after <tt>ephemeron-broken?</tt> returns. Thus, the correct idiom to fetch an ephemeron's key and datum and use them if the ephemeron is not broken is:
</p>
<pre>
(let ((key (ephemeron-key ephemeron))
(datum (ephemeron-datum ephemeron)))
(if (ephemeron-broken? ephemeron)
... broken case ...
... code using key and datum ...))
</pre>
<p>
<tt>(ephemeron-key </tt><em>ephemeron</em><tt>)</tt>
</p>
<p>
<tt>(ephemeron-datum </tt><em>ephemeron</em><tt>)</tt>
</p>
<p>
These return the key or datum component, respectively, of <em>ephemeron</em>. If <em>ephemeron</em> has been broken, these operations return <tt>#f</tt>, but they can also return <tt>#f</tt> if that is what was stored as the key or datum.
</p>
<p>
</p>
<p id="reference-barrier">
<tt>(reference-barrier </tt><em>key</em><tt>)</tt>
</p>
<p>
This procedure ensures that the garbage collector does not break an
ephemeron containing an unreferenced key before a certain point in
a program.
The program can invoke a <i>reference barrier</i> on the key by
calling this procedure, which guarantees that
even if the program does not use the key, it will be considered
strongly reachable until after <code>reference-barrier</code> returns.
</p>
<p>Because one cannot reliably operate on ephemerons in a portable
way without calling the procedure <code>reference-barrier</code>,
<code>reference-barrier</code> is mandatory.</p>
<p>The following is an example where <code>reference-barrier</code> is
needed:</p>
<pre>
;; Return the datum component of the ephemeron if its key component is
KEY. Return #f otherwise.
(define (ephemeron-ref ephemeron key)
(let ((k (ephemeron-key ephemeron))
(d (ephemeron-datum ephemeron)))
(and (not (ephemeron-broken? ephemeron))
(eq? key k)
(reference-barrier k)
d)))</pre>
<p>In this procedure, the evaluation of <code>(eq? key k)</code>
is side-effect-free, so it can be evaluated at any time
after <code>k</code> has been retrieved, in particular before the
call to <code>ephemeron-broken?</code>. Without the call to
<code>reference-barrier</code>, <code>key</code> may, therefore, be
no longer referenced when <code>ephemeron-broken?</code> is called.
In that case, this predicate would return <code>#f</code>. In other words,
without the call to <code>reference-barrier</code>, a Scheme
implementation may implement the above procedure as
<code>(define (ephemeron-ref ephemeron key) #f)</code>.</p>
<h1>Implementation</h1>
<p>
Ephemerons are currently available in <a
href="http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Ephemerons.html">MIT
Scheme</a>, in <a
href="http://docs.racket-lang.org/reference/ephemerons.html">Racket</a>,
and in Chibi, though current versions of Chibi have a bug; the
Chibi GC will not break an ephemeron properly if its datum refers to its key.
The MIT version allows ephemeron keys and datums to be mutated using
<tt>set-ephemeron-key!</tt> and <tt>set-ephemeron-datum!</tt>,
but this SRFI does not require this capacity, as it is tricky to
implement on systems where the GC runs in a separate thread.
The effect of mutable ephemerons can be achieved using immutable
ephemerons that hold <a href="https://srfi.schemers.org/srfi-111/srfi-111.html">
SRFI 111</a> mutable boxes, provided care is taken to always point to the
box and not to its contents.
</p>
<p>
The implementation in <code>ephemerons-trivial.scm</code> does not have any hooks to the GC, but it is still a correct implementation, because there are no guarantees that the GC will ever break any ephemerons, or run at all, or even exist. (Thanks to Will Clinger for this insight.) It is portable to any R7RS-small or R5RS + SRFI 9 system.
</p>
<p>
The implementation in <code>ephemerons-racket.scm</code> layers this SRFI's semantics on top of Racket's native ephemerons. The idea here is that the native-level ephemeron value is a pair containing the key and the datum, so that the key can be reliably retrieved and a broken ephemeron can be distinguished from one whose key or value is <tt>#f</tt>.
Reference barriers are not supported.
</p>
<p>The files <code>ephemeron-hash.scm</code> and
<code>ephemeron-tree.scm</code> are by Taylor Campbell, and constitute
a demonstration written in pseudo-Scheme of how ephemerons can be
implemented in full. He has offered to provide assistance in transforming
them into Pre-Scheme for Scheme48.</p>
<p>
Ephemerons with built-in finalizers
are also available in GHC's implementation of Haskell under the name of <a
href="https://hackage.haskell.org/package/base-4.8.1.0/docs/System-Mem-Weak.html">weak
pointers</a>.
</p>
<h1>References</h1>
<p>
The original paper on ephemerons is Barry Hayes,
<a href="https://static.aminer.org/pdf/PDF/000/522/273/ephemerons_a_new_finalization_mechanism.pdf">
"Ephemerons: a New Finalization Mechanism"</a>,
<em>Object-Oriented Languages, Programming, Systems, and Applications</em>, 1997.
</p>
<p>
A useful implementation paper is Bruno Haible,
<a href="http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html">
"Weak References: Data Types and Implementation"</a>
posted 2005-04-24.
</p>
<p>
<a href="http://www.inf.puc-rio.br/~roberto/docs/ry08-06.pdf">
"Eliminating Cycles in Weak Tables"</a>
is about the addition of ephemeron
tables to Lua 5.2. It explains how Lua's tricolor mark-sweep GC is
extended to handle them, unfortunately using the O(N^2) algorithm of
Hayes 1997.</p>
<p>
<a href="https://www.cs.hmc.edu/~oneill/papers/Blobs-SPACE.pdf">
"Extending Garbage Collection to Complex Data Structures"
</a>
extends ephemerons, which have a fixed GC strategy, to a new data structure
called <i>blobs</i> that explain to the GC how they are to be processed,
thus allowing an arbitrary number of key-like and value-like pointers.
</p>
<h1>Verse</h1>
<p>
Reclaimer, spare that tree! <br />
Take not a single bit! <br />
It used to point to me, <br />
Now I'm protecting it. <br />
It was the reader's <tt>cons</tt> <br />
That made it, paired by dot; <br />
Now, GC, for the nonce, <br />
Thou shalt reclaim it not.
</p>
<p>
That old familiar tree, <br />
Whose <tt>cdr</tt>s and whose <tt>car</tt>s <br />
Are spread o'er memory — <br />
And wouldst thou it <a href="http://catb.org/jargon/html/P/parse.html">unparse</a>? <br />
GC, cease and desist! <br />
In it no free list store; <br />
Oh spare that <a href="http://catb.org/jargon/html/M/moby.html">moby</a> list <br />
Now pointing throughout core!
</p>
<p>
It was my parent tree <br />
When it was circular; <br />
It pointed then to me: <br />
I was its <tt>cadadr</tt>. <br />
My <tt>cdr</tt> was a list, <br />
My <tt>car</tt> a dotted pair — <br />
That tree will sore be missed <br />
If it remains not there.
</p>
<p>
And now I to thee point, <br />
A saving root, old friend! <br />
Thou shalt remain disjoint <br />
From free lists to the end. <br />
Old tree! The <a href="https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na.C3.AFve_mark-and-sweep">sweep</a> still brave! <br />
And, GC, <a href="https://en.wikipedia.org/wiki/Tracing_garbage_collection#Na.C3.AFve_mark-and-sweep">mark</a> this well: <br />
While I exist to save, <br />
Thou shan't reclaim one cell.
</p>
<blockquote>
<p>
<a href="https://en.wikipedia.org/wiki/Guy_L._Steele,_Jr.">The Great Quux</a> (with <a href="http://www.bartleby.com/248/131.html">apologies</a> to <a href="https://en.wikipedia.org/wiki/George_Pope_Morris">George Pope Morris</a>)
</p>
</blockquote>
<p>(Pedantic note: In Scheme, pairs constructed by <code>read</code> are
officially immutable, so this scenario is technically impossible.)</p>
<h1>Copyright</h1>
Copyright (C) John Cowan (2015).
<p>
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:
</p><p>
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
</p><p>
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.
</p><hr />
<address>Editor: <a href="mailto:srfi-editors at srfi dot schemers dot org">Arthur A. Gleckler</a></address></body></html>