doc/guide/localhost/FirstClassPolymorphism

   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>FirstClassPolymorphism</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>FirstClassPolymorphism</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p>First-class polymorphism is the ability to treat polymorphic functions
  32 just like other values: pass them as arguments, store them in data
  33 structures, etc.  Although <a href="StandardML">Standard ML</a> does have
  34 polymorphic functions, it does not support first-class polymorphism.</p></div>
  35 <div class="paragraph"><p>For example, the following declares and uses the polymorphic function
  36 <span class="monospaced">id</span>.</p></div>
  37 <div class="listingblock">
  38 <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="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
  39 <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">id</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>
  40 <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">id</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="w"></span>
  41 </pre></div></div></div>
  42 <div class="paragraph"><p>If SML supported first-class polymorphism, we could write the
  43 following.</p></div>
  44 <div class="listingblock">
  45 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">useId</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="mi">13</span><span class="p">;</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">)</span><span class="w"></span>
  46 </pre></div></div></div>
  47 <div class="paragraph"><p>However, this does not type check.  MLton reports the following error.</p></div>
  48 <div class="listingblock">
  49 <div class="content monospaced">
  50 <pre>Error: z.sml 1.24-1.31.
  51   Function applied to incorrect argument.
  52     expects: [int]
  53     but got: [string]
  54     in: id "foo"</pre>
  55 </div></div>
  56 <div class="paragraph"><p>The error message arises because MLton infers from <span class="monospaced">id 13</span> that <span class="monospaced">id</span>
  57 accepts an integer argument, but that <span class="monospaced">id "foo"</span> is passing a string.</p></div>
  58 <div class="paragraph"><p>Using explicit types sheds some light on the problem.</p></div>
  59 <div class="listingblock">
  60 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">useId</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="mi">13</span><span class="p">;</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">)</span><span class="w"></span>
  61 </pre></div></div></div>
  62 <div class="paragraph"><p>On this, MLton reports the following errors.</p></div>
  63 <div class="listingblock">
  64 <div class="content monospaced">
  65 <pre>Error: z.sml 1.29-1.33.
  66   Function applied to incorrect argument.
  67     expects: ['a]
  68     but got: [int]
  69     in: id 13
  70 Error: z.sml 1.36-1.43.
  71   Function applied to incorrect argument.
  72     expects: ['a]
  73     but got: [string]
  74     in: id "foo"</pre>
  75 </div></div>
  76 <div class="paragraph"><p>The errors arise because the argument <span class="monospaced">id</span> is <em>not</em> polymorphic;
  77 rather, it is monomorphic, with type <span class="monospaced">'a -&gt; 'a</span>.  It is perfectly
  78 valid to apply <span class="monospaced">id</span> to a value of type <span class="monospaced">'a</span>, as in the following</p></div>
  79 <div class="listingblock">
  80 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">useId</span><span class="w"> </span><span class="p">(</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="p">,</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="p">)</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">x</span><span class="w">  </span><span class="cm">(* type correct *)</span><span class="w"></span>
  81 </pre></div></div></div>
  82 <div class="paragraph"><p>So, what is the difference between the type specification on <span class="monospaced">id</span> in
  83 the following two declarations?</p></div>
  84 <div class="listingblock">
  85 <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>
  86 <span class="k">fun</span><span class="w"> </span><span class="n">useId</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="mi">13</span><span class="p">;</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">)</span><span class="w"></span>
  87 </pre></div></div></div>
  88 <div class="paragraph"><p>While the type specifications on <span class="monospaced">id</span> look identical, they mean
  89 different things.  The difference can be made clearer by explicitly
  90 <a href="TypeVariableScope">scoping the type variables</a>.</p></div>
  91 <div class="listingblock">
  92 <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>
  93 <span class="k">fun</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">useId</span><span class="w"> </span><span class="p">(</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="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="w"> </span><span class="mi">13</span><span class="p">;</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="s">&quot;foo&quot;</span><span class="p">)</span><span class="w">  </span><span class="cm">(* type error *)</span><span class="w"></span>
  94 </pre></div></div></div>
  95 <div class="paragraph"><p>In <span class="monospaced">val 'a id</span>, the type variable scoping means that for any <span class="monospaced">'a</span>,
  96 <span class="monospaced">id</span> has type <span class="monospaced">'a -&gt; 'a</span>.  Hence, <span class="monospaced">id</span> can be applied to arguments of
  97 type <span class="monospaced">int</span>, <span class="monospaced">real</span>, etc.  Similarly, in <span class="monospaced">fun 'a useId</span>, the scoping
  98 means that <span class="monospaced">useId</span> is a polymorphic function that for any <span class="monospaced">'a</span> takes a
  99 function of type <span class="monospaced">'a -&gt; 'a</span> and does something.  Thus, <span class="monospaced">useId</span> could
 100 be applied to a function of type <span class="monospaced">int -&gt; int</span>, <span class="monospaced">real -&gt; real</span>, etc.</p></div>
 101 <div class="paragraph"><p>One could imagine an extension of SML that allowed scoping of type
 102 variables at places other than <span class="monospaced">fun</span> or <span class="monospaced">val</span> declarations, as in the
 103 following.</p></div>
 104 <div class="listingblock">
 105 <div class="content monospaced">
 106 <pre>fun useId (id: ('a).'a -&gt; 'a) = (id 13; id "foo")  (* not SML *)</pre>
 107 </div></div>
 108 <div class="paragraph"><p>Such an extension would need to be thought through very carefully, as
 109 it could cause significant complications with <a href="TypeInference">TypeInference</a>,
 110 possible even undecidability.</p></div>
 111 </div>
 112 </div>
 113 </div>
 114 <div id="footnotes"><hr></div>
 115 <div id="footer">
 116 <div id="footer-text">
 117 </div>
 118 <div id="footer-badges">
 119 </div>
 120 </div>
 121 </body>
 122 </html>