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

<!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>XMLShrink</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>XMLShrink</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p>XMLShrink is an optimization pass for the <a href="XML">XML</a>\r
<a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="XMLSimplify">XMLSimplify</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 optimizations based on a reduction system.</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/xml/shrink.sig"><span class="monospaced">shrink.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/shrink.fun"><span class="monospaced">shrink.fun</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>The simplifier is based on <a href="References#AppelJim97"> Shrinking Lambda\r
Expressions in Linear Time</a>.</p></div>\r
<div class="paragraph"><p>The source program may contain functions that are only called once, or\r
not even called at all.  Match compilation introduces many such\r
functions.  In order to reduce the program size, speed up later\r
phases, and improve the flow analysis, a source to source simplifier\r
is run on <a href="XML">XML</a> after type inference and match compilation.</p></div>\r
<div class="paragraph"><p>The simplifier implements the reductions shown below.  The reductions\r
eliminate unnecessary declarations (see the side constraint in the\r
figure), applications where the function is immediate, and case\r
statements where the test is immediate.  Declarations can be\r
eliminated only when the expression is nonexpansive (see Section 4.7\r
of the <a href="DefinitionOfStandardML"> Definition</a>), which is a syntactic\r
condition that ensures that the expression has no effects\r
(assignments, raises, or nontermination).  The reductions on case\r
statements do not show the other irrelevant cases that may exist.  The\r
reductions were chosen so that they were strongly normalizing and so\r
that they never increased tree size.</p></div>\r
<div class="ulist"><ul>\r
<li>\r
<p>\r
</p>\r
<div class="openblock">\r
<div class="content">\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">let</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">e1</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>reduces to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="n">e2</span><span class="w"> </span><span class="p">[</span><span class="n">x</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">e1</span><span class="p">]</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>if <span class="monospaced">e1</span> is a constant or variable or if <span class="monospaced">e1</span> is nonexpansive and <span class="monospaced">x</span> occurs zero or one time in <span class="monospaced">e2</span></p></div>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
</p>\r
<div class="openblock">\r
<div class="content">\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e1</span><span class="p">)</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>reduces to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">let</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">e2</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e1</span><span class="w"></span>\r
</pre></div></div></div>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
</p>\r
<div class="openblock">\r
<div class="content">\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="n">e1</span><span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>reduces to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="n">e1</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>if <span class="monospaced">e1</span> is nonexpansive</p></div>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
</p>\r
<div class="openblock">\r
<div class="content">\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">case</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">p1</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>reduces to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">let</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="k">case</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">p1</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="k">end</span><span class="w"></span>\r
</pre></div></div></div>\r
</div></div>\r
</li>\r
<li>\r
<p>\r
</p>\r
<div class="openblock">\r
<div class="content">\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">case</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
</pre></div></div></div>\r
<div class="paragraph"><p>reduces to</p></div>\r
<div class="listingblock">\r
<div class="content"><div class="highlight"><pre><span class="k">let</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">e1</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
</pre></div></div></div>\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
Commit	Line	Data
7f918cf1 CE	1	<!DOCTYPE html>\r
	2	<html lang="en">\r
	3	<head>\r
	4	<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r
	5	<meta name="generator" content="AsciiDoc 8.6.9">\r
	6	<title>XMLShrink</title>\r
	7	<link rel="stylesheet" href="./asciidoc.css" type="text/css">\r
	8	<link rel="stylesheet" href="./pygments.css" type="text/css">\r
	9	\r
	10	\r
	11	<script type="text/javascript" src="./asciidoc.js"></script>\r
	12	<script type="text/javascript">\r
	13	/<![CDATA[/\r
	14	asciidoc.install();\r
	15	/]]>/\r
	16	</script>\r
	17	<link rel="stylesheet" href="./mlton.css" type="text/css">\r
	18	</head>\r
	19	<body class="article">\r
	20	<div id="banner">\r
	21	<div id="banner-home">\r
	22	<a href="./Home">MLton 20180207</a>\r
	23	</div>\r
	24	</div>\r
	25	<div id="header">\r
	26	<h1>XMLShrink</h1>\r
	27	</div>\r
	28	<div id="content">\r
	29	<div id="preamble">\r
	30	<div class="sectionbody">\r
	31	<div class="paragraph"><p>XMLShrink is an optimization pass for the <a href="XML">XML</a>\r
	32	<a href="IntermediateLanguage">IntermediateLanguage</a>, invoked from <a href="XMLSimplify">XMLSimplify</a>.</p></div>\r
	33	</div>\r
	34	</div>\r
	35	<div class="sect1">\r
	36	<h2 id="_description">Description</h2>\r
	37	<div class="sectionbody">\r
	38	<div class="paragraph"><p>This pass performs optimizations based on a reduction system.</p></div>\r
	39	</div>\r
	40	</div>\r
	41	<div class="sect1">\r
	42	<h2 id="_implementation">Implementation</h2>\r
	43	<div class="sectionbody">\r
	44	<div class="ulist"><ul>\r
	45	<li>\r
	46	<p>\r
	47	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/shrink.sig"><span class="monospaced">shrink.sig</span></a>\r
	48	</p>\r
	49	</li>\r
	50	<li>\r
	51	<p>\r
	52	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/shrink.fun"><span class="monospaced">shrink.fun</span></a>\r
	53	</p>\r
	54	</li>\r
	55	</ul></div>\r
	56	</div>\r
	57	</div>\r
	58	<div class="sect1">\r
	59	<h2 id="_details_and_notes">Details and Notes</h2>\r
	60	<div class="sectionbody">\r
	61	<div class="paragraph"><p>The simplifier is based on <a href="References#AppelJim97"> Shrinking Lambda\r
	62	Expressions in Linear Time</a>.</p></div>\r
	63	<div class="paragraph"><p>The source program may contain functions that are only called once, or\r
	64	not even called at all. Match compilation introduces many such\r
