doc/guide/localhost/ReturnStatement

   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>ReturnStatement</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>ReturnStatement</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>Programmers coming from languages that have a <span class="monospaced">return</span> statement, such
  32 as C, Java, and Python, often ask how one can translate functions that
  33 return early into SML.  This page briefly describes a number of ways
  34 to translate uses of <span class="monospaced">return</span> to SML.</p></div>
  35 </div>
  36 </div>
  37 <div class="sect1">
  38 <h2 id="_conditional_iterator_function">Conditional iterator function</h2>
  39 <div class="sectionbody">
  40 <div class="paragraph"><p>A conditional iterator function, such as
  41 <a href="http://www.standardml.org/Basis/list.html#SIG:LIST.find:VAL"><span class="monospaced">List.find</span></a>,
  42 <a href="http://www.standardml.org/Basis/list.html#SIG:LIST.exists:VAL"><span class="monospaced">List.exists</span></a>,
  43 or
  44 <a href="http://www.standardml.org/Basis/list.html#SIG:LIST.all:VAL"><span class="monospaced">List.all</span></a>
  45 is probably what you want in most cases.  Unfortunately, it might be
  46 the case that the particular conditional iteration pattern that you
  47 want isn&#8217;t provided for your data structure.  Usually the best
  48 alternative in such a case is to implement the desired iteration
  49 pattern as a higher-order function.  For example, to implement a
  50 <span class="monospaced">find</span> function for arrays (which already exists as
  51 <a href="http://www.standardml.org/Basis/array.html#SIG:ARRAY.findi:VAL"><span class="monospaced">Array.find</span></a>)
  52 one could write</p></div>
  53 <div class="listingblock">
  54 <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>
  55 <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>
  56 <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>
  57 <span class="w">          </span><span class="n">NONE</span><span class="w"></span>
  58 <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>
  59 <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>
  60 <span class="w">       </span><span class="k">else</span><span class="w"></span>
  61 <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>
  62 <span class="k">in</span><span class="w"></span>
  63 <span class="w">   </span><span class="n">loop</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
  64 <span class="k">end</span><span class="w"></span>
  65 </pre></div></div></div>
  66 <div class="paragraph"><p>Of course, this technique, while probably the most common case in
  67 practice, applies only if you are essentially iterating over some data
  68 structure.</p></div>
  69 </div>
  70 </div>
  71 <div class="sect1">
  72 <h2 id="_escape_handler">Escape handler</h2>
  73 <div class="sectionbody">
  74 <div class="paragraph"><p>Probably the most direct way to translate code using <span class="monospaced">return</span>
  75 statements is to basically implement <span class="monospaced">return</span> using exception
  76 handling.  The mechanism can be packaged into a reusable module with
  77 the signature
  78 (<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>
  79 <div class="listingblock">
  80 <div class="content"><div class="highlight"><pre><span class="cm">(**</span>
  81 <span class="cm"> * Signature for exit (or escape) handlers.</span>
  82 <span class="cm"> *</span>
  83 <span class="cm"> * Note that the implementation necessarily uses exception handling.  This</span>
  84 <span class="cm"> * is to make proper resource handling possible.  Exceptions raised by the</span>
  85 <span class="cm"> * implementation can be caught by wildcard exception handlers.  Wildcard</span>
  86 <span class="cm"> * exception handlers should generally reraise exceptions after performing</span>
  87 <span class="cm"> * their effects.</span>
  88 <span class="cm"> *)</span><span class="w"></span>
  89 <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>
  90 <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>
  91 <span class="w">   </span><span class="cm">(** The type of exits. *)</span><span class="w"></span>
  92
  93 <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>
  94 <span class="w">   </span><span class="cm">(**</span>
  95 <span class="cm">    * Sets up an exit and passes it to the given function.  The function</span>
  96 <span class="cm">    * may then return normally or by calling {to} with the exit and a</span>
  97 <span class="cm">    * return value.  For example,</span>
  98 <span class="cm">    *</span>
  99 <span class="cm">    *&gt; Exit.within</span>
 100 <span class="cm">    *&gt;    (fn l =&gt;</span>
 101 <span class="cm">    *&gt;        if condition then</span>
 102 <span class="cm">    *&gt;           Exit.to l 1</span>
 103 <span class="cm">    *&gt;        else</span>
 104 <span class="cm">    *&gt;           2)</span>
 105 <span class="cm">    *</span>
 106 <span class="cm">    * evaluates either to {1} or to {2} depending on the {condition}.</span>
 107 <span class="cm">    *</span>
 108 <span class="cm">    * Note that the function receiving the exit is called from a non-tail</span>
 109 <span class="cm">    * position.</span>
 110 <span class="cm">    *)</span><span class="w"></span>
 111
 112 <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>
 113 <span class="w">   </span><span class="cm">(**</span>
 114 <span class="cm">    * {to l v} returns from the {within} invocation that introduced the</span>
 115 <span class="cm">    * exit {l} with the value {v}.  Evaluating {to l v} outside of the</span>
 116 <span class="cm">    * {within} invocation that introduced {l} is a programming error and</span>
 117 <span class="cm">    * raises an exception.</span>
 118 <span class="cm">    *</span>
 119 <span class="cm">    * Note that the type variable {&#39;b} only appears as the return type.</span>
 120 <span class="cm">    * This means that {to} doesn&#39;t return normally to the caller and can</span>
 121 <span class="cm">    * be called from a context of any type.</span>
 122 <span class="cm">    *)</span><span class="w"></span>
 123
 124 <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>
 125 <span class="w">   </span><span class="cm">(**</span>
 126 <span class="cm">    * Simpler, but less flexibly typed, interface to {within} and {to}.</span>
 127 <span class="cm">    * Specifically, {call f} is equivalent to {within (f o to)}.</span>
 128 <span class="cm">    *)</span><span class="w"></span>
 129 <span class="k">end</span><span class="w"></span>
 130 </pre></div></div></div>
 131 <div class="paragraph"><p>(<a href="References#HarperEtAl93"> Typing First-Class Continuations in ML</a>
 132 discusses the typing of a related construct.)  The implementation
 133 (<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>)
 134 is straightforward:</p></div>
 135 <div class="listingblock">
 136 <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>
 137 <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>
 138
 139 <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>
 140 <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>
 141 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 142 <span class="w">      </span><span class="n">block</span><span class="w"> </span><span class="n">EscapedExit</span><span class="w"></span>
 143 <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>
 144 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 145
 146 <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>
 147
 148 <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>
 149 <span class="k">end</span><span class="w"></span>
 150 </pre></div></div></div>
 151 <div class="paragraph"><p>Here is an example of how one could implement a <span class="monospaced">find</span> function given
 152 an <span class="monospaced">app</span> function:</p></div>
 153 <div class="listingblock">
 154 <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>
 155 <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>
 156 <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>
 157 <span class="w">    </span><span class="n">Exit</span><span class="p">.</span><span class="n">call</span><span class="w"></span>
 158 <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>
 159 <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>
 160 <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>
 161 <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>
 162 <span class="w">                    </span><span class="k">else</span><span class="w"></span>
 163 <span class="w">                       </span><span class="p">())</span><span class="w"></span>
 164 <span class="w">                </span><span class="n">data</span><span class="w"></span>
 165 <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>
 166 </pre></div></div></div>
 167 <div class="paragraph"><p>In the above, as soon as the expression <span class="monospaced">predicate x</span> evaluates to
 168 <span class="monospaced">true</span> the <span class="monospaced">app</span> invocation is terminated.</p></div>
 169 </div>
 170 </div>
 171 <div class="sect1">
 172 <h2 id="_continuation_passing_style_cps">Continuation-passing Style (CPS)</h2>
 173 <div class="sectionbody">
 174 <div class="paragraph"><p>A general way to implement complex control patterns is to use
 175 <a href="http://en.wikipedia.org/wiki/Continuation-passing_style">CPS</a>.  In CPS,
 176 instead of returning normally, functions invoke a function passed as
 177 an argument.  In general, multiple continuation functions may be
 178 passed as arguments and the ordinary return continuation may also be
 179 used.  As an example, here is a function that finds the leftmost
 180 element of a binary tree satisfying a given predicate:</p></div>
 181 <div class="listingblock">
 182 <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>
 183
 184 <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>
 185 <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>
 186 <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>
 187 <span class="w">          </span><span class="n">continue</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 188 <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>
 189 <span class="w">          </span><span class="n">recurse</span><span class="w"></span>
 190 <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>
 191 <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>
 192 <span class="w">                    </span><span class="n">SOME</span><span class="w"> </span><span class="n">elem</span><span class="w"></span>
 193 <span class="w">                 </span><span class="k">else</span><span class="w"></span>
 194 <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>
 195 <span class="w">             </span><span class="n">lhs</span><span class="w"></span>
 196 <span class="k">in</span><span class="w"></span>
 197 <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>
 198 <span class="k">end</span><span class="w"></span>
 199 </pre></div></div></div>
 200 <div class="paragraph"><p>Note that the above function returns as soon as the leftmost element
 201 satisfying the predicate is found.</p></div>
 202 </div>
 203 </div>
 204 </div>
 205 <div id="footnotes"><hr></div>
 206 <div id="footer">
 207 <div id="footer-text">
 208 </div>
 209 <div id="footer-badges">
 210 </div>
 211 </div>
 212 </body>
 213 </html>