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
|
<!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>TypeVariableScope - 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%;">
TypeVariableScope
<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">
In <a href="StandardML">Standard ML</a>, every type variable is <em>scoped</em> (or bound) at a particular point in the program. A type variable can be either implicitly scoped or explicitly scoped. For example, <tt>'a</tt> is implicitly scoped in
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
</PRE>
<p>
</p>
<p>
and is implicitly scoped in
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> id = <B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a => x
</PRE>
<p>
</p>
<p>
On the other hand, <tt>'a</tt> is explicitly scoped in
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
</PRE>
<p>
</p>
<p>
and is explicitly scoped in
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> id = <B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a => x
</PRE>
<p>
</p>
<p>
A type variable can be scoped at a <tt>val</tt> or <tt>fun</tt> declaration. An SML type checker performs scope inference on each top-level declaration to determine the scope of each implicitly scoped type variable. After scope inference, every type variable is scoped at exactly one enclosing <tt>val</tt> or <tt>fun</tt> declaration. Scope inference shows that the first and second example above are equivalent to the third and fourth example, respectively.
</p>
<p>
Section 4.6 of the <a href="DefinitionOfStandardML">Definition</a> specifies precisely the scope of an implicitly scoped type variable. A free occurrence of a type variable <tt>'a</tt> in a declaration <tt>d</tt> is said to be <em>unguarded</em> in <tt>d</tt> if <tt>'a</tt> is not part of a smaller declaration. A type variable <tt>'a</tt> is implicitly scoped at <tt>d</tt> if <tt>'a</tt> is unguarded in <tt>d</tt> and <tt>'a</tt> does not occur unguarded in any declaration containing <tt>d</tt>.
</p>
<h2 id="head-f24dd90ad62588fe27464c5912820b859384b6d0">Scope inference examples</h2>
<ul>
<li>
<p>
In this example,
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
</PRE>
<tt>'a</tt> is unguarded in <tt>val id</tt> and does not occur unguarded in any containing declaration. Hence, <tt>'a</tt> is scoped at <tt>val id</tt> and the declaration is equivalent to the following.
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
</PRE>
</p>
</li>
<li class="gap">
<p>
In this example,
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> f = <B><FONT COLOR="#A020F0">fn</FONT></B> x => <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">exception</FONT></B><B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">E</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a </FONT></B><B><FONT COLOR="#A020F0">in</FONT></B> E x <B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<tt>'a</tt> is unguarded in <tt>val f</tt> and does not occur unguarded in any containing declaration. Hence, <tt>'a</tt> is scoped at <tt>val f</tt> and the declaration is equivalent to the following.
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> f = <B><FONT COLOR="#A020F0">fn</FONT></B> x => <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">exception</FONT></B><B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">E</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a </FONT></B><B><FONT COLOR="#A020F0">in</FONT></B> E x <B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
</p>
</li>
<li class="gap">
<p>
In this example (taken from the <a href="DefinitionOfStandardML">Definition</a>),
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> x: int -> int = <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> z => z <B><FONT COLOR="#A020F0">in</FONT></B> id id <B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<tt>'a</tt> occurs unguarded in <tt>val id</tt>, but not in <tt>val x</tt>. Hence, <tt>'a</tt> is implicitly scoped at <tt>val id</tt>, and the declaration is equivalent to the following.
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> x: int -> int = <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> z => z <B><FONT COLOR="#A020F0">in</FONT></B> id id <B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
</p>
</li>
<li class="gap">
<p>
In this example,
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> f = (<B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a => x) (<B><FONT COLOR="#A020F0">fn</FONT></B> y => y)
</PRE>
<tt>'a</tt> occurs unguarded in <tt>val f</tt> and does not occur unguarded in any containing declaration. Hence, <tt>'a</tt> is implicitly scoped at <tt>val f</tt>, and the declaration is equivalent to the following.
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> f = (<B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a => x) (<B><FONT COLOR="#A020F0">fn</FONT></B> y => y)
</PRE>
This does not type check due to the <a href="ValueRestriction">ValueRestriction</a>.
</p>
</li>
<li class="gap">
<p>
In this example,
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> f x =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> g (y: 'a) = <B><FONT COLOR="#A020F0">if</FONT></B> true <B><FONT COLOR="#A020F0">then</FONT></B> x <B><FONT COLOR="#A020F0">else</FONT></B> y
<B><FONT COLOR="#A020F0">in</FONT></B>
g x
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<tt>'a</tt> occurs unguarded in <tt>fun g</tt>, not in <tt>fun f</tt>. Hence, <tt>'a</tt> is implicitly scoped at <tt>fun g</tt>, and the declaration is equivalent to
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> f x =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> g (y: 'a) = <B><FONT COLOR="#A020F0">if</FONT></B> true <B><FONT COLOR="#A020F0">then</FONT></B> x <B><FONT COLOR="#A020F0">else</FONT></B> y
<B><FONT COLOR="#A020F0">in</FONT></B>
g x
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
This fails to type check because <tt>x</tt> and <tt>y</tt> must have the same type, and hence <tt>'a</tt> can not be generalized at <tt>fun g</tt>. MLton reports
<pre>Error: scope.sml 3.7.
Unable to generalize 'a.
in: fun 'a g ((y): 'a) = (if true then x else y)</pre> This problem could be fixed either by adding an explicit type constraint, as in <tt>fun f (x: 'a)</tt>, or by explicitly scoping <tt>'a</tt>, as in <tt>fun 'a f x</tt>.
</p>
</li>
</ul>
<h2 id="head-81ce55eaa74172900a5b3e8e477b08f4b4327a0b">Restrictions on type variable scope</h2>
<p>
It is not allowed to scope a type variable within a declaration in which it is already in scope (see the last restriction listed on page 9 of the <a href="DefinitionOfStandardML">Definition</a>). For example, the following program is invalid.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> f (x: 'a) =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> g (y: 'a) = y
<B><FONT COLOR="#A020F0">in</FONT></B>
()
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<p>
MLton reports
<pre>Error: z.sml 3.11.
Type variable 'a scoped at an outer declaration.
</pre>
</p>
<p>
This is an error even if the scoping is implicit. That is, the following program is invalid as well.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> f (x: 'a) =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> g (y: 'a) = y
<B><FONT COLOR="#A020F0">in</FONT></B>
()
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
</div>
<p>
<hr>
Last edited on 2005-12-02 03:01:09 by <span title="ppp-71-139-183-221.dsl.snfc21.pacbell.net"><a href="StephenWeeks">StephenWeeks</a></span>.
</body></html>
|
