File: ReturnStatement

package info (click to toggle)
mlton 20100608-5.1
  • links: PTS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 36,628 kB
  • ctags: 70,047
  • sloc: ansic: 18,441; lisp: 2,879; makefile: 1,572; sh: 1,326; pascal: 256; asm: 97
file content (222 lines) | stat: -rw-r--r-- 10,774 bytes parent folder | download | duplicates (3) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
<!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>
      &nbsp;<a href = "TitleIndex">Index</a>
      &nbsp;
</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,
    *
    *&gt; Exit.within
    *&gt;    (fn l =&gt;
    *&gt;        if condition then
    *&gt;           Exit.to l 1
    *&gt;        else
    *&gt;           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 -&gt; 'a -&gt; '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 -&gt; '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 :&gt; 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 -&gt; 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 =&gt; 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 -&gt; unit) -&gt; 'b -&gt; unit)
              (predicate : 'a -&gt; bool)
              (data : 'b) =
    Exit.call
       (<B><FONT COLOR="#A020F0">fn</FONT></B> return =&gt;
           (app (<B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt;
                    <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&nbsp;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 =&gt;
          continue ()
        | BRANCH (lhs, elem, rhs) =&gt;
          recurse
             (<B><FONT COLOR="#A020F0">fn</FONT></B> () =&gt;
                 <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> () =&gt; 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>