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
|
<!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>PropertyList</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>PropertyList</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph"><p>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></div>
<div class="paragraph"><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></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">signature</span><span class="w"> </span><span class="n">PROPERTY_LIST</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">new</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">t</span><span class="w"></span>
<span class="w"> </span><span class="k">val</span><span class="w"> </span><span class="n">newProperty</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">add</span><span class="p">:</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">'a</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">peek</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="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>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></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">P</span><span class="p">:</span><span class="w"> </span><span class="n">PROPERTY_LIST</span><span class="p">)</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="n">pl</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">P</span><span class="p">.</span><span class="n">new</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="n">add</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">addInt</span><span class="p">:</span><span class="w"> </span><span class="n">P</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">*</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">unit</span><span class="p">,</span><span class="w"> </span><span class="n">peek</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">peekInt</span><span class="p">}</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">P</span><span class="p">.</span><span class="n">newProperty</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="n">add</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">addReal</span><span class="p">:</span><span class="w"> </span><span class="n">P</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">*</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">unit</span><span class="p">,</span><span class="w"> </span><span class="n">peek</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">peekReal</span><span class="p">}</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">P</span><span class="p">.</span><span class="n">newProperty</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">addInt</span><span class="w"> </span><span class="p">(</span><span class="n">pl</span><span class="p">,</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="p">()</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">addReal</span><span class="w"> </span><span class="p">(</span><span class="n">pl</span><span class="p">,</span><span class="w"> </span><span class="mf">17.0</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="n">Int</span><span class="p">.</span><span class="n">toString</span><span class="w"> </span><span class="p">(</span><span class="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">peekInt</span><span class="w"> </span><span class="n">pl</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">s2</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="p">(</span><span class="n">valOf</span><span class="w"> </span><span class="p">(</span><span class="n">peekReal</span><span class="w"> </span><span class="n">pl</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">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="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>Applied to an appropriate implementation <span class="monospaced">PROPERTY_LIST</span>, the <span class="monospaced">Test</span>
functor will produce the following output.</p></div>
<div class="listingblock">
<div class="content monospaced">
<pre>13 17.0</pre>
</div></div>
</div>
</div>
<div class="sect1">
<h2 id="_implementation">Implementation</h2>
<div class="sectionbody">
<div class="paragraph"><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></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">functor</span><span class="w"> </span><span class="n">PropertyList</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="n">PROPERTY_LIST</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="n">U</span><span class="p">.</span><span class="n">t</span><span class="w"> </span><span class="n">list</span><span class="w"> </span><span class="n">ref</span><span class="w"></span>
<span class="w"> </span><span class="k">fun</span><span class="w"> </span><span class="n">new</span><span class="w"> </span><span class="p">()</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">ref</span><span class="w"> </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">newProperty</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="p">(</span><span class="n">inject</span><span class="p">,</span><span class="w"> </span><span class="n">out</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">fun</span><span class="w"> </span><span class="n">add</span><span class="w"> </span><span class="p">(</span><span class="n">T</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="p">:</span><span class="w"> </span><span class="n">'a</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">r</span><span class="w"> </span><span class="n">:=</span><span class="w"> </span><span class="n">inject</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">!r</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">peek</span><span class="w"> </span><span class="p">(</span><span class="n">T</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="w"> </span><span class="n">Option</span><span class="p">.</span><span class="n">map</span><span class="w"> </span><span class="p">(</span><span class="n">valOf</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">out</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="n">List</span><span class="p">.</span><span class="n">find</span><span class="w"> </span><span class="p">(</span><span class="n">isSome</span><span class="w"> </span><span class="n">o</span><span class="w"> </span><span class="n">out</span><span class="p">)</span><span class="w"> </span><span class="p">(</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">add</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="n">peek</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">peek</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>If <span class="monospaced">U: UNIVERSAL_TYPE</span>, then we can test our code as follows.</p></div>
<div class="listingblock">
<div class="content"><div class="highlight"><pre><span class="k">structure</span><span class="w"> </span><span class="n">Z</span><span class="w"> </span><span class="p">=</span><span class="w"> </span><span class="n">Test</span><span class="w"> </span><span class="p">(</span><span class="n">PropertyList</span><span class="w"> </span><span class="p">(</span><span class="n">U</span><span class="p">))</span><span class="w"></span>
</pre></div></div></div>
<div class="paragraph"><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></div>
</div>
</div>
<div class="sect1">
<h2 id="_also_see">Also see</h2>
<div class="sectionbody">
<div class="ulist"><ul>
<li>
<p>
MLton relies heavily on property lists for attaching information to
syntax tree nodes in its intermediate languages. See
<a href="https://github.com/MLton/mlton/blob/master/lib/mlton/basic/property-list.sig"><span class="monospaced">property-list.sig</span></a> and
<a href="https://github.com/MLton/mlton/blob/master/lib/mlton/basic/property-list.fun"><span class="monospaced">property-list.fun</span></a>.
</p>
</li>
<li>
<p>
The <a href="MLRISCLibrary">MLRISCLibrary</a> <a href="References#LeungGeorge98"> uses property lists
extensively</a>.
</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>
|
