doc/guide/localhost/ValueRestriction

   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>ValueRestriction</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(2);
  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>ValueRestriction</h1>
  27 <div id="toc">
  28   <div id="toctitle">Table of Contents</div>
  29   <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
  30 </div>
  31 </div>
  32 <div id="content">
  33 <div id="preamble">
  34 <div class="sectionbody">
  35 <div class="paragraph"><p>The value restriction is a rule that governs when type inference is
  36 allowed to polymorphically generalize a value declaration.  In short,
  37 the value restriction says that generalization can only occur if the
  38 right-hand side of an expression is syntactically a value.  For
  39 example, in</p></div>
  40 <div class="listingblock">
  41 <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="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>
  42 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
  43 </pre></div></div></div>
  44 <div class="paragraph"><p>the expression <span class="monospaced">fn x =&gt; x</span> is syntactically a value, so <span class="monospaced">f</span> has
  45 polymorphic type <span class="monospaced">'a -&gt; 'a</span> and both calls to <span class="monospaced">f</span> type check.  On the
  46 other hand, 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">f</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">in</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><span class="k">end</span><span class="w"></span>
  49 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
  50 </pre></div></div></div>
  51 <div class="paragraph"><p>the expression <span class="monospaced">let in fn x =&gt; end end</span> is not syntactically a value
  52 and so <span class="monospaced">f</span> can either have type <span class="monospaced">int -&gt; int</span> or <span class="monospaced">string -&gt; string</span>,
  53 but not <span class="monospaced">'a -&gt; 'a</span>.  Hence, the program does not type check.</p></div>
  54 <div class="paragraph"><p><a href="DefinitionOfStandardML">The Definition of Standard ML</a> spells out
  55 precisely which expressions are syntactic values (it refers to such
  56 expressions as <em>non-expansive</em>).  An expression is a value if it is of
  57 one of the following forms.</p></div>
  58 <div class="ulist"><ul>
  59 <li>
  60 <p>
  61 a constant (<span class="monospaced">13</span>, <span class="monospaced">"foo"</span>, <span class="monospaced">13.0</span>, &#8230;)
  62 </p>
  63 </li>
  64 <li>
  65 <p>
  66 a variable (<span class="monospaced">x</span>, <span class="monospaced">y</span>, &#8230;)
  67 </p>
  68 </li>
  69 <li>
  70 <p>
  71 a function (<span class="monospaced">fn x =&gt; e</span>)
  72 </p>
  73 </li>
  74 <li>
  75 <p>
  76 the application of a constructor other than <span class="monospaced">ref</span> to a value (<span class="monospaced">Foo v</span>)
  77 </p>
  78 </li>
  79 <li>
  80 <p>
  81 a type constrained value (<span class="monospaced">v: t</span>)
  82 </p>
  83 </li>
  84 <li>
  85 <p>
  86 a tuple in which each field is a value <span class="monospaced">(v1, v2, ...)</span>
  87 </p>
  88 </li>
  89 <li>
  90 <p>
  91 a record in which each field is a value <span class="monospaced">{l1 = v1, l2 = v2, ...}</span>
  92 </p>
  93 </li>
  94 <li>
  95 <p>
  96 a list in which each element is a value <span class="monospaced">[v1, v2, ...]</span>
  97 </p>
  98 </li>
  99 </ul></div>
 100 </div>
 101 </div>
 102 <div class="sect1">
 103 <h2 id="_why_the_value_restriction_exists">Why the value restriction exists</h2>
 104 <div class="sectionbody">
 105 <div class="paragraph"><p>The value restriction prevents a ref cell (or an array) from holding
 106 values of different types, which would allow a value of one type to be
 107 cast to another and hence would break type safety.  If the restriction
 108 were not in place, the following program would type check.</p></div>
 109 <div class="listingblock">
 110 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 111 <span class="k">val</span><span class="w"> </span><span class="n">r1</span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 112 <span class="k">val</span><span class="w"> </span><span class="n">r2</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 113 <span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r1</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="w"></span>
 114 <span class="k">val</span><span class="w"> </span><span class="n">v</span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">!r2</span><span class="p">)</span><span class="w"></span>
 115 </pre></div></div></div>
 116 <div class="paragraph"><p>The first line violates the value restriction because <span class="monospaced">ref NONE</span> is
 117 not a value.  All other lines are type correct.  By its last line, the
 118 program has cast the string <span class="monospaced">"foo"</span> to an integer.  This breaks type
 119 safety, because now we can add a string to an integer with an
 120 expression like <span class="monospaced">v + 13</span>.  We could even be more devious, by adding
 121 the following two lines, which allow us to threat the string <span class="monospaced">"foo"</span>
 122 as a function.</p></div>
 123 <div class="listingblock">
 124 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">r3</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 125 <span class="k">val</span><span class="w"> </span><span class="n">v</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="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">!r3</span><span class="p">)</span><span class="w"></span>
 126 </pre></div></div></div>
 127 <div class="paragraph"><p>Eliminating the explicit <span class="monospaced">ref</span> does nothing to fix the problem.  For
 128 example, we could replace the declaration of <span class="monospaced">r</span> with the following.</p></div>
 129 <div class="listingblock">
 130 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">unit</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="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 131 <span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 132 </pre></div></div></div>
 133 <div class="paragraph"><p>The declaration of <span class="monospaced">f</span> is well typed, while the declaration of <span class="monospaced">r</span>
 134 violates the value restriction because <span class="monospaced">f ()</span> is not a value.</p></div>
 135 </div>
 136 </div>
 137 <div class="sect1">
 138 <h2 id="_unnecessarily_rejected_programs">Unnecessarily rejected programs</h2>
 139 <div class="sectionbody">
 140 <div class="paragraph"><p>Unfortunately, the value restriction rejects some programs that could
 141 be accepted.</p></div>
 142 <div class="listingblock">
 143 <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>
 144 <span class="k">val</span><span class="w"> </span><span class="n">f</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="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 145 </pre></div></div></div>
 146 <div class="paragraph"><p>The type constraint on <span class="monospaced">f</span> requires <span class="monospaced">f</span> to be polymorphic, which is
 147 disallowed because <span class="monospaced">id id</span> is not a value.  MLton reports the
 148 following type error.</p></div>
 149 <div class="listingblock">
 150 <div class="content monospaced">
 151 <pre>Error: z.sml 2.5-2.5.
 152   Type of variable cannot be generalized in expansive declaration: f.
 153     type: ['a] -&gt; ['a]
 154     in: val 'a f: ('a -&gt; 'a) = id id</pre>
 155 </div></div>
 156 <div class="paragraph"><p>MLton indicates the inability to make <span class="monospaced">f</span> polymorphic by saying that
 157 the type of <span class="monospaced">f</span> cannot be generalized (made polymorphic) its
 158 declaration is expansive (not a value).  MLton doesn&#8217;t explicitly
 159 mention the value restriction, but that is the reason.  If we leave
 160 the type constraint off of <span class="monospaced">f</span></p></div>
 161 <div class="listingblock">
 162 <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>
 163 <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="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 164 </pre></div></div></div>
 165 <div class="paragraph"><p>then the program succeeds; however, MLton gives us the following
 166 warning.</p></div>
 167 <div class="listingblock">
 168 <div class="content monospaced">
 169 <pre>Warning: z.sml 2.5-2.5.
 170   Type of variable was not inferred and could not be generalized: f.
 171     type: ??? -&gt; ???
 172     in: val f = id id</pre>
 173 </div></div>
 174 <div class="paragraph"><p>This warning indicates that MLton couldn&#8217;t polymorphically generalize
 175 <span class="monospaced">f</span>, nor was there enough context using <span class="monospaced">f</span> to determine its type.
 176 This in itself is not a type error, but it it is a hint that something
 177 is wrong with our program.  Using <span class="monospaced">f</span> provides enough context to
 178 eliminate the warning.</p></div>
 179 <div class="listingblock">
 180 <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>
 181 <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="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 182 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
 183 </pre></div></div></div>
 184 <div class="paragraph"><p>But attempting to use <span class="monospaced">f</span> as a polymorphic function will fail.</p></div>
 185 <div class="listingblock">
 186 <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>
 187 <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="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 188 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
 189 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="w"></span>
 190 </pre></div></div></div>
 191 <div class="listingblock">
 192 <div class="content monospaced">
 193 <pre>Error: z.sml 4.9-4.15.
 194   Function applied to incorrect argument.
 195     expects: [int]
 196     but got: [string]
 197     in: f "foo"</pre>
 198 </div></div>
 199 </div>
 200 </div>
 201 <div class="sect1">
 202 <h2 id="_alternatives_to_the_value_restriction">Alternatives to the value restriction</h2>
 203 <div class="sectionbody">
 204 <div class="paragraph"><p>There would be nothing wrong with treating <span class="monospaced">f</span> as polymorphic in</p></div>
 205 <div class="listingblock">
 206 <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>
 207 <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="n">id</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 208 </pre></div></div></div>
 209 <div class="paragraph"><p>One might think that the value restriction could be relaxed, and that
 210 only types involving <span class="monospaced">ref</span> should be disallowed.  Unfortunately, the
 211 following example shows that even the type <span class="monospaced">'a -&gt; 'a</span> can cause
 212 problems.  If this program were allowed, then we could cast an integer
 213 to a string (or any other type).</p></div>
 214 <div class="listingblock">
 215 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">f</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>
 216 <span class="w">   </span><span class="k">let</span><span class="w"></span>
 217 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">NONE</span><span class="w"></span>
 218 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 219 <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>
 220 <span class="w">      </span><span class="k">let</span><span class="w"></span>
 221 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">!r</span><span class="w"></span>
 222 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 223 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 224 <span class="w">         </span><span class="k">case</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
 225 <span class="w">            </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 226 <span class="w">          </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</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="w"></span>
 227 <span class="w">      </span><span class="k">end</span><span class="w"></span>
 228 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 229 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
 230 <span class="k">val</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="w"></span>
 231 </pre></div></div></div>
 232 <div class="paragraph"><p>The previous version of Standard ML took a different approach
 233 (<a href="References#MilnerEtAl90">MilnerEtAl90</a>, <a href="References#Tofte90">Tofte90</a>, <a href="ImperativeTypeVariable">ImperativeTypeVariable</a>)
 234 than the value restriction.  It encoded information in the type system
 235 about when ref cells would be created, and used this to prevent a ref
 236 cell from holding multiple types.  Although it allowed more programs
 237 to be type checked, this approach had significant drawbacks.  First,
 238 it was significantly more complex, both for implementers and for
 239 programmers.  Second, it had an unfortunate interaction with the
 240 modularity, because information about ref usage was exposed in module
 241 signatures.  This either prevented the use of references for
 242 implementing a signature, or required information that one would like
 243 to keep hidden to propagate across modules.</p></div>
 244 <div class="paragraph"><p>In the early nineties, Andrew Wright studied about 250,000 lines of
 245 existing SML code and discovered that it did not make significant use
 246 of the extended typing ability, and proposed the value restriction as
 247 a simpler alternative (<a href="References#Wright95">Wright95</a>).  This was adopted in the
 248 revised <a href="DefinitionOfStandardML">Definition</a>.</p></div>
 249 </div>
 250 </div>
 251 <div class="sect1">
 252 <h2 id="_working_with_the_value_restriction">Working with the value restriction</h2>
 253 <div class="sectionbody">
 254 <div class="paragraph"><p>One technique that works with the value restriction is
 255 <a href="EtaExpansion">EtaExpansion</a>.  We can use eta expansion to make our <span class="monospaced">id id</span>
 256 example type check follows.</p></div>
 257 <div class="listingblock">
 258 <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>
 259 <span class="k">val</span><span class="w"> </span><span class="n">f</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="p">(</span><span class="n">id</span><span class="w"> </span><span class="n">id</span><span class="p">)</span><span class="w"> </span><span class="n">z</span><span class="w"></span>
 260 </pre></div></div></div>
 261 <div class="paragraph"><p>This solution means that the computation (in this case <span class="monospaced">id id</span>) will
 262 be performed each time <span class="monospaced">f</span> is applied, instead of just once when <span class="monospaced">f</span>
 263 is declared.  In this case, that is not a problem, but it could be if
 264 the declaration of <span class="monospaced">f</span> performs substantial computation or creates a
 265 shared data structure.</p></div>
 266 <div class="paragraph"><p>Another technique that sometimes works is to move a monomorphic
 267 computation prior to a (would-be) polymorphic declaration so that the
 268 expression is a value.  Consider the following program, which fails
 269 due to the value restriction.</p></div>
 270 <div class="listingblock">
 271 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>
 272 <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">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="p">(</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="s">&quot;yes&quot;</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="s">&quot;no&quot;</span><span class="p">)</span><span class="w"></span>
 273 </pre></div></div></div>
 274 <div class="paragraph"><p>It is easy to rewrite this program as</p></div>
 275 <div class="listingblock">
 276 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>
 277 <span class="k">local</span><span class="w"></span>
 278 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">s</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="s">&quot;yes&quot;</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="s">&quot;no&quot;</span><span class="w"></span>
 279 <span class="k">in</span><span class="w"></span>
 280 <span class="w">   </span><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">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 281 <span class="k">end</span><span class="w"></span>
 282 </pre></div></div></div>
 283 <div class="paragraph"><p>The following example (taken from <a href="References#Wright95">Wright95</a>) creates a ref
 284 cell to count the number of times a function is called.</p></div>
 285 <div class="listingblock">
 286 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">count</span><span class="p">:</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 287 <span class="w">   </span><span class="k">fn</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 288 <span class="w">   </span><span class="k">let</span><span class="w"></span>
 289 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="mi">0</span><span class="w"></span>
 290 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 291 <span class="w">      </span><span class="p">(</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="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">!r</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="p">),</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">!r</span><span class="p">)</span><span class="w"></span>
 292 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 293 <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>
 294 <span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">countId</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="p">,</span><span class="w"> </span><span class="n">numCalls</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 295 </pre></div></div></div>
 296 <div class="paragraph"><p>The example does not type check, due to the value restriction.
 297 However, it is easy to rewrite the program, staging the ref cell
 298 creation before the polymorphic code.</p></div>
 299 <div class="listingblock">
 300 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>
 301 <span class="k">val</span><span class="w"> </span><span class="n">count1</span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="p">(</span><span class="n">ref</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
 302 <span class="k">val</span><span class="w"> </span><span class="n">count2</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 303 <span class="w">   </span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">T</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">!r</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="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">!r</span><span class="p">;</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"></span>
 304 <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>
 305 <span class="k">val</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">count1</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 306 <span class="k">val</span><span class="w"> </span><span class="n">countId</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="p">#</span><span class="mi">2</span><span class="w"> </span><span class="p">(</span><span class="n">count2</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">))</span><span class="w"> </span><span class="n">z</span><span class="w"></span>
 307 <span class="k">val</span><span class="w"> </span><span class="n">numCalls</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">#</span><span class="mi">1</span><span class="w"> </span><span class="p">(</span><span class="n">count2</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">id</span><span class="p">))</span><span class="w"></span>
 308 </pre></div></div></div>
 309 <div class="paragraph"><p>Of course, one can hide the constructor <span class="monospaced">T</span> inside a <span class="monospaced">local</span> or behind
 310 a signature.</p></div>
 311 </div>
 312 </div>
 313 <div class="sect1">
 314 <h2 id="_also_see">Also see</h2>
 315 <div class="sectionbody">
 316 <div class="ulist"><ul>
 317 <li>
 318 <p>
 319 <a href="ImperativeTypeVariable">ImperativeTypeVariable</a>
 320 </p>
 321 </li>
 322 </ul></div>
 323 </div>
 324 </div>
 325 </div>
 326 <div id="footnotes"><hr></div>
 327 <div id="footer">
 328 <div id="footer-text">
 329 </div>
 330 <div id="footer-badges">
 331 </div>
 332 </div>
 333 </body>
 334 </html>