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
318
319
320
321
322
323
324
325
326
327
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.8">
<title>ConcurrentMLImplementation</title>
<link rel="stylesheet" href="./asciidoc.css" type="text/css">
<link rel="stylesheet" href="./pygments.css" type="text/css">
<script type="text/javascript" src="./asciidoc.js"></script>
<script type="text/javascript">
/*<![CDATA[*/
asciidoc.install();
/*]]>*/
</script>
<link rel="stylesheet" href="./mlton.css" type="text/css"/>
</head>
<body class="article">
<div id="banner">
<div id="banner-home">
<a href="./Home">MLton 20130715</a>
</div>
</div>
<div id="header">
<h1>ConcurrentMLImplementation</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>Here are some notes on MLton’s implementation of <a href="ConcurrentML">ConcurrentML</a>.</p></div>
<div class="paragraph"><p>Concurrent ML was originally implemented for SML/NJ. It was ported to
MLton in the summer of 2004. The main difference between the
implementations is that SML/NJ uses continuations to implement CML
threads, while MLton uses its underlying <a href="MLtonThread">thread</a>
package. Presently, MLton’s threads are a little more heavyweight
than SML/NJ’s continuations, but it’s pretty clear that there is some
fat there that could be trimmed.</p></div>
<div class="paragraph"><p>The implementation of CML in SML/NJ is built upon the first-class
continuations of the <span class="monospaced">SMLofNJ.Cont</span> module.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">cont</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">callcc</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="n">cont</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">isolate</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">cont</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">throw</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">cont</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'b</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The implementation of CML in MLton is built upon the first-class
threads of the <a href="MLtonThread">MLtonThread</a> module.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">new</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">prepare</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">Runnable</span><span class="p">.</span><span class="n">t</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">switch</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">Runnable</span><span class="p">.</span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The port is relatively straightforward, because CML always throws to a
continuation at most once. Hence, an "abstract" implementation of
CML could be built upon first-class one-shot continuations, which map
equally well to SML/NJ’s continuations and MLton’s threads.</p></div>
<div class="paragraph"><p>The "essence" of the port is to transform:</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>callcc (fn k => ... throw k' v')</pre>
</div></div>
<div class="paragraph"><p>to</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>switch (fn t => ... prepare (t', v'))</pre>
</div></div>
<div class="paragraph"><p>which suffices for the vast majority of the CML implementation.</p></div>
<div class="paragraph"><p>There was only one complicated transformation: blocking multiple base
events. In SML/NJ CML, the representation of base events is given by:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">event_status</span><span class="w"></span>
<span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ENABLED</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="n">prio</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="p">,</span><span class="w"> </span><span class="n">doFn</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">BLOCKED</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">transId</span><span class="p">:</span><span class="w"> </span><span class="n">trans_id</span><span class="w"> </span><span class="n">ref</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">cleanUp</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">next</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"></span>
<span class="k">type</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">base_evt</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">event_status</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>When synchronizing on a set of base events, which are all blocked, we
must invoke each <span class="monospaced">BLOCKED</span> function with the same <span class="monospaced">transId</span> and
<span class="monospaced">cleanUp</span> (the <span class="monospaced">transId</span> is (checked and) set to <span class="monospaced">CANCEL</span> by the
<span class="monospaced">cleanUp</span> function, which is invoked by the first enabled event; this
"fizzles" every other event in the synchronization group that later
becomes enabled). However, each <span class="monospaced">BLOCKED</span> function is implemented by
a callcc, so that when the event is enabled, it throws back to the
point of synchronization. Hence, the next function (which doesn’t
return) is invoked by the <span class="monospaced">BLOCKED</span> function to escape the callcc and
continue in the thread performing the synchronization. In SML/NJ this
is implemented as follows:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">ext</span><span class="w"> </span><span class="p">([],</span><span class="w"> </span><span class="n">blockFns</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">callcc</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="n">k</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">transId</span><span class="p">,</span><span class="w"> </span><span class="n">setFlg</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">mkFlg</span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="p">[]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">atomicDispatch</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="p">(</span><span class="n">blockFn::</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">blockFn</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">transId</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">transId</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">cleanUp</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">setFlg</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
<span class="w"> </span><span class="p">})</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="n">blockFns</span><span class="p">;</span><span class="w"> </span><span class="n">error</span><span class="w"> </span><span class="s">"[log]"</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>(Note that <span class="monospaced">S.atomicDispatch</span> invokes the continuation of the next
continuation on the ready queue.) This doesn’t map well to the MLton
thread model. Although it follows the</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>callcc (fn k => ... throw k v)</pre>
</div></div>
<div class="paragraph"><p>model, the fact that <span class="monospaced">blockFn</span> will also attempt to do</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>callcc (fn k' => ... next ())</pre>
</div></div>
<div class="paragraph"><p>means that the naive transformation will result in nested <span class="monospaced">switch</span>-es.</p></div>
<div class="paragraph"><p>We need to think a little more about what this code is trying to do.
Essentially, each <span class="monospaced">blockFn</span> wants to capture this continuation, hold
on to it until the event is enabled, and continue with next; when the
event is enabled, before invoking the continuation and returning to
the synchronization point, the <span class="monospaced">cleanUp</span> and other event specific
operations are performed.</p></div>
<div class="paragraph"><p>To accomplish the same effect in the MLton thread implementation, we
have the following:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">status</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="n">ENABLED</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="n">prio</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="p">,</span><span class="w"> </span><span class="n">doitFn</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">BLOCKED</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="n">transId</span><span class="p">:</span><span class="w"> </span><span class="n">trans_id</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">cleanUp</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">next</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">rdy_thread</span><span class="p">}</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"></span>
<span class="k">type</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">base</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">status</span><span class="w"></span>
<span class="k">fun</span><span class="w"> </span><span class="n">ext</span><span class="w"> </span><span class="p">([],</span><span class="w"> </span><span class="n">blockFns</span><span class="p">):</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">atomicSwitch</span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">thread</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">transId</span><span class="p">,</span><span class="w"> </span><span class="n">cleanUp</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">TransID</span><span class="p">.</span><span class="n">mkFlg</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="n">blockFns</span><span class="p">:</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">rdy_thread</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">blockFns</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="p">[]</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">next</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">blockFn::blockFns</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="n">S</span><span class="p">.</span><span class="n">prep</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">new</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">atomicBegin</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">blockFn</span><span class="w"> </span><span class="p">{</span><span class="n">transId</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">transId</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">cleanUp</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">cleanUp</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="n">blockFns</span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">switch</span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">prepVal</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">log</span><span class="w"> </span><span class="n">blockFns</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>To avoid the nested <span class="monospaced">switch</span>-es, I run the <span class="monospaced">blockFn</span> in it’s own
thread, whose only purpose is to return to the synchronization point.
This corresponds to the <span class="monospaced">throw (blockFn {...})</span> in the SML/NJ
implementation. I’m worried that this implementation might be a
little expensive, starting a new thread for each blocked event (when
there are only multiple blocked events in a synchronization group).
But, I don’t see another way of implementing this behavior in the
MLton thread model.</p></div>
<div class="paragraph"><p>Note that another way of thinking about what is going on is to
consider each <span class="monospaced">blockFn</span> as prepending a different set of actions to
the thread <span class="monospaced">t</span>. It might be possible to give a
<span class="monospaced">MLton.Thread.unsafePrepend</span>.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">unsafePrepend</span><span class="w"> </span><span class="p">(</span><span class="n">T</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="p">):</span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">!r</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="n">Dead</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="k">raise</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="s">"prepend to a Dead thread"</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">New</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">New</span><span class="w"> </span><span class="p">(</span><span class="n">g</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">Paused</span><span class="w"> </span><span class="p">(</span><span class="n">g</span><span class="p">,</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Paused</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">h</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">h</span><span class="p">),</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="cm">(* r := Dead; *)</span><span class="w"></span>
<span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="p">(</span><span class="n">ref</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>I have commented out the <span class="monospaced">r := Dead</span>, which would allow multiple
prepends to the same thread (i.e., not destroying the original thread
in the process). Of course, only one of the threads could be run: if
the original thread were in the <span class="monospaced">Paused</span> state, then multiple threads
would share the underlying runtime/primitive thread. Now, this
matches the "one-shot" nature of CML continuations/threads, but I’m
not comfortable with extending <span class="monospaced">MLton.Thread</span> with such an unsafe
operation.</p></div>
<div class="paragraph"><p>Other than this complication with blocking multiple base events, the
port was quite routine. (As a very pleasant surprise, the CML
implementation in SML/NJ doesn’t use any SML/NJ-isms.) There is a
slight difference in the way in which critical sections are handled in
SML/NJ and MLton; since <span class="monospaced">MLton.Thread.switch</span> <em>always</em> leaves a
critical section, it is sometimes necessary to add additional
<span class="monospaced">atomicBegin</span>-s/<span class="monospaced">atomicEnd</span>-s to ensure that we remain in a critical
section after a thread switch.</p></div>
<div class="paragraph"><p>While looking at virtually every file in the core CML implementation,
I took the liberty of simplifying things where it seemed possible; in
terms of style, the implementation is about half-way between Reppy’s
original and MLton’s.</p></div>
<div class="paragraph"><p>Some changes of note:</p></div>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">util/</span> contains all pertinent data-structures: (functional and
imperative) queues, (functional) priority queues. Hence, it should be
easier to switch in more efficient or real-time implementations.
</p>
</li>
<li>
<p>
<span class="monospaced">core-cml/scheduler.sml</span>: in both implementations, this is where
most of the interesting action takes place. I’ve made the connection
between <span class="monospaced">MLton.Thread.t</span>-s and <span class="monospaced">ThreadId.thread_id</span>-s more abstract
than it is in the SML/NJ implementation, and encapsulated all of the
<span class="monospaced">MLton.Thread</span> operations in this module.
</p>
</li>
<li>
<p>
eliminated all of the "by hand" inlining
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect1">
<h2 id="_future_extensions">Future Extensions</h2>
<div class="sectionbody">
<div class="paragraph"><p>The CML documentation says the following:</p></div>
<div class="quoteblock">
<div class="content">
<div class="listingblock">
<div class="content monospaced">
<pre>CML.joinEvt: thread_id -> unit event</pre>
</div></div>
<div class="ulist"><ul>
<li>
<p>
<span class="monospaced">joinEvt tid</span>
</p>
<div class="paragraph"><p>creates an event value for synchronizing on the termination of the
thread with the ID tid. There are three ways that a thread may
terminate: the function that was passed to spawn (or spawnc) may
return; it may call the exit function, or it may have an uncaught
exception. Note that <span class="monospaced">joinEvt</span> does not distinguish between these
cases; it also does not become enabled if the named thread deadlocks
(even if it is garbage collected).</p></div>
</li>
</ul></div>
</div>
<div class="attribution">
</div></div>
<div class="paragraph"><p>I believe that the <span class="monospaced">MLton.Finalizable</span> might be able to relax that
last restriction. Upon the creation of a <span class="monospaced">'a Scheduler.thread</span>, we
could attach a finalizer to the underlying <span class="monospaced">'a MLton.Thread.t</span> that
enables the <span class="monospaced">joinEvt</span> (in the associated <span class="monospaced">ThreadID.thread_id</span>) when
the <span class="monospaced">'a MLton.Thread.t</span> becomes unreachable.</p></div>
<div class="paragraph"><p>I don’t know why CML doesn’t have</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>CML.kill: thread_id -> unit</pre>
</div></div>
<div class="paragraph"><p>which has a fairly simple implementation — setting a kill flag in the
<span class="monospaced">thread_id</span> and adjusting the scheduler to discard any killed threads
that it takes off the ready queue. The fairness of the scheduler
ensures that a killed thread will eventually be discarded. The
semantics are little murky for blocked threads that are killed,
though. For example, consider a thread blocked on <span class="monospaced">SyncVar.mTake mv</span>
and a thread blocked on <span class="monospaced">SyncVar.mGet mv</span>. If the first thread is
killed while blocked, and a third thread does <span class="monospaced">SyncVar.mPut (mv, x)</span>,
then we might expect that we’ll enable the second thread, and never
the first. But, when only the ready queue is able to discard killed
threads, then the <span class="monospaced">SyncVar.mPut</span> could enable the first thread
(putting it on the ready queue, from which it will be discarded) and
leave the second thread blocked. We could solve this by adjusting the
<span class="monospaced">TransID.trans_id types</span> and the "cleaner" functions to look for both
canceled transactions and transactions on killed threads.</p></div>
<div class="paragraph"><p>John Reppy says that <a href="References#MarlowEtAl01">MarlowEtAl01</a> and <a href="References#FlattFindler04">FlattFindler04</a>
explain why <span class="monospaced">CML.kill</span> would be a bad idea.</p></div>
<div class="paragraph"><p>Between <span class="monospaced">CML.timeOutEvt</span> and <span class="monospaced">CML.kill</span>, one could give an efficient
solution to the recent <span class="monospaced">comp.lang.ml</span> post about terminating a
function that doesn’t complete in a given time.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">timeOut</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'a</span><span class="p">,</span><span class="w"> </span><span class="n">t</span><span class="p">:</span><span class="w"> </span><span class="n">Time</span><span class="p">.</span><span class="n">time</span><span class="p">):</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">iv</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">SyncVar</span><span class="p">.</span><span class="n">iVar</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">tid</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">CML</span><span class="p">.</span><span class="n">spawn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">SyncVar</span><span class="p">.</span><span class="n">iPut</span><span class="w"> </span><span class="p">(</span><span class="n">iv</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">()))</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">CML</span><span class="p">.</span><span class="n">select</span><span class="w"></span>
<span class="w"> </span><span class="p">[</span><span class="n">CML</span><span class="p">.</span><span class="n">wrap</span><span class="w"> </span><span class="p">(</span><span class="n">CML</span><span class="p">.</span><span class="n">timeOutEvt</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">(</span><span class="n">CML</span><span class="p">.</span><span class="n">kill</span><span class="w"> </span><span class="n">tid</span><span class="p">;</span><span class="w"> </span><span class="n">NONE</span><span class="p">)),</span><span class="w"></span>
<span class="w"> </span><span class="n">CML</span><span class="p">.</span><span class="n">wrap</span><span class="w"> </span><span class="p">(</span><span class="n">SyncVar</span><span class="p">.</span><span class="n">iGetEvt</span><span class="w"> </span><span class="n">iv</span><span class="p">,</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="p">)]</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
</div>
</div>
<div class="sect1">
<h2 id="_space_safety">Space Safety</h2>
<div class="sectionbody">
<div class="paragraph"><p>There are some CML related posts on the MLton mailing list:</p></div>
<div class="ulist"><ul>
<li>
<p>
<a href="http://www.mlton.org/pipermail/mlton/2004-May/">http://www.mlton.org/pipermail/mlton/2004-May/</a>
</p>
</li>
</ul></div>
<div class="paragraph"><p>that discuss concerns that SML/NJ’s implementation is not space
efficient, because multi-shot continuations can be held indefinitely
on event queues. MLton is better off because of the one-shot nature — when an event enables a thread, all other copies of the thread
waiting in other event queues get turned into dead threads (of zero
size).</p></div>
</div>
</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
</div>
<div id="footer-badges">
</div>
</div>
</body>
</html>
|
