doc/guide/localhost/Elaborate

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>Elaborate</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install();
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>Elaborate</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="Elaborate">Elaborate</a> is a translation pass from the <a href="AST">AST</a>
  32 <a href="IntermediateLanguage">IntermediateLanguage</a> to the <a href="CoreML">CoreML</a> <a href="IntermediateLanguage">IntermediateLanguage</a>.</p></div>
  33 </div>
  34 </div>
  35 <div class="sect1">
  36 <h2 id="_description">Description</h2>
  37 <div class="sectionbody">
  38 <div class="paragraph"><p>This pass performs type inference and type checking according to the
  39 <a href="DefinitionOfStandardML">Definition</a>.  It also defunctorizes the
  40 program, eliminating all module-level constructs.</p></div>
  41 </div>
  42 </div>
  43 <div class="sect1">
  44 <h2 id="_implementation">Implementation</h2>
  45 <div class="sectionbody">
  46 <div class="ulist"><ul>
  47 <li>
  48 <p>
  49 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate.sig"><span class="monospaced">elaborate.sig</span></a>
  50 </p>
  51 </li>
  52 <li>
  53 <p>
  54 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate.fun"><span class="monospaced">elaborate.fun</span></a>
  55 </p>
  56 </li>
  57 <li>
  58 <p>
  59 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-env.sig"><span class="monospaced">elaborate-env.sig</span></a>
  60 </p>
  61 </li>
  62 <li>
  63 <p>
  64 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-env.fun"><span class="monospaced">elaborate-env.fun</span></a>
  65 </p>
  66 </li>
  67 <li>
  68 <p>
  69 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-modules.sig"><span class="monospaced">elaborate-modules.sig</span></a>
  70 </p>
  71 </li>
  72 <li>
  73 <p>
  74 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-modules.fun"><span class="monospaced">elaborate-modules.fun</span></a>
  75 </p>
  76 </li>
  77 <li>
  78 <p>
  79 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.sig"><span class="monospaced">elaborate-core.sig</span></a>
  80 </p>
  81 </li>
  82 <li>
  83 <p>
  84 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/elaborate-core.fun"><span class="monospaced">elaborate-core.fun</span></a>
  85 </p>
  86 </li>
  87 <li>
  88 <p>
  89 <a href="https://github.com/MLton/mlton/tree/master/mlton/elaborate"><span class="monospaced">elaborate</span></a>
  90 </p>
  91 </li>
  92 </ul></div>
  93 </div>
  94 </div>
  95 <div class="sect1">
  96 <h2 id="_details_and_notes">Details and Notes</h2>
  97 <div class="sectionbody">
  98 <div class="paragraph"><p>At the modules level, the <a href="Elaborate">Elaborate</a> pass:</p></div>
  99 <div class="ulist"><ul>
 100 <li>
 101 <p>
 102 elaborates signatures with interfaces (see
 103 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/interface.sig"><span class="monospaced">interface.sig</span></a> and
 104 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/interface.fun"><span class="monospaced">interface.fun</span></a>)
 105 </p>
 106 <div class="paragraph"><p>The main trick is to use disjoint sets to efficiently handle sharing
 107 of tycons and of structures and then to copy signatures as dags rather
 108 than as trees.</p></div>
 109 </li>
 110 <li>
 111 <p>
 112 checks functors at the point of definition, using functor summaries
 113 to speed up checking of functor applications.
 114 </p>
 115 <div class="paragraph"><p>When a functor is first type checked, we keep track of the dummy
 116 argument structure and the dummy result structure, as well as all the
 117 tycons that were created while elaborating the body.  Then, if we
 118 later need to type check an application of the functor (as opposed to
 119 defunctorize an application), we pair up tycons in the dummy argument
 120 structure with the actual argument structure and then replace the
 121 dummy tycons with the actual tycons in the dummy result structure,
 122 yielding the actual result structure.  We also generate new tycons for
 123 all the tycons that we created while originally elaborating the body.</p></div>
 124 </li>
 125 <li>
 126 <p>
 127 handles opaque signature constraints.
 128 </p>
 129 <div class="paragraph"><p>This is implemented by building a dummy structure realized from the
 130 signature, just as we would for a functor argument when type checking
 131 a functor.  The dummy structure contains exactly the type information
 132 that is in the signature, which is what opacity requires.  We then
 133 replace the variables (and constructors) in the dummy structure with
 134 the corresponding variables (and constructors) from the actual
 135 structure so that the translation to <a href="CoreML">CoreML</a> uses the right stuff.
 136 For each tycon in the dummy structure, we keep track of the
 137 corresponding type structure in the actual structure.  This is used
 138 when producing the <a href="CoreML">CoreML</a> types (see <span class="monospaced">expandOpaque</span> in
 139 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/type-env.sig"><span class="monospaced">type-env.sig</span></a> and
 140 <a href="https://github.com/MLton/mlton/blob/master/mlton/elaborate/type-env.fun"><span class="monospaced">type-env.fun</span></a>).</p></div>
 141 <div class="paragraph"><p>Then, within each <span class="monospaced">structure</span> or <span class="monospaced">functor</span> body, for each declaration
 142 (<span class="monospaced">&lt;dec&gt;</span> in the <a href="StandardML">Standard ML</a> grammar), the <a href="Elaborate">Elaborate</a>
 143 pass does three steps:</p></div>
 144 <div class="openblock">
 145 <div class="content">
 146 <div class="olist arabic"><ol class="arabic">
 147 <li>
 148 <p>
 149 <a href="ScopeInference">ScopeInference</a>
 150 </p>
 151 </li>
 152 <li>
 153 <p>
 154 </p>
 155 <div class="ulist"><ul>
 156 <li>
 157 <p>
 158 <a href="PrecedenceParse">PrecedenceParse</a>
 159 </p>
 160 </li>
 161 <li>
 162 <p>
 163 <span class="monospaced">_{ex,im}port</span> expansion
 164 </p>
 165 </li>
 166 <li>
 167 <p>
 168 profiling insertion
 169 </p>
 170 </li>
 171 <li>
 172 <p>
 173 unification
 174 </p>
 175 </li>
 176 </ul></div>
 177 </li>
 178 <li>
 179 <p>
 180 Overloaded {constant, function, record pattern} resolution
 181 </p>
 182 </li>
 183 </ol></div>
 184 </div></div>
 185 </li>
 186 </ul></div>
 187 <div class="sect2">
 188 <h3 id="_defunctorization">Defunctorization</h3>
 189 <div class="paragraph"><p>The <a href="Elaborate">Elaborate</a> pass performs a number of duties historically
 190 assigned to the <a href="Defunctorize">Defunctorize</a> pass.</p></div>
 191 <div class="paragraph"><p>As part of the <a href="Elaborate">Elaborate</a> pass, all module level constructs
 192 (<span class="monospaced">open</span>, <span class="monospaced">signature</span>, <span class="monospaced">structure</span>, <span class="monospaced">functor</span>, long identifiers) are
 193 removed.  This works because the <a href="Elaborate">Elaborate</a> pass assigns a unique
 194 name to every type and variable in the program.  This also allows the
 195 <a href="Elaborate">Elaborate</a> pass to eliminate <span class="monospaced">local</span> declarations, which are purely
 196 for namespace management.</p></div>
 197 </div>
 198 </div>
 199 </div>
 200 <div class="sect1">
 201 <h2 id="_examples">Examples</h2>
 202 <div class="sectionbody">
 203 <div class="paragraph"><p>Here are a number of examples of elaboration.</p></div>
 204 <div class="ulist"><ul>
 205 <li>
 206 <p>
 207 All variables bound in <span class="monospaced">val</span> declarations are renamed.
 208 </p>
 209 <div class="listingblock">
 210 <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>
 211 <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>
 212 </pre></div></div></div>
 213 <div class="listingblock">
 214 <div class="content monospaced">
 215 <pre>val x_0 = 13
 216 val y_0 = x_0</pre>
 217 </div></div>
 218 </li>
 219 <li>
 220 <p>
 221 All variables in <span class="monospaced">fun</span> declarations are renamed.
 222 </p>
 223 <div class="listingblock">
 224 <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>
 225 <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>
 226 </pre></div></div></div>
 227 <div class="listingblock">
 228 <div class="content monospaced">
 229 <pre>fun f_0 x_0 = g_0 x_0
 230 and g_0 y_0 = f_0 y_0</pre>
 231 </div></div>
 232 </li>
 233 <li>
 234 <p>
 235 Type abbreviations are removed, and the abbreviation is expanded
 236 wherever it is used.
 237 </p>
 238 <div class="listingblock">
 239 <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>
 240 <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>
 241 <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>
 242 </pre></div></div></div>
 243 <div class="listingblock">
 244 <div class="content monospaced">
 245 <pre>fun f_0 (x_0 : (int * bool) * real) = x_0</pre>
 246 </div></div>
 247 </li>
 248 <li>
 249 <p>
 250 Exception declarations create a new constructor and rename the type.
 251 </p>
 252 <div class="listingblock">
 253 <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>
 254 <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>
 255 </pre></div></div></div>
 256 <div class="listingblock">
 257 <div class="content monospaced">
 258 <pre>exception E_0 of int * real</pre>
 259 </div></div>
 260 </li>
 261 <li>
 262 <p>
 263 The type and value constructors in datatype declarations are renamed.
 264 </p>
 265 <div class="listingblock">
 266 <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>
 267 </pre></div></div></div>
 268 <div class="listingblock">
 269 <div class="content monospaced">
 270 <pre>datatype t_0 = A_0 of int | B_0 of real * t_0</pre>
 271 </div></div>
 272 </li>
 273 <li>
 274 <p>
 275 Local declarations are moved to the top-level.  The environment
 276 keeps track of the variables in scope.
 277 </p>
 278 <div class="listingblock">
 279 <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>
 280 <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>
 281 <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>
 282 <span class="k">end</span><span class="w"></span>
 283 <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>
 284 </pre></div></div></div>
 285 <div class="listingblock">
 286 <div class="content monospaced">
 287 <pre>val x_0 = 13
 288 val x_1 = 14
 289 val y_0 = x_1
 290 val z_0 = x_0</pre>
 291 </div></div>
 292 </li>
 293 <li>
 294 <p>
 295 Structure declarations are eliminated, with all declarations moved
 296 to the top level.  Long identifiers are renamed.
 297 </p>
 298 <div class="listingblock">
 299 <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>
 300 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 301 <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>
 302 <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>
 303 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 304 <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>
 305 </pre></div></div></div>
 306 <div class="listingblock">
 307 <div class="content monospaced">
 308 <pre>val x_0 : int = 13
 309 val y_0 : int = x_0</pre>
 310 </div></div>
 311 </li>
 312 <li>
 313 <p>
 314 Open declarations are eliminated.
 315 </p>
 316 <div class="listingblock">
 317 <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>
 318 <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>
 319 <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>
 320 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 321 <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>
 322 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 323 <span class="k">open</span><span class="w"> </span><span class="n">S</span><span class="w"></span>
 324 <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>
 325 </pre></div></div></div>
 326 <div class="listingblock">
 327 <div class="content monospaced">
 328 <pre>val x_0 = 13
 329 val y_0 = 14
 330 val x_1 = 15
 331 val z_0 = x_1 + y_0</pre>
 332 </div></div>
 333 </li>
 334 <li>
 335 <p>
 336 Functor declarations are eliminated, and the body of a functor is
 337 duplicated wherever the functor is applied.
 338 </p>
 339 <div class="listingblock">
 340 <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>
 341 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 342 <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>
 343 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 344 <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>
 345 <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>
 346 <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>
 347 </pre></div></div></div>
 348 <div class="listingblock">
 349 <div class="content monospaced">
 350 <pre>val x_0 = 13
 351 val y_0 = x_0
 352 val x_1 = 14
 353 val y_1 = x_1
 354 val z_0 = y_0 + y_1</pre>
 355 </div></div>
 356 </li>
 357 <li>
 358 <p>
 359 Signature constraints are eliminated.  Note that signatures do
 360 affect how subsequent variables are renamed.
 361 </p>
 362 <div class="listingblock">
 363 <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>
 364 <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>
 365 <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>
 366 <span class="w">              </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 367 <span class="w">   </span><span class="k">struct</span><span class="w"></span>
 368 <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>
 369 <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>
 370 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 371 <span class="k">open</span><span class="w"> </span><span class="n">S</span><span class="w"></span>
 372 <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>
 373 </pre></div></div></div>
 374 <div class="listingblock">
 375 <div class="content monospaced">
 376 <pre>val y_0 = 13
 377 val x_0 = 14
 378 val y_1 = x_0
 379 val z_0 = x_0 + y_0</pre>
 380 </div></div>
 381 </li>
 382 </ul></div>
 383 </div>
 384 </div>
 385 </div>
 386 <div id="footnotes"><hr></div>
 387 <div id="footer">
 388 <div id="footer-text">
 389 </div>
 390 <div id="footer-badges">
 391 </div>
 392 </div>
 393 </body>
 394 </html>