<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>FirstClassPolymorphism - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
FirstClassPolymorphism
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
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>
For example, the following declares and uses the polymorphic function <tt>id</tt>.
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> id = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
<B><FONT COLOR="#A020F0">val</FONT></B> _ = id <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> _ = id <B><FONT COLOR="#BC8F8F">"foo"</FONT></B>
</PRE>
</p>
<p>
If SML supported first-class polymorphism, we could write the following.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> useId id = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <B><FONT COLOR="#BC8F8F">"foo"</FONT></B>)
</PRE>
<p>
</p>
<p>
However, this does not type check. MLton reports the following error.
</p>
<pre>Error: z.sml 1.24.
Function applied to incorrect argument.
expects: [int]
but got: [string]
in: id "foo"
</pre><p>
The error message arises because MLton infers from <tt>id 13</tt> that <tt>id</tt> accepts an integer argument, but that <tt>id "foo"</tt> is passing a string. Using explicit types sheds some light on the problem.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> useId (id: 'a -> 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <B><FONT COLOR="#BC8F8F">"foo"</FONT></B>)
</PRE>
<p>
</p>
<p>
On this, MLton reports the following errors.
</p>
<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><p>
The errors arise because the argument <tt>id</tt> is <em>not</em> polymorphic; rather, it is monomorphic, with type <tt>'a -> 'a</tt>. It is perfectly valid to apply <tt>id</tt> to a value of type <tt>'a</tt>, as in the following
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> useId (id: 'a -> 'a, x: 'a) = id x <I><FONT COLOR="#B22222">(* type correct *)</FONT></I>
</PRE>
<p>
</p>
<p>
So, what is the difference between the type specification on <tt>id</tt> in the following two declarations?
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
<B><FONT COLOR="#A020F0">fun</FONT></B> useId (id: 'a -> 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <B><FONT COLOR="#BC8F8F">"foo"</FONT></B>)
</PRE>
<p>
</p>
<p>
While the type specifications on <tt>id</tt> look identical, they mean different things. The difference can be made clearer by explicitly <a href="TypeVariableScope">scoping the type variables</a>.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> id: 'a -> 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x => x
<B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> useId (id: 'a -> 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <B><FONT COLOR="#BC8F8F">"foo"</FONT></B>) <I><FONT COLOR="#B22222">(* type error *)</FONT></I>
</PRE>
<p>
</p>
<p>
In <tt>val 'a id</tt>, the type variable scoping means that for any <tt>'a</tt>, <tt>id</tt> has type <tt>'a -> 'a</tt>. Hence, <tt>id</tt> can be applied to arguments of type <tt>int</tt>, <tt>real</tt>, etc. Similarly, in <tt>fun 'a useId</tt>, the scoping means that <tt>useId</tt> is a polymorphic function that for any <tt>'a</tt> takes a function of type <tt>'a -> 'a</tt> and does something. Thus, <tt>useId</tt> could be applied to a function of type <tt>int -> int</tt>, <tt>real -> real</tt>, etc.
</p>
<p>
One could imagine an extension of SML that allowed scoping of type variables at places other than <tt>fun</tt> or <tt>val</tt> declarations, as in the following.
</p>
<pre>fun useId (id: ('a).'a -> 'a) = (id 13; id "foo") (* not SML *)
</pre><p>
Such an extension would need to be thought through very carefully, as it could cause significant complications with <a class="nonexistent" href="TypeInference">TypeInference</a>, possible even undecidability.
</p>
</div>
<p>
<hr>
Last edited on 2005-12-01 04:14:09 by <span title="ppp-71-139-183-221.dsl.snfc21.pacbell.net"><a href="StephenWeeks">StephenWeeks</a></span>.
</body></html>
