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

<!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>ReturnStatement</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>ReturnStatement</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p>Programmers coming from languages that have a <span class="monospaced">return</span> statement, such\r
as C, Java, and Python, often ask how one can translate functions that\r
return early into SML.  This page briefly describes a number of ways\r
to translate uses of <span class="monospaced">return</span> to SML.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_conditional_iterator_function">Conditional iterator function</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>A conditional iterator function, such as\r
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.find:VAL"><span class="monospaced">List.find</span></a>,\r
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.exists:VAL"><span class="monospaced">List.exists</span></a>,\r
or\r
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.all:VAL"><span class="monospaced">List.all</span></a>\r
is probably what you want in most cases.  Unfortunately, it might be\r
the case that the particular conditional iteration pattern that you\r
want isn&#8217;t provided for your data structure.  Usually the best\r
alternative in such a case is to implement the desired iteration\r
pattern as a higher-order function.  For example, to implement a\r
<span class="monospaced">find</span> function for arrays (which already exists as\r
<a href="http://www.standardml.org/Basis/array.html#SIG:ARRAY.findi:VAL"><span class="monospaced">Array.find</span></a>)\r
one could write</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">find</span><span class="w"> </span><span class="n">predicate</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>\r
<span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">       </span><span class="k">if</span><span class="w"> </span><span class="n">i</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Array</span><span class="p">.</span><span class="n">length</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="k">then</span><span class="w"></span>\r
<span class="w">          </span><span class="n">NONE</span><span class="w"></span>\r
<span class="w">       </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">predicate</span><span class="w"> </span><span class="p">(</span><span class="n">Array</span><span class="p">.</span><span class="n">sub</span><span class="w"> </span><span class="p">(</span><span class="n">array</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"> </span><span class="k">then</span><span class="w"></span>\r
<span class="w">          </span><span class="n">SOME</span><span class="w"> </span><span class="p">(</span><span class="n">Array</span><span class="p">.</span><span class="n">sub</span><span class="w"> </span><span class="p">(</span><span class="n">array</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">))</span><span class="w"></span>\r
<span class="w">       </span><span class="k">else</span><span class="w"></span>\r
<span class="w">          </span><span class="n">loop</span><span class="w"> </span><span class="p">(</span><span class="n">i+</span><span class="mi">1</span><span class="p">)</span><span class="w"></span>\r
<span class="k">in</span><span class="w"></span>\r
<span class="w">   </span><span class="n">loop</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>\r
<span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Of course, this technique, while probably the most common case in\r
practice, applies only if you are essentially iterating over some data\r
structure.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_escape_handler">Escape handler</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>Probably the most direct way to translate code using <span class="monospaced">return</span>\r
statements is to basically implement <span class="monospaced">return</span> using exception\r
handling.  The mechanism can be packaged into a reusable module with\r
the signature\r
(<a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/extended-basis/unstable/public/control/exit.sig"><span class="monospaced">exit.sig</span></a>):</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="cm">(**</span>\r
<span class="cm"> * Signature for exit (or escape) handlers.</span>\r
<span class="cm"> *</span>\r
<span class="cm"> * Note that the implementation necessarily uses exception handling.  This</span>\r
<span class="cm"> * is to make proper resource handling possible.  Exceptions raised by the</span>\r
<span class="cm"> * implementation can be caught by wildcard exception handlers.  Wildcard</span>\r
<span class="cm"> * exception handlers should generally reraise exceptions after performing</span>\r
<span class="cm"> * their effects.</span>\r
<span class="cm"> *)</span><span class="w"></span>\r
<span class="k">signature</span><span class="w"> </span><span class="n">EXIT</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">sig</span><span class="w"></span>\r
<span class="w">   </span><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="w">   </span><span class="cm">(** The type of exits. *)</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">within</span><span class="w"> </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="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="n">CPS</span><span class="p">.</span><span class="n">t</span><span class="w"></span>\r
<span class="w">   </span><span class="cm">(**</span>\r
<span class="cm">    * Sets up an exit and passes it to the given function.  The function</span>\r
<span class="cm">    * may then return normally or by calling {to} with the exit and a</span>\r
<span class="cm">    * return value.  For example,</span>\r
<span class="cm">    *</span>\r
<span class="cm">    *&gt; Exit.within</span>\r
<span class="cm">    *&gt;    (fn l =&gt;</span>\r
<span class="cm">    *&gt;        if condition then</span>\r
<span class="cm">    *&gt;           Exit.to l 1</span>\r
<span class="cm">    *&gt;        else</span>\r
<span class="cm">    *&gt;           2)</span>\r
<span class="cm">    *</span>\r
<span class="cm">    * evaluates either to {1} or to {2} depending on the {condition}.</span>\r
<span class="cm">    *</span>\r
<span class="cm">    * Note that the function receiving the exit is called from a non-tail</span>\r
<span class="cm">    * position.</span>\r
<span class="cm">    *)</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">to</span><span class="w"> </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="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
<span class="w">   </span><span class="cm">(**</span>\r
<span class="cm">    * {to l v} returns from the {within} invocation that introduced the</span>\r
<span class="cm">    * exit {l} with the value {v}.  Evaluating {to l v} outside of the</span>\r
<span class="cm">    * {within} invocation that introduced {l} is a programming error and</span>\r
<span class="cm">    * raises an exception.</span>\r
<span class="cm">    *</span>\r
<span class="cm">    * Note that the type variable {&#39;b} only appears as the return type.</span>\r
<span class="cm">    * This means that {to} doesn&#39;t return normally to the caller and can</span>\r
<span class="cm">    * be called from a context of any type.</span>\r
<span class="cm">    *)</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">call</span><span class="w"> </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">&#39;b</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="n">CPS</span><span class="p">.</span><span class="n">t</span><span class="w"></span>\r
<span class="w">   </span><span class="cm">(**</span>\r
<span class="cm">    * Simpler, but less flexibly typed, interface to {within} and {to}.</span>\r
<span class="cm">    * Specifically, {call f} is equivalent to {within (f o to)}.</span>\r
<span class="cm">    *)</span><span class="w"></span>\r
<span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>(<a href="References#HarperEtAl93"> Typing First-Class Continuations in ML</a>\r
discusses the typing of a related construct.)  The implementation\r
(<a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/extended-basis/unstable/detail/control/exit.sml"><span class="monospaced">exit.sml</span></a>)\r
is straightforward:</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Exit</span><span class="w"> </span><span class="p">:&gt;</span><span class="w"> </span><span class="n">EXIT</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">struct</span><span class="w"></span>\r
<span class="w">   </span><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><span class="p">=</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">exn</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">within</span><span class="w"> </span><span class="n">block</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>\r
<span class="w">      </span><span class="k">exception</span><span class="w"> </span><span class="n">EscapedExit</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</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">block</span><span class="w"> </span><span class="n">EscapedExit</span><span class="w"></span>\r
<span class="w">      </span><span class="k">handle</span><span class="w"> </span><span class="n">EscapedExit</span><span class="w"> </span><span class="n">value</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">value</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">exit</span><span class="w"> </span><span class="n">value</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">exit</span><span class="w"> </span><span class="n">value</span><span class="w"></span>\r
\r
<span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">call</span><span class="w"> </span><span class="n">block</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">within</span><span class="w"> </span><span class="p">(</span><span class="n">block</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">to</span><span class="p">)</span><span class="w"></span>\r
<span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Here is an example of how one could implement a <span class="monospaced">find</span> function given\r
an <span class="monospaced">app</span> function:</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">appToFind</span><span class="w"> </span><span class="p">(</span><span class="n">app</span><span class="w"> </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;b</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="p">(</span><span class="n">predicate</span><span class="w"> </span><span class="p">:</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">bool</span><span class="p">)</span><span class="w"></span>\r
<span class="w">              </span><span class="p">(</span><span class="n">data</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;b</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">Exit</span><span class="p">.</span><span class="n">call</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="n">return</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">app</span><span class="w"> </span><span class="p">(</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>\r
<span class="w">                    </span><span class="k">if</span><span class="w"> </span><span class="n">predicate</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">then</span><span class="w"></span>\r
<span class="w">                       </span><span class="n">return</span><span class="w"> </span><span class="p">(</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">else</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="n">data</span><span class="w"></span>\r
<span class="w">          </span><span class="p">;</span><span class="w"> </span><span class="n">NONE</span><span class="p">))</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>In the above, as soon as the expression <span class="monospaced">predicate x</span> evaluates to\r
<span class="monospaced">true</span> the <span class="monospaced">app</span> invocation is terminated.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_continuation_passing_style_cps">Continuation-passing Style (CPS)</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>A general way to implement complex control patterns is to use\r
<a href="http://en.wikipedia.org/wiki/Continuation-passing_style">CPS</a>.  In CPS,\r
instead of returning normally, functions invoke a function passed as\r
an argument.  In general, multiple continuation functions may be\r
passed as arguments and the ordinary return continuation may also be\r
used.  As an example, here is a function that finds the leftmost\r
element of a binary tree satisfying a given predicate:</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">tree</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">LEAF</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">BRANCH</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">tree</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="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">tree</span><span class="w"></span>\r
\r
<span class="k">fun</span><span class="w"> </span><span class="n">find</span><span class="w"> </span><span class="n">predicate</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>\r
<span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">recurse</span><span class="w"> </span><span class="n">continue</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">       </span><span class="k">fn</span><span class="w"> </span><span class="n">LEAF</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>\r
<span class="w">          </span><span class="n">continue</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">BRANCH</span><span class="w"> </span><span class="p">(</span><span class="n">lhs</span><span class="p">,</span><span class="w"> </span><span class="n">elem</span><span class="p">,</span><span class="w"> </span><span class="n">rhs</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="n">recurse</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>\r
<span class="w">                 </span><span class="k">if</span><span class="w"> </span><span class="n">predicate</span><span class="w"> </span><span class="n">elem</span><span class="w"> </span><span class="k">then</span><span class="w"></span>\r
<span class="w">                    </span><span class="n">SOME</span><span class="w"> </span><span class="n">elem</span><span class="w"></span>\r
<span class="w">                 </span><span class="k">else</span><span class="w"></span>\r
<span class="w">                    </span><span class="n">recurse</span><span class="w"> </span><span class="n">continue</span><span class="w"> </span><span class="n">rhs</span><span class="p">)</span><span class="w"></span>\r
<span class="w">             </span><span class="n">lhs</span><span class="w"></span>\r
<span class="k">in</span><span class="w"></span>\r
<span class="w">   </span><span class="n">recurse</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">NONE</span><span class="p">)</span><span class="w"></span>\r
<span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>Note that the above function returns as soon as the leftmost element\r
satisfying the predicate is found.</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