1 <html> 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) 71 (#T(number ?n) (* ?n (factorial (1- ?n)))) 72 (otherwise (error "Incorrect match for ~S." x)))) 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 211 <!-- <h1>News</h1> 212 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> 221 --> 222 223 </div> 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"> 237 © 2003-2011, Marco Antoniotti, all rights reserved. 238 </div> 239 </td> 240 </tr> 241 242 </table> 243 </body> 244 </html>