doc/guide/localhost/ConcurrentMLImplementation

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>ConcurrentMLImplementation</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>ConcurrentMLImplementation</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>Here are some notes on MLton&#8217;s implementation of <a href="ConcurrentML">ConcurrentML</a>.</p></div>
  32 <div class="paragraph"><p>Concurrent ML was originally implemented for SML/NJ.  It was ported to
  33 MLton in the summer of 2004.  The main difference between the
  34 implementations is that SML/NJ uses continuations to implement CML
  35 threads, while MLton uses its underlying <a href="MLtonThread">thread</a>
  36 package.  Presently, MLton&#8217;s threads are a little more heavyweight
  37 than SML/NJ&#8217;s continuations, but it&#8217;s pretty clear that there is some
  38 fat there that could be trimmed.</p></div>
  39 <div class="paragraph"><p>The implementation of CML in SML/NJ is built upon the first-class
  40 continuations of the <span class="monospaced">SMLofNJ.Cont</span> module.</p></div>
  41 <div class="listingblock">
  42 <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>
  43 <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>
  44 <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>
  45 <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>
  46 </pre></div></div></div>
  47 <div class="paragraph"><p>The implementation of CML in MLton is built upon the first-class
  48 threads of the <a href="MLtonThread">MLtonThread</a> module.</p></div>
  49 <div class="listingblock">
  50 <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>
  51 <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>
  52 <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>
  53 <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>
  54 </pre></div></div></div>
  55 <div class="paragraph"><p>The port is relatively straightforward, because CML always throws to a
  56 continuation at most once.  Hence, an "abstract" implementation of
  57 CML could be built upon first-class one-shot continuations, which map
  58 equally well to SML/NJ&#8217;s continuations and MLton&#8217;s threads.</p></div>
  59 <div class="paragraph"><p>The "essence" of the port is to transform:</p></div>
  60 <div class="listingblock">
  61 <div class="content monospaced">
  62 <pre>callcc (fn k =&gt; ... throw k' v')</pre>
  63 </div></div>
  64 <div class="paragraph"><p>to</p></div>
  65 <div class="listingblock">
  66 <div class="content monospaced">
  67 <pre>switch (fn t =&gt; ... prepare (t', v'))</pre>
  68 </div></div>
  69 <div class="paragraph"><p>which suffices for the vast majority of the CML implementation.</p></div>
  70 <div class="paragraph"><p>There was only one complicated transformation: blocking multiple base
  71 events.  In SML/NJ CML, the representation of base events is given by:</p></div>
  72 <div class="listingblock">
  73 <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>
  74 <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>
  75 <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>
  76 <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>
  77 <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>
  78 <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>
  79 <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>
  80 <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>
  81 </pre></div></div></div>
  82 <div class="paragraph"><p>When synchronizing on a set of base events, which are all blocked, we
  83 must invoke each <span class="monospaced">BLOCKED</span> function with the same <span class="monospaced">transId</span> and
  84 <span class="monospaced">cleanUp</span> (the <span class="monospaced">transId</span> is (checked and) set to <span class="monospaced">CANCEL</span> by the
  85 <span class="monospaced">cleanUp</span> function, which is invoked by the first enabled event; this
  86 "fizzles" every other event in the synchronization group that later
  87 becomes enabled).  However, each <span class="monospaced">BLOCKED</span> function is implemented by
  88 a callcc, so that when the event is enabled, it throws back to the
  89 point of synchronization.  Hence, the next function (which doesn&#8217;t
  90 return) is invoked by the <span class="monospaced">BLOCKED</span> function to escape the callcc and
  91 continue in the thread performing the synchronization.  In SML/NJ this
  92 is implemented as follows:</p></div>
  93 <div class="listingblock">
  94 <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>
  95 <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>
  96 <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>
  97 <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>
  98 <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>
  99 <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>
 100 <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>
 101 <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>
 102 <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>
 103 <span class="w">              </span><span class="p">})</span><span class="w"></span>
 104 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 105 <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>
 106 <span class="w">      </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
 107 </pre></div></div></div>
 108 <div class="paragraph"><p>(Note that <span class="monospaced">S.atomicDispatch</span> invokes the continuation of the next
 109 continuation on the ready queue.)  This doesn&#8217;t map well to the MLton
 110 thread model.  Although it follows the</p></div>
 111 <div class="listingblock">
 112 <div class="content monospaced">
 113 <pre>callcc (fn k =&gt; ... throw k v)</pre>
 114 </div></div>
 115 <div class="paragraph"><p>model, the fact that <span class="monospaced">blockFn</span> will also attempt to do</p></div>
 116 <div class="listingblock">
 117 <div class="content monospaced">
 118 <pre>callcc (fn k' =&gt; ... next ())</pre>
 119 </div></div>
 120 <div class="paragraph"><p>means that the naive transformation will result in nested <span class="monospaced">switch</span>-es.</p></div>
 121 <div class="paragraph"><p>We need to think a little more about what this code is trying to do.
 122 Essentially, each <span class="monospaced">blockFn</span> wants to capture this continuation, hold
 123 on to it until the event is enabled, and continue with next; when the
 124 event is enabled, before invoking the continuation and returning to
 125 the synchronization point, the <span class="monospaced">cleanUp</span> and other event specific
 126 operations are performed.</p></div>
 127 <div class="paragraph"><p>To accomplish the same effect in the MLton thread implementation, we
 128 have the following:</p></div>
 129 <div class="listingblock">
 130 <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>
 131 <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>
 132 <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>
 133 <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>
 134 <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>
 135
 136 <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>
 137
 138 <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>
 139 <span class="w">     </span><span class="n">S</span><span class="p">.</span><span class="n">atomicSwitch</span><span class="w"></span>
 140 <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>
 141 <span class="w">      </span><span class="k">let</span><span class="w"></span>
 142 <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>
 143 <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>
 144 <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>
 145 <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>
 146 <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>
 147 <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>
 148 <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>
 149 <span class="w">                   </span><span class="k">let</span><span class="w"></span>
 150 <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>
 151 <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>
 152 <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>
 153 <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>
 154 <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>
 155 <span class="w">                   </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
 156 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 157 <span class="w">         </span><span class="n">log</span><span class="w"> </span><span class="n">blockFns</span><span class="w"></span>
 158 <span class="w">      </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
 159 </pre></div></div></div>
 160 <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
 161 thread, whose only purpose is to return to the synchronization point.
 162 This corresponds to the <span class="monospaced">throw (blockFn {...})</span> in the SML/NJ
 163 implementation.  I&#8217;m worried that this implementation might be a
 164 little expensive, starting a new thread for each blocked event (when
 165 there are only multiple blocked events in a synchronization group).
 166 But, I don&#8217;t see another way of implementing this behavior in the
 167 MLton thread model.</p></div>
 168 <div class="paragraph"><p>Note that another way of thinking about what is going on is to
 169 consider each <span class="monospaced">blockFn</span> as prepending a different set of actions to
 170 the thread <span class="monospaced">t</span>.  It might be possible to give a
 171 <span class="monospaced">MLton.Thread.unsafePrepend</span>.</p></div>
 172 <div class="listingblock">
 173 <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>
 174 <span class="w">   </span><span class="k">let</span><span class="w"></span>
 175 <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>
 176 <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>
 177 <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>
 178 <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>
 179 <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>
 180 <span class="w">   </span><span class="k">in</span><span class="w"> </span><span class="cm">(* r := Dead; *)</span><span class="w"></span>
 181 <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>
 182 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 183 </pre></div></div></div>
 184 <div class="paragraph"><p>I have commented out the <span class="monospaced">r := Dead</span>, which would allow multiple
 185 prepends to the same thread (i.e., not destroying the original thread
 186 in the process).  Of course, only one of the threads could be run: if
 187 the original thread were in the <span class="monospaced">Paused</span> state, then multiple threads
 188 would share the underlying runtime/primitive thread.  Now, this
 189 matches the "one-shot" nature of CML continuations/threads, but I&#8217;m
 190 not comfortable with extending <span class="monospaced">MLton.Thread</span> with such an unsafe
 191 operation.</p></div>
 192 <div class="paragraph"><p>Other than this complication with blocking multiple base events, the
 193 port was quite routine.  (As a very pleasant surprise, the CML
 194 implementation in SML/NJ doesn&#8217;t use any SML/NJ-isms.)  There is a
 195 slight difference in the way in which critical sections are handled in
 196 SML/NJ and MLton; since <span class="monospaced">MLton.Thread.switch</span> <em>always</em> leaves a
 197 critical section, it is sometimes necessary to add additional
 198 <span class="monospaced">atomicBegin</span>-s/<span class="monospaced">atomicEnd</span>-s to ensure that we remain in a critical
 199 section after a thread switch.</p></div>
 200 <div class="paragraph"><p>While looking at virtually every file in the core CML implementation,
 201 I took the liberty of simplifying things where it seemed possible; in
 202 terms of style, the implementation is about half-way between Reppy&#8217;s
 203 original and MLton&#8217;s.</p></div>
 204 <div class="paragraph"><p>Some changes of note:</p></div>
 205 <div class="ulist"><ul>
 206 <li>
 207 <p>
 208 <span class="monospaced">util/</span> contains all pertinent data-structures: (functional and
 209 imperative) queues, (functional) priority queues.  Hence, it should be
 210 easier to switch in more efficient or real-time implementations.
 211 </p>
 212 </li>
 213 <li>
 214 <p>
 215 <span class="monospaced">core-cml/scheduler.sml</span>: in both implementations, this is where
 216 most of the interesting action takes place.  I&#8217;ve made the connection
 217 between <span class="monospaced">MLton.Thread.t</span>-s and <span class="monospaced">ThreadId.thread_id</span>-s more abstract
 218 than it is in the SML/NJ implementation, and encapsulated all of the
 219 <span class="monospaced">MLton.Thread</span> operations in this module.
 220 </p>
 221 </li>
 222 <li>
 223 <p>
 224 eliminated all of the "by hand" inlining
 225 </p>
 226 </li>
 227 </ul></div>
 228 </div>
 229 </div>
 230 <div class="sect1">
 231 <h2 id="_future_extensions">Future Extensions</h2>
 232 <div class="sectionbody">
 233 <div class="paragraph"><p>The CML documentation says the following:</p></div>
 234 <div class="quoteblock">
 235 <div class="content">
 236 <div class="listingblock">
 237 <div class="content monospaced">
 238 <pre>CML.joinEvt: thread_id -&gt; unit event</pre>
 239 </div></div>
 240 <div class="ulist"><ul>
 241 <li>
 242 <p>
 243 <span class="monospaced">joinEvt tid</span>
 244 </p>
 245 <div class="paragraph"><p>creates an event value for synchronizing on the termination of the
 246 thread with the ID tid.  There are three ways that a thread may
 247 terminate: the function that was passed to spawn (or spawnc) may
 248 return; it may call the exit function, or it may have an uncaught
 249 exception.  Note that <span class="monospaced">joinEvt</span> does not distinguish between these
 250 cases; it also does not become enabled if the named thread deadlocks
 251 (even if it is garbage collected).</p></div>
 252 </li>
 253 </ul></div>
 254 </div>
 255 <div class="attribution">
 256 </div></div>
 257 <div class="paragraph"><p>I believe that the <span class="monospaced">MLton.Finalizable</span> might be able to relax that
 258 last restriction.  Upon the creation of a <span class="monospaced">'a Scheduler.thread</span>, we
 259 could attach a finalizer to the underlying <span class="monospaced">'a MLton.Thread.t</span> that
 260 enables the <span class="monospaced">joinEvt</span> (in the associated <span class="monospaced">ThreadID.thread_id</span>) when
 261 the <span class="monospaced">'a MLton.Thread.t</span> becomes unreachable.</p></div>
 262 <div class="paragraph"><p>I don&#8217;t know why CML doesn&#8217;t have</p></div>
 263 <div class="listingblock">
 264 <div class="content monospaced">
 265 <pre>CML.kill: thread_id -&gt; unit</pre>
 266 </div></div>
 267 <div class="paragraph"><p>which has a fairly simple implementation&#8201;&#8212;&#8201;setting a kill flag in the
 268 <span class="monospaced">thread_id</span> and adjusting the scheduler to discard any killed threads
 269 that it takes off the ready queue.  The fairness of the scheduler
 270 ensures that a killed thread will eventually be discarded.  The
 271 semantics are little murky for blocked threads that are killed,
 272 though.  For example, consider a thread blocked on <span class="monospaced">SyncVar.mTake mv</span>
 273 and a thread blocked on <span class="monospaced">SyncVar.mGet mv</span>.  If the first thread is
 274 killed while blocked, and a third thread does <span class="monospaced">SyncVar.mPut (mv, x)</span>,
 275 then we might expect that we&#8217;ll enable the second thread, and never
 276 the first.  But, when only the ready queue is able to discard killed
 277 threads, then the <span class="monospaced">SyncVar.mPut</span> could enable the first thread
 278 (putting it on the ready queue, from which it will be discarded) and
 279 leave the second thread blocked.  We could solve this by adjusting the
 280 <span class="monospaced">TransID.trans_id types</span> and the "cleaner" functions to look for both
 281 canceled transactions and transactions on killed threads.</p></div>
 282 <div class="paragraph"><p>John Reppy says that <a href="References#MarlowEtAl01">MarlowEtAl01</a> and <a href="References#FlattFindler04">FlattFindler04</a>
 283 explain why <span class="monospaced">CML.kill</span> would be a bad idea.</p></div>
 284 <div class="paragraph"><p>Between <span class="monospaced">CML.timeOutEvt</span> and <span class="monospaced">CML.kill</span>, one could give an efficient
 285 solution to the recent <span class="monospaced">comp.lang.ml</span> post about terminating a
 286 function that doesn&#8217;t complete in a given time.</p></div>
 287 <div class="listingblock">
 288 <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>
 289 <span class="w">    </span><span class="k">let</span><span class="w"></span>
 290 <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>
 291 <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>
 292 <span class="w">    </span><span class="k">in</span><span class="w"></span>
 293 <span class="w">       </span><span class="n">CML</span><span class="p">.</span><span class="n">select</span><span class="w"></span>
 294 <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>
 295 <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>
 296 <span class="w">    </span><span class="k">end</span><span class="w"></span>
 297 </pre></div></div></div>
 298 </div>
 299 </div>
 300 <div class="sect1">
 301 <h2 id="_space_safety">Space Safety</h2>
 302 <div class="sectionbody">
 303 <div class="paragraph"><p>There are some CML related posts on the MLton mailing list:</p></div>
 304 <div class="ulist"><ul>
 305 <li>
 306 <p>
 307 <a href="http://www.mlton.org/pipermail/mlton/2004-May/">http://www.mlton.org/pipermail/mlton/2004-May/</a>
 308 </p>
 309 </li>
 310 </ul></div>
 311 <div class="paragraph"><p>that discuss concerns that SML/NJ&#8217;s implementation is not space
 312 efficient, because multi-shot continuations can be held indefinitely
 313 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
 314 waiting in other event queues get turned into dead threads (of zero
 315 size).</p></div>
 316 </div>
 317 </div>
 318 </div>
 319 <div id="footnotes"><hr></div>
 320 <div id="footer">
 321 <div id="footer-text">
 322 </div>
 323 <div id="footer-badges">
 324 </div>
 325 </div>
 326 </body>
 327 </html>