<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.9">
<title>ReturnStatement</title>
<link rel="stylesheet" href="./asciidoc.css" type="text/css">
<link rel="stylesheet" href="./pygments.css" type="text/css">


<script type="text/javascript" src="./asciidoc.js"></script>
<script type="text/javascript">
/*<![CDATA[*/
asciidoc.install();
/*]]>*/
</script>
<link rel="stylesheet" href="./mlton.css" type="text/css"/>
</head>
<body class="article">
<div id="banner">
<div id="banner-home">
<a href="./Home">MLton 20130715</a>
</div>
</div>
<div id="header">
<h1>ReturnStatement</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>Programmers coming from languages that have a <span class="monospaced">return</span> statement, such
as C, Java, and Python, often ask how one can translate functions that
return early into SML.  This page briefly describes a number of ways
to translate uses of <span class="monospaced">return</span> to SML.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_conditional_iterator_function">Conditional iterator function</h2>
<div class="sectionbody">
<div class="paragraph"><p>A conditional iterator function, such as
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.find:VAL"><span class="monospaced">List.find</span></a>,
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.exists:VAL"><span class="monospaced">List.exists</span></a>,
or
<a href="http://www.standardml.org/Basis/list.html#SIG:LIST.all:VAL"><span class="monospaced">List.all</span></a>
is probably what you want in most cases.  Unfortunately, it might be
the case that the particular conditional iteration pattern that you
want isn&#8217;t provided for your data structure.  Usually the best
alternative in such a case is to implement the desired iteration
pattern as a higher-order function.  For example, to implement a
<span class="monospaced">find</span> function for arrays (which already exists as
<a href="http://www.standardml.org/Basis/array.html#SIG:ARRAY.findi:VAL"><span class="monospaced">Array.find</span></a>)
one could write</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="kr">fun</span> <span class="nf">find</span> <span class="n">predicate</span> <span class="n">array</span> <span class="p">=</span> <span class="kr">let</span>
   <span class="kr">fun</span> <span class="nf">loop</span> <span class="n">i</span> <span class="p">=</span>
       <span class="kr">if</span> <span class="n">i</span> <span class="p">=</span> <span class="nn">Array</span><span class="p">.</span><span class="n">length</span> <span class="n">array</span> <span class="kr">then</span>
          <span class="n">NONE</span>
       <span class="kr">else</span> <span class="kr">if</span> <span class="n">predicate</span> <span class="p">(</span><span class="nn">Array</span><span class="p">.</span><span class="n">sub</span> <span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">i</span><span class="p">))</span> <span class="kr">then</span>
          <span class="n">SOME</span> <span class="p">(</span><span class="nn">Array</span><span class="p">.</span><span class="n">sub</span> <span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">i</span><span class="p">))</span>
       <span class="kr">else</span>
          <span class="n">loop</span> <span class="p">(</span><span class="n">i+</span><span class="mi">1</span><span class="p">)</span>
<span class="kr">in</span>
   <span class="n">loop</span> <span class="mi">0</span>
<span class="kr">end</span>
</pre></div></div></div>
<div class="paragraph"><p>Of course, this technique, while probably the most common case in
practice, applies only if you are essentially iterating over some data
structure.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_escape_handler">Escape handler</h2>
<div class="sectionbody">
<div class="paragraph"><p>Probably the most direct way to translate code using <span class="monospaced">return</span>
statements is to basically implement <span class="monospaced">return</span> using exception
handling.  The mechanism can be packaged into a reusable module with
the signature
(<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>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span>
</pre></div></div></div>
<div class="paragraph"><p>(<a href="References#HarperEtAl93"> Typing First-Class Continuations in ML</a>
discusses the typing of a related construct.)  The implementation
(<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>)
is straightforward:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span>
</pre></div></div></div>
<div class="paragraph"><p>Here is an example of how one could implement a <span class="monospaced">find</span> function given
an <span class="monospaced">app</span> function:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="kr">fun</span> <span class="nf">appToFind</span> <span class="p">(</span><span class="n">app</span> <span class="p">:</span> <span class="p">(</span><span class="nd">&#39;a</span> <span class="p">-&gt;</span> <span class="n">unit</span><span class="p">)</span> <span class="p">-&gt;</span> <span class="nd">&#39;b</span> <span class="p">-&gt;</span> <span class="n">unit</span><span class="p">)</span>
              <span class="p">(</span><span class="n">predicate</span> <span class="p">:</span> <span class="nd">&#39;a</span> <span class="p">-&gt;</span> <span class="n">bool</span><span class="p">)</span>
              <span class="p">(</span><span class="n">data</span> <span class="p">:</span> <span class="nd">&#39;b</span><span class="p">)</span> <span class="p">=</span>
    <span class="nn">Exit</span><span class="p">.</span><span class="n">call</span>
       <span class="p">(</span><span class="kr">fn</span> <span class="n">return</span> <span class="p">=&gt;</span>
           <span class="p">(</span><span class="n">app</span> <span class="p">(</span><span class="kr">fn</span> <span class="n">x</span> <span class="p">=&gt;</span>
                    <span class="kr">if</span> <span class="n">predicate</span> <span class="n">x</span> <span class="kr">then</span>
                       <span class="n">return</span> <span class="p">(</span><span class="n">SOME</span> <span class="n">x</span><span class="p">)</span>
                    <span class="kr">else</span>
                       <span class="p">())</span>
                <span class="n">data</span>
          <span class="p">;</span> <span class="n">NONE</span><span class="p">))</span>
</pre></div></div></div>
<div class="paragraph"><p>In the above, as soon as the expression <span class="monospaced">predicate x</span> evaluates to
<span class="monospaced">true</span> the <span class="monospaced">app</span> invocation is terminated.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_continuation_passing_style_cps">Continuation-passing Style (CPS)</h2>
<div class="sectionbody">
<div class="paragraph"><p>A general way to implement complex control patterns is to use
<a href="http://en.wikipedia.org/wiki/Continuation-passing_style">CPS</a>.  In CPS,
instead of returning normally, functions invoke a function passed as
an argument.  In general, multiple continuation functions may be
passed as arguments and the ordinary return continuation may also be
used.  As an example, here is a function that finds the leftmost
element of a binary tree satisfying a given predicate:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="kr">datatype</span> <span class="nd">&#39;a</span> <span class="kt">tree</span> <span class="p">=</span> <span class="nc">LEAF</span> <span class="p">|</span> <span class="nc">BRANCH</span> <span class="kr">of</span> <span class="nd">&#39;a</span> <span class="n">tree</span> <span class="n">*</span> <span class="nd">&#39;a</span> <span class="n">*</span> <span class="nd">&#39;a</span> <span class="n">tree</span>

<span class="kr">fun</span> <span class="nf">find</span> <span class="n">predicate</span> <span class="p">=</span> <span class="kr">let</span>
   <span class="kr">fun</span> <span class="nf">recurse</span> <span class="n">continue</span> <span class="p">=</span>
       <span class="kr">fn</span> <span class="n">LEAF</span> <span class="p">=&gt;</span>
          <span class="n">continue</span> <span class="p">()</span>
        <span class="p">|</span> <span class="nf">BRANCH</span> <span class="p">(</span><span class="n">lhs</span><span class="p">,</span> <span class="n">elem</span><span class="p">,</span> <span class="n">rhs</span><span class="p">)</span> <span class="p">=&gt;</span>
          <span class="n">recurse</span>
             <span class="p">(</span><span class="kr">fn</span> <span class="p">()</span> <span class="p">=&gt;</span>
                 <span class="kr">if</span> <span class="n">predicate</span> <span class="n">elem</span> <span class="kr">then</span>
                    <span class="n">SOME</span> <span class="n">elem</span>
                 <span class="kr">else</span>
                    <span class="n">recurse</span> <span class="n">continue</span> <span class="n">rhs</span><span class="p">)</span>
             <span class="n">lhs</span>
<span class="kr">in</span>
   <span class="n">recurse</span> <span class="p">(</span><span class="kr">fn</span> <span class="p">()</span> <span class="p">=&gt;</span> <span class="n">NONE</span><span class="p">)</span>
<span class="kr">end</span>
</pre></div></div></div>
<div class="paragraph"><p>Note that the above function returns as soon as the leftmost element
satisfying the predicate is found.</p></div>
</div>
</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
</div>
<div id="footer-badges">
</div>
</div>
</body>
</html>
