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

<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 20051202</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>
      &nbsp;<a href = "Index">Index</a>
      &nbsp;
</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 -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; 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 =&gt; 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> <FONT COLOR="#228B22"><B>'a</FONT></B> id: 'a -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; x
</PRE>
<p>
 
</p>
<p>
and is explicitly scoped in 
</p>

<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> id = <B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a =&gt; 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 -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; x
</PRE>
  <tt>'a</tt> is unguarded in <tt>val&nbsp;id</tt> and does not occur unguarded in  any containing declaration.  Hence, <tt>'a</tt> is scoped at   <tt>val&nbsp;id</tt> and the declaration is equivalent to the  following. 
<pre class=code>
 <B><FONT COLOR="#A020F0">val</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> id: 'a -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; 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 =&gt; <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">exception</FONT></B><FONT COLOR="#228B22"><B> <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&nbsp;f</tt> and does not occur unguarded in  any containing declaration.  Hence, <tt>'a</tt> is scoped at <tt>val&nbsp;f</tt>  and the declaration is equivalent to the following. 
<pre class=code>
 <B><FONT COLOR="#A020F0">val</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> f = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">exception</FONT></B><FONT COLOR="#228B22"><B> <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 -&gt; int = <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> id: 'a -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> z =&gt; 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&nbsp;id</tt>, but not in <tt>val&nbsp;x</tt>.  Hence, <tt>'a</tt> is implicitly scoped at <tt>val&nbsp;id</tt>, and the  declaration is equivalent to the following. 
<pre class=code>
 <B><FONT COLOR="#A020F0">val</FONT></B> x: int -&gt; int = <B><FONT COLOR="#A020F0">let</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> id: 'a -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> z =&gt; 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 =&gt; x) (<B><FONT COLOR="#A020F0">fn</FONT></B> y =&gt; y)
</PRE>
  <tt>'a</tt> occurs unguarded in <tt>val&nbsp;f</tt> and does not occur unguarded  in any containing declaration.  Hence, <tt>'a</tt> is implicitly scoped  at <tt>val&nbsp;f</tt>, and the declaration is equivalent to the  following. 
<pre class=code>
 <B><FONT COLOR="#A020F0">val</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> f = (<B><FONT COLOR="#A020F0">fn</FONT></B> x: 'a =&gt; x) (<B><FONT COLOR="#A020F0">fn</FONT></B> y =&gt; 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&nbsp;g</tt>, not in <tt>fun&nbsp;f</tt>.  Hence,  <tt>'a</tt> is implicitly scoped at <tt>fun&nbsp;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> <FONT COLOR="#228B22"><B>'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&nbsp;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&nbsp;f&nbsp;(x:&nbsp;'a)</tt>, or by explicitly scoping  <tt>'a</tt>, as in <tt>fun&nbsp;'a&nbsp;f&nbsp;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> <FONT COLOR="#228B22"><B>'a</FONT></B> f (x: 'a) =
   <B><FONT COLOR="#A020F0">let</FONT></B>
      <B><FONT COLOR="#A020F0">fun</FONT></B> <FONT COLOR="#228B22"><B>'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> <FONT COLOR="#228B22"><B>'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>
