doc/guide/localhost/TypeIndexedValues

   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>TypeIndexedValues</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>TypeIndexedValues</h1>
  27 </div>
  28 <div id="content">
  29 <div id="preamble">
  30 <div class="sectionbody">
  31 <div class="paragraph"><p><a href="StandardML">Standard ML</a> does not support ad hoc polymorphism.  This
  32 presents a challenge to programmers.  The problem is that at first
  33 glance there seems to be no practical way to implement something like
  34 a function for converting a value of any type to a string or a
  35 function for computing a hash value for a value of any type.
  36 Fortunately there are ways to implement type-indexed values in SML as
  37 discussed in <a href="References#Yang98">Yang98</a>.  Various articles such as
  38 <a href="References#Danvy98">Danvy98</a>, <a href="References#Ramsey11">Ramsey11</a>, <a href="References#Elsman04">Elsman04</a>,
  39 <a href="References#Kennedy04">Kennedy04</a>, and <a href="References#Benton05">Benton05</a> also contain examples of
  40 type-indexed values.</p></div>
  41 <div class="paragraph"><p><strong>NOTE:</strong> The technique used in the following example uses an early (and
  42 somewhat broken) variation of the basic technique used in an
  43 experimental generic programming library (see
  44 <a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/generic/unstable/README"><span class="monospaced">README</span></a>) that can
  45 be found from the MLton repository.  The generic programming library
  46 also includes a more advanced generic pretty printing function (see
  47 <a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/generic/unstable/public/value/pretty.sig"><span class="monospaced">pretty.sig</span></a>).</p></div>
  48 </div>
  49 </div>
  50 <div class="sect1">
  51 <h2 id="_example_converting_any_sml_value_to_roughly_sml_syntax">Example: Converting any SML value to (roughly) SML syntax</h2>
  52 <div class="sectionbody">
  53 <div class="paragraph"><p>Consider the problem of converting any SML value to a textual
  54 presentation that matches the syntax of SML as closely as possible.
  55 One solution is a type-indexed function that maps a given type to a
  56 function that maps any value (of the type) to its textual
  57 presentation.  A type-indexed function like this can be useful for a
  58 variety of purposes.  For example, one could use it to show debugging
  59 information.  We&#8217;ll call this function "<span class="monospaced">show</span>".</p></div>
  60 <div class="paragraph"><p>We&#8217;ll do a fairly complete implementation of <span class="monospaced">show</span>.  We do not
  61 distinguish infix and nonfix constructors, but that is not an
  62 intrinsic property of SML datatypes.  We also don&#8217;t reconstruct a type
  63 name for the value, although it would be particularly useful for
  64 functional values.  To reconstruct type names, some changes would be
  65 needed and the reader is encouraged to consider how to do that.  A
  66 more realistic implementation would use some pretty printing
  67 combinators to compute a layout for the result.  This should be a
  68 relatively easy change (given a suitable pretty printing library).
  69 Cyclic values (through references and arrays) do not have a standard
  70 textual presentation and it is impossible to convert arbitrary
  71 functional values (within SML) to a meaningful textual presentation.
  72 Finally, it would also make sense to show sharing of references and
  73 arrays.  We&#8217;ll leave these improvements to an actual library
  74 implementation.</p></div>
  75 <div class="paragraph"><p>The following code uses the <a href="Fixpoints">fixpoint framework</a> and other
  76 utilities from an Extended Basis library (see
  77 <a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/extended-basis/unstable/README"><span class="monospaced">README</span></a>).</p></div>
  78 <div class="sect2">
  79 <h3 id="_signature">Signature</h3>
  80 <div class="paragraph"><p>Let&#8217;s consider the design of the <span class="monospaced">SHOW</span> signature:</p></div>
  81 <div class="listingblock">
  82 <div class="content"><div class="highlight"><pre><span class="k">infixr</span><span class="w"> </span><span class="n">--&gt;</span><span class="w"></span>
  83
  84 <span class="k">signature</span><span class="w"> </span><span class="n">SHOW</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">sig</span><span class="w"></span>
  85 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w">       </span><span class="cm">(* complete type-index *)</span><span class="w"></span>
  86 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w">       </span><span class="cm">(* incomplete sum *)</span><span class="w"></span>
  87 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="cm">(* incomplete product *)</span><span class="w"></span>
  88 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">u</span><span class="w">          </span><span class="cm">(* tuple or unlabelled product *)</span><span class="w"></span>
  89 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">l</span><span class="w">          </span><span class="cm">(* record or labelled product *)</span><span class="w"></span>
  90
  91 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">string</span><span class="w"></span>
  92
  93 <span class="w">   </span><span class="cm">(* user-defined types *)</span><span class="w"></span>
  94 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">inj</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
  95
  96 <span class="w">   </span><span class="cm">(* tuples and records *)</span><span class="w"></span>
  97 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;b</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">((</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">product</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>
  98
  99 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">U</span><span class="w"> </span><span class="p">:</span><span class="w">           </span><span class="n">&#39;a</span><span class="w"> </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">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">u</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>
 100 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">L</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </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">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>
 101
 102 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">tuple</span><span class="w">  </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">u</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 103 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">record</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 104
 105 <span class="w">   </span><span class="cm">(* datatypes *)</span><span class="w"></span>
 106 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">((</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">sum</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 107
 108 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">C0</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 109 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">C1</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 110
 111 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 112
 113 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">Y</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">Tie</span><span class="p">.</span><span class="n">t</span><span class="w"></span>
 114
 115 <span class="w">   </span><span class="cm">(* exceptions *)</span><span class="w"></span>
 116 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 117 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">regExn</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">exn</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="n">option</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 118
 119 <span class="w">   </span><span class="cm">(* some built-in type constructors *)</span><span class="w"></span>
 120 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">refc</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 121 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 122 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 123 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">vector</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">vector</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 124 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">--&gt;</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </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">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 125
 126 <span class="w">   </span><span class="cm">(* some built-in base types *)</span><span class="w"></span>
 127 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 128 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 129 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 130 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">char</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">char</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 131 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 132 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">word</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">word</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 133 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 134 <span class="k">end</span><span class="w"></span>
 135 </pre></div></div></div>
 136 <div class="paragraph"><p>While some details are shaped by the specific requirements of <span class="monospaced">show</span>,
 137 there are a number of (design) patterns that translate to other
 138 type-indexed values.  The former kind of details are mostly shaped by
 139 the syntax of SML values that <span class="monospaced">show</span> is designed to produce.  To this
 140 end, abstract types and phantom types are used to distinguish
 141 incomplete record, tuple, and datatype type-indices from each other
 142 and from complete type-indices.  Also, names of record labels and
 143 datatype constructors need to be provided by the user.</p></div>
 144 <div class="sect3">
 145 <h4 id="_arbitrary_user_defined_datatypes">Arbitrary user-defined datatypes</h4>
 146 <div class="paragraph"><p>Perhaps the most important pattern is how the design supports
 147 arbitrary user-defined datatypes.  A number of combinators together
 148 conspire to provide the functionality.  First of all, to support new
 149 user-defined types, a combinator taking a conversion function to a
 150 previously supported type is provided:</p></div>
 151 <div class="listingblock">
 152 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">inj</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 153 </pre></div></div></div>
 154 <div class="paragraph"><p>An injection function is sufficient in this case, but in the general
 155 case, an embedding with injection and projection functions may be
 156 needed.</p></div>
 157 <div class="paragraph"><p>To support products (tuples and records) a product combinator is
 158 provided:</p></div>
 159 <div class="listingblock">
 160 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;b</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">((</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">product</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>
 161 </pre></div></div></div>
 162 <div class="paragraph"><p>The second (phantom) type variable <span class="monospaced">'k</span> is there to distinguish
 163 between labelled and unlabelled products and the type <span class="monospaced">p</span>
 164 distinguishes incomplete products from complete type-indices of type
 165 <span class="monospaced">t</span>.  Most type-indexed values do not need to make such distinctions.</p></div>
 166 <div class="paragraph"><p>To support sums (datatypes) a sum combinator is provided:</p></div>
 167 <div class="listingblock">
 168 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;b</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">((</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;b</span><span class="p">)</span><span class="w"> </span><span class="n">sum</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 169 </pre></div></div></div>
 170 <div class="paragraph"><p>Again, the purpose of the type <span class="monospaced">s</span> is to distinguish incomplete sums
 171 from complete type-indices of type <span class="monospaced">t</span>, which usually isn&#8217;t necessary.</p></div>
 172 <div class="paragraph"><p>Finally, to support recursive datatypes, including sets of mutually
 173 recursive datatypes, a <a href="Fixpoints">fixpoint tier</a> is provided:</p></div>
 174 <div class="listingblock">
 175 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">Y</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">Tie</span><span class="p">.</span><span class="n">t</span><span class="w"></span>
 176 </pre></div></div></div>
 177 <div class="paragraph"><p>Together these combinators (with the more domain specific combinators
 178 <span class="monospaced">U</span>, <span class="monospaced">L</span>, <span class="monospaced">tuple</span>, <span class="monospaced">record</span>, <span class="monospaced">C0</span>, <span class="monospaced">C1</span>, and <span class="monospaced">data</span>) enable one to
 179 encode a type-index for any user-defined datatype.</p></div>
 180 </div>
 181 <div class="sect3">
 182 <h4 id="_exceptions">Exceptions</h4>
 183 <div class="paragraph"><p>The <span class="monospaced">exn</span> type in SML is a <a href="UniversalType">universal type</a> into which
 184 all types can be embedded.  SML also allows a program to generate new
 185 exception variants at run-time.  Thus a mechanism is required to register
 186 handlers for particular variants:</p></div>
 187 <div class="listingblock">
 188 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 189 <span class="k">val</span><span class="w"> </span><span class="n">regExn</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">exn</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="n">option</span><span class="p">)</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 190 </pre></div></div></div>
 191 <div class="paragraph"><p>The universal <span class="monospaced">exn</span> type-index then makes use of the registered
 192 handlers.  The above particular form of handler, which converts an
 193 exception value to a value of some type and a type-index for that type
 194 (essentially an existential type) is designed to make it convenient to
 195 write handlers.  To write a handler, one can conveniently reuse
 196 existing type-indices:</p></div>
 197 <div class="listingblock">
 198 <div class="content"><div class="highlight"><pre><span class="k">exception</span><span class="w"> </span><span class="n">Int</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">int</span><span class="w"></span>
 199
 200 <span class="k">local</span><span class="w"></span>
 201 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 202 <span class="k">in</span><span class="w"></span>
 203 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">regExn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">Int</span><span class="w"> </span><span class="n">v</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;Int&quot;</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"></span>
 204 <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="n">NONE</span><span class="p">)</span><span class="w"></span>
 205 <span class="k">end</span><span class="w"></span>
 206 </pre></div></div></div>
 207 <div class="paragraph"><p>Note that a single handler may actually handle an arbitrary number of
 208 different exceptions.</p></div>
 209 </div>
 210 <div class="sect3">
 211 <h4 id="_other_types">Other types</h4>
 212 <div class="paragraph"><p>Some built-in and standard types typically require special treatment
 213 due to their special nature.  The most important of these are arrays
 214 and references, because cyclic data (ignoring closures) and observable
 215 sharing can only be constructed through them.</p></div>
 216 <div class="paragraph"><p>When arrow types are really supported, unlike in this case, they
 217 usually need special treatment due to the contravariance of arguments.</p></div>
 218 <div class="paragraph"><p>Lists and vectors require special treatment in the case of <span class="monospaced">show</span>,
 219 because of their special syntax.  This isn&#8217;t usually the case.</p></div>
 220 <div class="paragraph"><p>The set of base types to support also needs to be considered unless
 221 one exports an interface for constructing type-indices for entirely
 222 new base types.</p></div>
 223 </div>
 224 </div>
 225 </div>
 226 </div>
 227 <div class="sect1">
 228 <h2 id="_usage">Usage</h2>
 229 <div class="sectionbody">
 230 <div class="paragraph"><p>Before going to the implementation, let&#8217;s look at some examples.  For
 231 the following examples, we&#8217;ll assume a structure binding
 232 <span class="monospaced">Show :&gt; SHOW</span>.  If you want to try the examples immediately, just
 233 skip forward to the implementation.</p></div>
 234 <div class="paragraph"><p>To use <span class="monospaced">show</span>, one first needs a type-index, which is then given to
 235 <span class="monospaced">show</span>.  To show a list of integers, one would use the type-index
 236 <span class="monospaced">list int</span>, which has the type <span class="monospaced">int list Show.t</span>:</p></div>
 237 <div class="listingblock">
 238 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">&quot;[3, 1, 4]&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 239 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">list</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 240 <span class="w">       </span><span class="p">[</span><span class="mi">3</span><span class="p">,</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">4</span><span class="p">]</span><span class="w"></span>
 241 </pre></div></div></div>
 242 <div class="paragraph"><p>Likewise, to show a list of lists of characters, one would use the
 243 type-index <span class="monospaced">list (list char)</span>, which has the type <span class="monospaced">char list list
 244 Show.t</span>:</p></div>
 245 <div class="listingblock">
 246 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">&quot;[[#</span><span class="se">\&quot;</span><span class="s">a</span><span class="se">\&quot;</span><span class="s">, #</span><span class="se">\&quot;</span><span class="s">b</span><span class="se">\&quot;</span><span class="s">, #</span><span class="se">\&quot;</span><span class="s">c</span><span class="se">\&quot;</span><span class="s">], []]&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 247 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">list</span><span class="w"> </span><span class="p">(</span><span class="n">list</span><span class="w"> </span><span class="n">char</span><span class="p">))</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 248 <span class="w">       </span><span class="p">[[#</span><span class="s">&quot;a&quot;</span><span class="p">,</span><span class="w"> </span><span class="p">#</span><span class="s">&quot;b&quot;</span><span class="p">,</span><span class="w"> </span><span class="p">#</span><span class="s">&quot;c&quot;</span><span class="p">],</span><span class="w"> </span><span class="p">[]]</span><span class="w"></span>
 249 </pre></div></div></div>
 250 <div class="paragraph"><p>Handling standard types is not particularly interesting.  It is more
 251 interesting to see how user-defined types can be handled.  Although
 252 the <span class="monospaced">option</span> datatype is a standard type, it requires no special
 253 support, so we can treat it as a user-defined type.  Options can be
 254 encoded easily using a sum:</p></div>
 255 <div class="listingblock">
 256 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 257 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 258 <span class="k">in</span><span class="w"></span>
 259 <span class="w">   </span><span class="n">inj</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">INL</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
 260 <span class="w">         </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">v</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">INR</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="w"></span>
 261 <span class="w">       </span><span class="p">(</span><span class="n">data</span><span class="w"> </span><span class="p">(</span><span class="n">C0</span><span class="s">&quot;NONE&quot;</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;SOME&quot;</span><span class="w"> </span><span class="n">t</span><span class="p">))</span><span class="w"></span>
 262 <span class="k">end</span><span class="w"></span>
 263
 264 <span class="k">val</span><span class="w"> </span><span class="s">&quot;SOME 5&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 265 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">option</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 266 <span class="w">       </span><span class="p">(</span><span class="n">SOME</span><span class="w"> </span><span class="mi">5</span><span class="p">)</span><span class="w"></span>
 267 </pre></div></div></div>
 268 <div class="paragraph"><p>Readers new to type-indexed values might want to type annotate each
 269 subexpression of the above example as an exercise.  (Use a compiler to
 270 check your annotations.)</p></div>
 271 <div class="paragraph"><p>Using a product, user specified records can be also be encoded easily:</p></div>
 272 <div class="listingblock">
 273 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">abc</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 274 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 275 <span class="k">in</span><span class="w"></span>
 276 <span class="w">   </span><span class="n">inj</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">{</span><span class="n">a</span><span class="p">,</span><span class="w"> </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">=&gt;</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"></span>
 277 <span class="w">       </span><span class="p">(</span><span class="n">record</span><span class="w"> </span><span class="p">(</span><span class="n">L</span><span class="s">&quot;a&quot;</span><span class="w"> </span><span class="p">(</span><span class="n">option</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"></span>
 278 <span class="w">                </span><span class="n">L</span><span class="s">&quot;b&quot;</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"></span>
 279 <span class="w">                </span><span class="n">L</span><span class="s">&quot;c&quot;</span><span class="w"> </span><span class="n">bool</span><span class="p">))</span><span class="w"></span>
 280 <span class="k">end</span><span class="w"></span>
 281
 282 <span class="k">val</span><span class="w"> </span><span class="s">&quot;{a = SOME 1, b = 3.0, c = false}&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 283 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="n">abc</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 284 <span class="w">       </span><span class="p">{</span><span class="n">a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mf">3.0</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">false</span><span class="p">}</span><span class="w"></span>
 285 </pre></div></div></div>
 286 <div class="paragraph"><p>As you can see, both of the above use <span class="monospaced">inj</span> to inject user-defined
 287 types to the general purpose sum and product types.</p></div>
 288 <div class="paragraph"><p>Of particular interest is whether recursive datatypes and cyclic data
 289 can be handled.  For example, how does one write a type-index for a
 290 recursive datatype such as a cyclic graph?</p></div>
 291 <div class="listingblock">
 292 <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">graph</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">graph</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>
 293 <span class="k">fun</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="p">(</span><span class="n">VTX</span><span class="w"> </span><span class="p">(_,</span><span class="w"> </span><span class="n">r</span><span class="p">))</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 294 </pre></div></div></div>
 295 <div class="paragraph"><p>Using the <span class="monospaced">Show</span> combinators, we could first write a new type-index
 296 combinator for <span class="monospaced">graph</span>:</p></div>
 297 <div class="listingblock">
 298 <div class="content"><div class="highlight"><pre><span class="k">fun</span><span class="w"> </span><span class="n">graph</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 299 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Tie</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 300 <span class="k">in</span><span class="w"></span>
 301 <span class="w">   </span><span class="n">fix</span><span class="w"> </span><span class="n">Y</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">graph_a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 302 <span class="w">             </span><span class="n">inj</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"></span>
 303 <span class="w">                 </span><span class="p">(</span><span class="n">data</span><span class="w"> </span><span class="p">(</span><span class="n">C1</span><span class="s">&quot;VTX&quot;</span><span class="w"></span>
 304 <span class="w">                          </span><span class="p">(</span><span class="n">tuple</span><span class="w"> </span><span class="p">(</span><span class="n">U</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">*</span><span class="w"></span>
 305 <span class="w">                                  </span><span class="n">U</span><span class="w"> </span><span class="p">(</span><span class="n">refc</span><span class="w"> </span><span class="p">(</span><span class="n">list</span><span class="w"> </span><span class="n">graph_a</span><span class="p">)))))))</span><span class="w"></span>
 306 <span class="k">end</span><span class="w"></span>
 307 </pre></div></div></div>
 308 <div class="paragraph"><p>To show a graph with integer labels</p></div>
 309 <div class="listingblock">
 310 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">a_graph</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 311 <span class="w">   </span><span class="k">val</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">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 312 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 313 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 314 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 315 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">e</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 316 <span class="w">   </span><span class="k">val</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">VTX</span><span class="w"> </span><span class="p">(</span><span class="mi">6</span><span class="p">,</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">[])</span><span class="w"></span>
 317 <span class="k">in</span><span class="w"></span>
 318 <span class="w">   </span><span class="n">arcs</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">:=</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">d</span><span class="p">]</span><span class="w"></span>
 319 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">[</span><span class="n">c</span><span class="p">,</span><span class="w"> </span><span class="n">e</span><span class="p">]</span><span class="w"></span>
 320 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">[</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">f</span><span class="p">]</span><span class="w"></span>
 321 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">[</span><span class="n">f</span><span class="p">]</span><span class="w"></span>
 322 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="n">e</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">[</span><span class="n">d</span><span class="p">]</span><span class="w"></span>
 323 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">arcs</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">[</span><span class="n">e</span><span class="p">]</span><span class="w"></span>
 324 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
 325 <span class="k">end</span><span class="w"></span>
 326 </pre></div></div></div>
 327 <div class="paragraph"><p>we could then simply write</p></div>
 328 <div class="listingblock">
 329 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">&quot;VTX (1, ref [VTX (2, ref [VTX (3, ref [VTX (1, %0), \</span>
 330 <span class="s">    \VTX (6, ref [VTX (5, ref [VTX (4, ref [VTX (6, %3)])])] as %3)]), \</span>
 331 <span class="s">    \VTX (5, ref [VTX (4, ref [VTX (6, ref [VTX (5, %2)])])] as %2)]), \</span>
 332 <span class="s">    \VTX (4, ref [VTX (6, ref [VTX (5, ref [VTX (4, %1)])])] as %1)] as %0)&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 333 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">graph</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 334 <span class="w">       </span><span class="n">a_graph</span><span class="w"></span>
 335 </pre></div></div></div>
 336 <div class="paragraph"><p>There is a subtle gotcha with cyclic data.  Consider the following code:</p></div>
 337 <div class="listingblock">
 338 <div class="content"><div class="highlight"><pre><span class="k">exception</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="n">array</span><span class="w"></span>
 339
 340 <span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 341 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 342 <span class="k">in</span><span class="w"></span>
 343 <span class="w">   </span><span class="n">regExn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 344 <span class="w">              </span><span class="n">SOME</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;ExnArray&quot;</span><span class="w"> </span><span class="p">(</span><span class="n">array</span><span class="w"> </span><span class="n">exn</span><span class="p">))</span><span class="w"></span>
 345 <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="n">NONE</span><span class="p">)</span><span class="w"></span>
 346 <span class="k">end</span><span class="w"></span>
 347
 348 <span class="k">val</span><span class="w"> </span><span class="n">a_cycle</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 349 <span class="w">   </span><span class="k">val</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">Array</span><span class="p">.</span><span class="n">fromList</span><span class="w"> </span><span class="p">[</span><span class="n">Empty</span><span class="p">]</span><span class="w"></span>
 350 <span class="k">in</span><span class="w"></span>
 351 <span class="w">   </span><span class="n">Array</span><span class="p">.</span><span class="n">update</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
 352 <span class="k">end</span><span class="w"></span>
 353 </pre></div></div></div>
 354 <div class="paragraph"><p>Although the above looks innocent enough, the evaluation  of</p></div>
 355 <div class="listingblock">
 356 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">&quot;[|ExnArray %0|] as %0&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 357 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">array</span><span class="w"> </span><span class="n">exn</span><span class="p">)</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 358 <span class="w">       </span><span class="n">a_cycle</span><span class="w"></span>
 359 </pre></div></div></div>
 360 <div class="paragraph"><p>goes into an infinite loop.  To avoid this problem, the type-index
 361 <span class="monospaced">array exn</span> must be evaluated only once, as in the following:</p></div>
 362 <div class="listingblock">
 363 <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="n">array_exn</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 364
 365 <span class="k">exception</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="n">array</span><span class="w"></span>
 366
 367 <span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 368 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 369 <span class="k">in</span><span class="w"></span>
 370 <span class="w">   </span><span class="n">regExn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 371 <span class="w">              </span><span class="n">SOME</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;ExnArray&quot;</span><span class="w"> </span><span class="n">array_exn</span><span class="p">)</span><span class="w"></span>
 372 <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="n">NONE</span><span class="p">)</span><span class="w"></span>
 373 <span class="k">end</span><span class="w"></span>
 374
 375 <span class="k">val</span><span class="w"> </span><span class="n">a_cycle</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 376 <span class="w">   </span><span class="k">val</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">Array</span><span class="p">.</span><span class="n">fromList</span><span class="w"> </span><span class="p">[</span><span class="n">Empty</span><span class="p">]</span><span class="w"></span>
 377 <span class="k">in</span><span class="w"></span>
 378 <span class="w">   </span><span class="n">Array</span><span class="p">.</span><span class="n">update</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">ExnArray</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
 379 <span class="k">end</span><span class="w"></span>
 380
 381 <span class="k">val</span><span class="w"> </span><span class="s">&quot;[|ExnArray %0|] as %0&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 382 <span class="w">    </span><span class="k">let</span><span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="k">in</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="n">array_exn</span><span class="w"> </span><span class="k">end</span><span class="w"></span>
 383 <span class="w">       </span><span class="n">a_cycle</span><span class="w"></span>
 384 </pre></div></div></div>
 385 <div class="paragraph"><p>Cyclic data (excluding closures) in Standard ML can only be
 386 constructed imperatively through arrays and references (combined with
 387 exceptions or recursive datatypes).  Before recursing to a reference
 388 or an array, one needs to check whether that reference or array has
 389 already been seen before.  When <span class="monospaced">ref</span> or <span class="monospaced">array</span> is called with a
 390 type-index, a new cyclicity checker is instantiated.</p></div>
 391 </div>
 392 </div>
 393 <div class="sect1">
 394 <h2 id="_implementation">Implementation</h2>
 395 <div class="sectionbody">
 396 <div class="listingblock">
 397 <div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">SmlSyntax</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">struct</span><span class="w"></span>
 398 <span class="w">   </span><span class="k">local</span><span class="w"></span>
 399 <span class="w">      </span><span class="k">structure</span><span class="w"> </span><span class="n">CV</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">CharVector</span><span class="w"> </span><span class="k">and</span><span class="w"> </span><span class="n">C</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Char</span><span class="w"></span>
 400 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 401 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">isSym</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Char</span><span class="p">.</span><span class="n">contains</span><span class="w"> </span><span class="s">&quot;!%&amp;$#+-/:&lt;=&gt;?@</span><span class="se">\\</span><span class="s">~`^|*&quot;</span><span class="w"></span>
 402
 403 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isSymId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n">&lt;</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="k">andalso</span><span class="w"> </span><span class="n">CV</span><span class="p">.</span><span class="n">all</span><span class="w"> </span><span class="n">isSym</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 404
 405 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isAlphaNumId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 406 <span class="w">          </span><span class="mi">0</span><span class="w"> </span><span class="n">&lt;</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 407 <span class="w">          </span><span class="k">andalso</span><span class="w"> </span><span class="n">C</span><span class="p">.</span><span class="n">isAlpha</span><span class="w"> </span><span class="p">(</span><span class="n">CV</span><span class="p">.</span><span class="n">sub</span><span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">))</span><span class="w"></span>
 408 <span class="w">          </span><span class="k">andalso</span><span class="w"> </span><span class="n">CV</span><span class="p">.</span><span class="n">all</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">C</span><span class="p">.</span><span class="n">isAlphaNum</span><span class="w"> </span><span class="n">c</span><span class="w"></span>
 409 <span class="w">                                  </span><span class="k">orelse</span><span class="w"> </span><span class="p">#</span><span class="s">&quot;&#39;&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">c</span><span class="w"></span>
 410 <span class="w">                                  </span><span class="k">orelse</span><span class="w"> </span><span class="p">#</span><span class="s">&quot;_&quot;</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 411
 412 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isNumLabel</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 413 <span class="w">          </span><span class="mi">0</span><span class="w"> </span><span class="n">&lt;</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 414 <span class="w">          </span><span class="k">andalso</span><span class="w"> </span><span class="p">#</span><span class="s">&quot;0&quot;</span><span class="w"> </span><span class="n">&lt;&gt;</span><span class="w"> </span><span class="n">CV</span><span class="p">.</span><span class="n">sub</span><span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"></span>
 415 <span class="w">          </span><span class="k">andalso</span><span class="w"> </span><span class="n">CV</span><span class="p">.</span><span class="n">all</span><span class="w"> </span><span class="n">C</span><span class="p">.</span><span class="n">isDigit</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 416
 417 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">isAlphaNumId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="k">orelse</span><span class="w"> </span><span class="n">isSymId</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 418
 419 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isLongId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">List</span><span class="p">.</span><span class="n">all</span><span class="w"> </span><span class="n">isId</span><span class="w"> </span><span class="p">(</span><span class="n">String</span><span class="p">.</span><span class="n">fields</span><span class="w"> </span><span class="p">(#</span><span class="s">&quot;.&quot;</span><span class="w"> </span><span class="n">&lt;\</span><span class="w"> </span><span class="k">op</span><span class="w"> </span><span class="p">=)</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"></span>
 420
 421 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">isLabel</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">isId</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="k">orelse</span><span class="w"> </span><span class="n">isNumLabel</span><span class="w"> </span><span class="n">s</span><span class="w"></span>
 422 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 423 <span class="k">end</span><span class="w"></span>
 424
 425 <span class="k">structure</span><span class="w"> </span><span class="n">Show</span><span class="w"> </span><span class="p">:&gt;</span><span class="w"> </span><span class="n">SHOW</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">struct</span><span class="w"></span>
 426 <span class="w">   </span><span class="k">datatype</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="k">of</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">string</span><span class="w"></span>
 427 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 428 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="p">(</span><span class="n">&#39;a</span><span class="p">,</span><span class="w"> </span><span class="n">&#39;k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">&#39;a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 429 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">u</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 430 <span class="w">   </span><span class="k">type</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">unit</span><span class="w"></span>
 431
 432 <span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">show</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">#</span><span class="mi">2</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="w"> </span><span class="p">([],</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"></span>
 433
 434 <span class="w">   </span><span class="cm">(* user-defined types *)</span><span class="w"></span>
 435 <span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">inj</span><span class="w"> </span><span class="n">inj</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">b</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">b</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">Pair</span><span class="p">.</span><span class="n">map</span><span class="w"> </span><span class="p">(</span><span class="n">id</span><span class="p">,</span><span class="w"> </span><span class="n">inj</span><span class="p">))</span><span class="w"></span>
 436
 437 <span class="w">   </span><span class="k">local</span><span class="w"></span>
 438 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">surround</span><span class="w"> </span><span class="n">pre</span><span class="w"> </span><span class="n">suf</span><span class="w"> </span><span class="p">(_,</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="n">concat</span><span class="w"> </span><span class="p">[</span><span class="n">pre</span><span class="p">,</span><span class="w"> </span><span class="n">s</span><span class="p">,</span><span class="w"> </span><span class="n">suf</span><span class="p">])</span><span class="w"></span>
 439 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">parenthesize</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">#</span><span class="mi">1</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;(&quot;</span><span class="w"> </span><span class="s">&quot;)&quot;</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
 440 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">construct</span><span class="w"> </span><span class="n">tag</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 441 <span class="w">          </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(_,</span><span class="w"> </span><span class="n">s</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">true</span><span class="p">,</span><span class="w"> </span><span class="n">concat</span><span class="w"> </span><span class="p">[</span><span class="n">tag</span><span class="p">,</span><span class="w"> </span><span class="s">&quot; &quot;</span><span class="p">,</span><span class="w"> </span><span class="n">s</span><span class="p">]))</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">parenthesize</span><span class="w"></span>
 442 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">check</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">m</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">raise</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="p">(</span><span class="n">m^s</span><span class="p">)</span><span class="w"></span>
 443 <span class="w">   </span><span class="k">in</span><span class="w"></span>
 444 <span class="w">      </span><span class="cm">(* tuples and records *)</span><span class="w"></span>
 445 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 446 <span class="w">          </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">&amp;</span><span class="w"> </span><span class="n">b</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 447 <span class="w">                 </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="n">concat</span><span class="w"> </span><span class="p">[#</span><span class="mi">2</span><span class="w"> </span><span class="p">(</span><span class="n">l</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)),</span><span class="w"></span>
 448 <span class="w">                                 </span><span class="s">&quot;, &quot;</span><span class="p">,</span><span class="w"></span>
 449 <span class="w">                                 </span><span class="p">#</span><span class="mi">2</span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="p">))]))</span><span class="w"></span>
 450
 451 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">U</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 452 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">L</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">check</span><span class="w"> </span><span class="n">SmlSyntax</span><span class="p">.</span><span class="n">isLabel</span><span class="w"> </span><span class="s">&quot;Invalid label: &quot;</span><span class="w"> </span><span class="n">l</span><span class="w"></span>
 453 <span class="w">               </span><span class="p">;</span><span class="w"> </span><span class="k">fn</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="p">(</span><span class="n">l^</span><span class="s">&quot; = &quot;</span><span class="p">)</span><span class="w"> </span><span class="s">&quot;&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">t</span><span class="p">))</span><span class="w"></span>
 454
 455 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">tuple</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;(&quot;</span><span class="w"> </span><span class="s">&quot;)&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"></span>
 456 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">record</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;{&quot;</span><span class="w"> </span><span class="s">&quot;}&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"></span>
 457
 458 <span class="w">      </span><span class="cm">(* datatypes *)</span><span class="w"></span>
 459 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">l</span><span class="p">)</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">INL</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">l</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"></span>
 460 <span class="w">                                 </span><span class="p">|</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">INR</span><span class="w"> </span><span class="n">b</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">b</span><span class="p">))</span><span class="w"></span>
 461
 462 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">C0</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">check</span><span class="w"> </span><span class="n">SmlSyntax</span><span class="p">.</span><span class="n">isId</span><span class="w"> </span><span class="s">&quot;Invalid constructor: &quot;</span><span class="w"> </span><span class="n">c</span><span class="w"></span>
 463 <span class="w">                </span><span class="p">;</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">const</span><span class="w"> </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)))</span><span class="w"></span>
 464 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">C1</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">check</span><span class="w"> </span><span class="n">SmlSyntax</span><span class="p">.</span><span class="n">isId</span><span class="w"> </span><span class="s">&quot;Invalid constructor: &quot;</span><span class="w"> </span><span class="n">c</span><span class="w"></span>
 465 <span class="w">                       </span><span class="p">;</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">construct</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">t</span><span class="p">))</span><span class="w"></span>
 466
 467 <span class="w">      </span><span class="k">val</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">id</span><span class="w"></span>
 468
 469 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="n">Y</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Tie</span><span class="p">.</span><span class="n">iso</span><span class="w"> </span><span class="n">Tie</span><span class="p">.</span><span class="n">function</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">IN</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">x</span><span class="p">,</span><span class="w"> </span><span class="n">IN</span><span class="p">)</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 470
 471 <span class="w">      </span><span class="cm">(* exceptions *)</span><span class="w"></span>
 472 <span class="w">      </span><span class="k">local</span><span class="w"></span>
 473 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">handlers</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="p">([]</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="p">(</span><span class="n">exn</span><span class="w"> </span><span class="p">-&gt;</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">option</span><span class="p">)</span><span class="w"> </span><span class="n">list</span><span class="p">)</span><span class="w"></span>
 474 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 475 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">exn</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">e</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 476 <span class="w">                             </span><span class="k">fun</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">[]</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 477 <span class="w">                                 </span><span class="n">C0</span><span class="p">(</span><span class="n">concat</span><span class="w"> </span><span class="p">[</span><span class="s">&quot;&lt;exn:&quot;</span><span class="p">,</span><span class="w"></span>
 478 <span class="w">                                            </span><span class="n">General</span><span class="p">.</span><span class="n">exnName</span><span class="w"> </span><span class="n">e</span><span class="p">,</span><span class="w"></span>
 479 <span class="w">                                            </span><span class="s">&quot;&gt;&quot;</span><span class="p">])</span><span class="w"></span>
 480 <span class="w">                               </span><span class="p">|</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">(</span><span class="n">f::fs</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 481 <span class="w">                                 </span><span class="k">case</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="n">e</span><span class="w"></span>
 482 <span class="w">                                  </span><span class="k">of</span><span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="n">fs</span><span class="w"></span>
 483 <span class="w">                                   </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
 484 <span class="w">                             </span><span class="k">val</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">(</span><span class="n">!handlers</span><span class="p">)</span><span class="w"></span>
 485 <span class="w">                          </span><span class="k">in</span><span class="w"></span>
 486 <span class="w">                             </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="p">())</span><span class="w"></span>
 487 <span class="w">                          </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
 488 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">regExn</span><span class="w"> </span><span class="n">f</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 489 <span class="w">             </span><span class="n">handlers</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="p">(</span><span class="n">Option</span><span class="p">.</span><span class="n">map</span><span class="w"></span>
 490 <span class="w">                             </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"></span>
 491 <span class="w">                                 </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</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>
 492 <span class="w">                                        </span><span class="n">f</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">)))</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">f</span><span class="p">)</span><span class="w"></span>
 493 <span class="w">                         </span><span class="n">::</span><span class="w"> </span><span class="n">!handlers</span><span class="w"></span>
 494 <span class="w">      </span><span class="k">end</span><span class="w"></span>
 495
 496 <span class="w">      </span><span class="cm">(* some built-in type constructors *)</span><span class="w"></span>
 497 <span class="w">      </span><span class="k">local</span><span class="w"></span>
 498 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">cyclic</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 499 <span class="w">            </span><span class="k">exception</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">&#39;&#39;a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>
 500 <span class="w">         </span><span class="k">in</span><span class="w"></span>
 501 <span class="w">            </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="w"> </span><span class="p">:</span><span class="w"> </span><span class="n">&#39;&#39;a</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 502 <span class="w">                      </span><span class="k">val</span><span class="w"> </span><span class="n">idx</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">length</span><span class="w"></span>
 503 <span class="w">                      </span><span class="k">fun</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">(</span><span class="n">E</span><span class="w"> </span><span class="p">(</span><span class="n">v&#39;</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="n">::rs</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 504 <span class="w">                          </span><span class="k">if</span><span class="w"> </span><span class="n">v&#39;</span><span class="w"> </span><span class="n">&lt;&gt;</span><span class="w"> </span><span class="n">v</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="n">rs</span><span class="w"></span>
 505 <span class="w">                          </span><span class="k">else</span><span class="w"> </span><span class="p">(</span><span class="n">c</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">false</span><span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;%&quot;</span><span class="n">^idx</span><span class="w"> </span><span class="n">rs</span><span class="p">))</span><span class="w"></span>
 506 <span class="w">                        </span><span class="p">|</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">(_</span><span class="n">::rs</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="n">rs</span><span class="w"></span>
 507 <span class="w">                        </span><span class="p">|</span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="p">[]</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 508 <span class="w">                             </span><span class="k">val</span><span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">true</span><span class="w"></span>
 509 <span class="w">                             </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">(</span><span class="n">E</span><span class="w"> </span><span class="p">(</span><span class="n">v</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="n">::rs</span><span class="p">,</span><span class="w"> </span><span class="n">v</span><span class="p">)</span><span class="w"></span>
 510 <span class="w">                          </span><span class="k">in</span><span class="w"></span>
 511 <span class="w">                             </span><span class="k">if</span><span class="w"> </span><span class="n">!c</span><span class="w"> </span><span class="k">then</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 512 <span class="w">                             </span><span class="k">else</span><span class="w"> </span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;&quot;</span><span class="w"> </span><span class="p">(</span><span class="s">&quot; as %&quot;</span><span class="n">^idx</span><span class="w"> </span><span class="n">rs</span><span class="p">)</span><span class="w"> </span><span class="n">r</span><span class="w"></span>
 513 <span class="w">                          </span><span class="k">end</span><span class="w"></span>
 514 <span class="w">                   </span><span class="k">in</span><span class="w"></span>
 515 <span class="w">                      </span><span class="n">lp</span><span class="w"> </span><span class="n">rs</span><span class="w"></span>
 516 <span class="w">                   </span><span class="k">end</span><span class="p">)</span><span class="w"></span>
 517 <span class="w">         </span><span class="k">end</span><span class="w"></span>
 518
 519 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">aggregate</span><span class="w"> </span><span class="n">pre</span><span class="w"> </span><span class="n">suf</span><span class="w"> </span><span class="n">toList</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="n">t</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 520 <span class="w">             </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="n">pre</span><span class="w"> </span><span class="n">suf</span><span class="w"> </span><span class="n">o</span><span class="w"></span>
 521 <span class="w">                 </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(</span><span class="n">rs</span><span class="p">,</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>
 522 <span class="w">                     </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"></span>
 523 <span class="w">                      </span><span class="n">String</span><span class="p">.</span><span class="n">concatWith</span><span class="w"></span>
 524 <span class="w">                         </span><span class="s">&quot;, &quot;</span><span class="w"></span>
 525 <span class="w">                         </span><span class="p">(</span><span class="n">map</span><span class="w"> </span><span class="p">(#</span><span class="mi">2</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">curry</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="n">rs</span><span class="p">)</span><span class="w"></span>
 526 <span class="w">                              </span><span class="p">(</span><span class="n">toList</span><span class="w"> </span><span class="n">a</span><span class="p">)))))</span><span class="w"></span>
 527 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 528 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">refc</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">cyclic</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">inj</span><span class="w"> </span><span class="n">!</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;ref&quot;</span><span class="p">)</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 529 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">cyclic</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">aggregate</span><span class="w"> </span><span class="s">&quot;[|&quot;</span><span class="w"> </span><span class="s">&quot;|]&quot;</span><span class="w"> </span><span class="p">(</span><span class="n">Array</span><span class="p">.</span><span class="n">foldr</span><span class="w"> </span><span class="k">op</span><span class="n">::</span><span class="w"> </span><span class="p">[]))</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 530 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">aggregate</span><span class="w"> </span><span class="s">&quot;[&quot;</span><span class="w"> </span><span class="s">&quot;]&quot;</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 531 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">vector</span><span class="w"> </span><span class="n">?</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">aggregate</span><span class="w"> </span><span class="s">&quot;#[&quot;</span><span class="w"> </span><span class="s">&quot;]&quot;</span><span class="w"> </span><span class="p">(</span><span class="n">Vector</span><span class="p">.</span><span class="n">foldr</span><span class="w"> </span><span class="k">op</span><span class="n">::</span><span class="w"> </span><span class="p">[])</span><span class="w"> </span><span class="n">?</span><span class="w"></span>
 532 <span class="w">      </span><span class="k">end</span><span class="w"></span>
 533
 534 <span class="w">      </span><span class="k">fun</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="p">_)</span><span class="w"> </span><span class="n">--&gt;</span><span class="w"> </span><span class="p">(</span><span class="n">IN</span><span class="w"> </span><span class="p">_)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">const</span><span class="w"> </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="s">&quot;&lt;fn&gt;&quot;</span><span class="p">))</span><span class="w"></span>
 535
 536 <span class="w">      </span><span class="cm">(* some built-in base types *)</span><span class="w"></span>
 537 <span class="w">      </span><span class="k">local</span><span class="w"></span>
 538 <span class="w">         </span><span class="k">fun</span><span class="w"> </span><span class="n">mk</span><span class="w"> </span><span class="n">toS</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><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="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">))</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">toS</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">(_,</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
 539 <span class="w">      </span><span class="k">in</span><span class="w"></span>
 540 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">string</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
 541 <span class="w">             </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;</span><span class="se">\&quot;</span><span class="s">&quot;</span><span class="w"> </span><span class="s">&quot;</span><span class="se">\&quot;</span><span class="s">&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">mk</span><span class="w"> </span><span class="p">(</span><span class="n">String</span><span class="p">.</span><span class="n">translate</span><span class="w"> </span><span class="n">Char</span><span class="p">.</span><span class="n">toString</span><span class="p">))</span><span class="w"></span>
 542 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">mk</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="s">&quot;()&quot;</span><span class="p">))</span><span class="w"></span>
 543 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">bool</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">mk</span><span class="w"> </span><span class="n">Bool</span><span class="p">.</span><span class="n">toString</span><span class="p">)</span><span class="w"></span>
 544 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">char</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;#</span><span class="se">\&quot;</span><span class="s">&quot;</span><span class="w"> </span><span class="s">&quot;</span><span class="se">\&quot;</span><span class="s">&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">mk</span><span class="w"> </span><span class="n">Char</span><span class="p">.</span><span class="n">toString</span><span class="p">)</span><span class="w"></span>
 545 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">int</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">mk</span><span class="w"> </span><span class="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="p">)</span><span class="w"></span>
 546 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">word</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">surround</span><span class="w"> </span><span class="s">&quot;0wx&quot;</span><span class="w"> </span><span class="s">&quot;&quot;</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">mk</span><span class="w"> </span><span class="n">Word</span><span class="p">.</span><span class="n">toString</span><span class="p">)</span><span class="w"></span>
 547 <span class="w">         </span><span class="k">val</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">IN</span><span class="w"> </span><span class="p">(</span><span class="n">mk</span><span class="w"> </span><span class="n">Real</span><span class="p">.</span><span class="n">toString</span><span class="p">)</span><span class="w"></span>
 548 <span class="w">      </span><span class="k">end</span><span class="w"></span>
 549 <span class="w">   </span><span class="k">end</span><span class="w"></span>
 550 <span class="k">end</span><span class="w"></span>
 551
 552 <span class="cm">(* Handlers for standard top-level exceptions *)</span><span class="w"></span>
 553 <span class="k">val</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">let</span><span class="w"></span>
 554 <span class="w">   </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>
 555 <span class="w">   </span><span class="k">fun</span><span class="w"> </span><span class="n">E0</span><span class="w"> </span><span class="n">name</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="p">((),</span><span class="w"> </span><span class="n">C0</span><span class="w"> </span><span class="n">name</span><span class="p">)</span><span class="w"></span>
 556 <span class="k">in</span><span class="w"></span>
 557 <span class="w">   </span><span class="n">regExn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">Bind</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Bind&quot;</span><span class="w"></span>
 558 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Chr</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Chr&quot;</span><span class="w"></span>
 559 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Div</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Div&quot;</span><span class="w"></span>
 560 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Domain</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Domain&quot;</span><span class="w"></span>
 561 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Empty</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Empty&quot;</span><span class="w"></span>
 562 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Match</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Match&quot;</span><span class="w"></span>
 563 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Option</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Option&quot;</span><span class="w"></span>
 564 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Overflow</span><span class="w">  </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Overflow&quot;</span><span class="w"></span>
 565 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Size</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Size&quot;</span><span class="w"></span>
 566 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Span</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Span&quot;</span><span class="w"></span>
 567 <span class="w">            </span><span class="p">|</span><span class="w"> </span><span class="n">Subscript</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">E0</span><span class="s">&quot;Subscript&quot;</span><span class="w"></span>
 568 <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="n">NONE</span><span class="p">)</span><span class="w"></span>
 569 <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">regExn</span><span class="w"> </span><span class="p">(</span><span class="k">fn</span><span class="w"> </span><span class="n">Fail</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">=&gt;</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="p">(</span><span class="n">s</span><span class="p">,</span><span class="w"> </span><span class="n">C1</span><span class="s">&quot;Fail&quot;</span><span class="w"> </span><span class="n">string</span><span class="p">)</span><span class="w"></span>
 570 <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="n">NONE</span><span class="p">)</span><span class="w"></span>
 571 <span class="k">end</span><span class="w"></span>
 572 </pre></div></div></div>
 573 </div>
 574 </div>
 575 <div class="sect1">
 576 <h2 id="_also_see">Also see</h2>
 577 <div class="sectionbody">
 578 <div class="paragraph"><p>There are a number of related techniques.  Here are some of them.</p></div>
 579 <div class="ulist"><ul>
 580 <li>
 581 <p>
 582 <a href="Fold">Fold</a>
 583 </p>
 584 </li>
 585 <li>
 586 <p>
 587 <a href="StaticSum">StaticSum</a>
 588 </p>
 589 </li>
 590 </ul></div>
 591 </div>
 592 </div>
 593 </div>
 594 <div id="footnotes"><hr></div>
 595 <div id="footer">
 596 <div id="footer-text">
 597 </div>
 598 <div id="footer-badges">
 599 </div>
 600 </div>
 601 </body>
 602 </html>