<!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>Elaborate - 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%;">
      Elaborate
    <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">
Elaborate is a translation pass from the <a href="AST">AST</a> <a href="IntermediateLanguage">IntermediateLanguage</a> to the <a href="CoreML">CoreML</a> <a href="IntermediateLanguage">IntermediateLanguage</a>. <h2 id="head-55f8ebc805e65b5b71ddafdae390e3be2bcd69af">Description</h2>
<p>
This pass performs type inference and type checking according to the <a href="DefinitionOfStandardML"> Definition</a>.  It also defunctorizes the program, eliminating all module-level constructs. 
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>

<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate.sig</a>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate.fun</a>
<br>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-env.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-env.sig</a>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-env.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-env.fun</a>
<br>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-modules.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-modules.sig</a>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-modules.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-modules.fun</a>
<br>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-core.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-core.sig</a>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/elaborate-core.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate-core.fun</a>
<br>
 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate"><img src="moin-www.png" alt="[WWW]" height="11" width="11">elaborate</a>
 <h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<p>
At the modules level, the Elaborate pass: 
</p>

    <ul>

    <li>
<p>
 elaborates signatures with interfaces (see 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/interface.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">interface.sig</a>
 and 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/interface.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">interface.fun</a>
).   
</p>
</li>

            <ul>

   The main trick is to use disjoint sets to efficiently handle    sharing of tycons and of structures and then to copy signatures as    dags rather than as trees. 
            </ul>


    <li>
<p>
 checks functors at the point of definition, using functor summaries to speed up checking of functor applications. 
</p>
</li>

            <ul>

   When a functor is first type checked, we keep track of the dummy    argument structure and the dummy result structure, as well as all    the tycons that were created while elaborating the body.  Then, if    we later need to type check an application of the functor (as    opposed to defunctorize an application), we pair up tycons in the    dummy argument structure with the actual argument structure and    then replace the dummy tycons with the actual tycons in the dummy    result structure, yielding the actual result structure.  We also    generate new tycons for all the tycons that we created while    originally elaborating the body. 
            </ul>


    <li>
<p>
 handles opaque signature constraints.   
</p>
</li>

            <ul>

   This is implemented by building a dummy structure realized from the    signature, just as we would for a functor argument when type    checking a functor.  The dummy structure contains exactly the type    information that is in the signature, which is what opacity    requires.  We then replace the variables (and constructors) in the    dummy structure with the corresponding variables (and constructors)    from the actual structure so that the translation to <a href="CoreML">CoreML</a>    uses the right stuff.  For each tycon in the dummy structure, we    keep track of the corresponding type structure in the actual    structure.  This is used when producing the <a href="CoreML">CoreML</a> types (see    <tt>expandOpaque</tt> in 
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/type-env.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">type-env.sig</a>
 and    
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20051202-release/mlton/elaborate/type-env.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">type-env.fun</a>
). 
            </ul>



    </ul>


<p>
Then, within each <tt>structure</tt> or <tt>functor</tt> body, for each declaration (<tt>&lt;dec&gt;</tt> in the <a href="StandardML">Standard ML</a> grammar), the Elaborate pass does three steps: 
</p>

    <ol type="1">

    <li>
<p>
<a href="ScopeInference">ScopeInference</a> 
</p>
</li>
    <li>
<p>
 
</p>
</li>

                <ul>

                <li>
<p>
 <a href="PrecedenceParse">PrecedenceParse</a> 
</p>
</li>
                <li>
<p>
 <tt>_{ex,im}port</tt> expansion 
</p>
</li>
                <li>
<p>
 profiling insertion 
</p>
</li>
                <li>
<p>
 unification 
</p>
</li>

                </ul>


    <li>
<p>
Overloaded {constant, function, record pattern} resolution 
</p>
</li>

    </ol>


<h4 id="head-4cd3688ea7edd2f9c363c4ca43ea16b47061e473">Defunctorization</h4>
<p>
The Elaborate pass performs a number of duties historically assigned to the <a href="Defunctorize">Defunctorize</a> pass. 
</p>
<p>
As part of the Elaborate pass, all module level constructs (<tt>open</tt>, <tt>signature</tt>, <tt>structure</tt>, <tt>functor</tt>, long identifiers) are removed.  This works because the Elaborate pass assigns a unique name to every type and variable in the program.  This also allows the Elaborate pass to eliminate <tt>local</tt> declarations, which are purely for namespace management. 
</p>
<h2 id="head-eb01bf04c9a0e8a71c45816513df424f1c7ffedb">Examples</h2>
Here are a number of examples of elaboration. 
    <ul>

    <li>
<p>
 All variables bound in <tt>val</tt> declarations are renamed.    
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> y = x
</PRE>
  
<pre>val x_0 = 13 
val y_0 = x_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 All variables in <tt>fun</tt> declarations are renamed.   
<pre class=code>
<B><FONT COLOR="#A020F0">fun</FONT></B> f x = g x
<B><FONT COLOR="#A020F0">and</FONT></B> g y = f y
</PRE>
  
