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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>UniversalType - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
UniversalType
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
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.
<pre class=code>
<B><FONT COLOR="#0000FF">signature</FONT></B> UNIVERSAL_TYPE =
<B><FONT COLOR="#0000FF">sig</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> t
</FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> embed: unit -> ('a -> t) * (t -> 'a option)
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<p>
The idea is that <tt>type t</tt> is the universal type and that each call to <tt>embed</tt> returns a new pair of functions <tt>(inject, project)</tt>, where <tt>inject</tt> embeds a value into the universal type and <tt>project</tt> extracts the value from the universal type. A pair <tt>(inject, project)</tt> returned by <tt>embed</tt> works together in that <tt>project u</tt> will return <tt>SOME v</tt> if and only if <tt>u</tt> was created by <tt>inject v</tt>. If <tt>u</tt> was created by a different function <tt>inject'</tt>, then <tt>project</tt> returns <tt>NONE</tt>.
</p>
<p>
Here's an example embedding integers and reals into a universal type.
<pre class=code>
<B><FONT COLOR="#0000FF">functor</FONT></B> Test (U: UNIVERSAL_TYPE): <B><FONT COLOR="#0000FF">sig</FONT></B> <B><FONT COLOR="#0000FF">end</FONT></B> =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> (intIn: int -> U.t, intOut) = U.embed ()
<B><FONT COLOR="#A020F0">val</FONT></B> r: U.t ref = ref (intIn <B><FONT COLOR="#5F9EA0">13</FONT></B>)
<B><FONT COLOR="#A020F0">val</FONT></B> s1 =
<B><FONT COLOR="#A020F0">case</FONT></B> intOut (!r) <B><FONT COLOR="#A020F0">of</FONT></B>
NONE => <B><FONT COLOR="#BC8F8F">"NONE"</FONT></B>
| SOME i => Int.toString i
<B><FONT COLOR="#A020F0">val</FONT></B> (realIn: real -> U.t, realOut) = U.embed ()
<B><FONT COLOR="#A020F0">val</FONT></B> () = r := realIn <B><FONT COLOR="#5F9EA0">13.0</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> s2 =
<B><FONT COLOR="#A020F0">case</FONT></B> intOut (!r) <B><FONT COLOR="#A020F0">of</FONT></B>
NONE => <B><FONT COLOR="#BC8F8F">"NONE"</FONT></B>
| SOME i => Int.toString i
<B><FONT COLOR="#A020F0">val</FONT></B> s3 =
<B><FONT COLOR="#A020F0">case</FONT></B> realOut (!r) <B><FONT COLOR="#A020F0">of</FONT></B>
NONE => <B><FONT COLOR="#BC8F8F">"NONE"</FONT></B>
| SOME x => Real.toString x
<B><FONT COLOR="#A020F0">val</FONT></B> () = print (concat [s1, <B><FONT COLOR="#BC8F8F">" "</FONT></B>, s2, <B><FONT COLOR="#BC8F8F">" "</FONT></B>, s3, <B><FONT COLOR="#BC8F8F">"\n"</FONT></B>])
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
</p>
<p>
Applying <tt>Test</tt> to an appropriate implementation will print
<pre>13 NONE 13.0
</pre>
</p>
<p>
Note that two different calls to embed on the same type return different embeddings.
</p>
<p>
Standard ML does not have explicit support for universal types; however, there are at least two ways to implement them.
</p>
<h2 id="head-5ab5e9f7a9267673649cd34bf0a7cf4b914d2288">Implementation Using Exceptions</h2>
<p>
While the intended use of SML exceptions is for exception handling, an accidental feature of their design is that the <tt>exn</tt> 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>
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> U:> UNIVERSAL_TYPE =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> exn
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> embed () =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">exception</FONT></B><B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">E</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> 'a
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> project (e: t): 'a option =
<B><FONT COLOR="#A020F0">case</FONT></B> e <B><FONT COLOR="#A020F0">of</FONT></B>
E a => SOME a
| _ => NONE
<B><FONT COLOR="#A020F0">in</FONT></B>
(E, project)
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<h2 id="head-ce424b82430977939b90a4c1cb21f7a8e6f6301c">Implementation Using Functions and References</h2>
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> U:> UNIVERSAL_TYPE =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">datatype</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> <FONT COLOR="#B8860B">T</FONT> <B><FONT COLOR="#A020F0">of</FONT></B> {clear: unit -> unit,
store: unit -> unit}
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> embed () =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> r: 'a option ref = ref NONE
<B><FONT COLOR="#A020F0">fun</FONT></B> inject (a: 'a): t =
T {clear = <B><FONT COLOR="#A020F0">fn</FONT></B> () => r := NONE,
store = <B><FONT COLOR="#A020F0">fn</FONT></B> () => r := SOME a}
<B><FONT COLOR="#A020F0">fun</FONT></B> project (T {clear, store}): 'a option =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> () = store ()
<B><FONT COLOR="#A020F0">val</FONT></B> res = !r
<B><FONT COLOR="#A020F0">val</FONT></B> () = clear ()
<B><FONT COLOR="#A020F0">in</FONT></B>
res
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#A020F0">in</FONT></B>
(inject, project)
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<p>
Note that due to the use of a shared ref cell, the above implementation is not thread safe.
</p>
<p>
One could try to simplify the above implementation by eliminating the <tt>clear</tt> function, making <tt>type t = unit -> unit</tt>.
</p>
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> U:> UNIVERSAL_TYPE =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> t </FONT></B>=<B><FONT COLOR="#228B22"> unit -> unit
</FONT></B><B><FONT COLOR="#A020F0">fun</FONT></B> <B><FONT COLOR="#228B22">'a</FONT></B> embed () =
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> r: 'a option ref = ref NONE
<B><FONT COLOR="#A020F0">fun</FONT></B> inject (a: 'a): t = <B><FONT COLOR="#A020F0">fn</FONT></B> () => r := SOME a
<B><FONT COLOR="#A020F0">fun</FONT></B> project (f: t): 'a option = (r := NONE; f (); !r)
<B><FONT COLOR="#A020F0">in</FONT></B>
(inject, project)
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<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 <tt>project</tt>, where the call to <tt>f</tt> stores some value in some ref cell <tt>r'</tt>. Perhaps <tt>r'</tt> is the same ref cell as <tt>r</tt>, but perhaps not. If we do not clear <tt>r'</tt> before returning from <tt>project</tt>, then <tt>r'</tt> will keep the value alive, even though it is useless.
</p>
<h2 id="head-a4bc8bf5caf54b18cea9f58e83dd4acb488deb17">Also see</h2>
<ul>
<li>
<p>
<a href="PropertyList">PropertyList</a>: Lisp-style property lists implemented with a universal type.
</p>
</li>
</ul>
</div>
<p>
<hr>
Last edited on 2005-05-29 03:04:34 by <span title="cs78147114.pp.htv.fi"><a href="VesaKarvonen">VesaKarvonen</a></span>.
</body></html>
|
