repos
/
cl-unification
/ annotate_shade
summary
|
shortlog
|
log
|
tree
|
commit
|
commitdiff
|
headdiff
|
annotate
|
headblob
|
headfilediff
|
filehistory
normal
|
plain
|
shade
|
zebra
Copyright updated.
Annotate for file docs/html/unifying-substitutions.html
2004-11-17 mantoniotti
1
<html>
22:19:54 '
2
<head>
'
3
<title>CL Unifying Substitutions</title>
'
4
<link rel="stylesheet" href="main.css">
'
5
</head>
'
6
'
7
<body marginheight="0" marginwidth="0" leftmargin="0" topmargin="0" bgcolor="#ffffff">
'
8
'
9
<table border="0" cellpadding="0" cellspacing="0" width="100%" height="100%" vspace="0" hspace="0">
'
10
<tr>
'
11
<td colspan="3">
'
12
<div class="header"
'
13
style="font-family:=Verdana,Arial,Helvetica; font-size: 18px; color: #41286f;">
'
14
<strong><i>CL Extensions: UNIFYING SUBSTITUTIONS</i><string>
'
15
<div class="navigation">
'
16
<a href="index.html" class="navigation-link-selected">Home</a>
'
17
| <a href="downloads.html" class="navigation-link">Downloads</a>
'
18
| <a href="links.html" class="navigation-link">Links</a>
'
19
</div>
'
20
</div>
'
21
<div class="black-line"><img src="images/shim.gif" height="1" width="1"></div>
'
22
<div class="middle-bar"><img src="images/shim.gif" height="5" width="1"></div>
'
23
<div class="black-line"><img src="images/shim.gif" height="1" width="1"></div>
'
24
</td>
'
25
</tr>
'
26
'
27
<tr height="100%">
'
28
<td height="100%"> </td>
'
29
<td valign="top" width="80%" height="100%">
'
30
'
31
<div class="content">
'
32
<div class="text" style="padding-top: 10px;">
'
33
'
34
<h1>Unifying Substitutions</h1>
'
35
'
36
<p>The central notion of every unification machinery is that of
'
37
<em>unifying substitution</em>. A unifying substitution - or
'
38
<em>environment</em> - is a
'
39
mapping from <em>variable names</em> (or <em>variables</em>) to
'
40
<em>values</em> (which can be variables themselves.)</p>
'
41
'
42
<p>The generic function UNIFY, and several other functions and macros
'
43
in the package accept unifying substitutions as parameters, and
'
44
return them as values.</p>
'
45
'
46
<p>There are several notations to describe such unifying
'
47
substitutions. The one chosen here is simply the following:</p>
'
48
'
49
<p>
'
50
<pre>
'
51
{x<sub>1</sub> -> y<sub>1</sub>, x<sub>2</sub> -> y<sub>2</sub>, ..., x<sub>k</sub> -> y<sub>k</sub>}
'
52
</pre>
'
53
</p>
'
54
'
55
<p>The UNIFY library has a number of functions and data structures
'
56
that can be used to construct and manipulate unifying substitutions.</p>
'
57
'
58
<p>In order to facilitate the construction of interpreter-like
'
59
programs the UNIFICATION library provides data structures
'
60
representing <em>bindings</em>, <em>frames</em>, and
'
61
<em>environments</em> - i.e. the unifying substitions proper.</p>
'
62
'
63
<ul>
'
64
<li><em>Bindings</em>
'
65
'
66
<p>A <em>binding</em> simply represent the mapping between a variable and a
'
67
value.</p>
'
68
'
69
<p>
'
70
<pre>
'
71
<i>binding</i>: <i>variable</i> --> <i>value</i>
'
72
</pre>
'
73
</p>
'
74
'
75
<li><em>Frames</em>
'
76
'
77
<p>A <em>frame</em> is simply a collection of bindings.</p>
'
78
'
79
<p>
'
80
<pre>
'
81
<i>frame</i>: {<i>binding</i><sub>i</sub>}
'
82
</pre>
'
83
</p>
'
84
'
85
'
86
<li><em>Environments</em>
'
87
'
88
<p>An <em>environment</em> is simply a stack of frames.</p>
'
89
'
90
<p>
'
91
<pre>
'
92
<i>environment</i>: <<i>frame</i><sub>0</sub>, <i>frame</i><sub>1</sub>, ..., <i>frame</i><sub>k</sub>>
'
93
</pre>
'
94
</p>
'
95
</ul>
'
96
'
97
<p>The collection of operators described hereafter manipulates these
'
98
opaque data structures.</p>
'
99
'
100
<h1>Unifying Substitutions Dictionary</h1>
'
101
'
102
<ul>
'
103
<li><a href="find-variable-value-function.html">FIND-VARIABLE-VALUE</a></li>
'
104
<li><a href="make-empty-environment-function.html">MAKE-EMTPY-ENVIRONMENT</a></li>
'
105
<li><a href="make-shared-environment-function.html">MAKE-SHARED-ENVIRONMENT</a></li>
'
106
'
107
</ul>
'
108
'
109
'
110
'
111
<h1>Notes</h1>
'
112
'
113
<h2>Current Implementation Details</h2>
'
114
'
115
<p>The current implementation is rather straightforward. A binding
'
116
is a CONS, a frame is a wrapper around an A-LIST, and an environment
'
117
is a wrapper around a LIST (stack) of frames.</p>
'
118
'
119
'
120
<h2>Functional Style Unifying Substitutions</h2>
'
121
'
122
<p>There are very elegant implementations of unification and
'
123
substitutions based on curried functions. A typical exercise in
'
124
functional programming using ML or a similar language is to write a
'
125
simplified Milner Type Checker. Writing the unifying substitution
'
126
support can be achieved by using curried functions in that context.</p>
'
127
'
128
'
129
<!--
'
130
;;; Copyright (c) 2004 Marco Antoniotti, All rigths reserved.
'
131
;;;
'
132
;;; Permission to use, modify, and redistribute this code is hereby
'
133
;;; granted.
'
134
;;; The code is provided AS IS with NO warranty whatsoever. The author
'
135
;;; will not be held liable etc etc etc etc etc.
'
136
-->
'
137
'
138
<h2>Site Map</h2>
'
139
'
140
'
141
<p>Enjoy!</p>
'
142
'
143
'
144
'
145
<hr>
'
146
<p>Questions? Queries? Suggestions? Comments? Please direct them
'
147
at <a href="mailto:marcoxa_PROVA_A_SPAMMARME@alu.org">me</a>.
'
148
</p>
'
149
'
150
</div>
'
151
</div>
'
152
'
153
</td>
'
154
'
155
<!-- <td height="100%"> </td> -->
'
156
</tr>
'
157
'
158
<tr height="100%">
'
159
<td height="100%"> </td>
'
160
<td valign="top" width="80%" height="100%">
'
161
'
162
<div class="content">
'
163
<div class="text" style="padding-top: 10px;">
'
164
2011-04-02 mantoniotti
165
<!-- <h1>News</h1>
2004-11-17 mantoniotti
166
22:19:54 '
167
<p>News in chronological order, most recent on top.
'
168
</p>
'
169
'
170
<ul>
'
171
<li><strong>2004-10-30</strong><br>
'
172
Document created
'
173
</li>
'
174
</ul>
2011-04-02 mantoniotti
175
-->
2004-11-17 mantoniotti
176
</div>
22:19:54 '
177
</div>
'
178
'
179
</td>
'
180
'
181
<td height="100%"> </td>
'
182
</tr>
'
183
'
184
'
185
'
186
'
187
<tr>
'
188
<td colspan="3" valign="bottom" align="right">
'
189
<div class="copyright">
2011-04-02 mantoniotti
190
© 2003-2011, Marco Antoniotti, all rights reserved.
2004-11-17 mantoniotti
191
</div>
22:19:54 '
192
</td>
'
193
</tr>
'
194
'
195
</table>
'
196
</body>
'
197
</html>