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
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.8">
<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’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 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>
<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>
<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>
<span class="w"> </span><span class="n">NONE</span><span class="w"></span>
<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>
<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>
<span class="w"> </span><span class="k">else</span><span class="w"></span>
<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>
<span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">loop</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="k">end</span><span class="w"></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 class="cm">(**</span>
<span class="cm"> * Signature for exit (or escape) handlers.</span>
<span class="cm"> *</span>
<span class="cm"> * Note that the implementation necessarily uses exception handling. This</span>
<span class="cm"> * is to make proper resource handling possible. Exceptions raised by the</span>
<span class="cm"> * implementation can be caught by wildcard exception handlers. Wildcard</span>
<span class="cm"> * exception handlers should generally reraise exceptions after performing</span>
<span class="cm"> * their effects.</span>
<span class="cm"> *)</span><span class="w"></span>
<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>
<span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
<span class="w"> </span><span class="cm">(** The type of exits. *)</span><span class="w"></span>
<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">'a</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">'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>
<span class="w"> </span><span class="cm">(**</span>
<span class="cm"> * Sets up an exit and passes it to the given function. The function</span>
<span class="cm"> * may then return normally or by calling {to} with the exit and a</span>
<span class="cm"> * return value. For example,</span>
<span class="cm"> *</span>
<span class="cm"> *> Exit.within</span>
<span class="cm"> *> (fn l =></span>
<span class="cm"> *> if condition then</span>
<span class="cm"> *> Exit.to l 1</span>
<span class="cm"> *> else</span>
<span class="cm"> *> 2)</span>
<span class="cm"> *</span>
<span class="cm"> * evaluates either to {1} or to {2} depending on the {condition}.</span>
<span class="cm"> *</span>
<span class="cm"> * Note that the function receiving the exit is called from a non-tail</span>
<span class="cm"> * position.</span>
<span class="cm"> *)</span><span class="w"></span>
<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">'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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'b</span><span class="w"></span>
<span class="w"> </span><span class="cm">(**</span>
<span class="cm"> * {to l v} returns from the {within} invocation that introduced the</span>
<span class="cm"> * exit {l} with the value {v}. Evaluating {to l v} outside of the</span>
<span class="cm"> * {within} invocation that introduced {l} is a programming error and</span>
<span class="cm"> * raises an exception.</span>
<span class="cm"> *</span>
<span class="cm"> * Note that the type variable {'b} only appears as the return type.</span>
<span class="cm"> * This means that {to} doesn't return normally to the caller and can</span>
<span class="cm"> * be called from a context of any type.</span>
<span class="cm"> *)</span><span class="w"></span>
<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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'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>
<span class="w"> </span><span class="cm">(**</span>
<span class="cm"> * Simpler, but less flexibly typed, interface to {within} and {to}.</span>
<span class="cm"> * Specifically, {call f} is equivalent to {within (f o to)}.</span>
<span class="cm"> *)</span><span class="w"></span>
<span class="k">end</span><span class="w"></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 class="k">structure</span><span class="w"> </span><span class="n">Exit</span><span class="w"> </span><span class="p">:></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>
<span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">'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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">exn</span><span class="w"></span>
<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>
<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">'a</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">block</span><span class="w"> </span><span class="n">EscapedExit</span><span class="w"></span>
<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">=></span><span class="w"> </span><span class="n">value</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<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>
<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>
<span class="k">end</span><span class="w"></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 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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'b</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">unit</span><span class="p">)</span><span class="w"></span>
<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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">bool</span><span class="p">)</span><span class="w"></span>
<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">'b</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="n">Exit</span><span class="p">.</span><span class="n">call</span><span class="w"></span>
<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">=></span><span class="w"></span>
<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">=></span><span class="w"></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="n">x</span><span class="w"> </span><span class="k">then</span><span class="w"></span>
<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>
<span class="w"> </span><span class="k">else</span><span class="w"></span>
<span class="w"> </span><span class="p">())</span><span class="w"></span>
<span class="w"> </span><span class="n">data</span><span class="w"></span>
<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>
</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 class="k">datatype</span><span class="w"> </span><span class="n">'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">'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">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">tree</span><span class="w"></span>
<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>
<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>
<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">=></span><span class="w"></span>
<span class="w"> </span><span class="n">continue</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<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">=></span><span class="w"></span>
<span class="w"> </span><span class="n">recurse</span><span class="w"></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">=></span><span class="w"></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="n">elem</span><span class="w"> </span><span class="k">then</span><span class="w"></span>
<span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">elem</span><span class="w"></span>
<span class="w"> </span><span class="k">else</span><span class="w"></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="n">rhs</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="n">lhs</span><span class="w"></span>
<span class="k">in</span><span class="w"></span>
<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">=></span><span class="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>
<span class="k">end</span><span class="w"></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>
|