65	functions. In order to reduce the program size, speed up later\r
66	phases, and improve the flow analysis, a source to source simplifier\r
67	is run on <a href="XML">XML</a> after type inference and match compilation.</p></div>\r
68	<div class="paragraph"><p>The simplifier implements the reductions shown below. The reductions\r
69	eliminate unnecessary declarations (see the side constraint in the\r
70	figure), applications where the function is immediate, and case\r
71	statements where the test is immediate. Declarations can be\r
72	eliminated only when the expression is nonexpansive (see Section 4.7\r
73	of the <a href="DefinitionOfStandardML"> Definition</a>), which is a syntactic\r
74	condition that ensures that the expression has no effects\r
75	(assignments, raises, or nontermination). The reductions on case\r
76	statements do not show the other irrelevant cases that may exist. The\r
77	reductions were chosen so that they were strongly normalizing and so\r
78	that they never increased tree size.</p></div>\r
79	<div class="ulist"><ul>\r
80	<li>\r
81	<p>\r
82	</p>\r
83	<div class="openblock">\r
84	<div class="content">\r
85	<div class="listingblock">\r
86	<div class="content"><div class="highlight"><pre><span class="k">let</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">e1</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
87	</pre></div></div></div>\r
88	<div class="paragraph"><p>reduces to</p></div>\r
89	<div class="listingblock">\r
90	<div class="content"><div class="highlight"><pre><span class="n">e2</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">e1</span><span class="p">]</span><span class="w"></span>\r
91	</pre></div></div></div>\r
92	<div class="paragraph"><p>if <span class="monospaced">e1</span> is a constant or variable or if <span class="monospaced">e1</span> is nonexpansive and <span class="monospaced">x</span> occurs zero or one time in <span class="monospaced">e2</span></p></div>\r
93	</div></div>\r
94	</li>\r
95	<li>\r
96	<p>\r
97	</p>\r
98	<div class="openblock">\r
99	<div class="content">\r
100	<div class="listingblock">\r
101	<div class="content"><div class="highlight"><pre><span class="p">(</span><span class="k">fn</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">e1</span><span class="p">)</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
102	</pre></div></div></div>\r
103	<div class="paragraph"><p>reduces to</p></div>\r
104	<div class="listingblock">\r
105	<div class="content"><div class="highlight"><pre><span class="k">let</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">e2</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e1</span><span class="w"></span>\r
106	</pre></div></div></div>\r
107	</div></div>\r
108	</li>\r
109	<li>\r
110	<p>\r
111	</p>\r
112	<div class="openblock">\r
113	<div class="content">\r
114	<div class="listingblock">\r
115	<div class="content"><div class="highlight"><pre><span class="n">e1</span><span class="w"> </span><span class="k">handle</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
116	</pre></div></div></div>\r
117	<div class="paragraph"><p>reduces to</p></div>\r
118	<div class="listingblock">\r
119	<div class="content"><div class="highlight"><pre><span class="n">e1</span><span class="w"></span>\r
120	</pre></div></div></div>\r
121	<div class="paragraph"><p>if <span class="monospaced">e1</span> is nonexpansive</p></div>\r
122	</div></div>\r
123	</li>\r
124	<li>\r
125	<p>\r
126	</p>\r
127	<div class="openblock">\r
128	<div class="content">\r
129	<div class="listingblock">\r
130	<div class="content"><div class="highlight"><pre><span class="k">case</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">p1</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="p">...</span><span class="w"></span>\r
131	</pre></div></div></div>\r
132	<div class="paragraph"><p>reduces to</p></div>\r
133	<div class="listingblock">\r
134	<div class="content"><div class="highlight"><pre><span class="k">let</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="k">case</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">p1</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="p">...</span><span class="w"> </span><span class="k">end</span><span class="w"></span>\r
135	</pre></div></div></div>\r
136	</div></div>\r
137	</li>\r
138	<li>\r
139	<p>\r
140	</p>\r
141	<div class="openblock">\r
142	<div class="content">\r
143	<div class="listingblock">\r
144	<div class="content"><div class="highlight"><pre><span class="k">case</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="n">e1</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">C</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">e2</span><span class="w"></span>\r
145	</pre></div></div></div>\r
146	<div class="paragraph"><p>reduces to</p></div>\r
147	<div class="listingblock">\r
148	<div class="content"><div class="highlight"><pre><span class="k">let</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">e1</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>\r
149	</pre></div></div></div>\r
150	</div></div>\r
151	</li>\r
152	</ul></div>\r
153	</div>\r
154	</div>\r
155	</div>\r
156	<div id="footnotes"><hr></div>\r
157	<div id="footer">\r
158	<div id="footer-text">\r
159	</div>\r
160	<div id="footer-badges">\r
161	</div>\r
162	</div>\r
163	</body>\r
164	</html>\r