doc/guide/localhost/MatchCompile

   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>MatchCompile</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>MatchCompile</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="MatchCompile">MatchCompile</a> is a translation pass, agnostic in the
  32 <a href="IntermediateLanguage">IntermediateLanguage</a>s between which it translates.</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><a href="MatchCompilation">Match compilation</a> converts a case expression with
  39 nested patterns into a case expression with flat patterns.</p></div>
  40 </div>
  41 </div>
  42 <div class="sect1">
  43 <h2 id="_implementation">Implementation</h2>
  44 <div class="sectionbody">
  45 <div class="ulist"><ul>
  46 <li>
  47 <p>
  48 <a href="https://github.com/MLton/mlton/blob/master/mlton/match-compile/match-compile.sig"><span class="monospaced">match-compile.sig</span></a>
  49 </p>
  50 </li>
  51 <li>
  52 <p>
  53 <a href="https://github.com/MLton/mlton/blob/master/mlton/match-compile/match-compile.fun"><span class="monospaced">match-compile.fun</span></a>
  54 </p>
  55 </li>
  56 </ul></div>
  57 </div>
  58 </div>
  59 <div class="sect1">
  60 <h2 id="_details_and_notes">Details and Notes</h2>
  61 <div class="sectionbody">
  62 <div class="listingblock">
  63 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">matchCompile</span><span class="p">:</span><span class="w"></span>
  64 <span class="w">   </span><span class="p">{</span><span class="n">caseType</span><span class="p">:</span><span class="w"> </span><span class="n">Type</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="cm">(* type of entire expression *)</span><span class="w"></span>
  65 <span class="w">    </span><span class="n">cases</span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">NestedPat</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">((</span><span class="n">Var</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">Var</span><span class="p">.</span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">))</span><span class="w"> </span><span class="n">vector</span><span class="p">,</span><span class="w"></span>
  66 <span class="w">    </span><span class="n">conTycon</span><span class="p">:</span><span class="w"> </span><span class="n">Con</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">Tycon</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"></span>
  67 <span class="w">    </span><span class="n">region</span><span class="p">:</span><span class="w"> </span><span class="n">Region</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"></span>
  68 <span class="w">    </span><span class="n">test</span><span class="p">:</span><span class="w"> </span><span class="n">Var</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"></span>
  69 <span class="w">    </span><span class="n">testType</span><span class="p">:</span><span class="w"> </span><span class="n">Type</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"></span>
  70 <span class="w">    </span><span class="n">tyconCons</span><span class="p">:</span><span class="w"> </span><span class="n">Tycon</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">{</span><span class="n">con</span><span class="p">:</span><span class="w"> </span><span class="n">Con</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">hasArg</span><span class="p">:</span><span class="w"> </span><span class="n">bool</span><span class="p">}</span><span class="w"> </span><span class="n">vector</span><span class="p">}</span><span class="w"></span>
  71 <span class="w">   </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">Exp</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">unit</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">((</span><span class="n">Layout</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">{</span><span class="n">isOnlyExns</span><span class="p">:</span><span class="w"> </span><span class="n">bool</span><span class="p">})</span><span class="w"> </span><span class="n">vector</span><span class="p">)</span><span class="w"> </span><span class="n">vector</span><span class="p">)</span><span class="w"></span>
  72 </pre></div></div></div>
  73 <div class="paragraph"><p><span class="monospaced">matchCompile</span> is complicated by the desire for modularity between the
  74 match compiler and its caller.  Its caller is responsible for building
  75 the right hand side of a rule <span class="monospaced">p =&gt; e</span>.  On the other hand, the match
  76 compiler is responsible for destructing the test and binding new
  77 variables to the components.  In order to connect the new variables
  78 created by the match compiler with the variables in the pattern <span class="monospaced">p</span>,
  79 the match compiler passes an environment back to its caller that maps
  80 each variable in <span class="monospaced">p</span> to the corresponding variable introduced by the
  81 match compiler.</p></div>
  82 <div class="paragraph"><p>The match compiler builds a tree of n-way case expressions by working
  83 from outside to inside and left to right in the patterns.  For example,</p></div>
  84 <div class="listingblock">
  85 <div class="content"><div class="highlight"><pre><span class="k">case</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  86 <span class="w">  </span><span class="p">(_,</span><span class="w"> </span><span class="n">C1</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e1</span><span class="w"></span>
  87 <span class="p">|</span><span class="w"> </span><span class="p">(</span><span class="n">C2</span><span class="w"> </span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">C3</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>
  88 </pre></div></div></div>
  89 <div class="paragraph"><p>is translated to</p></div>
  90 <div class="listingblock">
  91 <div class="content"><div class="highlight"><pre><span class="k">let</span><span class="w"></span>
  92 <span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">f1</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">e1</span><span class="w"></span>
  93 <span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">f2</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">e2</span><span class="w"></span>
  94 <span class="k">in</span><span class="w"></span>
  95 <span class="w">  </span><span class="k">case</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  96 <span class="w">     </span><span class="p">(</span><span class="n">x1</span><span class="p">,</span><span class="w"> </span><span class="n">x2</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
  97 <span class="w">       </span><span class="p">(</span><span class="k">case</span><span class="w"> </span><span class="n">x1</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  98 <span class="w">          </span><span class="n">C2</span><span class="w"> </span><span class="n">b&#39;</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="k">case</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
  99 <span class="w">                      </span><span class="n">C1</span><span class="w"> </span><span class="n">a&#39;</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">f1</span><span class="w"> </span><span class="n">a&#39;</span><span class="w"></span>
 100 <span class="w">                    </span><span class="p">|</span><span class="w"> </span><span class="n">C3</span><span class="w"> </span><span class="n">c&#39;</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">f2</span><span class="p">(</span><span class="n">b&#39;</span><span class="p">,</span><span class="n">c&#39;</span><span class="p">)</span><span class="w"></span>
 101 <span class="w">                    </span><span class="p">|</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">raise</span><span class="w"> </span><span class="n">Match</span><span class="p">)</span><span class="w"></span>
 102 <span class="w">        </span><span class="p">|</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="k">case</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
 103 <span class="w">                  </span><span class="n">C1</span><span class="w"> </span><span class="n">a_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">f1</span><span class="w"> </span><span class="n">a_</span><span class="w"></span>
 104 <span class="w">                </span><span class="p">|</span><span class="w"> </span><span class="p">_</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">raise</span><span class="w"> </span><span class="n">Match</span><span class="p">))</span><span class="w"></span>
 105 <span class="k">end</span><span class="w"></span>
 106 </pre></div></div></div>
 107 <div class="paragraph"><p>Here you can see the necessity of abstracting out the ride hand sides
 108 of the cases in order to avoid code duplication.  Right hand sides are
 109 always abstracted.  The simplifier cleans things up.  You can also see
 110 the new (primed) variables introduced by the match compiler and how
 111 the renaming works.  Finally, you can see how the match compiler
 112 introduces the necessary default clauses in order to make a match
 113 exhaustive, i.e. cover all the cases.</p></div>
 114 <div class="paragraph"><p>The match compiler uses <span class="monospaced">numCons</span> and <span class="monospaced">tyconCons</span> to determine
 115 the exhaustivity of matches against constructors.</p></div>
 116 </div>
 117 </div>
 118 </div>
 119 <div id="footnotes"><hr></div>
 120 <div id="footer">
 121 <div id="footer-text">
 122 </div>
 123 <div id="footer-badges">
 124 </div>
 125 </div>
 126 </body>
 127 </html>