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

<!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>Elaborate</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>Elaborate</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p><a href="Elaborate">Elaborate</a> is a translation pass from the <a href="AST">AST</a>\r
<a href="IntermediateLanguage">IntermediateLanguage</a> to the <a href="CoreML">CoreML</a> <a href="IntermediateLanguage">IntermediateLanguage</a>.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_description">Description</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>This pass performs type inference and type checking according to the\r
<a href="DefinitionOfStandardML">Definition</a>.  It also defunctorizes the\r
program, eliminating all module-level constructs.</p></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_implementation">Implementation</h2>\r
<div class="sectionbody">\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate.sig"><span class="monospaced">elaborate.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate.fun"><span class="monospaced">elaborate.fun</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-env.sig"><span class="monospaced">elaborate-env.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-env.fun"><span class="monospaced">elaborate-env.fun</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-modules.sig"><span class="monospaced">elaborate-modules.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-modules.fun"><span class="monospaced">elaborate-modules.fun</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.sig"><span class="monospaced">elaborate-core.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.fun"><span class="monospaced">elaborate-core.fun</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/tree/master/mlton/elaborate"><span class="monospaced">elaborate</span></a>\r
</p>\r
</li>\r
</ul></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_details_and_notes">Details and Notes</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>At the modules level, the <a href="Elaborate">Elaborate</a> pass:</p></div>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
elaborates signatures with interfaces (see\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/interface.sig"><span class="monospaced">interface.sig</span></a> and\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/interface.fun"><span class="monospaced">interface.fun</span></a>)\r
</p>\r
<div class="paragraph"><p>The main trick is to use disjoint sets to efficiently handle sharing\r
of tycons and of structures and then to copy signatures as dags rather\r
than as trees.</p></div>\r
</li>\r
<li>\r
<p>\r
checks functors at the point of definition, using functor summaries\r
to speed up checking of functor applications.\r
</p>\r
<div class="paragraph"><p>When a functor is first type checked, we keep track of the dummy\r
argument structure and the dummy result structure, as well as all the\r
tycons that were created while elaborating the body.  Then, if we\r
later need to type check an application of the functor (as opposed to\r
defunctorize an application), we pair up tycons in the dummy argument\r
structure with the actual argument structure and then replace the\r
dummy tycons with the actual tycons in the dummy result structure,\r
yielding the actual result structure.  We also generate new tycons for\r
all the tycons that we created while originally elaborating the body.</p></div>\r
</li>\r
<li>\r
<p>\r
handles opaque signature constraints.\r
</p>\r
<div class="paragraph"><p>This is implemented by building a dummy structure realized from the\r
signature, just as we would for a functor argument when type checking\r
a functor.  The dummy structure contains exactly the type information\r
that is in the signature, which is what opacity requires.  We then\r
replace the variables (and constructors) in the dummy structure with\r
the corresponding variables (and constructors) from the actual\r
structure so that the translation to <a href="CoreML">CoreML</a> uses the right stuff.\r
For each tycon in the dummy structure, we keep track of the\r
corresponding type structure in the actual structure.  This is used\r
when producing the <a href="CoreML">CoreML</a> types (see <span class="monospaced">expandOpaque</span> in\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/type-env.sig"><span class="monospaced">type-env.sig</span></a> and\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/type-env.fun"><span class="monospaced">type-env.fun</span></a>).</p></div>\r
<div class="paragraph"><p>Then, within each <span class="monospaced">structure</span> or <span class="monospaced">functor</span> body, for each declaration\r
(<span class="monospaced">&lt;dec&gt;</span> in the <a href="StandardML">Standard ML</a> grammar), the <a href="Elaborate">Elaborate</a>\r
pass does three steps:</p></div>\r
<div class="openblock">\r
<div class="content">\r
<div class="olist arabic"><ol class="arabic">\r
<li>\r
<p>\r
<a href="ScopeInference">ScopeInference</a>\r
</p>\r
</li>\r
<li>\r
<p>\r
</p>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
<a href="PrecedenceParse">PrecedenceParse</a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<span class="monospaced">_{ex,im}port</span> expansion\r
</p>\r
</li>\r
<li>\r
<p>\r
profiling insertion\r
</p>\r
</li>\r
<li>\r
<p>\r
unification\r
</p>\r
</li>\r
</ul></div>\r
</li>\r
<li>\r
<p>\r
Overloaded {constant, function, record pattern} resolution\r
</p>\r
</li>\r
</ol></div>\r
</div></div>\r
</li>\r
</ul></div>\r
<div class="sect2">\r
<h3 id="_defunctorization">Defunctorization</h3>\r
<div class="paragraph"><p>The <a href="Elaborate">Elaborate</a> pass performs a number of duties historically\r
assigned to the <a href="Defunctorize">Defunctorize</a> pass.</p></div>\r
<div class="paragraph"><p>As part of the <a href="Elaborate">Elaborate</a> pass, all module level constructs\r
(<span class="monospaced">open</span>, <span class="monospaced">signature</span>, <span class="monospaced">structure</span>, <span class="monospaced">functor</span>, long identifiers) are\r
removed.  This works because the <a href="Elaborate">Elaborate</a> pass assigns a unique\r
name to every type and variable in the program.  This also allows the\r
<a href="Elaborate">Elaborate</a> pass to eliminate <span class="monospaced">local</span> declarations, which are purely\r
for namespace management.</p></div>\r
</div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_examples">Examples</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p>Here are a number of examples of elaboration.</p></div>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
All variables bound in <span class="monospaced">val</span> declarations are renamed.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</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="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val x_0 = 13\r
val y_0 = x_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
All variables in <span class="monospaced">fun</span> declarations are renamed.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">f</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">g</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="k">and</span><span class="w"> </span><span class="n">g</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>fun f_0 x_0 = g_0 x_0\r
and g_0 y_0 = f_0 y_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Type abbreviations are removed, and the abbreviation is expanded\r
wherever it is used.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"></span>\r
<span class="k">type</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">real</span><span class="w"></span>\r
<span class="k">fun</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>fun f_0 (x_0 : (int * bool) * real) = x_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Exception declarations create a new constructor and rename the type.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">int</span><span class="w"></span>\r
<span class="k">exception</span><span class="w"> </span><span class="n">E</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">real</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>exception E_0 of int * real</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
The type and value constructors in datatype declarations are renamed.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">B</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>datatype t_0 = A_0 of int | B_0 of real * t_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Local declarations are moved to the top-level.  The environment\r
keeps track of the variables in scope.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>\r
<span class="k">local</span><span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">14</span><span class="w"></span>\r
<span class="k">in</span><span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="k">end</span><span class="w"></span>\r
<span class="k">val</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val x_0 = 13\r
val x_1 = 14\r
val y_0 = x_1\r
val z_0 = x_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Structure declarations are eliminated, with all declarations moved\r
to the top level.  Long identifiers are renamed.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">struct</span><span class="w"></span>\r
<span class="w">      </span><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">int</span><span class="w"></span>\r
<span class="w">      </span><span class="k">val</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">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
<span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">S</span><span class="p">.</span><span class="n">x</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val x_0 : int = 13\r
val y_0 : int = x_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Open declarations are eliminated.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</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="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">14</span><span class="w"></span>\r
<span class="k">structure</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">struct</span><span class="w"></span>\r
<span class="w">     </span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">15</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
<span class="k">open</span><span class="w"> </span><span class="n">S</span><span class="w"></span>\r
<span class="k">val</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val x_0 = 13\r
val y_0 = 14\r
val x_1 = 15\r
val z_0 = x_1 + y_0</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Functor declarations are eliminated, and the body of a functor is\r
duplicated wherever the functor is applied.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">functor</span><span class="w"> </span><span class="n">F</span><span class="p">(</span><span class="k">val</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">int</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">struct</span><span class="w"></span>\r
<span class="w">     </span><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
<span class="k">structure</span><span class="w"> </span><span class="n">F1</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">F</span><span class="p">(</span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>\r
<span class="k">structure</span><span class="w"> </span><span class="n">F2</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">F</span><span class="p">(</span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">14</span><span class="p">)</span><span class="w"></span>\r
<span class="k">val</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">F1</span><span class="p">.</span><span class="n">y</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">F2</span><span class="p">.</span><span class="n">y</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val x_0 = 13\r
val y_0 = x_0\r
val x_1 = 14\r
val y_1 = x_1\r
val z_0 = y_0 + y_1</pre>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
Signature constraints are eliminated.  Note that signatures do\r
affect how subsequent variables are renamed.\r
</p>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">13</span><span class="w"></span>\r
<span class="k">structure</span><span class="w"> </span><span class="n">S</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="k">sig</span><span class="w"></span>\r
<span class="w">                 </span><span class="k">val</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">int</span><span class="w"></span>\r
<span class="w">              </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r
<span class="w">   </span><span class="k">struct</span><span class="w"></span>\r
<span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">14</span><span class="w"></span>\r
<span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"></span>\r
<span class="w">   </span><span class="k">end</span><span class="w"></span>\r
<span class="k">open</span><span class="w"> </span><span class="n">S</span><span class="w"></span>\r
<span class="k">val</span><span class="w"> </span><span class="n">z</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">y</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="listingblock">\r
<div class="content monospaced">\r
<pre>val y_0 = 13\r
val x_0 = 14\r
val y_1 = x_0\r
val z_0 = x_0 + y_0</pre>\r
</div></div>\r
</li>\r
</ul></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