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

<!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>XML</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>XML</h1>\r
</div>\r
<div id="content">\r
<div id="preamble">\r
<div class="sectionbody">\r
<div class="paragraph"><p><a href="XML">XML</a> is an <a href="IntermediateLanguage">IntermediateLanguage</a>, translated from <a href="CoreML">CoreML</a> by\r
<a href="Defunctorize">Defunctorize</a>, optimized by <a href="XMLSimplify">XMLSimplify</a>, and translated by\r
<a href="Monomorphise">Monomorphise</a> to <a href="SXML">SXML</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><a href="XML">XML</a> is polymorphic, higher-order, with flat patterns.  Every\r
<a href="XML">XML</a> expression is annotated with its type.  Polymorphic\r
generalization is made explicit through type variables annotating\r
<span class="monospaced">val</span> and <span class="monospaced">fun</span> declarations.  Polymorphic instantiation is made\r
explicit by specifying type arguments at variable references.  <a href="XML">XML</a>\r
patterns can not be nested and can not contain wildcards, constraints,\r
flexible records, or layering.</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/xml.sig"><span class="monospaced">xml.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml.fun"><span class="monospaced">xml.fun</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml-tree.sig"><span class="monospaced">xml-tree.sig</span></a>\r
</p>\r
</li>\r
<li>\r
<p>\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml-tree.fun"><span class="monospaced">xml-tree.fun</span></a>\r
</p>\r
</li>\r
</ul></div>\r
</div>\r
</div>\r
<div class="sect1">\r
<h2 id="_type_checking">Type Checking</h2>\r
<div class="sectionbody">\r
<div class="paragraph"><p><a href="XML">XML</a> also has a type checker, used for debugging.  At present, the\r
type checker is also the best specification of the type system of\r
<a href="XML">XML</a>.  If you need more details, the type checker\r
(<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/type-check.sig"><span class="monospaced">type-check.sig</span></a>,\r
<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/type-check.fun"><span class="monospaced">type-check.fun</span></a>), is pretty short.</p></div>\r
<div class="paragraph"><p>Since the type checker does not affect the output of the compiler\r
(unless it reports an error), it can be turned off.  The type checker\r
recursively descends the program, checking that the type annotating\r
each node is the same as the type synthesized from the types of the\r
expressions subnodes.</p></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><a href="XML">XML</a> uses the same atoms as <a href="CoreML">CoreML</a>, hence all identifiers\r
(constructors, variables, etc.) are unique and can have properties\r
attached to them.  Finally, <a href="XML">XML</a> has a simplifier (<a href="XMLShrink">XMLShrink</a>),\r
which implements a reduction system.</p></div>\r
<div class="sect2">\r
<h3 id="_types">Types</h3>\r
<div class="paragraph"><p><a href="XML">XML</a> types are either type variables or applications of n-ary type\r
constructors.  There are many utility functions for constructing and\r
destructing types involving built-in type constructors.</p></div>\r
<div class="paragraph"><p>A type scheme binds list of type variables in a type.  The only\r
interesting operation on type schemes is the application of a type\r
scheme to a list of types, which performs a simultaneous substitution\r
of the type arguments for the bound type variables of the scheme.  For\r
the purposes of type checking, it is necessary to know the type scheme\r
of variables, constructors, and primitives.  This is done by\r
associating the scheme with the identifier using its property list.\r
This approach is used instead of the more traditional environment\r
approach for reasons of speed.</p></div>\r
</div>\r
<div class="sect2">\r
<h3 id="_xmltree">XmlTree</h3>\r
<div class="paragraph"><p>Before defining <span class="monospaced">XML</span>, the signature for language <a href="XML">XML</a>, we need to\r
define an auxiliary signature <span class="monospaced">XML_TREE</span>, that contains the datatype\r
declarations for the expression trees of <a href="XML">XML</a>.  This is done solely\r
for the purpose of modularity&#8201;&#8212;&#8201;it allows the simplifier and type\r
checker to be defined by separate functors (which take a structure\r
matching <span class="monospaced">XML_TREE</span>).  Then, <span class="monospaced">Xml</span> is defined as the signature for a\r
module containing the expression trees, the simplifier, and the type\r
checker.</p></div>\r
<div class="paragraph"><p>Both constructors and variables can have type schemes, hence both\r
constructor and variable references specify the instance of the scheme\r
at the point of references.  An instance is specified with a vector of\r
types, which corresponds to the type variables in the scheme.</p></div>\r
<div class="paragraph"><p><a href="XML">XML</a> patterns are flat (i.e. not nested).  A pattern is a\r
constructor with an optional argument variable.  Patterns only occur\r
in <span class="monospaced">case</span> expressions.  To evaluate a case expression, compare the\r
test value sequentially against each pattern.  For the first pattern\r
that matches, destruct the value if necessary to bind the pattern\r
variables and evaluate the corresponding expression.  If no pattern\r
matches, evaluate the default.  All patterns of a case statement are\r
of the same variant of <span class="monospaced">Pat.t</span>, although this is not enforced by ML&#8217;s\r
type system.  The type checker, however, does enforce this.  Because\r
tuple patterns are irrefutable, there will only ever be one tuple\r
pattern in a case expression and there will be no default.</p></div>\r
<div class="paragraph"><p><a href="XML">XML</a> contains value, exception, and mutually recursive function\r
declarations.  There are no free type variables in <a href="XML">XML</a>.  All type\r
variables are explicitly bound at either a value or function\r
declaration.  At some point in the future, exception declarations may\r
go away, and exceptions may be represented with a single datatype\r
containing a <span class="monospaced">unit ref</span> component to implement genericity.</p></div>\r
<div class="paragraph"><p><a href="XML">XML</a> expressions are like those of <a href="CoreML">CoreML</a>, with the following\r
exceptions.  There are no records expressions.  After type inference,\r
all records (some of which may have originally been tuples in the\r
source) are converted to tuples, because once flexible record patterns\r
have been resolved, tuple labels are superfluous.  Tuple components\r
are ordered based on the field ordering relation.  <a href="XML">XML</a> eta expands\r
primitives and constructors so that there are always fully applied.\r
Hence, the only kind of value of arrow type is a lambda.  This\r
property is useful for flow analysis and later in code generation.</p></div>\r
<div class="paragraph"><p>An <a href="XML">XML</a> program is a list of toplevel datatype declarations and a\r
body expression.  Because datatype declarations are not generative,\r
the defunctorizer can safely move them to toplevel.</p></div>\r
</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>XML</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>XML</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><a href="XML">XML</a> is an <a href="IntermediateLanguage">IntermediateLanguage</a>, translated from <a href="CoreML">CoreML</a> by\r
	32	<a href="Defunctorize">Defunctorize</a>, optimized by <a href="XMLSimplify">XMLSimplify</a>, and translated by\r
	33	<a href="Monomorphise">Monomorphise</a> to <a href="SXML">SXML</a>.</p></div>\r
	34	</div>\r
	35	</div>\r
	36	<div class="sect1">\r
	37	<h2 id="_description">Description</h2>\r
	38	<div class="sectionbody">\r
	39	<div class="paragraph"><p><a href="XML">XML</a> is polymorphic, higher-order, with flat patterns. Every\r
	40	<a href="XML">XML</a> expression is annotated with its type. Polymorphic\r
	41	generalization is made explicit through type variables annotating\r
	42	<span class="monospaced">val</span> and <span class="monospaced">fun</span> declarations. Polymorphic instantiation is made\r
	43	explicit by specifying type arguments at variable references. <a href="XML">XML</a>\r
	44	patterns can not be nested and can not contain wildcards, constraints,\r
	45	flexible records, or layering.</p></div>\r
	46	</div>\r
	47	</div>\r
	48	<div class="sect1">\r
	49	<h2 id="_implementation">Implementation</h2>\r
	50	<div class="sectionbody">\r
	51	<div class="ulist"><ul>\r
	52	<li>\r
	53	<p>\r
	54	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml.sig"><span class="monospaced">xml.sig</span></a>\r
	55	</p>\r
	56	</li>\r
	57	<li>\r
	58	<p>\r
	59	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml.fun"><span class="monospaced">xml.fun</span></a>\r
	60	</p>\r
	61	</li>\r
	62	<li>\r
	63	<p>\r
	64	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml-tree.sig"><span class="monospaced">xml-tree.sig</span></a>\r
65	</p>\r
66	</li>\r
67	<li>\r
68	<p>\r
69	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/xml-tree.fun"><span class="monospaced">xml-tree.fun</span></a>\r
70	</p>\r
71	</li>\r
72	</ul></div>\r
73	</div>\r
74	</div>\r
75	<div class="sect1">\r
76	<h2 id="_type_checking">Type Checking</h2>\r
77	<div class="sectionbody">\r
78	<div class="paragraph"><p><a href="XML">XML</a> also has a type checker, used for debugging. At present, the\r
79	type checker is also the best specification of the type system of\r
80	<a href="XML">XML</a>. If you need more details, the type checker\r
81	(<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/type-check.sig"><span class="monospaced">type-check.sig</span></a>,\r
82	<a href="https://github.com/MLton/mlton/blob/master/mlton/xml/type-check.fun"><span class="monospaced">type-check.fun</span></a>), is pretty short.</p></div>\r
83	<div class="paragraph"><p>Since the type checker does not affect the output of the compiler\r
84	(unless it reports an error), it can be turned off. The type checker\r
85	recursively descends the program, checking that the type annotating\r
86	each node is the same as the type synthesized from the types of the\r
87	expressions subnodes.</p></div>\r
88	</div>\r
89	</div>\r
90	<div class="sect1">\r
91	<h2 id="_details_and_notes">Details and Notes</h2>\r
92	<div class="sectionbody">\r
93	<div class="paragraph"><p><a href="XML">XML</a> uses the same atoms as <a href="CoreML">CoreML</a>, hence all identifiers\r
94	(constructors, variables, etc.) are unique and can have properties\r
95	attached to them. Finally, <a href="XML">XML</a> has a simplifier (<a href="XMLShrink">XMLShrink</a>),\r
96	which implements a reduction system.</p></div>\r
97	<div class="sect2">\r
98	<h3 id="_types">Types</h3>\r
99	<div class="paragraph"><p><a href="XML">XML</a> types are either type variables or applications of n-ary type\r
100	constructors. There are many utility functions for constructing and\r
101	destructing types involving built-in type constructors.</p></div>\r
102	<div class="paragraph"><p>A type scheme binds list of type variables in a type. The only\r
103	interesting operation on type schemes is the application of a type\r
104	scheme to a list of types, which performs a simultaneous substitution\r
105	of the type arguments for the bound type variables of the scheme. For\r
106	the purposes of type checking, it is necessary to know the type scheme\r
107	of variables, constructors, and primitives. This is done by\r
108	associating the scheme with the identifier using its property list.\r
109	This approach is used instead of the more traditional environment\r
110	approach for reasons of speed.</p></div>\r
111	</div>\r
112	<div class="sect2">\r
113	<h3 id="_xmltree">XmlTree</h3>\r
114	<div class="paragraph"><p>Before defining <span class="monospaced">XML</span>, the signature for language <a href="XML">XML</a>, we need to\r
115	define an auxiliary signature <span class="monospaced">XML_TREE</span>, that contains the datatype\r
116	declarations for the expression trees of <a href="XML">XML</a>. This is done solely\r
117	for the purpose of modularity — it allows the simplifier and type\r
118	checker to be defined by separate functors (which take a structure\r
119	matching <span class="monospaced">XML_TREE</span>). Then, <span class="monospaced">Xml</span> is defined as the signature for a\r
120	module containing the expression trees, the simplifier, and the type\r
121	checker.</p></div>\r
122	<div class="paragraph"><p>Both constructors and variables can have type schemes, hence both\r
123	constructor and variable references specify the instance of the scheme\r
124	at the point of references. An instance is specified with a vector of\r
125	types, which corresponds to the type variables in the scheme.</p></div>\r
126	<div class="paragraph"><p><a href="XML">XML</a> patterns are flat (i.e. not nested). A pattern is a\r
127	constructor with an optional argument variable. Patterns only occur\r
128	in <span class="monospaced">case</span> expressions. To evaluate a case expression, compare the\r
129	test value sequentially against each pattern. For the first pattern\r
130	that matches, destruct the value if necessary to bind the pattern\r
131	variables and evaluate the corresponding expression. If no pattern\r
132	matches, evaluate the default. All patterns of a case statement are\r
133	of the same variant of <span class="monospaced">Pat.t</span>, although this is not enforced by ML’s\r
134	type system. The type checker, however, does enforce this. Because\r
135	tuple patterns are irrefutable, there will only ever be one tuple\r
136	pattern in a case expression and there will be no default.</p></div>\r
137	<div class="paragraph"><p><a href="XML">XML</a> contains value, exception, and mutually recursive function\r
138	declarations. There are no free type variables in <a href="XML">XML</a>. All type\r
139	variables are explicitly bound at either a value or function\r
140	declaration. At some point in the future, exception declarations may\r
141	go away, and exceptions may be represented with a single datatype\r
142	containing a <span class="monospaced">unit ref</span> component to implement genericity.</p></div>\r
143	<div class="paragraph"><p><a href="XML">XML</a> expressions are like those of <a href="CoreML">CoreML</a>, with the following\r
144	exceptions. There are no records expressions. After type inference,\r
145	all records (some of which may have originally been tuples in the\r
146	source) are converted to tuples, because once flexible record patterns\r
147	have been resolved, tuple labels are superfluous. Tuple components\r
148	are ordered based on the field ordering relation. <a href="XML">XML</a> eta expands\r
149	primitives and constructors so that there are always fully applied.\r
150	Hence, the only kind of value of arrow type is a lambda. This\r
151	property is useful for flow analysis and later in code generation.</p></div>\r
152	<div class="paragraph"><p>An <a href="XML">XML</a> program is a list of toplevel datatype declarations and a\r
153	body expression. Because datatype declarations are not generative,\r
154	the defunctorizer can safely move them to toplevel.</p></div>\r
155	</div>\r
156	</div>\r
157	</div>\r
158	</div>\r
159	<div id="footnotes"><hr></div>\r
160	<div id="footer">\r
161	<div id="footer-text">\r
162	</div>\r
163	<div id="footer-badges">\r
164	</div>\r
165	</div>\r
166	</body>\r
167	</html>\r