1 <html> 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 165 <!-- <h1>News</h1> 166 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> 175 --> 176 </div> 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"> 190 © 2003-2011, Marco Antoniotti, all rights reserved. 191 </div> 192 </td> 193 </tr> 194 195 </table> 196 </body> 197 </html>