1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="generator" content="AsciiDoc 8.6.8">
<title>UniversalType</title>
<link rel="stylesheet" href="./asciidoc.css" type="text/css">
<link rel="stylesheet" href="./pygments.css" type="text/css">
<script type="text/javascript" src="./asciidoc.js"></script>
<script type="text/javascript">
/*<![CDATA[*/
asciidoc.install();
/*]]>*/
</script>
<link rel="stylesheet" href="./mlton.css" type="text/css"/>
</head>
<body class="article">
<div id="banner">
<div id="banner-home">
<a href="./Home">MLton 20130715</a>
</div>
</div>
<div id="header">
<h1>UniversalType</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>A universal type is a type into which all other types can be embedded.
Here’s a <a href="StandardML">Standard ML</a> signature for a universal type.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">signature</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">sig</span><span class="w"></span>
<span class="w"> </span><span class="k">type</span><span class="w"> </span><span class="n">t</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">embed</span><span class="p">:</span><span class="w"> </span><span class="n">unit</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">t</span><span class="p">)</span><span class="w"> </span><span class="n">*</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">'a</span><span class="w"> </span><span class="n">option</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>The idea is that <span class="monospaced">type t</span> is the universal type and that each call to
<span class="monospaced">embed</span> returns a new pair of functions <span class="monospaced">(inject, project)</span>, where
<span class="monospaced">inject</span> embeds a value into the universal type and <span class="monospaced">project</span> extracts
the value from the universal type. A pair <span class="monospaced">(inject, project)</span>
returned by <span class="monospaced">embed</span> works together in that <span class="monospaced">project u</span> will return
<span class="monospaced">SOME v</span> if and only if <span class="monospaced">u</span> was created by <span class="monospaced">inject v</span>. If <span class="monospaced">u</span> was
created by a different function <span class="monospaced">inject'</span>, then <span class="monospaced">project</span> returns
<span class="monospaced">NONE</span>.</p></div>
<div class="paragraph"><p>Here’s an example embedding integers and reals into a universal type.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">functor</span><span class="w"> </span><span class="n">Test</span><span class="w"> </span><span class="p">(</span><span class="n">U</span><span class="p">:</span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="p">):</span><span class="w"> </span><span class="k">sig</span><span class="w"> </span><span class="k">end</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">struct</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">intIn</span><span class="p">:</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">U</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">intOut</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">ref</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="n">intIn</span><span class="w"> </span><span class="mi">13</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s1</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">intOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="s">"NONE"</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">i</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">i</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="p">(</span><span class="n">realIn</span><span class="p">:</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">U</span><span class="p">.</span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">realOut</span><span class="p">)</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">U</span><span class="p">.</span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<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">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">realIn</span><span class="w"> </span><span class="mf">13.0</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s2</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">intOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="s">"NONE"</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">i</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">i</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">s3</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="n">realOut</span><span class="w"> </span><span class="p">(</span><span class="n">!r</span><span class="p">)</span><span class="w"> </span><span class="k">of</span><span class="w"></span>
<span class="w"> </span><span class="n">NONE</span><span class="w"> </span><span class="p">=></span><span class="w"> </span><span class="s">"NONE"</span><span class="w"></span>
<span class="w"> </span><span class="p">|</span><span class="w"> </span><span class="n">SOME</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">Real</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="n">x</span><span class="w"></span>
<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">print</span><span class="w"> </span><span class="p">(</span><span class="n">concat</span><span class="w"> </span><span class="p">[</span><span class="n">s1</span><span class="p">,</span><span class="w"> </span><span class="s">" "</span><span class="p">,</span><span class="w"> </span><span class="n">s2</span><span class="p">,</span><span class="w"> </span><span class="s">" "</span><span class="p">,</span><span class="w"> </span><span class="n">s3</span><span class="p">,</span><span class="w"> </span><span class="s">"</span><span class="se">\n</span><span class="s">"</span><span class="p">])</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>Applying <span class="monospaced">Test</span> to an appropriate implementation will print</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>13 NONE 13.0</pre>
</div></div>
<div class="paragraph"><p>Note that two different calls to embed on the same type return
different embeddings.</p></div>
<div class="paragraph"><p>Standard ML does not have explicit support for universal types;
however, there are at least two ways to implement them.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation_using_exceptions">Implementation Using Exceptions</h2>
<div class="sectionbody">
<div class="paragraph"><p>While the intended use of SML exceptions is for exception handling, an
accidental feature of their design is that the <span class="monospaced">exn</span> type is a
universal type. The implementation relies on being able to declare
exceptions locally to a function and on the fact that exceptions are
<a href="GenerativeException">generative</a>.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:></span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">struct</span><span class="w"></span>
<span class="w"> </span><span class="k">type</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">exn</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<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="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">e</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="p">):</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">case</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="w"> </span><span class="n">E</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">SOME</span><span class="w"> </span><span class="n">a</span><span class="w"></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="w"> </span><span class="n">NONE</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="n">E</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation_using_functions_and_references">Implementation Using Functions and References</h2>
<div class="sectionbody">
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:></span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">struct</span><span class="w"></span>
<span class="w"> </span><span class="k">datatype</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><span class="k">of</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="p">:</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="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">store</span><span class="p">:</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="p">}</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</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">NONE</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">inject</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">'a</span><span class="p">):</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="n">T</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="p">,</span><span class="w"></span>
<span class="w"> </span><span class="n">store</span><span class="w"> </span><span class="p">=</span><span class="w"> </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="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">a</span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">T</span><span class="w"> </span><span class="p">{</span><span class="n">clear</span><span class="p">,</span><span class="w"> </span><span class="n">store</span><span class="p">}):</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<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">store</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">res</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">!r</span><span class="w"></span>
<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">clear</span><span class="w"> </span><span class="p">()</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="n">res</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="n">inject</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>Note that due to the use of a shared ref cell, the above
implementation is not thread safe.</p></div>
<div class="paragraph"><p>One could try to simplify the above implementation by eliminating the
<span class="monospaced">clear</span> function, making <span class="monospaced">type t = unit -> unit</span>.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">U</span><span class="p">:></span><span class="w"> </span><span class="n">UNIVERSAL_TYPE</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">struct</span><span class="w"></span>
<span class="w"> </span><span class="k">type</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">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="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">embed</span><span class="w"> </span><span class="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"></span>
<span class="w"> </span><span class="k">let</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">r</span><span class="p">:</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="n">ref</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">NONE</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">inject</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">'a</span><span class="p">):</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">fn</span><span class="w"> </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="n">:=</span><span class="w"> </span><span class="n">SOME</span><span class="w"> </span><span class="n">a</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">project</span><span class="w"> </span><span class="p">(</span><span class="n">f</span><span class="p">:</span><span class="w"> </span><span class="n">t</span><span class="p">):</span><span class="w"> </span><span class="n">'a</span><span class="w"> </span><span class="n">option</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">NONE</span><span class="p">;</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">!r</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">in</span><span class="w"></span>
<span class="w"> </span><span class="p">(</span><span class="n">inject</span><span class="p">,</span><span class="w"> </span><span class="n">project</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
<span class="w"> </span><span class="k">end</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><p>While correct, this approach keeps the contents of the ref cell alive
longer than necessary, which could cause a space leak. The problem is
in <span class="monospaced">project</span>, where the call to <span class="monospaced">f</span> stores some value in some ref cell
<span class="monospaced">r'</span>. Perhaps <span class="monospaced">r'</span> is the same ref cell as <span class="monospaced">r</span>, but perhaps not. If
we do not clear <span class="monospaced">r'</span> before returning from <span class="monospaced">project</span>, then <span class="monospaced">r'</span> will
keep the value alive, even though it is useless.</p></div>
</div>
</div>
<div class="sect1">
<h2 id="_also_see">Also see</h2>
<div class="sectionbody">
<div class="ulist"><ul>
<li>
<p>
<a href="PropertyList">PropertyList</a>: Lisp-style property lists implemented with a universal type
</p>
</li>
</ul></div>
</div>
</div>
</div>
<div id="footnotes"><hr></div>
<div id="footer">
<div id="footer-text">
</div>
<div id="footer-badges">
</div>
</div>
</body>
</html>
|
