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/control-flow.html
2004-11-17 mantoniotti
1
<html>
22:19:54 '
2
<head>
'
3
<title>CL Control Flow</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: CONTROL FLOW</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>Control Flow</h1>
'
35
'
36
<p>In order to make the use of the UNIFICATION library easier, a few
'
37
utility macros are provided. The macros MATCH, MATCHING, and
'
38
MATCH-CASE can be used to unify two (or more) objects and then to
'
39
build a lexical environment where the variables present in the to
'
40
objects (or templates) are bound to the values resulting from the
'
41
application of UNIFY.</p>
'
42
'
43
<p>
'
44
<ul>
'
45
<li>MATCH is a "single shot" macro. It does one unification and
'
46
executes forms in an appropriate lexical environment.</li>
'
47
'
48
<li>MATCH-CASE is equivalent to CASE. It tries to match a single
'
49
object (or template) against a set of clauses. The forms associated
'
50
to the first clause for which there is a successful unification, are
'
51
then executed within an appropriate lexical environment.
'
52
'
53
<li>MATCHING is equivalent to COND. Each clause contains a
'
54
<em>head</em consisting of two objects to be unified. The first
'
55
clause whose head unifies sucessfully has its associated forms
'
56
executed within an appropriate lexical environment.
'
57
</ul>
'
58
</p>
'
59
'
60
'
61
<h1>Examples</h1>
'
62
'
63
<p>These macros allow the construction of interesting <em>pattern
'
64
matching</em> like code.</p>
'
65
'
66
<p>
'
67
<pre>
'
68
(defun factorial (x)
'
69
(<b>match-case</b> (x)
'
70
(0 1)
2005-04-27 mantoniotti
71
(#T(number ?n) (* ?n (factorial (1- ?n))))
2004-11-17 mantoniotti
72
(otherwise (error "Incorrect match for ~S." x))))
22:19:54 '
73
</pre>
'
74
</p>
'
75
'
76
<p>Or consider the more interesting piece of code from a not-so
'
77
hypothetical Red-Black tree implementation (<em>cfr.</em> [<a
'
78
href="#O98">O98</a>].) The function BALANCE is the key part of the
'
79
rebalancing act played by Red-Black trees.</p>
'
80
'
81
<p>
'
82
<pre>
'
83
(defstruct (tree-node (:conc-name tn-)
'
84
(:constructor mk-tn (color left elem right)))
'
85
color
'
86
left
'
87
elem
'
88
right)
'
89
'
90
(defun balance (&rest balancing-arguments)
'
91
(<b>match-case</b> (balancing-arguments)
'
92
((:black #T(tree-node tn-color :red
'
93
tn-left #T(tree-node tn-color :red
'
94
tn-left ?a
'
95
tn-elem ?x
'
96
tn-right ?b)
'
97
tn-elem ?y
'
98
tn-right ?c)
'
99
?z
'
100
?d)
'
101
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
'
102
((:black #T(tree-node tn-color :red
'
103
tn-left ?a
'
104
tn-elem ?x
'
105
tn-right #T(tree-node tn-color :red
'
106
tn-left ?b
'
107
tn-elem ?y
'
108
tn-right ?c))
'
109
?z
'
110
?d)
'
111
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
'
112
((:black ?a
'
113
?x
'
114
#T(tree-node tn-color :red
'
115
tn-left #T(tree-node tn-color :red
'
116
tn-left ?b
'
117
tn-elem ?y
'
118
tn-right ?c)
'
119
tn-elem ?z
'
120
tn-right ?d))
'
121
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
'
122
((:black ?a
'
123
?x
'
124
#T(tree-node tn-color :red
'
125
tn-left ?b
'
126
tn-elem ?y
'
127
tn-left #T(tree-node tn-color :red
'
128
tn-left ?c
'
129
tn-elem ?z
'
130
tn-right ?d)))
'
131
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
'
132
((?color ?left ?elem ?right)
'
133
(mk-tn ?color ?left ?elem ?right))))
'
134
</pre>
'
135
</p>
'
136
'
137
<p>This version of BALANCE is more verbose than the one given in [<a
'
138
href="#O98">O98</a>], but it preserves the general elegance of the
'
139
ML implementation.</p>
'
140
'
141
'
142
'
143
<h1>Control Flow Dictionary</h1>
'
144
'
145
<ul>
'
146
<li><a href="match-macro.html"><i>Macro</i> <b>MATCH</b></a>
'
147
<li><a href="matching-macro.html"><i>Macro</i> <b>MATCHING</b></a>
'
148
<li><a href="match-case-macro.html"><i>Macro</i> <b>MATCH-CASE</b></a>
'
149
</ul>
'
150
'
151
'
152
'
153
<h1>Notes</h1>
'
154
'
155
<h2>Other Forms</h2>
'
156
'
157
<p>It would be obvious to add the macros EMATCH-CASE and
'
158
CMATCH-CASE, for symmetry with ECASE and CCASE. Also, MATCHING
'
159
could be renamed to MATCH-COND.</p>
'
160
'
161
'
162
<h2>Current Implementation Details</h2>
'
163
'
164
<p>The current implementations of MATCHING and MATCH-CASE do not
'
165
handle user supplied environments yet.</p>
'
166
'
167
'
168
<h2>References</h2>
'
169
'
170
<p>
'
171
<a name="O98">[O98]</a> C. Okasaki, <i>Purely Functional Data
'
172
Structures</i>, Cambridge University Press, 1998.
'
173
'
174
'
175
<!--
'
176
;;; Copyright (c) 2004 Marco Antoniotti, All rigths reserved.
'
177
;;;
'
178
;;; Permission to use, modify, and redistribute this code is hereby
'
179
;;; granted.
'
180
;;; The code is provided AS IS with NO warranty whatsoever. The author
'
181
;;; will not be held liable etc etc etc etc etc.
'
182
-->
'
183
'
184
<h2>Site Map</h2>
'
185
'
186
'
187
<p>Enjoy!</p>
'
188
'
189
'
190
'
191
<hr>
'
192
<p>Questions? Queries? Suggestions? Comments? Please direct them
'
193
at <a href="mailto:marcoxa_PROVA_A_SPAMMARME@alu.org">me</a>.
'
194
</p>
'
195
'
196
</div>
'
197
</div>
'
198
'
199
</td>
'
200
'
201
<!-- <td height="100%"> </td> -->
'
202
</tr>
'
203
'
204
<tr height="100%">
'
205
<td height="100%"> </td>
'
206
<td valign="top" width="80%" height="100%">
'
207
'
208
<div class="content">
'
209
<div class="text" style="padding-top: 10px;">
'
210
2011-04-02 mantoniotti
211
<!-- <h1>News</h1>
2004-11-17 mantoniotti
212
22:19:54 '
213
<p>News in chronological order, most recent on top.
'
214
</p>
'
215
'
216
<ul>
'
217
<li><strong>2004-10-30</strong><br>
'
218
Document created
'
219
</li>
'
220
</ul>
2011-04-02 mantoniotti
221
-->
04:16:51 '
222
2004-11-17 mantoniotti
223
</div>
22:19:54 '
224
</div>
'
225
'
226
</td>
'
227
'
228
<td height="100%"> </td>
'
229
</tr>
'
230
'
231
'
232
'
233
'
234
<tr>
'
235
<td colspan="3" valign="bottom" align="right">
'
236
<div class="copyright">
2011-04-02 mantoniotti
237
© 2003-2011, Marco Antoniotti, all rights reserved.
2004-11-17 mantoniotti
238
</div>
22:19:54 '
239
</td>
'
240
</tr>
'
241
'
242
</table>
'
243
</body>
'
244
</html>