<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>ReturnStatement - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
ReturnStatement
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
Programmers coming from languages that have a <tt>return</tt> 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 <tt>return</tt> to SML. <h2 id="head-3ca0b14237a353e2e95c23391ec81ba4e1345790">Conditional iterator function</h2>
<p>
A conditional iterator function, such as <a class="external" href="http://mlton.org/basis/list.html#SIG:LIST.find:VAL"><img src="moin-www.png" alt="[WWW]" height="11" width="11">find</a>, <a class="external" href="http://mlton.org/basis/list.html#SIG:LIST.exists:VAL"><img src="moin-www.png" alt="[WWW]" height="11" width="11">exists</a>, or <a class="external" href="http://mlton.org/basis/list.html#SIG:LIST.all:VAL"><img src="moin-www.png" alt="[WWW]" height="11" width="11">all</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'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 <tt>find</tt> function for arrays (which already <a class="external" href="http://mlton.org/basis/array.html#SIG:ARRAY.findi:VAL"><img src="moin-www.png" alt="[WWW]" height="11" width="11">exists</a>) one could write
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> find predicate array = <B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> loop i =
<B><FONT COLOR="#A020F0">if</FONT></B> i = Array.length array <B><FONT COLOR="#A020F0">then</FONT></B>
NONE
<B><FONT COLOR="#A020F0">else</FONT></B> <B><FONT COLOR="#A020F0">if</FONT></B> predicate (Array.sub (array, i)) <B><FONT COLOR="#A020F0">then</FONT></B>
SOME (Array.sub (array, i))
<B><FONT COLOR="#A020F0">else</FONT></B>
loop (i+<B><FONT COLOR="#5F9EA0">1</FONT></B>)
<B><FONT COLOR="#A020F0">in</FONT></B>
loop <B><FONT COLOR="#5F9EA0">0</FONT></B>
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<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>
<h2 id="head-254ec9c154e3b1d82b87b3fde6dfb9207245a618">Escape handler</h2>
<p>
Probably the most direct way to translate code using <tt>return</tt> statements is to basically implement <tt>return</tt> using exception handling. The mechanism can be packaged into a reusable module with the signature (<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/extended-basis/unstable/public/control/exit.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">exit.sig</a>):
</p>
<p>
<pre class=code><I><FONT COLOR="#B22222">(**
* Signature for exit (or escape) handlers.
*
* Note that the implementation necessarily uses exception handling. This
* is to make proper resource handling possible. Exceptions raised by the
* implementation can be caught by wildcard exception handlers. Wildcard
* exception handlers should generally reraise exceptions after performing
* their effects.
*)</FONT></I>
<B><FONT COLOR="#0000FF">signature</FONT></B> EXIT = <B><FONT COLOR="#0000FF">sig</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> 'a t
<I><FONT COLOR="#B22222">(** The type of exits. *)</FONT></I>
</FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> within : ('a t, 'a) CPS.t
<I><FONT COLOR="#B22222">(**
* Sets up an exit and passes it to the given function. The function
* may then return normally or by calling {to} with the exit and a
* return value. For example,
*
*> Exit.within
*> (fn l =>
*> if condition then
*> Exit.to l 1
*> else
*> 2)
*
* evaluates either to {1} or to {2} depending on the {condition}.
*
* Note that the function receiving the exit is called from a non-tail
* position.
*)</FONT></I>
<B><FONT COLOR="#A020F0">val</FONT></B> to : 'a t -> 'a -> 'b
<I><FONT COLOR="#B22222">(**
* {to l v} returns from the {within} invocation that introduced the
* exit {l} with the value {v}. Evaluating {to l v} outside of the
* {within} invocation that introduced {l} is a programming error and
* raises an exception.
*
* Note that the type variable {'b} only appears as the return type.
* This means that {to} doesn't return normally to the caller and can
* be called from a context of any type.
*)</FONT></I>
<B><FONT COLOR="#A020F0">val</FONT></B> call : ('a -> 'b, 'a) CPS.t
<I><FONT COLOR="#B22222">(**
* Simpler, but less flexibly typed, interface to {within} and {to}.
* Specifically, {call f} is equivalent to {within (f o to)}.
*)</FONT></I>
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
</p>
<p>
(<a href = "References#HarperEtAl93"> Typing First-Class Continuations in ML</a> discusses the typing of a related construct.) The implementation (<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mltonlib/trunk/com/ssh/extended-basis/unstable/detail/control/exit.sml?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">exit.sml</a>) is straightforward:
</p>
<p>
<pre class=code><B><FONT COLOR="#0000FF">structure</FONT></B> Exit :> EXIT = <B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> 'a t </FONT></B>=<B><FONT COLOR="#228B22"> 'a -> exn
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> within block = <B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">exception</FONT></B><B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">EscapedExit</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a
</FONT></B><B><FONT COLOR="#A020F0">in</FONT></B>
block EscapedExit
<B><FONT COLOR="#A020F0">handle</FONT></B> EscapedExit value => value
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> to exit value = <B><FONT COLOR="#A020F0">raise</FONT></B> exit value
<B><FONT COLOR="#A020F0">fun</FONT></B> call block = within (block o to)
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
</p>
<p>
Here is an example of how one could implement a <tt>find</tt> function given an <tt>app</tt> function:
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> appToFind (app : ('a -> unit) -> 'b -> unit)
(predicate : 'a -> bool)
(data : 'b) =
Exit.call
(<B><FONT COLOR="#A020F0">fn</FONT></B> return =>
(app (<B><FONT COLOR="#A020F0">fn</FONT></B> x =>
<B><FONT COLOR="#A020F0">if</FONT></B> predicate x <B><FONT COLOR="#A020F0">then</FONT></B>
return (SOME x)
<B><FONT COLOR="#A020F0">else</FONT></B>
())
data
; NONE))
</PRE>
<p>
</p>
<p>
In the above, as soon as the expression <tt>predicate x</tt> evaluates to <tt>true</tt> the <tt>app</tt> invocation is terminated.
</p>
<h2 id="head-c0cae84294cfbcc003917ba0b073cc5acef108d3">Continuation-passing Style (CPS)</h2>
<p>
A general way to implement complex control patterns is to use <a class="external" href="http://en.wikipedia.org/wiki/Continuation-passing_style"><img src="moin-www.png" alt="[WWW]" height="11" width="11">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>
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> 'a tree </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">LEAF</FONT> </FONT></B>|<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">BRANCH</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a tree * 'a * 'a tree
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> find predicate = <B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> recurse continue =
<B><FONT COLOR="#A020F0">fn</FONT></B> LEAF =>
continue ()
| BRANCH (lhs, elem, rhs) =>
recurse
(<B><FONT COLOR="#A020F0">fn</FONT></B> () =>
<B><FONT COLOR="#A020F0">if</FONT></B> predicate elem <B><FONT COLOR="#A020F0">then</FONT></B>
SOME elem
<B><FONT COLOR="#A020F0">else</FONT></B>
recurse continue rhs)
lhs
<B><FONT COLOR="#A020F0">in</FONT></B>
recurse (<B><FONT COLOR="#A020F0">fn</FONT></B> () => NONE)
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<p>
Note that the above function returns as soon as the leftmost element satisfying the predicate is found.
</p>
</div>
<p>
<hr>
Last edited on 2007-03-06 06:55:52 by <span title="cs181143070.pp.htv.fi"><a href="VesaKarvonen">VesaKarvonen</a></span>.
</body></html>
