doc/guide/localhost/TypeVariableScope

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>TypeVariableScope</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>TypeVariableScope</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>In <a href="StandardML">Standard ML</a>, every type variable is <em>scoped</em> (or
  32 bound) at a particular point in the program.  A type variable can be
  33 either implicitly scoped or explicitly scoped.  For example, <span class="monospaced">'a</span> is
  34 implicitly scoped in</p></div>
  35 <div class="listingblock">
  36 <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>
  37 </pre></div></div></div>
  38 <div class="paragraph"><p>and is implicitly scoped in</p></div>
  39 <div class="listingblock">
  40 <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>
  41 </pre></div></div></div>
  42 <div class="paragraph"><p>On the other hand, <span class="monospaced">'a</span> is explicitly scoped in</p></div>
  43 <div class="listingblock">
  44 <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>
  45 </pre></div></div></div>
  46 <div class="paragraph"><p>and is explicitly scoped in</p></div>
  47 <div class="listingblock">
  48 <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>
  49 </pre></div></div></div>
  50 <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
  51 type checker performs scope inference on each top-level declaration to
  52 determine the scope of each implicitly scoped type variable.  After
  53 scope inference, every type variable is scoped at exactly one
  54 enclosing <span class="monospaced">val</span> or <span class="monospaced">fun</span> declaration.  Scope inference shows that the
  55 first and second example above are equivalent to the third and fourth
  56 example, respectively.</p></div>
  57 <div class="paragraph"><p>Section 4.6 of the <a href="DefinitionOfStandardML">Definition</a> specifies
  58 precisely the scope of an implicitly scoped type variable.  A free
  59 occurrence of a type variable <span class="monospaced">'a</span> in a declaration <span class="monospaced">d</span> is said to be
  60 <em>unguarded</em> in <span class="monospaced">d</span> if <span class="monospaced">'a</span> is not part of a smaller declaration.  A
  61 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
  62 <span class="monospaced">d</span> and <span class="monospaced">'a</span> does not occur unguarded in any declaration containing
  63 <span class="monospaced">d</span>.</p></div>
  64 </div>
  65 </div>
  66 <div class="sect1">
  67 <h2 id="_scope_inference_examples">Scope inference examples</h2>
  68 <div class="sectionbody">
  69 <div class="ulist"><ul>
  70 <li>
  71 <p>
  72 In this example,
  73 </p>
  74 <div class="listingblock">
  75 <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>
  76 </pre></div></div></div>
  77 <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
  78 containing declaration.  Hence, <span class="monospaced">'a</span> is scoped at <span class="monospaced">val id</span> and the
  79 declaration is equivalent to the following.</p></div>
  80 <div class="listingblock">
  81 <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>
  82 </pre></div></div></div>
  83 </li>
  84 <li>
  85 <p>
  86 In this example,
  87 </p>
  88 <div class="listingblock">
  89 <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>
  90 </pre></div></div></div>
  91 <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
  92 containing declaration.  Hence, <span class="monospaced">'a</span> is scoped at <span class="monospaced">val f</span> and the
  93 declaration is equivalent to the following.</p></div>
  94 <div class="listingblock">
  95 <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>
  96 </pre></div></div></div>
  97 </li>
  98 <li>
  99 <p>
 100 In this example (taken from the <a href="DefinitionOfStandardML">Definition</a>),
 101 </p>
 102 <div class="listingblock">
 103 <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>
 104 </pre></div></div></div>
 105 <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
 106 implicitly scoped at <span class="monospaced">val id</span>, and the declaration is equivalent to
 107 the following.</p></div>
 108 <div class="listingblock">
 109 <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>
 110 </pre></div></div></div>
 111 </li>
 112 <li>
 113 <p>
 114 In this example,
 115 </p>
 116 <div class="listingblock">
 117 <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>
 118 </pre></div></div></div>
 119 <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
 120 containing declaration.  Hence, <span class="monospaced">'a</span> is implicitly scoped at <span class="monospaced">val f</span>,
 121 and the declaration is equivalent to the following.</p></div>
 122 <div class="listingblock">
 123 <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>
 124 </pre></div></div></div>
 125 <div class="paragraph"><p>This does not type check due to the <a href="ValueRestriction">ValueRestriction</a>.</p></div>
 126 </li>
 127 <li>
 128 <p>
 129 In this example,
 130 </p>
 131 <div class="listingblock">
 132 <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>
 133 <span class="w">  </span><span class="k">let</span><span class="w"></span>
 134 <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>
 135 <span class="w">  </span><span class="k">in</span><span class="w"></span>
 136 <span class="w">    </span><span class="n">g</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 137 <span class="w">  </span><span class="k">end</span><span class="w"></span>
 138 </pre></div></div></div>
 139 <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
 140 implicitly scoped at <span class="monospaced">fun g</span>, and the declaration is equivalent to</p></div>
 141 <div class="listingblock">
 142 <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>
 143 <span class="w">  </span><span class="k">let</span><span class="w"></span>
 144 <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>
 145 <span class="w">  </span><span class="k">in</span><span class="w"></span>
 146 <span class="w">    </span><span class="n">g</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 147 <span class="w">  </span><span class="k">end</span><span class="w"></span>
 148 </pre></div></div></div>
 149 <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,
 150 but the <span class="monospaced">x</span> occurs outside the scope of the type variable <span class="monospaced">'a</span>.  MLton
 151 reports the following error.</p></div>
 152 <div class="listingblock">
 153 <div class="content monospaced">
 154 <pre>Error: z.sml 3.21-3.41.
 155   Then and else branches disagree.
 156     then: [???]
 157     else: ['a]
 158     in: if true then x else y
 159     note: type would escape its scope: 'a
 160     escape to: z.sml 1.1-6.5</pre>
 161 </div></div>
 162 <div class="paragraph"><p>This problem could be fixed either by adding an explicit type
 163 constraint, as in <span class="monospaced">fun f (x: 'a)</span>, or by explicitly scoping <span class="monospaced">'a</span>, as
 164 in <span class="monospaced">fun 'a f x = ...</span>.</p></div>
 165 </li>
 166 </ul></div>
 167 </div>
 168 </div>
 169 <div class="sect1">
 170 <h2 id="_restrictions_on_type_variable_scope">Restrictions on type variable scope</h2>
 171 <div class="sectionbody">
 172 <div class="paragraph"><p>It is not allowed to scope a type variable within a declaration in
 173 which it is already in scope (see the last restriction listed on page
 174 9 of the <a href="DefinitionOfStandardML">Definition</a>).  For example, the
 175 following program is invalid.</p></div>
 176 <div class="listingblock">
 177 <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>
 178 <span class="w">   </span><span class="k">let</span><span class="w"></span>
 179 <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>
 180 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 181 <span class="w">      </span><span class="p">()</span><span class="w"></span>
 182 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 183 </pre></div></div></div>
 184 <div class="paragraph"><p>MLton reports the following error.</p></div>
 185 <div class="listingblock">
 186 <div class="content monospaced">
 187 <pre>Error: z.sml 3.11-3.12.
 188   Type variable scoped at an outer declaration: 'a.
 189     scoped at: z.sml 1.1-6.6</pre>
 190 </div></div>
 191 <div class="paragraph"><p>This is an error even if the scoping is implicit.  That is, the
 192 following program is invalid as well.</p></div>
 193 <div class="listingblock">
 194 <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>
 195 <span class="w">   </span><span class="k">let</span><span class="w"></span>
 196 <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>
 197 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 198 <span class="w">      </span><span class="p">()</span><span class="w"></span>
 199 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 200 </pre></div></div></div>
 201 </div>
 202 </div>
 203 </div>
 204 <div id="footnotes"><hr></div>
 205 <div id="footer">
 206 <div id="footer-text">
 207 </div>
 208 <div id="footer-badges">
 209 </div>
 210 </div>
 211 </body>
 212 </html>