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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
|
<!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>ValueRestriction</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(2);
/*]]>*/
</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>ValueRestriction</h1>
<div id="toc">
<div id="toctitle">Table of Contents</div>
<noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
</div>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>The value restriction is a rule that governs when type inference is
allowed to polymorphically generalize a value declaration. In short,
the value restriction says that generalization can only occur if the
right-hand side of an expression is syntactically a value. For
example, in</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="s">"foo"</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>the expression <span class="monospaced">fn x => x</span> is syntactically a value, so <span class="monospaced">f</span> has
polymorphic type <span class="monospaced">'a -> 'a</span> and both calls to <span class="monospaced">f</span> type check. On the
other hand, in</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">in</span><span class="w"> </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="n">x</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="s">"foo"</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>the expression <span class="monospaced">let in fn x => end end</span> is not syntactically a value
and so <span class="monospaced">f</span> can either have type <span class="monospaced">int -> int</span> or <span class="monospaced">string -> string</span>,
but not <span class="monospaced">'a -> 'a</span>. Hence, the program does not type check.</p></div>
<div class="paragraph"><p><a href="DefinitionOfStandardML">The Definition of Standard ML</a> spells out
precisely which expressions are syntactic values (it refers to such
expressions as <em>non-expansive</em>). An expression is a value if it is of
one of the following forms.</p></div>
<div class="ulist"><ul>
<li>
<p>
a constant (<span class="monospaced">13</span>, <span class="monospaced">"foo"</span>, <span class="monospaced">13.0</span>, …)
</p>
</li>
<li>
<p>
a variable (<span class="monospaced">x</span>, <span class="monospaced">y</span>, …)
</p>
</li>
<li>
<p>
a function (<span class="monospaced">fn x => e</span>)
</p>
</li>
<li>
<p>
the application of a constructor other than <span class="monospaced">ref</span> to a value (<span class="monospaced">Foo v</span>)
</p>
</li>
<li>
<p>
a type constrained value (<span class="monospaced">v: t</span>)
</p>
</li>
<li>
<p>
a tuple in which each field is a value <span class="monospaced">(v1, v2, ...)</span>
</p>
</li>
<li>
<p>
a record in which each field is a value <span class="monospaced">{l1 = v1, l2 = v2, ...}</span>
</p>
</li>
<li>
<p>
a list in which each element is a value <span class="monospaced">[v1, v2, ...]</span>
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect1">
<h2 id="_why_the_value_restriction_exists">Why the value restriction exists</h2>
<div class="sectionbody">
<div class="paragraph"><p>The value restriction prevents a ref cell (or an array) from holding
values of different types, which would allow a value of one type to be
cast to another and hence would break type safety. If the restriction
were not in place, the following program would type check.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">r1</span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">r2</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r1</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="s">"foo"</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">v</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">!r2</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The first line violates the value restriction because <span class="monospaced">ref NONE</span> is
not a value. All other lines are type correct. By its last line, the
program has cast the string <span class="monospaced">"foo"</span> to an integer. This breaks type
safety, because now we can add a string to an integer with an
expression like <span class="monospaced">v + 13</span>. We could even be more devious, by adding
the following two lines, which allow us to threat the string <span class="monospaced">"foo"</span>
as a function.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">r3</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">int</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">v</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">!r3</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>Eliminating the explicit <span class="monospaced">ref</span> does nothing to fix the problem. For
example, we could replace the declaration of <span class="monospaced">r</span> with the following.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">unit</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">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </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">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The declaration of <span class="monospaced">f</span> is well typed, while the declaration of <span class="monospaced">r</span>
violates the value restriction because <span class="monospaced">f ()</span> is not a value.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_unnecessarily_rejected_programs">Unnecessarily rejected programs</h2>
<div class="sectionbody">
<div class="paragraph"><p>Unfortunately, the value restriction rejects some programs that could
be accepted.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The type constraint on <span class="monospaced">f</span> requires <span class="monospaced">f</span> to be polymorphic, which is
disallowed because <span class="monospaced">id id</span> is not a value. MLton reports the
following type error.</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>Error: z.sml 2.19.
Can't bind type variable: 'a.
in: val 'a (f): ('a -> 'a) = id id</pre>
</div></div>
<div class="paragraph"><p>MLton indicates the inability to make <span class="monospaced">f</span> polymorphic by saying that
it can’t bind the type variable <span class="monospaced">'a</span> at the declaration. MLton
doesn’t explicitly mention the value restriction, but that is the
reason. If we leave the type constraint off of <span class="monospaced">f</span></p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>then the program succeeds; however, MLton gives us the following
warning.</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>Warning: z.sml 2.1.
Unable to locally determine type of variable: f.
type: ??? -> ???
in: val f = id id</pre>
</div></div>
<div class="paragraph"><p>This warning indicates that MLton couldn’t polymorphically generalize
<span class="monospaced">f</span>, nor was there enough context using <span class="monospaced">f</span> to determine its type.
This in itself is not a type error, but it it is a hint that something
is wrong with our program. Using <span class="monospaced">f</span> provides enough context to
eliminate the warning.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>But attempting to use <span class="monospaced">f</span> as a polymorphic function will fail.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="s">"foo"</span><span class="w"></span>
</pre></div></div></div>
</div>
</div>
<div class="sect1">
<h2 id="_alternatives_to_the_value_restriction">Alternatives to the value restriction</h2>
<div class="sectionbody">
<div class="paragraph"><p>There would be nothing wrong with treating <span class="monospaced">f</span> as polymorphic in</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>One might think that the value restriction could be relaxed, and that
only types involving <span class="monospaced">ref</span> should be disallowed. Unfortunately, the
following example shows that even the type <span class="monospaced">'a -> 'a</span> can cause
problems. If this program were allowed, then we could cast an integer
to a string (or any other type).</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </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">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">!r</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">x</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">y</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">end</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="s">"foo"</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The previous version of Standard ML took a different approach
(<a href="References#MilnerEtAl90">MilnerEtAl90</a>, <a href="References#Tofte90">Tofte90</a>, <a href="ImperativeTypeVariable">ImperativeTypeVariable</a>)
than the value restriction. It encoded information in the type system
about when ref cells would be created, and used this to prevent a ref
cell from holding multiple types. Although it allowed more programs
to be type checked, this approach had significant drawbacks. First,
it was significantly more complex, both for implementers and for
programmers. Second, it had an unfortunate interaction with the
modularity, because information about ref usage was exposed in module
signatures. This either prevented the use of references for
implementing a signature, or required information that one would like
to keep hidden to propagate across modules.</p></div>
<div class="paragraph"><p>In the early nineties, Andrew Wright studied about 250,000 lines of
existing SML code and discovered that it did not make significant use
of the extended typing ability, and proposed the value restriction as
a simpler alternative (<a href="References#Wright95">Wright95</a>). This was adopted in the
revised <a href="DefinitionOfStandardML">Definition</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_working_with_the_value_restriction">Working with the value restriction</h2>
<div class="sectionbody">
<div class="paragraph"><p>One technique that works with the value restriction is
<a href="EtaExpansion">EtaExpansion</a>. We can use eta expansion to make our <span class="monospaced">id id</span>
example type check follows.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">f</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>This solution means that the computation (in this case <span class="monospaced">id id</span>) will
be performed each time <span class="monospaced">f</span> is applied, instead of just once when <span class="monospaced">f</span>
is declared. In this case, that is not a problem, but it could be if
the declaration of <span class="monospaced">f</span> performs substantial computation or creates a
shared data structure.</p></div>
<div class="paragraph"><p>Another technique that sometimes works is to move a monomorphic
computation prior to a (would-be) polymorphic declaration so that the
expression is a value. Consider the following program, which fails
due to the value restriction.</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">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="k">of</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</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="k">val</span><span class="w"> </span><span class="n">x</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="k">if</span><span class="w"> </span><span class="n">true</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="s">"yes"</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="s">"no"</span><span class="p">)</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>It is easy to rewrite this program as</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">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="k">of</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</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="k">local</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">true</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="s">"yes"</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="s">"no"</span><span class="w"></span>
<span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">x</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="n">s</span><span class="w"></span>
<span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The following example (taken from <a href="References#Wright95">Wright95</a>) creates a ref
cell to count the number of times a function is called.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">count</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">'a</span><span class="p">)</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">'a</span><span class="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">int</span><span class="p">)</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">f</span><span class="w"> </span><span class="p">=></span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
<span class="w"> </span><span class="k">in</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">x</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">!r</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="p">),</span><span class="w"> </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">!r</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">countId</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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">numCalls</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The example does not type check, due to the value restriction.
However, it is easy to rewrite the program, staging the ref cell
creation before the polymorphic code.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">datatype</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">T</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">count1</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </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">T</span><span class="w"> </span><span class="p">(</span><span class="n">ref</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">count2</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">*</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">'a</span><span class="p">)</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="p">(</span><span class="n">unit</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="n">*</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">'a</span><span class="p">)</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="p">(</span><span class="n">T</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">=></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">!r</span><span class="p">,</span><span class="w"> </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="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">!r</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">id</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">x</span><span class="w"></span>
<span class="k">val</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">count1</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">countId</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">'a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="p">#</span><span class="mi">2</span><span class="w"> </span><span class="p">(</span><span class="n">count2</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>
<span class="k">val</span><span class="w"> </span><span class="n">numCalls</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">#</span><span class="mi">1</span><span class="w"> </span><span class="p">(</span><span class="n">count2</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">))</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>Of course, one can hide the constructor <span class="monospaced">T</span> inside a <span class="monospaced">local</span> or behind
a signature.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_also_see">Also see</h2>
<div class="sectionbody">
<div class="ulist"><ul>
<li>
<p>
<a href="ImperativeTypeVariable">ImperativeTypeVariable</a>
</p>
</li>
</ul></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>
|
