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