<pre>fun f_0 x_0 = g_0 x_0
and g_0 y_0 = f_0 y_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Type abbreviations are removed, and the abbreviation is expanded  wherever it is used.   
<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'a u </FONT></B>=<FONT COLOR="#228B22"><B> int * 'a
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> 'b t </FONT></B>=<FONT COLOR="#228B22"><B> 'b u * real
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> f (x : bool t) = x
</PRE>
 
<pre>fun f_0 (x_0 : (int * bool) * real) = x_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Exception declarations create a new constructor and rename the  type.   
<pre class=code>
<B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> int
</FONT></B><B><FONT COLOR="#A020F0">exception</FONT></B><FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">E</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> t * real
</FONT></B></PRE>
   
<pre>exception E_0 of int * real
</pre>
</p>
</li>
    <li class="gap">
<p>
 The type and value constructors in datatype declarations are renamed.  
<pre class=code>
<B><FONT COLOR="#A020F0">datatype</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">A</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> int </FONT></B>|<FONT COLOR="#228B22"><B> <FONT COLOR="#B8860B">B</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> real * t
</FONT></B></PRE>
  
<pre>datatype t_0 = A_0 of int | B_0 of real * t_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Local declarations are moved to the top-level.  The environment  keeps track of the variables in scope.  
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#A020F0">local</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">14</FONT></B>
<B><FONT COLOR="#A020F0">in</FONT></B> <B><FONT COLOR="#A020F0">val</FONT></B> y = x
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> z = x
</PRE>
  
<pre>val x_0 = 13
val x_1 = 14
val y_0 = x_1
val z_0 = x_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Structure declarations are eliminated, with all declarations   moved to the top level.  Long identifiers are renamed.  
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> S =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
      <B><FONT COLOR="#A020F0">type</FONT></B><FONT COLOR="#228B22"><B> t </FONT></B>=<FONT COLOR="#228B22"><B> int
      </FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> x : t = <B><FONT COLOR="#5F9EA0">13</FONT></B>
   <B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> y : S.t = S.x
</PRE>
  
<pre>val x_0 : int = 13
val y_0 : int = x_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Open declarations are eliminated.  
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> y = <B><FONT COLOR="#5F9EA0">14</FONT></B>
<B><FONT COLOR="#0000FF">structure</FONT></B> S =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
     <B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">15</FONT></B>
   <B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#0000FF">open</FONT></B> S
<B><FONT COLOR="#A020F0">val</FONT></B> z = x + y
</PRE>
  
<pre>val x_0 = 13
val y_0 = 14
val x_1 = 15
val z_0 = x_1 + y_0
</pre>
</p>
</li>
    <li class="gap">
<p>
 Functor declarations are eliminated, and the body of a functor is  duplicated wherever the functor is applied.  
<pre class=code>
<B><FONT COLOR="#0000FF">functor</FONT></B> F(<B><FONT COLOR="#A020F0">val</FONT></B> x : int) =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
     <B><FONT COLOR="#A020F0">val</FONT></B> y = x
   <B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#0000FF">structure</FONT></B> F1 = F(<B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">13</FONT></B>)
<B><FONT COLOR="#0000FF">structure</FONT></B> F2 = F(<B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">14</FONT></B>)
<B><FONT COLOR="#A020F0">val</FONT></B> z = F1.y + F2.y
</PRE>
  
<pre>val x_0 = 13
val y_0 = x_0
val x_1 = 14
val y_1 = x_1
val z_0 = y_0 + y_1
</pre>
</p>
</li>
    <li class="gap">
<p>
 Signature constraints are eliminated.  Note that signatures do  affect how subsequent variables are renamed.  
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> y = <B><FONT COLOR="#5F9EA0">13</FONT></B>
<B><FONT COLOR="#0000FF">structure</FONT></B> S : <B><FONT COLOR="#0000FF">sig</FONT></B>
                 <B><FONT COLOR="#A020F0">val</FONT></B> x : int
              <B><FONT COLOR="#0000FF">end</FONT></B> =
   <B><FONT COLOR="#0000FF">struct</FONT></B>
      <B><FONT COLOR="#A020F0">val</FONT></B> x = <B><FONT COLOR="#5F9EA0">14</FONT></B>
      <B><FONT COLOR="#A020F0">val</FONT></B> y = x
   <B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#0000FF">open</FONT></B> S
<B><FONT COLOR="#A020F0">val</FONT></B> z = x + y
</PRE>
  
<pre>val y_0 = 13
val x_0 = 14
val y_1 = x_0
val z_0 = x_0 + y_0
</pre>
</p>
</li>
</ul>

</div>



<p>
<hr>
Last edited on 2005-12-01 03:54:13 by <span title="ppp-71-139-183-221.dsl.snfc21.pacbell.net"><a href="StephenWeeks">StephenWeeks</a></span>.
</body></html>
