<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 10.1.1">
<title>AST</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 20210117+dfsg-3</a>
</div>
</div>
<div id="header">
<h1>AST</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p><a href="AST">AST</a> is the <a href="IntermediateLanguage">IntermediateLanguage</a> produced by the <a href="FrontEnd">FrontEnd</a>
and translated by <a href="Elaborate">Elaborate</a> to <a href="CoreML">CoreML</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_description">Description</h2>
<div class="sectionbody">
<div class="paragraph"><p>The abstract syntax tree produced by the <a href="FrontEnd">FrontEnd</a>.</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/ast/ast-programs.sig"><span class="monospaced">ast-programs.sig</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ast/ast-programs.fun"><span class="monospaced">ast-programs.fun</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ast/ast-modules.sig"><span class="monospaced">ast-modules.sig</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ast/ast-modules.fun"><span class="monospaced">ast-modules.fun</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.sig"><span class="monospaced">ast-core.sig</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/blob/master/mlton/ast/ast-core.fun"><span class="monospaced">ast-core.fun</span></a>
</p>
</li>
<li>
<p>
<a href="https://github.com/MLton/mlton/tree/master/mlton/ast"><span class="monospaced">ast</span></a>
</p>
</li>
</ul></div>
</div>
</div>
<div class="sect1">
<h2 id="_type_checking">Type Checking</h2>
<div class="sectionbody">
<div class="paragraph"><p>The <a href="AST">AST</a> <a href="IntermediateLanguage">IntermediateLanguage</a> has no independent type
checker. Type inference is performed on an AST program as part of
<a href="Elaborate">Elaborate</a>.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_details_and_notes">Details and Notes</h2>
<div class="sectionbody">
<div class="sect2">
<h3 id="_source_locations">Source locations</h3>
<div class="paragraph"><p>MLton makes use of a relatively clean method for annotating the
abstract syntax tree with source location information.  Every source
program phrase is "wrapped" with the <span class="monospaced">WRAPPED</span> interface:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="cm">(* Copyright (C) 1999-2005 Henry Cejtin, Matthew Fluet, Suresh</span>
<span class="cm"> *    Jagannathan, and Stephen Weeks.</span>
<span class="cm"> * Copyright (C) 1997-2000 NEC Research Institute.</span>
<span class="cm"> *</span>
<span class="cm"> * MLton is released under a HPND-style license.</span>
<span class="cm"> * See the file MLton-LICENSE for details.</span>
<span class="cm"> *)</span>

<span class="kr">signature</span> <span class="nn">WRAPPED</span> <span class="p">=</span>
   <span class="kr">sig</span>
      <span class="kr">type</span> <span class="kt">node&#39;</span>
      <span class="kr">type</span> <span class="kt">obj</span>

      <span class="kr">val</span> <span class="nv">dest</span><span class="p">:</span> <span class="n">obj</span> <span class="p">-&gt;</span> <span class="n">node&#39;</span> <span class="n">*</span> <span class="nn">Region</span><span class="p">.</span><span class="n">t</span>
      <span class="kr">val</span> <span class="nv">makeRegion&#39;</span><span class="p">:</span> <span class="n">node&#39;</span> <span class="n">*</span> <span class="nn">SourcePos</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">SourcePos</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">obj</span>
      <span class="kr">val</span> <span class="nv">makeRegion</span><span class="p">:</span> <span class="n">node&#39;</span> <span class="n">*</span> <span class="nn">Region</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">obj</span>
      <span class="kr">val</span> <span class="nv">node</span><span class="p">:</span> <span class="n">obj</span> <span class="p">-&gt;</span> <span class="n">node&#39;</span>
      <span class="kr">val</span> <span class="nv">region</span><span class="p">:</span> <span class="n">obj</span> <span class="p">-&gt;</span> <span class="nn">Region</span><span class="p">.</span><span class="n">t</span>
   <span class="kr">end</span>
