4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
5 <meta name="generator" content="AsciiDoc 8.6.9">
6 <title>MLtonContIsolateImplementation</title>
7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
8 <link rel="stylesheet" href="./pygments.css" type="text/css">
11 <script type="text/javascript" src="./asciidoc.js"></script>
12 <script type="text/javascript">
17 <link rel="stylesheet" href="./mlton.css" type="text/css">
19 <body class="article">
21 <div id="banner-home">
22 <a href="./Home">MLton 20180207</a>
26 <h1>MLtonContIsolateImplementation</h1>
30 <div class="sectionbody">
31 <div class="paragraph"><p>As noted before, it is fairly easy to get the operational behavior of <span class="monospaced">isolate</span> with just <span class="monospaced">callcc</span> and <span class="monospaced">throw</span>, but establishing the right space behavior is trickier. Here, we show how to start from the obvious, but inefficient, implementation of <span class="monospaced">isolate</span> using only <span class="monospaced">callcc</span> and <span class="monospaced">throw</span>, and <em>derive</em> an equivalent, but more efficient, implementation of <span class="monospaced">isolate</span> using MLton’s primitive stack capture and copy operations. This isn’t a formal derivation, as we are not formally showing the equivalence of the programs (though I believe that they are all equivalent, modulo the space behavior).</p></div>
32 <div class="paragraph"><p>Here is a direct implementation of isolate using only <span class="monospaced">callcc</span> and <span class="monospaced">throw</span>:</p></div>
33 <div class="listingblock">
34 <div class="content"><div class="highlight"><pre><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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
35 <span class="w"> </span><span class="k">fn</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">'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>
36 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
37 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
38 <span class="w"> </span><span class="k">let</span><span class="w"></span>
39 <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">callcc</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
40 <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="p">(</span><span class="n">f</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">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
41 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
42 <span class="w"> </span><span class="k">in</span><span class="w"></span>
43 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
44 <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
45 </pre></div></div></div>
46 <div class="paragraph"><p>We use the standard nested <span class="monospaced">callcc</span> trick to return a continuation that is ready to receive an argument, execute the isolated function, and exit the program. Both <span class="monospaced">Exit.topLevelSuffix</span> and <span class="monospaced">MLtonExn.topLevelHandler</span> will terminate the program.</p></div>
47 <div class="paragraph"><p>Throwing to an isolated function will execute the function in a <em>semantically</em> empty context, in the sense that we never re-execute the <em>original</em> continuation of the call to isolate (i.e., the context that was in place at the time <span class="monospaced">isolate</span> was called). However, we assume that the compiler isn’t able to recognize that the <em>original</em> continuation is unused; for example, while we (the programmer) know that <span class="monospaced">Exit.topLevelSuffix</span> and <span class="monospaced">MLtonExn.topLevelHandler</span> will terminate the program, the compiler may only see opaque calls to unknown foreign-functions. So, that original continuation (in its entirety) is part of the continuation returned by <span class="monospaced">isolate</span> and throwing to the continuation returned by <span class="monospaced">isolate</span> will execute <span class="monospaced">f x</span> (with the exit wrapper) in the context of that original continuation. Thus, the garbage collector will retain everything reachable from that original continuation during the evaluation of <span class="monospaced">f x</span>, even though it is <em>semantically</em> garbage.</p></div>
48 <div class="paragraph"><p>Note that this space-leak is independent of the implementation of continuations (it arises in both MLton’s stack copying implementation of continuations and would arise in SML/NJ’s CPS-translation implementation); we are only assuming that the implementation can’t <em>see</em> the program termination, and so must retain the original continuation (and anything reachable from it).</p></div>
49 <div class="paragraph"><p>So, we need an <em>empty</em> continuation in which to execute <span class="monospaced">f x</span>. (No surprise there, as that is the written description of <span class="monospaced">isolate</span>.) To do this, we capture a top-level continuation and throw to that in order to execute <span class="monospaced">f x</span>:</p></div>
50 <div class="listingblock">
51 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
52 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
53 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
54 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
55 <span class="w"> </span><span class="k">let</span><span class="w"></span>
56 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">th</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">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
57 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
58 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
59 <span class="w"> </span><span class="k">in</span><span class="w"></span>
60 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
61 <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
62 <span class="k">in</span><span class="w"></span>
63 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
64 <span class="w"> </span><span class="k">fn</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">'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>
65 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
66 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
67 <span class="w"> </span><span class="k">let</span><span class="w"></span>
68 <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">callcc</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
69 <span class="w"> </span><span class="k">in</span><span class="w"></span>
70 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</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">f</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
71 <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
72 <span class="k">end</span><span class="w"></span>
73 </pre></div></div></div>
74 <div class="paragraph"><p>We presume that <span class="monospaced">base</span> is evaluated <em>early</em> in the program. There is a subtlety here, because one needs to believe that this <span class="monospaced">base</span> continuation (which technically corresponds to the entire rest of the program evaluation) <em>works</em> as an empty context; in particular, we want it to be the case that executing <span class="monospaced">f x</span> in the <span class="monospaced">base</span> context retains less space than executing <span class="monospaced">f x</span> in the context in place at the call to <span class="monospaced">isolate</span> (as occurred in the previous implementation of <span class="monospaced">isolate</span>). This isn’t particularly easy to believe if one takes a normal substitution-based operational semantics, because it seems that the context captured and bound to <span class="monospaced">base</span> is arbitrarily large. However, this context is mostly unevaluated code; the only heap-allocated values that are reachable from it are those that were evaluated before the evaluation of <span class="monospaced">base</span> (and used in the program after the evaluation of <span class="monospaced">base</span>). Assuming that <span class="monospaced">base</span> is evaluated <em>early</em> in the program, we conclude that there are few heap-allocated values reachable from its continuation. In contrast, the previous implementation of <span class="monospaced">isolate</span> could capture a context that has many heap-allocated values reachable from it (because we could evaluate <span class="monospaced">isolate f</span> <em>late</em> in the program and <em>deep</em> in a call stack), which would all remain reachable during the evaluation of
75 <span class="monospaced">f x</span>. [We’ll return to this point later, as it is taking a slightly MLton-esque view of the evaluation of a program, and may not apply as strongly to other implementations (e.g., SML/NJ).]</p></div>
76 <div class="paragraph"><p>Now, once we throw to <span class="monospaced">base</span> and begin executing <span class="monospaced">f x</span>, only the heap-allocated values reachable from <span class="monospaced">f</span> and <span class="monospaced">x</span> and the few heap-allocated values reachable from <span class="monospaced">base</span> are retained by the garbage collector. So, it seems that <span class="monospaced">base</span> <em>works</em> as an empty context.</p></div>
77 <div class="paragraph"><p>But, what about the continuation returned from <span class="monospaced">isolate f</span>? Note that the continuation returned by <span class="monospaced">isolate</span> is one that receives an argument <span class="monospaced">x</span> and then
78 throws to <span class="monospaced">base</span> to evaluate <span class="monospaced">f x</span>. If we used a CPS-translation implementation (and assume sufficient beta-contractions to eliminate administrative redexes), then the original continuation passed to <span class="monospaced">isolate</span> (i.e., the continuation bound to <span class="monospaced">k1</span>) will not be free in the continuation returned by <span class="monospaced">isolate f</span>. Rather, the only free variables in the continuation returned by <span class="monospaced">isolate f</span> will be <span class="monospaced">base</span> and <span class="monospaced">f</span>, so the only heap-allocated values reachable from the continuation returned by <span class="monospaced">isolate f</span> will be those values reachable from <span class="monospaced">base</span> (assumed to be few) and those values reachable from <span class="monospaced">f</span> (necessary in order to execute <span class="monospaced">f</span> at some later point).</p></div>
79 <div class="paragraph"><p>But, MLton doesn’t use a CPS-translation implementation. Rather, at each call to <span class="monospaced">callcc</span> in the body of <span class="monospaced">isolate</span>, MLton will copy the current execution stack. Thus, <span class="monospaced">k2</span> (the continuation returned by <span class="monospaced">isolate f</span>) will include execution stack at the time of the call to <span class="monospaced">isolate f</span> — that is, it will include the <em>original</em> continuation of the call to <span class="monospaced">isolate f</span>. Thus, the heap-allocated values reachable from the continuation returned by <span class="monospaced">isolate f</span> will include those values reachable from <span class="monospaced">base</span>, those values reachable from <span class="monospaced">f</span>, and those values reachable from the original continuation of the call to <span class="monospaced">isolate f</span>. So, just holding on to the continuation returned by <span class="monospaced">isolate f</span> will retain all of the heap-allocated values live at the time <span class="monospaced">isolate f</span> was called. This leaks space, since, <em>semantically</em>, the
80 continuation returned by <span class="monospaced">isolate f</span> only needs the heap-allocated values reachable from <span class="monospaced">f</span> (and <span class="monospaced">base</span>).</p></div>
81 <div class="paragraph"><p>In practice, this probably isn’t a significant issue. A common use of <span class="monospaced">isolate</span> is implement <span class="monospaced">abort</span>:</p></div>
82 <div class="listingblock">
83 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">abort</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">isolate</span><span class="w"> </span><span class="n">th</span><span class="p">,</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
84 </pre></div></div></div>
85 <div class="paragraph"><p>The continuation returned by <span class="monospaced">isolate th</span> is dead immediately after being thrown to — the continuation isn’t retained, so neither is the <em>semantic</em>
86 garbage it would have retained.</p></div>
87 <div class="paragraph"><p>But, it is easy enough to <em>move</em> onto the <em>empty</em> context <span class="monospaced">base</span> the capturing of the context that we want to be returned by <span class="monospaced">isolate f</span>:</p></div>
88 <div class="listingblock">
89 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
90 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
91 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
92 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
93 <span class="w"> </span><span class="k">let</span><span class="w"></span>
94 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">th</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">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
95 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
96 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
97 <span class="w"> </span><span class="k">in</span><span class="w"></span>
98 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
99 <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
100 <span class="k">in</span><span class="w"></span>
101 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
102 <span class="w"> </span><span class="k">fn</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">'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>
103 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
104 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
105 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</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>
106 <span class="w"> </span><span class="k">let</span><span class="w"></span>
107 <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">callcc</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
108 <span class="w"> </span><span class="k">in</span><span class="w"></span>
109 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</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">f</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
110 <span class="w"> </span><span class="k">end</span><span class="p">))</span><span class="w"></span>
111 <span class="k">end</span><span class="w"></span>
112 </pre></div></div></div>
113 <div class="paragraph"><p>This implementation now has the right space behavior; the continuation returned by <span class="monospaced">isolate f</span> will only retain the heap-allocated values reachable from <span class="monospaced">f</span> and from <span class="monospaced">base</span>. (Technically, the continuation will retain two copies of the stack that was in place at the time <span class="monospaced">base</span> was evaluated, but we are assuming that that stack small.)</p></div>
114 <div class="paragraph"><p>One minor inefficiency of this implementation (given MLton’s implementation of continuations) is that every <span class="monospaced">callcc</span> and <span class="monospaced">throw</span> entails copying a stack (albeit, some of them are small). We can avoid this in the evaluation of <span class="monospaced">base</span> by using a reference cell, because <span class="monospaced">base</span> is evaluated at the top-level:</p></div>
115 <div class="listingblock">
116 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
117 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
118 <span class="w"> </span><span class="k">let</span><span class="w"></span>
119 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">baseRef</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
120 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">th</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="p">(</span><span class="n">base</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"> </span><span class="n">NONE</span><span class="p">))</span><span class="w"></span>
121 <span class="w"> </span><span class="k">in</span><span class="w"></span>
122 <span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
123 <span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">(</span><span class="k">case</span><span class="w"> </span><span class="n">!baseRef</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
124 <span class="w"> </span><span class="n">NONE</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">"MLton.Cont.isolate: missing base"</span><span class="w"></span>
125 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</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">base</span><span class="p">)</span><span class="w"></span>
126 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="k">let</span><span class="w"></span>
127 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
128 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
129 <span class="w"> </span><span class="k">in</span><span class="w"></span>
130 <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">"MLton.Cont.isolate: return from (wrapped)</span><span class="err"></span>
131 <span class="s"> func"</span><span class="w"></span>
132 <span class="w"> </span><span class="k">end</span><span class="w"></span>
133 <span class="w"> </span><span class="k">end</span><span class="w"></span>
134 <span class="k">in</span><span class="w"></span>
135 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
136 <span class="w"> </span><span class="k">fn</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">'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>
137 <span class="w"> </span><span class="n">callcc</span><span class="w"></span>
138 <span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k1</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
139 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</span><span class="p">,</span><span class="w"> </span><span class="n">SOME</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>
140 <span class="w"> </span><span class="k">let</span><span class="w"></span>
141 <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">callcc</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">k2</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k1</span><span class="p">,</span><span class="w"> </span><span class="n">k2</span><span class="p">))</span><span class="w"></span>
142 <span class="w"> </span><span class="k">in</span><span class="w"></span>
143 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</span><span class="p">,</span><span class="w"> </span><span class="n">SOME</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">f</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"></span>
144 <span class="w"> </span><span class="k">end</span><span class="p">)))</span><span class="w"></span>
145 <span class="k">end</span><span class="w"></span>
146 </pre></div></div></div>
147 <div class="paragraph"><p>Now, to evaluate <span class="monospaced">base</span>, we only copy the stack once (instead of 3 times). Because we don’t have a dummy continuation around to initialize the reference cell, the reference cell holds a continuation <span class="monospaced">option</span>. To distinguish between the original evaluation of <span class="monospaced">base</span> (when we want to return the continuation) and the subsequent evaluations of <span class="monospaced">base</span> (when we want to evaluate a thunk), we capture a <span class="monospaced">(unit -> unit) option</span> continuation.</p></div>
148 <div class="paragraph"><p>This seems to be as far as we can go without exploiting the concrete implementation of continuations in <a href="MLtonCont">MLtonCont</a>. Examining the implementation, we note that the type of
149 continuations is given by</p></div>
150 <div class="listingblock">
151 <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="p">=</span><span class="w"> </span><span class="p">(</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="p">-></span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
152 </pre></div></div></div>
153 <div class="paragraph"><p>and the implementation of <span class="monospaced">throw</span> is given by</p></div>
154 <div class="listingblock">
155 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">)</span><span class="w"> </span><span class="n">throw'</span><span class="w"> </span><span class="p">(</span><span class="n">k</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">v</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">'b</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
156 <span class="w"> </span><span class="p">(</span><span class="n">k</span><span class="w"> </span><span class="n">v</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">"MLton.Cont.throw': return from continuation"</span><span class="p">)</span><span class="w"></span>
158 <span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'b</span><span class="p">)</span><span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">k</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">v</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="p">=</span><span class="w"> </span><span class="n">throw'</span><span class="w"> </span><span class="p">(</span><span class="n">k</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">v</span><span class="p">)</span><span class="w"></span>
159 </pre></div></div></div>
160 <div class="paragraph"><p>Suffice to say, a continuation is simply a function that accepts a thunk to yield the thrown value and the body of the function performs the actual throw. Using this knowledge, we can create a dummy continuation to initialize <span class="monospaced">baseRef</span> and greatly simplify the body of <span class="monospaced">isolate</span>:</p></div>
161 <div class="listingblock">
162 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
163 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
164 <span class="w"> </span><span class="k">let</span><span class="w"></span>
165 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">baseRef</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
166 <span class="w"> </span><span class="n">ref</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">raise</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="s">"MLton.Cont.isolate: missing base"</span><span class="p">)</span><span class="w"></span>
167 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">th</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="p">(</span><span class="n">baseRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"> </span><span class="n">NONE</span><span class="p">))</span><span class="w"></span>
168 <span class="w"> </span><span class="k">in</span><span class="w"></span>
169 <span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
170 <span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">!baseRef</span><span class="w"></span>
171 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="k">let</span><span class="w"></span>
172 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
173 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
174 <span class="w"> </span><span class="k">in</span><span class="w"></span>
175 <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">"MLton.Cont.isolate: return from (wrapped)</span><span class="err"></span>
176 <span class="s"> func"</span><span class="w"></span>
177 <span class="w"> </span><span class="k">end</span><span class="w"></span>
178 <span class="w"> </span><span class="k">end</span><span class="w"></span>
179 <span class="k">in</span><span class="w"></span>
180 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
181 <span class="w"> </span><span class="k">fn</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">'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>
182 <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">v</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="p">=></span><span class="w"></span>
183 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</span><span class="p">,</span><span class="w"> </span><span class="n">SOME</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">v</span><span class="p">))</span><span class="w"></span>
184 <span class="k">end</span><span class="w"></span>
185 </pre></div></div></div>
186 <div class="paragraph"><p>Note that this implementation of <span class="monospaced">isolate</span> makes it clear that the continuation returned by <span class="monospaced">isolate f</span> only retains the heap-allocated values reachable from <span class="monospaced">f</span> and <span class="monospaced">base</span>. It also retains only one copy of the stack that was in place at the time <span class="monospaced">base</span> was evaluated. Finally, it completely avoids making any copies of the stack that is in place at the time <span class="monospaced">isolate f</span> is evaluated; indeed, <span class="monospaced">isolate f</span> is a constant-time operation.</p></div>
187 <div class="paragraph"><p>Next, suppose we limited ourselves to capturing <span class="monospaced">unit</span> continuations with <span class="monospaced">callcc</span>. We can’t pass the thunk to be evaluated in the <em>empty</em> context directly, but we can use a reference cell.</p></div>
188 <div class="listingblock">
189 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
190 <span class="k">val</span><span class="w"> </span><span class="n">thRef</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
191 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
192 <span class="w"> </span><span class="k">let</span><span class="w"></span>
193 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">baseRef</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
194 <span class="w"> </span><span class="n">ref</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">raise</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="s">"MLton.Cont.isolate: missing base"</span><span class="p">)</span><span class="w"></span>
195 <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">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="n">baseRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">k</span><span class="p">)</span><span class="w"></span>
196 <span class="w"> </span><span class="k">in</span><span class="w"></span>
197 <span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">!thRef</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
198 <span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">!baseRef</span><span class="w"></span>
199 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
200 <span class="w"> </span><span class="k">let</span><span class="w"></span>
201 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
202 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
203 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
204 <span class="w"> </span><span class="k">in</span><span class="w"></span>
205 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
206 <span class="w"> </span><span class="k">end</span><span class="w"></span>
207 <span class="w"> </span><span class="k">end</span><span class="w"></span>
208 <span class="k">in</span><span class="w"></span>
209 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
210 <span class="w"> </span><span class="k">fn</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">'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>
211 <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">v</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="p">=></span><span class="w"></span>
212 <span class="w"> </span><span class="k">let</span><span class="w"></span>
213 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</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">v</span><span class="p">)</span><span class="w"></span>
214 <span class="w"> </span><span class="k">in</span><span class="w"></span>
215 <span class="w"> </span><span class="n">throw</span><span class="w"> </span><span class="p">(</span><span class="n">base</span><span class="p">,</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
216 <span class="w"> </span><span class="k">end</span><span class="w"></span>
217 <span class="k">end</span><span class="w"></span>
218 </pre></div></div></div>
219 <div class="paragraph"><p>Note that it is important to set <span class="monospaced">thRef</span> to <span class="monospaced">NONE</span> before evaluating the thunk, so that the garbage collector doesn’t retain all the heap-allocated values reachable from <span class="monospaced">f</span> and <span class="monospaced">v</span> during the evaluation of <span class="monospaced">f (v ())</span>. This is because <span class="monospaced">thRef</span> is still live during the evaluation of the thunk; in particular, it was allocated before the evaluation of <span class="monospaced">base</span> (and used after), and so is retained by continuation on which the thunk is evaluated.</p></div>
220 <div class="paragraph"><p>This implementation can be easily adapted to use MLton’s primitive stack copying operations.</p></div>
221 <div class="listingblock">
222 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
223 <span class="k">val</span><span class="w"> </span><span class="n">thRef</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
224 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">preThread</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
225 <span class="w"> </span><span class="k">let</span><span class="w"></span>
226 <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">Thread</span><span class="p">.</span><span class="n">copyCurrent</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
227 <span class="w"> </span><span class="k">in</span><span class="w"></span>
228 <span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">!thRef</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
229 <span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">savedPre</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
230 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
231 <span class="w"> </span><span class="k">let</span><span class="w"></span>
232 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
233 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
234 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
235 <span class="w"> </span><span class="k">in</span><span class="w"></span>
236 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
237 <span class="w"> </span><span class="k">end</span><span class="w"></span>
238 <span class="w"> </span><span class="k">end</span><span class="w"></span>
239 <span class="k">in</span><span class="w"></span>
240 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
241 <span class="w"> </span><span class="k">fn</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">'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>
242 <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">v</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="p">=></span><span class="w"></span>
243 <span class="w"> </span><span class="k">let</span><span class="w"></span>
244 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</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">v</span><span class="p">)</span><span class="w"></span>
245 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">new</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">copy</span><span class="w"> </span><span class="n">base</span><span class="w"></span>
246 <span class="w"> </span><span class="k">in</span><span class="w"></span>
247 <span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">switchTo</span><span class="w"> </span><span class="n">new</span><span class="w"></span>
248 <span class="w"> </span><span class="k">end</span><span class="w"></span>
249 <span class="k">end</span><span class="w"></span>
250 </pre></div></div></div>
251 <div class="paragraph"><p>In essence, <span class="monospaced">Thread.copyCurrent</span> copies the current execution stack and stores it in an implicit reference cell in the runtime system, which is fetchable with <span class="monospaced">Thread.savedPre</span>. When we are ready to throw to the isolated function, <span class="monospaced">Thread.copy</span> copies the saved execution stack (because the stack is modified in place during execution, we need to retain a pristine copy in case the isolated function itself throws to other isolated functions) and <span class="monospaced">Thread.switchTo</span> abandons the current execution stack, installing the newly copied execution stack.</p></div>
252 <div class="paragraph"><p>The actual implementation of <span class="monospaced">MLton.Cont.isolate</span> simply adds some <span class="monospaced">Thread.atomicBegin</span> and <span class="monospaced">Thread.atomicEnd</span> commands, which effectively protect the global <span class="monospaced">thRef</span> and accommodate the fact that <span class="monospaced">Thread.switchTo</span> does an implicit <span class="monospaced">Thread.atomicEnd</span> (used for leaving a signal handler thread).</p></div>
253 <div class="listingblock">
254 <div class="content"><div class="highlight"><pre><span class="k">local</span><span class="w"></span>
255 <span class="k">val</span><span class="w"> </span><span class="n">thRef</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
256 <span class="k">val</span><span class="w"> </span><span class="n">base</span><span class="p">:</span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">preThread</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
257 <span class="w"> </span><span class="k">let</span><span class="w"></span>
258 <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">Thread</span><span class="p">.</span><span class="n">copyCurrent</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
259 <span class="w"> </span><span class="k">in</span><span class="w"></span>
260 <span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">!thRef</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
261 <span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">savedPre</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
262 <span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
263 <span class="w"> </span><span class="k">let</span><span class="w"></span>
264 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
265 <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">MLton</span><span class="p">.</span><span class="n">atomicEnd</span><span class="w"> </span><span class="cm">(* Match 1 *)</span><span class="w"></span>
266 <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="p">(</span><span class="n">th</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
267 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
268 <span class="w"> </span><span class="k">in</span><span class="w"></span>
269 <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">"MLton.Cont.isolate: return from (wrapped) func"</span><span class="w"></span>
270 <span class="w"> </span><span class="k">end</span><span class="w"></span>
271 <span class="w"> </span><span class="k">end</span><span class="w"></span>
272 <span class="k">in</span><span class="w"></span>
273 <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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
274 <span class="w"> </span><span class="k">fn</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">'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>
275 <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">v</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="p">=></span><span class="w"></span>
276 <span class="w"> </span><span class="k">let</span><span class="w"></span>
277 <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">MLton</span><span class="p">.</span><span class="n">atomicBegin</span><span class="w"> </span><span class="cm">(* Match 1 *)</span><span class="w"></span>
278 <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">thRef</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</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">v</span><span class="p">)</span><span class="w"></span>
279 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">new</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">copy</span><span class="w"> </span><span class="n">base</span><span class="w"></span>
280 <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">MLton</span><span class="p">.</span><span class="n">atomicBegin</span><span class="w"> </span><span class="cm">(* Match 2 *)</span><span class="w"></span>
281 <span class="w"> </span><span class="k">in</span><span class="w"></span>
282 <span class="w"> </span><span class="n">Thread</span><span class="p">.</span><span class="n">switchTo</span><span class="w"> </span><span class="n">new</span><span class="w"> </span><span class="cm">(* Match 2 *)</span><span class="w"></span>
283 <span class="w"> </span><span class="k">end</span><span class="w"></span>
284 <span class="k">end</span><span class="w"></span>
285 </pre></div></div></div>
286 <div class="paragraph"><p>It is perhaps interesting to note that the above implementation was originally <em>derived</em> by specializing implementations of the <a href="MLtonThread">MLtonThread</a> <span class="monospaced">new</span>, <span class="monospaced">prepare</span>, and <span class="monospaced">switch</span> functions as if their only use was in the following implementation of <span class="monospaced">isolate</span>:</p></div>
287 <div class="listingblock">
288 <div class="content"><div class="highlight"><pre><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">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
289 <span class="w"> </span><span class="k">fn</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">'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>
290 <span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">v</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="p">=></span><span class="w"></span>
291 <span class="w"> </span><span class="k">let</span><span class="w"></span>
292 <span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">th</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">v</span><span class="w"> </span><span class="p">())</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">topLevelSuffix</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
293 <span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">MLtonExn</span><span class="p">.</span><span class="n">topLevelHandler</span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
294 <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="n">MLton</span><span class="p">.</span><span class="n">Thread</span><span class="p">.</span><span class="n">prepare</span><span class="w"> </span><span class="p">(</span><span class="n">MLton</span><span class="p">.</span><span class="n">Thread</span><span class="p">.</span><span class="n">new</span><span class="w"> </span><span class="n">th</span><span class="p">,</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
295 <span class="w"> </span><span class="k">in</span><span class="w"></span>
296 <span class="w"> </span><span class="n">MLton</span><span class="p">.</span><span class="n">Thread</span><span class="p">.</span><span class="n">switch</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">t</span><span class="p">)</span><span class="w"></span>
297 <span class="w"> </span><span class="k">end</span><span class="w"></span>
298 </pre></div></div></div>
299 <div class="paragraph"><p>It was pleasant to discover that it could equally well be <em>derived</em> starting from the <span class="monospaced">callcc</span> and <span class="monospaced">throw</span> implementation.</p></div>
300 <div class="paragraph"><p>As a final comment, we noted that the degree to which the context of <span class="monospaced">base</span> could be considered <em>empty</em> (i.e., retaining few heap-allocated values) depended upon a slightly MLton-esque view. In particular, MLton does not heap allocate executable code. So, although the <span class="monospaced">base</span> context keeps a lot of unevaluated code <em>live</em>, such code is not heap allocated. In a system like SML/NJ, that does heap allocate executable code, one might want it to be the case that after throwing to an isolated function, the garbage collector retains only the code necessary to evaluate the function, and not any code that was necessary to evaluate the <span class="monospaced">base</span> context.</p></div>
304 <div id="footnotes"><hr></div>
306 <div id="footer-text">
308 <div id="footer-badges">
HCoop / hcoop / debian / mlton.git / blob