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