</pre></div></div></div>
<div class="paragraph"><p>The key idea is that <span class="monospaced">node'</span> is the type of an unannotated syntax
phrase and <span class="monospaced">obj</span> is the type of its annotated counterpart. In the
implementation, every <span class="monospaced">node'</span> is annotated with a <span class="monospaced">Region.t</span>
(<a href="https://github.com/MLton/mlton/blob/master/mlton/control/region.sig"><span class="monospaced">region.sig</span></a>,
<a href="https://github.com/MLton/mlton/blob/master/mlton/control/region.sml"><span class="monospaced">region.sml</span></a>), which describes the
syntax phrase&#8217;s left source position and right source position, where
<span class="monospaced">SourcePos.t</span> (<a href="https://github.com/MLton/mlton/blob/master/mlton/control/source-pos.sig"><span class="monospaced">source-pos.sig</span></a>,
<a href="https://github.com/MLton/mlton/blob/master/mlton/control/source-pos.sml"><span class="monospaced">source-pos.sml</span></a>) denotes a
particular file, line, and column.  A typical use of the <span class="monospaced">WRAPPED</span>
interface is illustrated by the following code:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="cm">(* Copyright (C) 2009,2012,2015,2017,2019 Matthew Fluet.</span>
<span class="cm"> * Copyright (C) 1999-2008 Henry Cejtin, Matthew Fluet, Suresh</span>
<span class="cm"> *    Jagannathan, and Stephen Weeks.</span>
<span class="cm"> * Copyright (C) 1997-2000 NEC Research Institute.</span>
<span class="cm"> *</span>
<span class="cm"> * MLton is released under a HPND-style license.</span>
<span class="cm"> * See the file MLton-LICENSE for details.</span>
<span class="cm"> *)</span>

<span class="kr">signature</span> <span class="nn">AST_CORE_STRUCTS</span> <span class="p">=</span>
   <span class="kr">sig</span>
      <span class="kr">include</span> <span class="nn">AST_ATOMS</span>
   <span class="kr">end</span>

