<!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>
