[hcoop/debian/mlton.git] / doc / guide / localhost / TypeVariableScope

<!DOCTYPE html>\r
<html lang="en">\r
<head>\r
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
<meta name="generator" content="AsciiDoc 8.6.9">\r
<title>TypeVariableScope</title>\r
<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
<link rel="stylesheet" href="./pygments.css" type="text/css">\r
\r
\r
<script type="text/javascript" src="./asciidoc.js"></script>\r
<script type="text/javascript">\r
/*<![CDATA[*/\r
asciidoc.install();\r
/*]]>*/\r
</script>\r
<link rel="stylesheet" href="./mlton.css" type="text/css">\r
</head>\r
<body class="article">\r
<div id="banner">\r
<div id="banner-home">\r
<a href="./Home">MLton 20180207</a>\r
</div>\r
</div>\r
<div id="header">\r
<h1>TypeVariableScope</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p>In <a href="StandardML">Standard ML</a>, every type variable is <em>scoped</em> (or\r
bound) at a particular point in the program.  A type variable can be\r
either implicitly scoped or explicitly scoped.  For example, <span class="monospaced">'a</span> is\r
implicitly scoped in</p></div>\r
<div class="listingblock">\r
<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">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>and is implicitly scoped in</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">id</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="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>On the other hand, <span class="monospaced">'a</span> is explicitly scoped in</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">id</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>and is explicitly scoped in</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">id</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="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>A type variable can be scoped at a <span class="monospaced">val</span> or <span class="monospaced">fun</span> declaration.  An SML\r
type checker performs scope inference on each top-level declaration to\r
determine the scope of each implicitly scoped type variable.  After\r
scope inference, every type variable is scoped at exactly one\r
enclosing <span class="monospaced">val</span> or <span class="monospaced">fun</span> declaration.  Scope inference shows that the\r
first and second example above are equivalent to the third and fourth\r
example, respectively.</p></div>\r
<div class="paragraph"><p>Section 4.6 of the <a href="DefinitionOfStandardML">Definition</a> specifies\r
precisely the scope of an implicitly scoped type variable.  A free\r
occurrence of a type variable <span class="monospaced">'a</span> in a declaration <span class="monospaced">d</span> is said to be\r
<em>unguarded</em> in <span class="monospaced">d</span> if <span class="monospaced">'a</span> is not part of a smaller declaration.  A\r
type variable <span class="monospaced">'a</span> is implicitly scoped at <span class="monospaced">d</span> if <span class="monospaced">'a</span> is unguarded in\r
<span class="monospaced">d</span> and <span class="monospaced">'a</span> does not occur unguarded in any declaration containing\r
<span class="monospaced">d</span>.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_scope_inference_examples">Scope inference examples</h2>\r
<div class="sectionbody">\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
In this example,\r
</p>\r
<div class="listingblock">\r
<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">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p><span class="monospaced">'a</span> is unguarded in <span class="monospaced">val id</span> and does not occur unguarded in any\r
containing declaration.  Hence, <span class="monospaced">'a</span> is scoped at <span class="monospaced">val id</span> and the\r
declaration is equivalent to the following.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">id</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
</li>\r
<li>\r
<p>\r
In this example,\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><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="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">exception</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p><span class="monospaced">'a</span> is unguarded in <span class="monospaced">val f</span> and does not occur unguarded in any\r
containing declaration.  Hence, <span class="monospaced">'a</span> is scoped at <span class="monospaced">val f</span> and the\r
declaration is equivalent to the following.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">&#39;a</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">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">exception</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
</li>\r
<li>\r
<p>\r
In this example (taken from the <a href="DefinitionOfStandardML">Definition</a>),\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><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">int</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</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">val</span><span class="w"> </span><span class="n">id</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="k">in</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">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p><span class="monospaced">'a</span> occurs unguarded in <span class="monospaced">val id</span>, but not in <span class="monospaced">val x</span>.  Hence, <span class="monospaced">'a</span> is\r
implicitly scoped at <span class="monospaced">val id</span>, and the declaration is equivalent to\r
the following.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><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">int</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</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">val</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">id</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;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">=&gt;</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="k">in</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">end</span><span class="w"></span>\r
</pre></div></div></div>\r
</li>\r
<li>\r
<p>\r
In this example,\r
</p>\r
<div class="listingblock">\r
<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="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p><span class="monospaced">'a</span> occurs unguarded in <span class="monospaced">val f</span> and does not occur unguarded in any\r
containing declaration.  Hence, <span class="monospaced">'a</span> is implicitly scoped at <span class="monospaced">val f</span>,\r
and the declaration is equivalent to the following.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">f</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="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>This does not type check due to the <a href="ValueRestriction">ValueRestriction</a>.</p></div>\r
</li>\r
<li>\r
<p>\r
In this example,\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">  </span><span class="k">let</span><span class="w"></span>\r
<span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</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="n">x</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
<span class="w">  </span><span class="k">in</span><span class="w"></span>\r
<span class="w">    </span><span class="n">g</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="w">  </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p><span class="monospaced">'a</span> occurs unguarded in <span class="monospaced">fun g</span>, not in <span class="monospaced">fun f</span>.  Hence, <span class="monospaced">'a</span> is\r
implicitly scoped at <span class="monospaced">fun g</span>, and the declaration is equivalent to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">  </span><span class="k">let</span><span class="w"></span>\r
<span class="w">    </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</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="n">x</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
<span class="w">  </span><span class="k">in</span><span class="w"></span>\r
<span class="w">    </span><span class="n">g</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="w">  </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>This fails to type check because <span class="monospaced">x</span> and <span class="monospaced">y</span> must have the same type,\r
but the <span class="monospaced">x</span> occurs outside the scope of the type variable <span class="monospaced">'a</span>.  MLton\r
reports the following error.</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>Error: z.sml 3.21-3.41.\r
  Then and else branches disagree.\r
    then: [???]\r
    else: ['a]\r
    in: if true then x else y\r
    note: type would escape its scope: 'a\r
    escape to: z.sml 1.1-6.5</pre>\r
</div></div>\r
<div class="paragraph"><p>This problem could be fixed either by adding an explicit type\r
constraint, as in <span class="monospaced">fun f (x: 'a)</span>, or by explicitly scoping <span class="monospaced">'a</span>, as\r
in <span class="monospaced">fun 'a f x = ...</span>.</p></div>\r
</li>\r
</ul></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_restrictions_on_type_variable_scope">Restrictions on type variable scope</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>It is not allowed to scope a type variable within a declaration in\r
which it is already in scope (see the last restriction listed on page\r
9 of the <a href="DefinitionOfStandardML">Definition</a>).  For example, the\r
following program is invalid.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">let</span><span class="w"></span>\r
<span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
<span class="w">   </span><span class="k">in</span><span class="w"></span>\r
<span class="w">      </span><span class="p">()</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>MLton reports the following error.</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>Error: z.sml 3.11-3.12.\r
  Type variable scoped at an outer declaration: 'a.\r
    scoped at: z.sml 1.1-6.6</pre>\r
</div></div>\r
<div class="paragraph"><p>This is an error even if the scoping is implicit.  That is, the\r
following program is invalid as well.</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">let</span><span class="w"></span>\r
<span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="p">(</span><span class="n">y</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
<span class="w">   </span><span class="k">in</span><span class="w"></span>\r
<span class="w">      </span><span class="p">()</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
</div>\r
</div>\r
</div>\r
<div id="footnotes"><hr></div>\r
<div id="footer">\r
<div id="footer-text">\r
</div>\r
<div id="footer-badges">\r
</div>\r
</div>\r
</body>\r
</html>\r