Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | <!DOCTYPE html>\r |
2 | <html lang="en">\r | |
3 | <head>\r | |
4 | <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">\r | |
5 | <meta name="generator" content="AsciiDoc 8.6.9">\r | |
6 | <title>TypeIndexedValues</title>\r | |
7 | <link rel="stylesheet" href="./asciidoc.css" type="text/css">\r | |
8 | <link rel="stylesheet" href="./pygments.css" type="text/css">\r | |
9 | \r | |
10 | \r | |
11 | <script type="text/javascript" src="./asciidoc.js"></script>\r | |
12 | <script type="text/javascript">\r | |
13 | /*<![CDATA[*/\r | |
14 | asciidoc.install();\r | |
15 | /*]]>*/\r | |
16 | </script>\r | |
17 | <link rel="stylesheet" href="./mlton.css" type="text/css">\r | |
18 | </head>\r | |
19 | <body class="article">\r | |
20 | <div id="banner">\r | |
21 | <div id="banner-home">\r | |
22 | <a href="./Home">MLton 20180207</a>\r | |
23 | </div>\r | |
24 | </div>\r | |
25 | <div id="header">\r | |
26 | <h1>TypeIndexedValues</h1>\r | |
27 | </div>\r | |
28 | <div id="content">\r | |
29 | <div id="preamble">\r | |
30 | <div class="sectionbody">\r | |
31 | <div class="paragraph"><p><a href="StandardML">Standard ML</a> does not support ad hoc polymorphism. This\r | |
32 | presents a challenge to programmers. The problem is that at first\r | |
33 | glance there seems to be no practical way to implement something like\r | |
34 | a function for converting a value of any type to a string or a\r | |
35 | function for computing a hash value for a value of any type.\r | |
36 | Fortunately there are ways to implement type-indexed values in SML as\r | |
37 | discussed in <a href="References#Yang98">Yang98</a>. Various articles such as\r | |
38 | <a href="References#Danvy98">Danvy98</a>, <a href="References#Ramsey11">Ramsey11</a>, <a href="References#Elsman04">Elsman04</a>,\r | |
39 | <a href="References#Kennedy04">Kennedy04</a>, and <a href="References#Benton05">Benton05</a> also contain examples of\r | |
40 | type-indexed values.</p></div>\r | |
41 | <div class="paragraph"><p><strong>NOTE:</strong> The technique used in the following example uses an early (and\r | |
42 | somewhat broken) variation of the basic technique used in an\r | |
43 | experimental generic programming library (see\r | |
44 | <a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/generic/unstable/README"><span class="monospaced">README</span></a>) that can\r | |
45 | be found from the MLton repository. The generic programming library\r | |
46 | also includes a more advanced generic pretty printing function (see\r | |
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>\r | |
48 | </div>\r | |
49 | </div>\r | |
50 | <div class="sect1">\r | |
51 | <h2 id="_example_converting_any_sml_value_to_roughly_sml_syntax">Example: Converting any SML value to (roughly) SML syntax</h2>\r | |
52 | <div class="sectionbody">\r | |
53 | <div class="paragraph"><p>Consider the problem of converting any SML value to a textual\r | |
54 | presentation that matches the syntax of SML as closely as possible.\r | |
55 | One solution is a type-indexed function that maps a given type to a\r | |
56 | function that maps any value (of the type) to its textual\r | |
57 | presentation. A type-indexed function like this can be useful for a\r | |
58 | variety of purposes. For example, one could use it to show debugging\r | |
59 | information. We’ll call this function "<span class="monospaced">show</span>".</p></div>\r | |
60 | <div class="paragraph"><p>We’ll do a fairly complete implementation of <span class="monospaced">show</span>. We do not\r | |
61 | distinguish infix and nonfix constructors, but that is not an\r | |
62 | intrinsic property of SML datatypes. We also don’t reconstruct a type\r | |
63 | name for the value, although it would be particularly useful for\r | |
64 | functional values. To reconstruct type names, some changes would be\r | |
65 | needed and the reader is encouraged to consider how to do that. A\r | |
66 | more realistic implementation would use some pretty printing\r | |
67 | combinators to compute a layout for the result. This should be a\r | |
68 | relatively easy change (given a suitable pretty printing library).\r | |
69 | Cyclic values (through references and arrays) do not have a standard\r | |
70 | textual presentation and it is impossible to convert arbitrary\r | |
71 | functional values (within SML) to a meaningful textual presentation.\r | |
72 | Finally, it would also make sense to show sharing of references and\r | |
73 | arrays. We’ll leave these improvements to an actual library\r | |
74 | implementation.</p></div>\r | |
75 | <div class="paragraph"><p>The following code uses the <a href="Fixpoints">fixpoint framework</a> and other\r | |
76 | utilities from an Extended Basis library (see\r | |
77 | <a href="https://github.com/MLton/mltonlib/blob/master/com/ssh/extended-basis/unstable/README"><span class="monospaced">README</span></a>).</p></div>\r | |
78 | <div class="sect2">\r | |
79 | <h3 id="_signature">Signature</h3>\r | |
80 | <div class="paragraph"><p>Let’s consider the design of the <span class="monospaced">SHOW</span> signature:</p></div>\r | |
81 | <div class="listingblock">\r | |
82 | <div class="content"><div class="highlight"><pre><span class="k">infixr</span><span class="w"> </span><span class="n">--></span><span class="w"></span>\r | |
83 | \r | |
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>\r | |
85 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">'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>\r | |
86 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">'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>\r | |
87 | <span class="w"> </span><span class="k">type</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">'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>\r | |
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>\r | |
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>\r | |
90 | \r | |
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">'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">'a</span><span class="w"> </span><span class="p">-></span><span class="w"> </span><span class="n">string</span><span class="w"></span>\r | |
92 | \r | |
93 | <span class="w"> </span><span class="cm">(* user-defined types *)</span><span class="w"></span>\r | |
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">'a</span><span class="w"> </span><span class="p">-></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">'b</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">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
95 | \r | |
96 | <span class="w"> </span><span class="cm">(* tuples and records *)</span><span class="w"></span>\r | |
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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'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="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">product</span><span class="p">,</span><span class="w"> </span><span class="n">'k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>\r | |
98 | \r | |
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">'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="p">(</span><span class="n">'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>\r | |
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">-></span><span class="w"> </span><span class="n">'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="p">(</span><span class="n">'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>\r | |
101 | \r | |
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">'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">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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">'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">-></span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
104 | \r | |
105 | <span class="w"> </span><span class="cm">(* datatypes *)</span><span class="w"></span>\r | |
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">'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">'b</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">-></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">sum</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
107 | \r | |
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">-></span><span class="w"> </span><span class="n">unit</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
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">-></span><span class="w"> </span><span class="n">'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">'a</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
110 | \r | |
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">'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">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
112 | \r | |
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">'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>\r | |
114 | \r | |
115 | <span class="w"> </span><span class="cm">(* exceptions *)</span><span class="w"></span>\r | |
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>\r | |
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">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'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">-></span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
118 | \r | |
119 | <span class="w"> </span><span class="cm">(* some built-in type constructors *)</span><span class="w"></span>\r | |
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">'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">'a</span><span class="w"> </span><span class="n">ref</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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">'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">'a</span><span class="w"> </span><span class="n">array</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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">'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">'a</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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">'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">'a</span><span class="w"> </span><span class="n">vector</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
124 | <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">'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">'b</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">-></span><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">'b</span><span class="p">)</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
125 | \r | |
126 | <span class="w"> </span><span class="cm">(* some built-in base types *)</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
134 | <span class="k">end</span><span class="w"></span>\r | |
135 | </pre></div></div></div>\r | |
136 | <div class="paragraph"><p>While some details are shaped by the specific requirements of <span class="monospaced">show</span>,\r | |
137 | there are a number of (design) patterns that translate to other\r | |
138 | type-indexed values. The former kind of details are mostly shaped by\r | |
139 | the syntax of SML values that <span class="monospaced">show</span> is designed to produce. To this\r | |
140 | end, abstract types and phantom types are used to distinguish\r | |
141 | incomplete record, tuple, and datatype type-indices from each other\r | |
142 | and from complete type-indices. Also, names of record labels and\r | |
143 | datatype constructors need to be provided by the user.</p></div>\r | |
144 | <div class="sect3">\r | |
145 | <h4 id="_arbitrary_user_defined_datatypes">Arbitrary user-defined datatypes</h4>\r | |
146 | <div class="paragraph"><p>Perhaps the most important pattern is how the design supports\r | |
147 | arbitrary user-defined datatypes. A number of combinators together\r | |
148 | conspire to provide the functionality. First of all, to support new\r | |
149 | user-defined types, a combinator taking a conversion function to a\r | |
150 | previously supported type is provided:</p></div>\r | |
151 | <div class="listingblock">\r | |
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">'a</span><span class="w"> </span><span class="p">-></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">'b</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">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
153 | </pre></div></div></div>\r | |
154 | <div class="paragraph"><p>An injection function is sufficient in this case, but in the general\r | |
155 | case, an embedding with injection and projection functions may be\r | |
156 | needed.</p></div>\r | |
157 | <div class="paragraph"><p>To support products (tuples and records) a product combinator is\r | |
158 | provided:</p></div>\r | |
159 | <div class="listingblock">\r | |
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">'a</span><span class="p">,</span><span class="w"> </span><span class="n">'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">'b</span><span class="p">,</span><span class="w"> </span><span class="n">'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="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">product</span><span class="p">,</span><span class="w"> </span><span class="n">'k</span><span class="p">)</span><span class="w"> </span><span class="n">p</span><span class="w"></span>\r | |
161 | </pre></div></div></div>\r | |
162 | <div class="paragraph"><p>The second (phantom) type variable <span class="monospaced">'k</span> is there to distinguish\r | |
163 | between labelled and unlabelled products and the type <span class="monospaced">p</span>\r | |
164 | distinguishes incomplete products from complete type-indices of type\r | |
165 | <span class="monospaced">t</span>. Most type-indexed values do not need to make such distinctions.</p></div>\r | |
166 | <div class="paragraph"><p>To support sums (datatypes) a sum combinator is provided:</p></div>\r | |
167 | <div class="listingblock">\r | |
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">'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">'b</span><span class="w"> </span><span class="n">s</span><span class="w"> </span><span class="p">-></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">sum</span><span class="p">)</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
169 | </pre></div></div></div>\r | |
170 | <div class="paragraph"><p>Again, the purpose of the type <span class="monospaced">s</span> is to distinguish incomplete sums\r | |
171 | from complete type-indices of type <span class="monospaced">t</span>, which usually isn’t necessary.</p></div>\r | |
172 | <div class="paragraph"><p>Finally, to support recursive datatypes, including sets of mutually\r | |
173 | recursive datatypes, a <a href="Fixpoints">fixpoint tier</a> is provided:</p></div>\r | |
174 | <div class="listingblock">\r | |
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">'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>\r | |
176 | </pre></div></div></div>\r | |
177 | <div class="paragraph"><p>Together these combinators (with the more domain specific combinators\r | |
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\r | |
179 | encode a type-index for any user-defined datatype.</p></div>\r | |
180 | </div>\r | |
181 | <div class="sect3">\r | |
182 | <h4 id="_exceptions">Exceptions</h4>\r | |
183 | <div class="paragraph"><p>The <span class="monospaced">exn</span> type in SML is a <a href="UniversalType">universal type</a> into which\r | |
184 | all types can be embedded. SML also allows a program to generate new\r | |
185 | exception variants at run-time. Thus a mechanism is required to register\r | |
186 | handlers for particular variants:</p></div>\r | |
187 | <div class="listingblock">\r | |
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>\r | |
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">-></span><span class="w"> </span><span class="p">(</span><span class="n">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'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">-></span><span class="w"> </span><span class="n">unit</span><span class="w"></span>\r | |
190 | </pre></div></div></div>\r | |
191 | <div class="paragraph"><p>The universal <span class="monospaced">exn</span> type-index then makes use of the registered\r | |
192 | handlers. The above particular form of handler, which converts an\r | |
193 | exception value to a value of some type and a type-index for that type\r | |
194 | (essentially an existential type) is designed to make it convenient to\r | |
195 | write handlers. To write a handler, one can conveniently reuse\r | |
196 | existing type-indices:</p></div>\r | |
197 | <div class="listingblock">\r | |
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>\r | |
199 | \r | |
200 | <span class="k">local</span><span class="w"></span>\r | |
201 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
202 | <span class="k">in</span><span class="w"></span>\r | |
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">=></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">"Int"</span><span class="w"> </span><span class="n">int</span><span class="p">)</span><span class="w"></span>\r | |
204 | <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="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>\r | |
205 | <span class="k">end</span><span class="w"></span>\r | |
206 | </pre></div></div></div>\r | |
207 | <div class="paragraph"><p>Note that a single handler may actually handle an arbitrary number of\r | |
208 | different exceptions.</p></div>\r | |
209 | </div>\r | |
210 | <div class="sect3">\r | |
211 | <h4 id="_other_types">Other types</h4>\r | |
212 | <div class="paragraph"><p>Some built-in and standard types typically require special treatment\r | |
213 | due to their special nature. The most important of these are arrays\r | |
214 | and references, because cyclic data (ignoring closures) and observable\r | |
215 | sharing can only be constructed through them.</p></div>\r | |
216 | <div class="paragraph"><p>When arrow types are really supported, unlike in this case, they\r | |
217 | usually need special treatment due to the contravariance of arguments.</p></div>\r | |
218 | <div class="paragraph"><p>Lists and vectors require special treatment in the case of <span class="monospaced">show</span>,\r | |
219 | because of their special syntax. This isn’t usually the case.</p></div>\r | |
220 | <div class="paragraph"><p>The set of base types to support also needs to be considered unless\r | |
221 | one exports an interface for constructing type-indices for entirely\r | |
222 | new base types.</p></div>\r | |
223 | </div>\r | |
224 | </div>\r | |
225 | </div>\r | |
226 | </div>\r | |
227 | <div class="sect1">\r | |
228 | <h2 id="_usage">Usage</h2>\r | |
229 | <div class="sectionbody">\r | |
230 | <div class="paragraph"><p>Before going to the implementation, let’s look at some examples. For\r | |
231 | the following examples, we’ll assume a structure binding\r | |
232 | <span class="monospaced">Show :> SHOW</span>. If you want to try the examples immediately, just\r | |
233 | skip forward to the implementation.</p></div>\r | |
234 | <div class="paragraph"><p>To use <span class="monospaced">show</span>, one first needs a type-index, which is then given to\r | |
235 | <span class="monospaced">show</span>. To show a list of integers, one would use the type-index\r | |
236 | <span class="monospaced">list int</span>, which has the type <span class="monospaced">int list Show.t</span>:</p></div>\r | |
237 | <div class="listingblock">\r | |
238 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">"[3, 1, 4]"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
241 | </pre></div></div></div>\r | |
242 | <div class="paragraph"><p>Likewise, to show a list of lists of characters, one would use the\r | |
243 | type-index <span class="monospaced">list (list char)</span>, which has the type <span class="monospaced">char list list\r | |
244 | Show.t</span>:</p></div>\r | |
245 | <div class="listingblock">\r | |
246 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">"[[#</span><span class="se">\"</span><span class="s">a</span><span class="se">\"</span><span class="s">, #</span><span class="se">\"</span><span class="s">b</span><span class="se">\"</span><span class="s">, #</span><span class="se">\"</span><span class="s">c</span><span class="se">\"</span><span class="s">], []]"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
248 | <span class="w"> </span><span class="p">[[#</span><span class="s">"a"</span><span class="p">,</span><span class="w"> </span><span class="p">#</span><span class="s">"b"</span><span class="p">,</span><span class="w"> </span><span class="p">#</span><span class="s">"c"</span><span class="p">],</span><span class="w"> </span><span class="p">[]]</span><span class="w"></span>\r | |
249 | </pre></div></div></div>\r | |
250 | <div class="paragraph"><p>Handling standard types is not particularly interesting. It is more\r | |
251 | interesting to see how user-defined types can be handled. Although\r | |
252 | the <span class="monospaced">option</span> datatype is a standard type, it requires no special\r | |
253 | support, so we can treat it as a user-defined type. Options can be\r | |
254 | encoded easily using a sum:</p></div>\r | |
255 | <div class="listingblock">\r | |
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>\r | |
257 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
258 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">INL</span><span class="w"> </span><span class="p">()</span><span class="w"></span>\r | |
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">=></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>\r | |
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">"NONE"</span><span class="w"> </span><span class="n">+</span><span class="w"> </span><span class="n">C1</span><span class="s">"SOME"</span><span class="w"> </span><span class="n">t</span><span class="p">))</span><span class="w"></span>\r | |
262 | <span class="k">end</span><span class="w"></span>\r | |
263 | \r | |
264 | <span class="k">val</span><span class="w"> </span><span class="s">"SOME 5"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
267 | </pre></div></div></div>\r | |
268 | <div class="paragraph"><p>Readers new to type-indexed values might want to type annotate each\r | |
269 | subexpression of the above example as an exercise. (Use a compiler to\r | |
270 | check your annotations.)</p></div>\r | |
271 | <div class="paragraph"><p>Using a product, user specified records can be also be encoded easily:</p></div>\r | |
272 | <div class="listingblock">\r | |
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>\r | |
274 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
275 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="n">&</span><span class="w"> </span><span class="n">b</span><span class="w"> </span><span class="n">&</span><span class="w"> </span><span class="n">c</span><span class="p">)</span><span class="w"></span>\r | |
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">"a"</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>\r | |
278 | <span class="w"> </span><span class="n">L</span><span class="s">"b"</span><span class="w"> </span><span class="n">real</span><span class="w"> </span><span class="n">*</span><span class="w"></span>\r | |
279 | <span class="w"> </span><span class="n">L</span><span class="s">"c"</span><span class="w"> </span><span class="n">bool</span><span class="p">))</span><span class="w"></span>\r | |
280 | <span class="k">end</span><span class="w"></span>\r | |
281 | \r | |
282 | <span class="k">val</span><span class="w"> </span><span class="s">"{a = SOME 1, b = 3.0, c = false}"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
285 | </pre></div></div></div>\r | |
286 | <div class="paragraph"><p>As you can see, both of the above use <span class="monospaced">inj</span> to inject user-defined\r | |
287 | types to the general purpose sum and product types.</p></div>\r | |
288 | <div class="paragraph"><p>Of particular interest is whether recursive datatypes and cyclic data\r | |
289 | can be handled. For example, how does one write a type-index for a\r | |
290 | recursive datatype such as a cyclic graph?</p></div>\r | |
291 | <div class="listingblock">\r | |
292 | <div class="content"><div class="highlight"><pre><span class="k">datatype</span><span class="w"> </span><span class="n">'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">'a</span><span class="w"> </span><span class="n">*</span><span class="w"> </span><span class="n">'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>\r | |
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>\r | |
294 | </pre></div></div></div>\r | |
295 | <div class="paragraph"><p>Using the <span class="monospaced">Show</span> combinators, we could first write a new type-index\r | |
296 | combinator for <span class="monospaced">graph</span>:</p></div>\r | |
297 | <div class="listingblock">\r | |
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>\r | |
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>\r | |
300 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">&</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"></span>\r | |
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">"VTX"</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
306 | <span class="k">end</span><span class="w"></span>\r | |
307 | </pre></div></div></div>\r | |
308 | <div class="paragraph"><p>To show a graph with integer labels</p></div>\r | |
309 | <div class="listingblock">\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
317 | <span class="k">in</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
324 | <span class="w"> </span><span class="p">;</span><span class="w"> </span><span class="n">a</span><span class="w"></span>\r | |
325 | <span class="k">end</span><span class="w"></span>\r | |
326 | </pre></div></div></div>\r | |
327 | <div class="paragraph"><p>we could then simply write</p></div>\r | |
328 | <div class="listingblock">\r | |
329 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">"VTX (1, ref [VTX (2, ref [VTX (3, ref [VTX (1, %0), \</span>\r | |
330 | <span class="s"> \VTX (6, ref [VTX (5, ref [VTX (4, ref [VTX (6, %3)])])] as %3)]), \</span>\r | |
331 | <span class="s"> \VTX (5, ref [VTX (4, ref [VTX (6, ref [VTX (5, %2)])])] as %2)]), \</span>\r | |
332 | <span class="s"> \VTX (4, ref [VTX (6, ref [VTX (5, ref [VTX (4, %1)])])] as %1)] as %0)"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
334 | <span class="w"> </span><span class="n">a_graph</span><span class="w"></span>\r | |
335 | </pre></div></div></div>\r | |
336 | <div class="paragraph"><p>There is a subtle gotcha with cyclic data. Consider the following code:</p></div>\r | |
337 | <div class="listingblock">\r | |
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>\r | |
339 | \r | |
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>\r | |
341 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
342 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"></span>\r | |
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">"ExnArray"</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>\r | |
345 | <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="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>\r | |
346 | <span class="k">end</span><span class="w"></span>\r | |
347 | \r | |
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>\r | |
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>\r | |
350 | <span class="k">in</span><span class="w"></span>\r | |
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>\r | |
352 | <span class="k">end</span><span class="w"></span>\r | |
353 | </pre></div></div></div>\r | |
354 | <div class="paragraph"><p>Although the above looks innocent enough, the evaluation of</p></div>\r | |
355 | <div class="listingblock">\r | |
356 | <div class="content"><div class="highlight"><pre><span class="k">val</span><span class="w"> </span><span class="s">"[|ExnArray %0|] as %0"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
358 | <span class="w"> </span><span class="n">a_cycle</span><span class="w"></span>\r | |
359 | </pre></div></div></div>\r | |
360 | <div class="paragraph"><p>goes into an infinite loop. To avoid this problem, the type-index\r | |
361 | <span class="monospaced">array exn</span> must be evaluated only once, as in the following:</p></div>\r | |
362 | <div class="listingblock">\r | |
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>\r | |
364 | \r | |
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>\r | |
366 | \r | |
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>\r | |
368 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
369 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"></span>\r | |
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">"ExnArray"</span><span class="w"> </span><span class="n">array_exn</span><span class="p">)</span><span class="w"></span>\r | |
372 | <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="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>\r | |
373 | <span class="k">end</span><span class="w"></span>\r | |
374 | \r | |
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>\r | |
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>\r | |
377 | <span class="k">in</span><span class="w"></span>\r | |
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>\r | |
379 | <span class="k">end</span><span class="w"></span>\r | |
380 | \r | |
381 | <span class="k">val</span><span class="w"> </span><span class="s">"[|ExnArray %0|] as %0"</span><span class="w"> </span><span class="p">=</span><span class="w"></span>\r | |
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>\r | |
383 | <span class="w"> </span><span class="n">a_cycle</span><span class="w"></span>\r | |
384 | </pre></div></div></div>\r | |
385 | <div class="paragraph"><p>Cyclic data (excluding closures) in Standard ML can only be\r | |
386 | constructed imperatively through arrays and references (combined with\r | |
387 | exceptions or recursive datatypes). Before recursing to a reference\r | |
388 | or an array, one needs to check whether that reference or array has\r | |
389 | already been seen before. When <span class="monospaced">ref</span> or <span class="monospaced">array</span> is called with a\r | |
390 | type-index, a new cyclicity checker is instantiated.</p></div>\r | |
391 | </div>\r | |
392 | </div>\r | |
393 | <div class="sect1">\r | |
394 | <h2 id="_implementation">Implementation</h2>\r | |
395 | <div class="sectionbody">\r | |
396 | <div class="listingblock">\r | |
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>\r | |
398 | <span class="w"> </span><span class="k">local</span><span class="w"></span>\r | |
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>\r | |
400 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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">"!%&$#+-/:<=>?@</span><span class="se">\\</span><span class="s">~`^|*"</span><span class="w"></span>\r | |
402 | \r | |
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"><</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>\r | |
404 | \r | |
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>\r | |
406 | <span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n"><</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
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>\r | |
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">=></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>\r | |
409 | <span class="w"> </span><span class="k">orelse</span><span class="w"> </span><span class="p">#</span><span class="s">"'"</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">c</span><span class="w"></span>\r | |
410 | <span class="w"> </span><span class="k">orelse</span><span class="w"> </span><span class="p">#</span><span class="s">"_"</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>\r | |
411 | \r | |
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>\r | |
413 | <span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="n"><</span><span class="w"> </span><span class="n">size</span><span class="w"> </span><span class="n">s</span><span class="w"></span>\r | |
414 | <span class="w"> </span><span class="k">andalso</span><span class="w"> </span><span class="p">#</span><span class="s">"0"</span><span class="w"> </span><span class="n"><></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>\r | |
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>\r | |
416 | \r | |
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>\r | |
418 | \r | |
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">"."</span><span class="w"> </span><span class="n"><\</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>\r | |
420 | \r | |
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>\r | |
422 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
423 | <span class="k">end</span><span class="w"></span>\r | |
424 | \r | |
425 | <span class="k">structure</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">SHOW</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="k">struct</span><span class="w"></span>\r | |
426 | <span class="w"> </span><span class="k">datatype</span><span class="w"> </span><span class="n">'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">'a</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">*</span><span class="w"> </span><span class="n">string</span><span class="w"></span>\r | |
427 | <span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">'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">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
428 | <span class="w"> </span><span class="k">type</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">'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">'a</span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
431 | \r | |
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>\r | |
433 | \r | |
434 | <span class="w"> </span><span class="cm">(* user-defined types *)</span><span class="w"></span>\r | |
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>\r | |
436 | \r | |
437 | <span class="w"> </span><span class="k">local</span><span class="w"></span>\r | |
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>\r | |
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">"("</span><span class="w"> </span><span class="s">")"</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>\r | |
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>\r | |
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">=></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">" "</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>\r | |
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>\r | |
443 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
444 | <span class="w"> </span><span class="cm">(* tuples and records *)</span><span class="w"></span>\r | |
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>\r | |
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">&</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>\r | |
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>\r | |
448 | <span class="w"> </span><span class="s">", "</span><span class="p">,</span><span class="w"></span>\r | |
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>\r | |
450 | \r | |
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>\r | |
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">"Invalid label: "</span><span class="w"> </span><span class="n">l</span><span class="w"></span>\r | |
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">=></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">" = "</span><span class="p">)</span><span class="w"> </span><span class="s">""</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>\r | |
454 | \r | |
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">"("</span><span class="w"> </span><span class="s">")"</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>\r | |
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">"{"</span><span class="w"> </span><span class="s">"}"</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>\r | |
457 | \r | |
458 | <span class="w"> </span><span class="cm">(* datatypes *)</span><span class="w"></span>\r | |
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">=></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>\r | |
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">=></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>\r | |
461 | \r | |
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">"Invalid constructor: "</span><span class="w"> </span><span class="n">c</span><span class="w"></span>\r | |
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>\r | |
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">"Invalid constructor: "</span><span class="w"> </span><span class="n">c</span><span class="w"></span>\r | |
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>\r | |
466 | \r | |
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>\r | |
468 | \r | |
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">=></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>\r | |
470 | \r | |
471 | <span class="w"> </span><span class="cm">(* exceptions *)</span><span class="w"></span>\r | |
472 | <span class="w"> </span><span class="k">local</span><span class="w"></span>\r | |
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">-></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>\r | |
474 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="k">let</span><span class="w"></span>\r | |
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>\r | |
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">"<exn:"</span><span class="p">,</span><span class="w"></span>\r | |
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>\r | |
479 | <span class="w"> </span><span class="s">">"</span><span class="p">])</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
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">=></span><span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="n">fs</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">t</span><span class="w"></span>\r | |
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>\r | |
485 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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>\r | |
487 | <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
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">=></span><span class="w"></span>\r | |
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">=></span><span class="w"></span>\r | |
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>\r | |
493 | <span class="w"> </span><span class="n">::</span><span class="w"> </span><span class="n">!handlers</span><span class="w"></span>\r | |
494 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
495 | \r | |
496 | <span class="w"> </span><span class="cm">(* some built-in type constructors *)</span><span class="w"></span>\r | |
497 | <span class="w"> </span><span class="k">local</span><span class="w"></span>\r | |
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>\r | |
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">''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>\r | |
500 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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">''a</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>\r | |
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>\r | |
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'</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>\r | |
504 | <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="n">v'</span><span class="w"> </span><span class="n"><></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>\r | |
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">"%"</span><span class="n">^idx</span><span class="w"> </span><span class="n">rs</span><span class="p">))</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
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>\r | |
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>\r | |
510 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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>\r | |
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">""</span><span class="w"> </span><span class="p">(</span><span class="s">" as %"</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>\r | |
513 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
514 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
515 | <span class="w"> </span><span class="n">lp</span><span class="w"> </span><span class="n">rs</span><span class="w"></span>\r | |
516 | <span class="w"> </span><span class="k">end</span><span class="p">)</span><span class="w"></span>\r | |
517 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
518 | \r | |
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>\r | |
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>\r | |
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">=></span><span class="w"></span>\r | |
522 | <span class="w"> </span><span class="p">(</span><span class="n">false</span><span class="p">,</span><span class="w"></span>\r | |
523 | <span class="w"> </span><span class="n">String</span><span class="p">.</span><span class="n">concatWith</span><span class="w"></span>\r | |
524 | <span class="w"> </span><span class="s">", "</span><span class="w"></span>\r | |
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>\r | |
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>\r | |
527 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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">"ref"</span><span class="p">)</span><span class="w"> </span><span class="n">?</span><span class="w"></span>\r | |
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">"[|"</span><span class="w"> </span><span class="s">"|]"</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>\r | |
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">"["</span><span class="w"> </span><span class="s">"]"</span><span class="w"> </span><span class="n">id</span><span class="w"> </span><span class="n">?</span><span class="w"></span>\r | |
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">"#["</span><span class="w"> </span><span class="s">"]"</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>\r | |
532 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
533 | \r | |
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">--></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">"<fn>"</span><span class="p">))</span><span class="w"></span>\r | |
535 | \r | |
536 | <span class="w"> </span><span class="cm">(* some built-in base types *)</span><span class="w"></span>\r | |
537 | <span class="w"> </span><span class="k">local</span><span class="w"></span>\r | |
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">=></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">=></span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>\r | |
539 | <span class="w"> </span><span class="k">in</span><span class="w"></span>\r | |
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>\r | |
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">"</span><span class="se">\"</span><span class="s">"</span><span class="w"> </span><span class="s">"</span><span class="se">\"</span><span class="s">"</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>\r | |
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">=></span><span class="w"> </span><span class="s">"()"</span><span class="p">))</span><span class="w"></span>\r | |
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>\r | |
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">"#</span><span class="se">\"</span><span class="s">"</span><span class="w"> </span><span class="s">"</span><span class="se">\"</span><span class="s">"</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>\r | |
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>\r | |
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">"0wx"</span><span class="w"> </span><span class="s">""</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>\r | |
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>\r | |
548 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
549 | <span class="w"> </span><span class="k">end</span><span class="w"></span>\r | |
550 | <span class="k">end</span><span class="w"></span>\r | |
551 | \r | |
552 | <span class="cm">(* Handlers for standard top-level exceptions *)</span><span class="w"></span>\r | |
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>\r | |
554 | <span class="w"> </span><span class="k">open</span><span class="w"> </span><span class="n">Show</span><span class="w"></span>\r | |
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>\r | |
556 | <span class="k">in</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Bind"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Chr"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Div"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Domain"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Empty"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Match"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Option"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Overflow"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Size"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Span"</span><span class="w"></span>\r | |
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">=></span><span class="w"> </span><span class="n">E0</span><span class="s">"Subscript"</span><span class="w"></span>\r | |
568 | <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="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>\r | |
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">=></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">"Fail"</span><span class="w"> </span><span class="n">string</span><span class="p">)</span><span class="w"></span>\r | |
570 | <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="w"> </span><span class="n">NONE</span><span class="p">)</span><span class="w"></span>\r | |
571 | <span class="k">end</span><span class="w"></span>\r | |
572 | </pre></div></div></div>\r | |
573 | </div>\r | |
574 | </div>\r | |
575 | <div class="sect1">\r | |
576 | <h2 id="_also_see">Also see</h2>\r | |
577 | <div class="sectionbody">\r | |
578 | <div class="paragraph"><p>There are a number of related techniques. Here are some of them.</p></div>\r | |
579 | <div class="ulist"><ul>\r | |
580 | <li>\r | |
581 | <p>\r | |
582 | <a href="Fold">Fold</a>\r | |
583 | </p>\r | |
584 | </li>\r | |
585 | <li>\r | |
586 | <p>\r | |
587 | <a href="StaticSum">StaticSum</a>\r | |
588 | </p>\r | |
589 | </li>\r | |
590 | </ul></div>\r | |
591 | </div>\r | |
592 | </div>\r | |
593 | </div>\r | |
594 | <div id="footnotes"><hr></div>\r | |
595 | <div id="footer">\r | |
596 | <div id="footer-text">\r | |
597 | </div>\r | |
598 | <div id="footer-badges">\r | |
599 | </div>\r | |
600 | </div>\r | |
601 | </body>\r | |
602 | </html>\r |