<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>MatchCompile - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
MatchCompile
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
MatchCompile is a translation pass, agnostic in the <a href="IntermediateLanguage">IntermediateLanguage</a>s between which it translates. <h2 id="head-55f8ebc805e65b5b71ddafdae390e3be2bcd69af">Description</h2>
<p>
<a href="MatchCompilation">Match compilation</a> converts a case expression with nested patterns into a case expression with flat patterns.
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/match-compile/match-compile.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">match-compile.sig</a> <a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-MLTONWIKIVERSION-release/mlton/match-compile/match-compile.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">match-compile.fun</a> <h2 id="head-35ec00231a68203708e39f0e2cc10b50c6bf62de">Details and Notes</h2>
<pre>val matchCompile:
{caseType: Type.t, (* type of entire expression *)
cases: (NestedPat.t * ((Var.t -> Var.t) -> Exp.t)) vector,
conTycon: Con.t -> Tycon.t,
region: Region.t,
test: Var.t,
testType: Type.t,
tyconCons: Tycon.t -> {con: Con.t, hasArg: bool} vector}
-> Exp.t * (unit -> ((Layout.t * {isOnlyExns: bool}) vector) vector)
</pre><p>
<tt>matchCompile</tt> is complicated by the desire for modularity between the match compiler and its caller. Its caller is responsible for building the right hand side of a rule <tt>p => e</tt>. On the other hand, the match compiler is responsible for destructing the test and binding new variables to the components. In order to connect the new variables created by the match compiler with the variables in the pattern <tt>p</tt>, the match compiler passes an environment back to its caller that maps each variable in <tt>p</tt> to the corresponding variable introduced by the match compiler.
</p>
<p>
The match compiler builds a tree of n-way case expressions by working from outside to inside and left to right in the patterns. For example,
<pre>case x of
(_, C1 a) => e1
| (C2 b, C3 c) => e2
</pre>is translated to
<pre>let
fun f1 a = e1
fun f2 (b, c) = e2
in
case x of
(x1, x2) =>
(case x1 of
C2 b' => (case x2 of
C1 a' => f1 a'
| C3 c' => f2(b',c')
| _ => raise Match)
| _ => (case x2 of
C1 a'' => f1 a''
| _ => raise Match))
end
</pre>
</p>
<p>
Here you can see the necessity of abstracting out the ride hand sides of the cases in order to avoid code duplication. Right hand sides are always abstracted. The simplifier cleans things up. You can also see the new (primed) variables introduced by the match compiler and how the renaming works. Finally, you can see how the match compiler introduces the necessary default clauses in order to make a match exhaustive, i.e. cover all the cases.
</p>
<p>
The match compiler uses <tt>numCons</tt> and <tt>tyconCons</tt> to determine the exhaustivity of matches against constructors.
</p>
</div>
<p>
<hr>
Last edited on 2006-11-02 17:35:55 by <span title="76.16.241.4"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
