<!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">

<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 20051202</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>
      &nbsp;<a href = "Index">Index</a>
      &nbsp;
</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 =&gt; x
<B><FONT COLOR="#A020F0">val</FONT></B> _ = id <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> _ = id <FONT COLOR="#BC8F8F"><B>&quot;foo&quot;</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 <FONT COLOR="#BC8F8F"><B>&quot;foo&quot;</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&nbsp;13</tt> that <tt>id</tt> accepts an integer argument, but that <tt>id&nbsp;"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 -&gt; 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <FONT COLOR="#BC8F8F"><B>&quot;foo&quot;</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&nbsp;-&gt;&nbsp;'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 -&gt; '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 -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; x
<B><FONT COLOR="#A020F0">fun</FONT></B> useId (id: 'a -&gt; 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <FONT COLOR="#BC8F8F"><B>&quot;foo&quot;</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> <FONT COLOR="#228B22"><B>'a</FONT></B> id: 'a -&gt; 'a = <B><FONT COLOR="#A020F0">fn</FONT></B> x =&gt; x
<B><FONT COLOR="#A020F0">fun</FONT></B> <FONT COLOR="#228B22"><B>'a</FONT></B> useId (id: 'a -&gt; 'a) = (id <B><FONT COLOR="#5F9EA0">13</FONT></B>; id <FONT COLOR="#BC8F8F"><B>&quot;foo&quot;</FONT></B>)  <I><FONT COLOR="#B22222">(* type error *)</FONT></I>
</PRE>
<p>
 
</p>
<p>
In <tt>val&nbsp;'a&nbsp;id</tt>, the type variable scoping means that for any <tt>'a</tt>, <tt>id</tt> has type <tt>'a&nbsp;-&gt;&nbsp;'a</tt>.  Hence, <tt>id</tt> can be applied to arguments of type <tt>int</tt>, <tt>real</tt>, etc.  Similarly, in <tt>fun&nbsp;'a&nbsp;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&nbsp;-&gt;&nbsp;'a</tt> and does something.  Thus, <tt>useId</tt> could be applied to a function of type <tt>int&nbsp;-&gt;&nbsp;int</tt>, <tt>real&nbsp;-&gt;&nbsp;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 -&gt; '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>
