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
|
<!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>PropertyList - 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 20061025</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
PropertyList
<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 = "Index">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
A property list is a dictionary-like data structure into which properties (name-value pairs) can be inserted and from which properties can be looked up by name. The term comes from the Lisp language, where every symbol has a property list for storing information, and where the names are typically symbols and keys can be any type of value. <p>
Here is an SML signature for property lists such that for any type of value a new property can be dynamically created to manipulate that type of value in a property list.
</p>
<pre class=code>
<B><FONT COLOR="#5F9EA0">signature</FONT></B> PROPERTY_LIST <B><FONT COLOR="#5F9EA0">=</FONT></B>
<B><FONT COLOR="#5F9EA0">sig</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B> t
<B><FONT COLOR="#A020F0">val</FONT></B> new: <B><FONT COLOR="#228B22">unit</FONT></B> <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> t
<B><FONT COLOR="#A020F0">val</FONT></B> newProperty: <B><FONT COLOR="#228B22">unit</FONT></B> <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> {add: t <B><FONT COLOR="#5F9EA0">*</FONT></B> 'a <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> <B><FONT COLOR="#228B22">unit</FONT></B>,
peek: t <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> 'a option}
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<p>
Here is a functor demonstrating the use of property lists. It first creates a property list, then two new properties (of different types), and adds a value to the list for each property.
</p>
<pre class=code>
<B><FONT COLOR="#5F9EA0">functor</FONT></B> Test (P: PROPERTY_LIST) <B><FONT COLOR="#5F9EA0">=</FONT></B>
<B><FONT COLOR="#5F9EA0">struct</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> pl <B><FONT COLOR="#5F9EA0">=</FONT></B> P.new ()
<B><FONT COLOR="#A020F0">val</FONT></B> {add <B><FONT COLOR="#5F9EA0">=</FONT></B> addInt: P.t <B><FONT COLOR="#5F9EA0">*</FONT></B> <B><FONT COLOR="#228B22">int</FONT></B> <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> <B><FONT COLOR="#228B22">unit</FONT></B>, peek <B><FONT COLOR="#5F9EA0">=</FONT></B> peekInt} <B><FONT COLOR="#5F9EA0">=</FONT></B> P.newProperty ()
<B><FONT COLOR="#A020F0">val</FONT></B> {add <B><FONT COLOR="#5F9EA0">=</FONT></B> addReal: P.t <B><FONT COLOR="#5F9EA0">*</FONT></B> <B><FONT COLOR="#228B22">real</FONT></B> <B><FONT COLOR="#5F9EA0">-</FONT></B><B><FONT COLOR="#5F9EA0">></FONT></B> <B><FONT COLOR="#228B22">unit</FONT></B>, peek <B><FONT COLOR="#5F9EA0">=</FONT></B> peekReal} <B><FONT COLOR="#5F9EA0">=</FONT></B> P.newProperty ()
<B><FONT COLOR="#A020F0">val</FONT></B> () <B><FONT COLOR="#5F9EA0">=</FONT></B> addInt (pl, 13)
<B><FONT COLOR="#A020F0">val</FONT></B> () <B><FONT COLOR="#5F9EA0">=</FONT></B> addReal (pl, 17.0)
<B><FONT COLOR="#A020F0">val</FONT></B> s1 <B><FONT COLOR="#5F9EA0">=</FONT></B> Int.toString (valOf (peekInt pl))
<B><FONT COLOR="#A020F0">val</FONT></B> s2 <B><FONT COLOR="#5F9EA0">=</FONT></B> Real.toString (valOf (peekReal pl))
<B><FONT COLOR="#A020F0">val</FONT></B> () <B><FONT COLOR="#5F9EA0">=</FONT></B> <B><FONT COLOR="#A020F0">print</FONT></B> (<B><FONT COLOR="#A020F0">concat</FONT></B> [s1, <B><FONT COLOR="#BC8F8F">" "</FONT></B>, s2, <B><FONT COLOR="#BC8F8F">"\n"</FONT></B>])
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<p>
Applied to an appropriate implementation <tt>PROPERTY_LIST</tt>, the <tt>Test</tt> functor will produce the following output.
<pre>13 17.0
</pre>
</p>
<h2 id="head-8781d615fd77be9578225c40ac67b9471394cced">Implementation</h2>
<p>
Because property lists can hold values of any type, their implementation requires a <a href="UniversalType">UniversalType</a>. Given that, a property list is simply a list of elements of the universal type. Adding a property adds to the front of the list, and looking up a property scans the list.
</p>
<pre class=code>
<B><FONT COLOR="#5F9EA0">functor</FONT></B> PropertyList (U: UNIVERSAL_TYPE): PROPERTY_LIST <B><FONT COLOR="#5F9EA0">=</FONT></B>
<B><FONT COLOR="#5F9EA0">struct</FONT></B>
<B><FONT COLOR="#A020F0">datatype</FONT></B> t <B><FONT COLOR="#5F9EA0">=</FONT></B> T <B><FONT COLOR="#A020F0">of</FONT></B> U.t <B><FONT COLOR="#228B22">list</FONT></B> <B><FONT COLOR="#A020F0">ref</FONT></B>
<B><FONT COLOR="#A020F0"> fun </FONT></B><B><FONT COLOR="#0000FF"><B><I><FONT COLOR="#000000">new</FONT></I></B></FONT></B> () <B><FONT COLOR="#5F9EA0">=</FONT></B> T (<B><FONT COLOR="#A020F0">ref</FONT></B> [])
<B><FONT COLOR="#A020F0">fun</FONT></B> 'a newProperty () <B><FONT COLOR="#5F9EA0">=</FONT></B>
<B><FONT COLOR="#A020F0">let</FONT></B>
<B><FONT COLOR="#A020F0">val</FONT></B> (inject, out) <B><FONT COLOR="#5F9EA0">=</FONT></B> U.embed ()
<B><FONT COLOR="#A020F0"> fun </FONT></B><B><FONT COLOR="#0000FF"><B><I><FONT COLOR="#000000">add</FONT></I></B></FONT></B> (T r, a: 'a): <B><FONT COLOR="#228B22">unit</FONT></B> <B><FONT COLOR="#5F9EA0">=</FONT></B> r <B><FONT COLOR="#5F9EA0">:=</FONT></B> inject a <B><FONT COLOR="#5F9EA0">::</FONT></B> (<B><FONT COLOR="#5F9EA0">!</FONT></B>r)
<B><FONT COLOR="#A020F0"> fun </FONT></B><B><FONT COLOR="#0000FF"><B><I><FONT COLOR="#000000">peek</FONT></I></B></FONT></B> (T r) <B><FONT COLOR="#5F9EA0">=</FONT></B>
Option.map (valOf <B><FONT COLOR="#A020F0">o</FONT></B> out) (List.find (isSome <B><FONT COLOR="#A020F0">o</FONT></B> out) (<B><FONT COLOR="#5F9EA0">!</FONT></B>r))
<B><FONT COLOR="#A020F0">in</FONT></B>
{add <B><FONT COLOR="#5F9EA0">=</FONT></B> add, peek <B><FONT COLOR="#5F9EA0">=</FONT></B> peek}
<B><FONT COLOR="#A020F0">end</FONT></B>
<B><FONT COLOR="#A020F0">end</FONT></B>
</PRE>
<p>
</p>
<p>
If <tt>U: UNIVERSAL_TYPE</tt>, then we can test our code as follows.
<pre class=code>
<B><FONT COLOR="#5F9EA0">structure</FONT></B> Z <B><FONT COLOR="#5F9EA0">=</FONT></B> Test (PropertyList (U))
</PRE>
</p>
<p>
Of course, a serious implementation of property lists would have to handle duplicate insertions of the same property, as well as the removal of elements in order to avoid space leaks.
</p>
<h2 id="head-a4bc8bf5caf54b18cea9f58e83dd4acb488deb17">Also see</h2>
<p>
MLton relies heavily on property lists for attaching information to syntax tree nodes in its intermediate languages. See
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20061025-release/lib/mlton/basic/property-list.sig?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">property-list.sig</a>
<a href = "http://mlton.org/cgi-bin/viewsvn.cgi/mlton/tags/on-20061025-release/lib/mlton/basic/property-list.fun?view=markup"><img src="moin-www.png" alt="[WWW]" height="11" width="11">property-list.fun</a>
.
</p>
<p>
<a class="nonexistent" href="MLRISC">MLRISC</a> <a href = "References#LeungGeorge98">uses property lists extensively</a>.
</p>
</div>
<p>
<hr>
Last edited on 2005-08-19 15:30:27 by <span title="cfs32.cs.cornell.edu"><a href="MatthewFluet">MatthewFluet</a></span>.
</body></html>
|