<span class="kr">signature</span> <span class="nn">AST_CORE</span> <span class="p">=</span>
   <span class="kr">sig</span>
      <span class="kr">include</span> <span class="nn">AST_CORE_STRUCTS</span>

      <span class="kr">structure</span> <span class="nn">Fixity</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span>
               <span class="nc">Infix</span> <span class="kr">of</span> <span class="n">int</span> <span class="n">option</span>
             <span class="p">|</span> <span class="nc">Infixr</span> <span class="kr">of</span> <span class="n">int</span> <span class="n">option</span>
             <span class="p">|</span> <span class="nc">Nonfix</span>
            <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Fixop</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span> <span class="nc">Op</span> <span class="p">|</span> <span class="nc">None</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Pat</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">type</span> <span class="kt">t</span>

            <span class="kr">structure</span> <span class="nn">Item</span><span class="p">:</span>
               <span class="kr">sig</span>
                  <span class="kr">type</span> <span class="kt">pat</span>
                  <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span>
                     <span class="nc">Field</span> <span class="kr">of</span> <span class="n">pat</span>
                   <span class="p">|</span> <span class="nc">Vid</span> <span class="kr">of</span> <span class="nn">Vid</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span> <span class="n">*</span> <span class="n">pat</span> <span class="n">option</span>
                     <span class="cm">(* vid &lt;:ty&gt; &lt;as pat&gt; *)</span>
               <span class="kr">end</span>
            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">Item</span><span class="err">.pat</span> <span class="p">=</span> <span class="n">t</span>

            <span class="kr">datatype</span> <span class="kt">node</span> <span class="p">=</span>
               <span class="nc">App</span> <span class="kr">of</span> <span class="nn">Longcon</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Const</span> <span class="kr">of</span> <span class="nn">Const</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Constraint</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">FlatApp</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Layered</span> <span class="kr">of</span> <span class="p">{</span><span class="n">constraint</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span><span class="p">,</span>
                           <span class="n">fixop</span><span class="p">:</span> <span class="nn">Fixop</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                           <span class="n">pat</span><span class="p">:</span> <span class="n">t</span><span class="p">,</span>
                           <span class="n">var</span><span class="p">:</span> <span class="nn">Var</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">List</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Paren</span> <span class="kr">of</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Or</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Record</span> <span class="kr">of</span> <span class="p">{</span><span class="n">flexible</span><span class="p">:</span> <span class="n">bool</span><span class="p">,</span>
                          <span class="n">items</span><span class="p">:</span> <span class="p">(</span><span class="nn">Record</span><span class="p">.</span><span class="nn">Field</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Region</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Item</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Tuple</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Var</span> <span class="kr">of</span> <span class="p">{</span><span class="n">fixop</span><span class="p">:</span> <span class="nn">Fixop</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                       <span class="n">name</span><span class="p">:</span> <span class="nn">Longvid</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Vector</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Wild</span>

            <span class="kr">include</span> <span class="nn">WRAPPED</span> <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">node&#39;</span> <span class="p">=</span> <span class="n">node</span>
                            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">obj</span> <span class="p">=</span> <span class="n">t</span>

            <span class="kr">val</span> <span class="nv">constraint</span><span class="p">:</span> <span class="n">t</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layered</span><span class="p">:</span> <span class="p">{</span><span class="n">fixop</span><span class="p">:</span> <span class="nn">Fixop</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                          <span class="n">var</span><span class="p">:</span> <span class="nn">Var</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                          <span class="n">constraint</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span><span class="p">,</span>
                          <span class="n">pat</span><span class="p">:</span> <span class="n">t</span><span class="p">}</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layoutFlatApp</span><span class="p">:</span> <span class="n">t</span> <span class="n">vector</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
            <span class="kr">val</span> <span class="nv">longvid</span><span class="p">:</span> <span class="nn">Longvid</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">tuple</span><span class="p">:</span> <span class="n">t</span> <span class="n">vector</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">var</span><span class="p">:</span> <span class="nn">Var</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">wild</span><span class="p">:</span> <span class="n">t</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">PrimKind</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">structure</span> <span class="nn">ImportExportAttribute</span><span class="p">:</span>
               <span class="kr">sig</span>
                  <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span> <span class="nc">Cdecl</span> <span class="p">|</span> <span class="nc">External</span> <span class="p">|</span> <span class="nc">Impure</span> <span class="p">|</span> <span class="nc">Inline</span> <span class="p">|</span> <span class="nc">Private</span> <span class="p">|</span> <span class="nc">Public</span> <span class="p">|</span> <span class="nc">Pure</span> <span class="p">|</span> <span class="nc">Reentrant</span> <span class="p">|</span> <span class="nc">Runtime</span> <span class="p">|</span> <span class="nc">Stdcall</span>

                  <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
               <span class="kr">end</span>

            <span class="kr">structure</span> <span class="nn">SymbolAttribute</span><span class="p">:</span>
               <span class="kr">sig</span>
                  <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span> <span class="nc">Alloc</span> <span class="p">|</span> <span class="nc">External</span> <span class="p">|</span> <span class="nc">Private</span> <span class="p">|</span> <span class="nc">Public</span>

                  <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
               <span class="kr">end</span>

            <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span>
               <span class="nc">Address</span> <span class="kr">of</span> <span class="p">{</span><span class="n">attributes</span><span class="p">:</span> <span class="nn">SymbolAttribute</span><span class="p">.</span><span class="n">t</span> <span class="n">list</span><span class="p">,</span>
                           <span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                           <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">BuildConst</span> <span class="kr">of</span> <span class="p">{</span><span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                              <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">CommandLineConst</span> <span class="kr">of</span> <span class="p">{</span><span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                                    <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                                    <span class="n">value</span><span class="p">:</span> <span class="nn">Const</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Const</span> <span class="kr">of</span> <span class="p">{</span><span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                         <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Export</span> <span class="kr">of</span> <span class="p">{</span><span class="n">attributes</span><span class="p">:</span> <span class="nn">ImportExportAttribute</span><span class="p">.</span><span class="n">t</span> <span class="n">list</span><span class="p">,</span>
                          <span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                          <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">IImport</span> <span class="kr">of</span> <span class="p">{</span><span class="n">attributes</span><span class="p">:</span> <span class="nn">ImportExportAttribute</span><span class="p">.</span><span class="n">t</span> <span class="n">list</span><span class="p">,</span>
                           <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Import</span> <span class="kr">of</span> <span class="p">{</span><span class="n">attributes</span><span class="p">:</span> <span class="nn">ImportExportAttribute</span><span class="p">.</span><span class="n">t</span> <span class="n">list</span><span class="p">,</span>
                          <span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                          <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">ISymbol</span> <span class="kr">of</span> <span class="p">{</span><span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Prim</span> <span class="kr">of</span> <span class="p">{</span><span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                        <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Symbol</span> <span class="kr">of</span> <span class="p">{</span><span class="n">attributes</span><span class="p">:</span> <span class="nn">SymbolAttribute</span><span class="p">.</span><span class="n">t</span> <span class="n">list</span><span class="p">,</span>
                          <span class="n">name</span><span class="p">:</span> <span class="n">string</span><span class="p">,</span>
                          <span class="n">ty</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Priority</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">datatype</span> <span class="kt">t</span> <span class="p">=</span> <span class="nc">T</span> <span class="kr">of</span> <span class="n">int</span> <span class="n">option</span>
            <span class="kr">val</span> <span class="nv">&lt;</span><span class="p">=</span> <span class="p">:</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="n">bool</span>
            <span class="kr">val</span> <span class="nv">default</span><span class="p">:</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Exp</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">type</span> <span class="kt">dec</span>
            <span class="kr">type</span> <span class="kt">match</span>
            <span class="kr">type</span> <span class="kt">t</span>
            <span class="kr">datatype</span> <span class="kt">node</span> <span class="p">=</span>
               <span class="nc">Andalso</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">App</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Case</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">match</span>
             <span class="p">|</span> <span class="nc">Const</span> <span class="kr">of</span> <span class="nn">Const</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Constraint</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">FlatApp</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Fn</span> <span class="kr">of</span> <span class="n">match</span>
             <span class="p">|</span> <span class="nc">Handle</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">match</span>
             <span class="p">|</span> <span class="nc">If</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Let</span> <span class="kr">of</span> <span class="n">dec</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">List</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Orelse</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Paren</span> <span class="kr">of</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Prim</span> <span class="kr">of</span> <span class="nn">PrimKind</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Raise</span> <span class="kr">of</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Record</span> <span class="kr">of</span> <span class="p">(</span><span class="nn">Region</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="n">t</span><span class="p">)</span> <span class="nn">Record</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Selector</span> <span class="kr">of</span> <span class="nn">Record</span><span class="p">.</span><span class="nn">Field</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Seq</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Var</span> <span class="kr">of</span> <span class="p">{</span><span class="n">fixop</span><span class="p">:</span> <span class="nn">Fixop</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                       <span class="n">name</span><span class="p">:</span> <span class="nn">Longvid</span><span class="p">.</span><span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Vector</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">While</span> <span class="kr">of</span> <span class="p">{</span><span class="n">expr</span><span class="p">:</span> <span class="n">t</span><span class="p">,</span>
                         <span class="n">test</span><span class="p">:</span> <span class="n">t</span><span class="p">}</span>

            <span class="kr">include</span> <span class="nn">WRAPPED</span> <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">node&#39;</span> <span class="p">=</span> <span class="n">node</span>
                            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">obj</span> <span class="p">=</span> <span class="n">t</span>

            <span class="kr">val</span> <span class="nv">app</span><span class="p">:</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">const</span><span class="p">:</span> <span class="nn">Const</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">constraint</span><span class="p">:</span> <span class="n">t</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">fnn</span><span class="p">:</span> <span class="p">(</span><span class="nn">Pat</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="n">t</span><span class="p">)</span> <span class="n">vector</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
            <span class="kr">val</span> <span class="nv">lett</span><span class="p">:</span> <span class="n">dec</span> <span class="n">vector</span> <span class="n">*</span> <span class="n">t</span> <span class="n">*</span> <span class="nn">Region</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">longvid</span><span class="p">:</span> <span class="nn">Longvid</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">tuple</span><span class="p">:</span> <span class="n">t</span> <span class="n">vector</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">unit</span><span class="p">:</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">var</span><span class="p">:</span> <span class="nn">Var</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Match</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">type</span> <span class="kt">t</span>
            <span class="kr">datatype</span> <span class="kt">node</span> <span class="p">=</span> <span class="nc">T</span> <span class="kr">of</span> <span class="p">(</span><span class="nn">Pat</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span>
            <span class="kr">include</span> <span class="nn">WRAPPED</span> <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">node&#39;</span> <span class="p">=</span> <span class="n">node</span>
                            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">obj</span> <span class="p">=</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layout</span> <span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layoutRule</span> <span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
         <span class="kr">end</span>
      <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">Exp</span><span class="err">.match</span>  <span class="p">=</span> <span class="nn">Match</span><span class="p">.</span><span class="n">t</span>

      <span class="kr">structure</span> <span class="nn">EbRhs</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">type</span> <span class="kt">t</span>
            <span class="kr">datatype</span> <span class="kt">node</span> <span class="p">=</span>
               <span class="nc">Def</span> <span class="kr">of</span> <span class="nn">Longcon</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Gen</span> <span class="kr">of</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span>
            <span class="kr">include</span> <span class="nn">WRAPPED</span> <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">node&#39;</span> <span class="p">=</span> <span class="n">node</span>
                            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">obj</span> <span class="p">=</span> <span class="n">t</span>
         <span class="kr">end</span>

      <span class="kr">structure</span> <span class="nn">Dec</span><span class="p">:</span>
         <span class="kr">sig</span>
            <span class="kr">type</span> <span class="kt">t</span>
            <span class="kr">datatype</span> <span class="kt">node</span> <span class="p">=</span>
               <span class="nc">Abstype</span> <span class="kr">of</span> <span class="p">{</span><span class="n">datBind</span><span class="p">:</span> <span class="nn">DatBind</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                           <span class="n">body</span><span class="p">:</span> <span class="n">t</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Datatype</span> <span class="kr">of</span> <span class="nn">DatatypeRhs</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">DoDec</span> <span class="kr">of</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Exception</span> <span class="kr">of</span> <span class="p">(</span><span class="nn">Con</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">EbRhs</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Fix</span> <span class="kr">of</span> <span class="p">{</span><span class="n">fixity</span><span class="p">:</span> <span class="nn">Fixity</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                       <span class="n">ops</span><span class="p">:</span> <span class="nn">Vid</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Fun</span> <span class="kr">of</span> <span class="p">{</span><span class="n">tyvars</span><span class="p">:</span> <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                       <span class="n">fbs</span><span class="p">:</span> <span class="p">{</span><span class="n">body</span><span class="p">:</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                             <span class="n">pats</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                             <span class="n">resultType</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span><span class="p">}</span> <span class="n">vector</span> <span class="n">vector</span><span class="p">}</span>
             <span class="p">|</span> <span class="nc">Local</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">*</span> <span class="n">t</span>
             <span class="p">|</span> <span class="nc">Open</span> <span class="kr">of</span> <span class="nn">Longstrid</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Overload</span> <span class="kr">of</span> <span class="nn">Priority</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span>
                           <span class="nn">Var</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span>
                           <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span> <span class="n">*</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span>
                           <span class="nn">Longvid</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">SeqDec</span> <span class="kr">of</span> <span class="n">t</span> <span class="n">vector</span>
             <span class="p">|</span> <span class="nc">Type</span> <span class="kr">of</span> <span class="nn">TypBind</span><span class="p">.</span><span class="n">t</span>
             <span class="p">|</span> <span class="nc">Val</span> <span class="kr">of</span> <span class="p">{</span><span class="n">rvbs</span><span class="p">:</span> <span class="p">{</span><span class="n">match</span><span class="p">:</span> <span class="nn">Match</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                              <span class="n">pat</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span><span class="p">}</span> <span class="n">vector</span><span class="p">,</span>
                       <span class="n">tyvars</span><span class="p">:</span> <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                       <span class="n">vbs</span><span class="p">:</span> <span class="p">{</span><span class="n">exp</span><span class="p">:</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                             <span class="n">pat</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span><span class="p">}</span> <span class="n">vector</span><span class="p">}</span>
            <span class="kr">include</span> <span class="nn">WRAPPED</span> <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">node&#39;</span> <span class="p">=</span> <span class="n">node</span>
                            <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">obj</span> <span class="p">=</span> <span class="n">t</span>

            <span class="kr">val</span> <span class="nv">checkSyntax</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="n">unit</span>
            <span class="kr">val</span> <span class="nv">fromExp</span><span class="p">:</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layout</span><span class="p">:</span> <span class="n">t</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span>
            <span class="kr">val</span> <span class="nv">layoutFun</span><span class="p">:</span>
               <span class="p">{</span><span class="n">tyvars</span><span class="p">:</span> <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                <span class="n">fbs</span><span class="p">:</span> <span class="p">{</span><span class="n">body</span><span class="p">:</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                      <span class="n">pats</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                      <span class="n">resultType</span><span class="p">:</span> <span class="nn">Type</span><span class="p">.</span><span class="n">t</span> <span class="n">option</span><span class="p">}</span> <span class="n">vector</span> <span class="n">vector</span><span class="p">}</span>
               <span class="p">-&gt;</span> <span class="p">(</span><span class="n">unit</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span>
            <span class="kr">val</span> <span class="nv">layoutVal</span><span class="p">:</span>
               <span class="p">{</span><span class="n">rvbs</span><span class="p">:</span> <span class="p">{</span><span class="n">match</span><span class="p">:</span> <span class="nn">Match</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                       <span class="n">pat</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span><span class="p">}</span> <span class="n">vector</span><span class="p">,</span>
                <span class="n">tyvars</span><span class="p">:</span> <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span><span class="p">,</span>
                <span class="n">vbs</span><span class="p">:</span> <span class="p">{</span><span class="n">exp</span><span class="p">:</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span><span class="p">,</span>
                      <span class="n">pat</span><span class="p">:</span> <span class="nn">Pat</span><span class="p">.</span><span class="n">t</span><span class="p">}</span> <span class="n">vector</span><span class="p">}</span>
               <span class="p">-&gt;</span> <span class="p">{</span><span class="n">rvbs</span><span class="p">:</span> <span class="p">(</span><span class="n">unit</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span><span class="p">,</span>
                   <span class="n">vbs</span><span class="p">:</span> <span class="p">(</span><span class="n">unit</span> <span class="p">-&gt;</span> <span class="nn">Layout</span><span class="p">.</span><span class="n">t</span><span class="p">)</span> <span class="n">vector</span><span class="p">}</span>
            <span class="kr">val</span> <span class="nv">openn</span><span class="p">:</span> <span class="nn">Longstrid</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span> <span class="p">-&gt;</span> <span class="n">t</span>
            <span class="kr">val</span> <span class="nv">vall</span><span class="p">:</span> <span class="nn">Tyvar</span><span class="p">.</span><span class="n">t</span> <span class="n">vector</span> <span class="n">*</span> <span class="nn">Var</span><span class="p">.</span><span class="n">t</span> <span class="n">*</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">t</span> <span class="p">-&gt;</span> <span class="n">t</span>
         <span class="kr">end</span>
      <span class="kr">sharing</span> <span class="kr">type</span> <span class="kt">Dec</span><span class="err">.t</span> <span class="p">=</span> <span class="nn">Exp</span><span class="p">.</span><span class="n">dec</span>
   <span class="kr">end</span>
</pre></div></div></div>
<div class="paragraph"><p>Thus, AST nodes are cleanly separated from source locations.  By way
of contrast, consider the approach taken by <a href="SMLNJ">SML/NJ</a> (and also
by the <a href="CKitLibrary">CKit Library</a>).  Each datatype denoting a syntax
phrase dedicates a special constructor for annotating source
locations:</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span></span><span class="kr">datatype</span> <span class="kt">pat</span> <span class="p">=</span> <span class="nc">WildPat</span>                             <span class="cm">(* empty pattern *)</span>
             <span class="p">|</span> <span class="nc">AppPat</span> <span class="kr">of</span> <span class="p">{</span><span class="n">constr</span><span class="p">:</span><span class="n">pat</span><span class="p">,</span><span class="n">argument</span><span class="p">:</span><span class="n">pat</span><span class="p">}</span> <span class="cm">(* application *)</span>
             <span class="p">|</span> <span class="nc">MarkPat</span> <span class="kr">of</span> <span class="n">pat</span> <span class="n">*</span> <span class="n">region</span>             <span class="cm">(* mark a pattern *)</span>
</pre></div></div></div>
<div class="paragraph"><p>The main drawback of this approach is that static type checking is not
sufficient to guarantee that the AST emitted from the front-end is
properly annotated.</p></div>
</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>
