[hcoop/debian/mlton.git] / doc / guide / localhost / ConcurrentMLImplementation

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