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

<!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>FirstClassPolymorphism</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>FirstClassPolymorphism</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p>First-class polymorphism is the ability to treat polymorphic functions\r
just like other values: pass them as arguments, store them in data\r
structures, etc.  Although <a href="StandardML">Standard ML</a> does have\r
polymorphic functions, it does not support first-class polymorphism.</p></div>\r
<div class="paragraph"><p>For example, the following declares and uses the polymorphic function\r
<span class="monospaced">id</span>.</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="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<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>\r
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>If SML supported first-class polymorphism, we could write the\r
following.</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">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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>However, this does not type check.  MLton reports the following error.</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>Error: z.sml 1.24-1.31.\r
  Function applied to incorrect argument.\r
    expects: [int]\r
    but got: [string]\r
    in: id "foo"</pre>\r
</div></div>\r
<div class="paragraph"><p>The error message arises because MLton infers from <span class="monospaced">id 13</span> that <span class="monospaced">id</span>\r
accepts an integer argument, but that <span class="monospaced">id "foo"</span> is passing a string.</p></div>\r
<div class="paragraph"><p>Using explicit types sheds some light on the problem.</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">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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>On this, MLton reports the following errors.</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>Error: z.sml 1.29-1.33.\r
  Function applied to incorrect argument.\r
    expects: ['a]\r
    but got: [int]\r
    in: id 13\r
Error: z.sml 1.36-1.43.\r
  Function applied to incorrect argument.\r
    expects: ['a]\r
    but got: [string]\r
    in: id "foo"</pre>\r
</div></div>\r
<div class="paragraph"><p>The errors arise because the argument <span class="monospaced">id</span> is <em>not</em> polymorphic;\r
rather, it is monomorphic, with type <span class="monospaced">'a -&gt; 'a</span>.  It is perfectly\r
valid to apply <span class="monospaced">id</span> to a value of type <span class="monospaced">'a</span>, as in the following</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">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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>So, what is the difference between the type specification on <span class="monospaced">id</span> in\r
the following two declarations?</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
<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>\r
</pre></div></div></div>\r
<div class="paragraph"><p>While the type specifications on <span class="monospaced">id</span> look identical, they mean\r
different things.  The difference can be made clearer by explicitly\r
<a href="TypeVariableScope">scoping the type variables</a>.</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
<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>\r
</pre></div></div></div>\r
<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>,\r
<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\r
type <span class="monospaced">int</span>, <span class="monospaced">real</span>, etc.  Similarly, in <span class="monospaced">fun 'a useId</span>, the scoping\r
means that <span class="monospaced">useId</span> is a polymorphic function that for any <span class="monospaced">'a</span> takes a\r
function of type <span class="monospaced">'a -&gt; 'a</span> and does something.  Thus, <span class="monospaced">useId</span> could\r
be applied to a function of type <span class="monospaced">int -&gt; int</span>, <span class="monospaced">real -&gt; real</span>, etc.</p></div>\r
<div class="paragraph"><p>One could imagine an extension of SML that allowed scoping of type\r
variables at places other than <span class="monospaced">fun</span> or <span class="monospaced">val</span> declarations, as in the\r
following.</p></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>fun useId (id: ('a).'a -&gt; 'a) = (id 13; id "foo")  (* not SML *)</pre>\r
</div></div>\r
<div class="paragraph"><p>Such an extension would need to be thought through very carefully, as\r
it could cause significant complications with <a href="TypeInference">TypeInference</a>,\r
possible even undecidability.</p></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
Commit	Line	Data
7f918cf1 CE	1	<!DOCTYPE html>\r
	2	<html lang="en">\r
	3	<head>\r
	4	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
	5	<meta name="generator" content="AsciiDoc 8.6.9">\r
	6	<title>FirstClassPolymorphism</title>\r
	7	<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
	8	<link rel="stylesheet" href="./pygments.css" type="text/css">\r
	9	\r
	10	\r
	11	<script type="text/javascript" src="./asciidoc.js"></script>\r
	12	<script type="text/javascript">\r
	13	/<![CDATA[/\r
	14	asciidoc.install();\r
	15	/]]>/\r
	16	</script>\r
	17	<link rel="stylesheet" href="./mlton.css" type="text/css">\r
	18	</head>\r
	19	<body class="article">\r
	20	<div id="banner">\r
	21	<div id="banner-home">\r
	22	<a href="./Home">MLton 20180207</a>\r
	23	</div>\r
	24	</div>\r
	25	<div id="header">\r
	26	<h1>FirstClassPolymorphism</h1>\r
	27	</div>\r
	28	<div id="content">\r
	29	<div id="preamble">\r
	30	<div class="sectionbody">\r
	31	<div class="paragraph"><p>First-class polymorphism is the ability to treat polymorphic functions\r
	32	just like other values: pass them as arguments, store them in data\r
	33	structures, etc. Although <a href="StandardML">Standard ML</a> does have\r
	34	polymorphic functions, it does not support first-class polymorphism.</p></div>\r
	35	<div class="paragraph"><p>For example, the following declares and uses the polymorphic function\r
	36	<span class="monospaced">id</span>.</p></div>\r
	37	<div class="listingblock">\r
	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">=></span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
	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>\r
	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">"foo"</span><span class="w"></span>\r
	41	</pre></div></div></div>\r
	42	<div class="paragraph"><p>If SML supported first-class polymorphism, we could write the\r
	43	following.</p></div>\r
	44	<div class="listingblock">\r
	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">"foo"</span><span class="p">)</span><span class="w"></span>\r
	46	</pre></div></div></div>\r
	47	<div class="paragraph"><p>However, this does not type check. MLton reports the following error.</p></div>\r
	48	<div class="listingblock">\r
	49	<div class="content monospaced">\r
	50	<pre>Error: z.sml 1.24-1.31.\r
	51	Function applied to incorrect argument.\r
	52	expects: [int]\r
	53	but got: [string]\r
	54	in: id "foo"</pre>\r
	55	</div></div>\r
	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>\r
	57	accepts an integer argument, but that <span class="monospaced">id "foo"</span> is passing a string.</p></div>\r
	58	<div class="paragraph"><p>Using explicit types sheds some light on the problem.</p></div>\r
	59	<div class="listingblock">\r
	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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'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">"foo"</span><span class="p">)</span><span class="w"></span>\r
	61	</pre></div></div></div>\r
	62	<div class="paragraph"><p>On this, MLton reports the following errors.</p></div>\r
	63	<div class="listingblock">\r
	64	<div class="content monospaced">\r
65	<pre>Error: z.sml 1.29-1.33.\r
66	Function applied to incorrect argument.\r
67	expects: ['a]\r
68	but got: [int]\r
69	in: id 13\r
70	Error: z.sml 1.36-1.43.\r
71	Function applied to incorrect argument.\r
72	expects: ['a]\r
73	but got: [string]\r
74	in: id "foo"</pre>\r
75	</div></div>\r
76	<div class="paragraph"><p>The errors arise because the argument <span class="monospaced">id</span> is <em>not</em> polymorphic;\r
77	rather, it is monomorphic, with type <span class="monospaced">'a -> 'a</span>. It is perfectly\r
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>\r
79	<div class="listingblock">\r
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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'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">'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>\r
81	</pre></div></div></div>\r
82	<div class="paragraph"><p>So, what is the difference between the type specification on <span class="monospaced">id</span> in\r
83	the following two declarations?</p></div>\r
84	<div class="listingblock">\r
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">'a</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="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'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">"foo"</span><span class="p">)</span><span class="w"></span>\r
87	</pre></div></div></div>\r
88	<div class="paragraph"><p>While the type specifications on <span class="monospaced">id</span> look identical, they mean\r
89	different things. The difference can be made clearer by explicitly\r
90	<a href="TypeVariableScope">scoping the type variables</a>.</p></div>\r
91	<div class="listingblock">\r
92	<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">id</span><span class="p">:</span><span class="w"> </span><span class="n">'a</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="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
93	<span class="k">fun</span><span class="w"> </span><span class="n">'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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">'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">"foo"</span><span class="p">)</span><span class="w"> </span><span class="cm">(* type error *)</span><span class="w"></span>\r
94	</pre></div></div></div>\r
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>,\r
96	<span class="monospaced">id</span> has type <span class="monospaced">'a -> 'a</span>. Hence, <span class="monospaced">id</span> can be applied to arguments of\r
97	type <span class="monospaced">int</span>, <span class="monospaced">real</span>, etc. Similarly, in <span class="monospaced">fun 'a useId</span>, the scoping\r
98	means that <span class="monospaced">useId</span> is a polymorphic function that for any <span class="monospaced">'a</span> takes a\r
99	function of type <span class="monospaced">'a -> 'a</span> and does something. Thus, <span class="monospaced">useId</span> could\r
100	be applied to a function of type <span class="monospaced">int -> int</span>, <span class="monospaced">real -> real</span>, etc.</p></div>\r
101	<div class="paragraph"><p>One could imagine an extension of SML that allowed scoping of type\r
102	variables at places other than <span class="monospaced">fun</span> or <span class="monospaced">val</span> declarations, as in the\r
103	following.</p></div>\r
104	<div class="listingblock">\r
105	<div class="content monospaced">\r
106	<pre>fun useId (id: ('a).'a -> 'a) = (id 13; id "foo") (* not SML *)</pre>\r
107	</div></div>\r
108	<div class="paragraph"><p>Such an extension would need to be thought through very carefully, as\r
109	it could cause significant complications with <a href="TypeInference">TypeInference</a>,\r
110	possible even undecidability.</p></div>\r
111	</div>\r
112	</div>\r
113	</div>\r
114	<div id="footnotes"><hr></div>\r
115	<div id="footer">\r
116	<div id="footer-text">\r
117	</div>\r
118	<div id="footer-badges">\r
119	</div>\r
120	</div>\r
121	</body>\r
122	</html>\r