environments.texi (11914B)
1 @c -*-texinfo-*- 2 @setfilename ../src/environments 3 4 @node Environments, Combiners, Pairs and lists, Top 5 @comment node-name, next, previous, up 6 7 @chapter Environments 8 @cindex environments 9 @cindex ignore 10 11 An environment consists of a set of bindings, and a list of zero or 12 more references to other environments called its parents. 13 @c TODO add xref to lookup algo & ground env 14 Changing the set of bindings of an environment, or setting the 15 referent of the reference in a binding, is a mutation of the 16 environment. (Changing the parent list, or a referent in the list, 17 would be a mutation of the environment too, but there is no facility 18 provided to do it.) The Kernel data type environment is encapsulated. 19 Among other things, there is no facility provided for enumerating all 20 the variables exhibited by an environment (which is not required, 21 after all, to be a finite set), and no facility for identifying the 22 parents of an environment. Two environments are @code{equal?} iff 23 they are @code{eq?}. 24 25 An auxiliary data type used by combiners that perform binding is 26 ignore. The ignore type consists of a single immutable value, having 27 external representation @code{#ignore}. The ignore type is 28 encapsulated. 29 30 @deffn Applicative environment? (environment? . objects) 31 The primitive type predicate for type environment. 32 @code{environment?} returns true iff all the objects in @code{objects} 33 are of type environment. 34 @end deffn 35 36 @deffn Applicative ignore? (ignore? . objects) 37 The primitive type predicate for type ignore. @code{ignore?} 38 returns true iff all the objects in @code{objects} are of type ignore. 39 @end deffn 40 41 @deffn Applicative eval (eval expression environment) 42 @c TODO add xref to tail context 43 @c TODO add xref to evaluation description 44 The @code{eval} applicative evaluates @code{expression} in 45 @code{environment}, as a tail context, returning the resulting value. 46 @end deffn 47 48 @deffn Applicative make-environment (make-environment . environments) 49 The applicative constructs and returns a new environment, with 50 initially no local bindings, and parent environments the environments 51 listed in @code{environments}. The constructed environment internally 52 stores its list of parents independent of the first-class list 53 @code{environments}, so that subsequent mutation of 54 @code{environments} will not change the parentage of the constructed 55 environment. If the provided list @code{environments} is cyclic, the 56 constructed environment will still check each of its parents at most 57 once, and signal an error if no binding is found locally or in any of 58 @c TODO add xref to cons, mutation, eq? and equal? 59 the parents. No two objects returned by different calls to 60 @code{make-environment} are @code{eq?} to each other. 61 @end deffn 62 63 @deffn Operative $define! ($define! <definiend> <expression>) 64 @c TODO move formal parameter tree definition to the intro 65 @c TODO move matching definition to the intro 66 @code{<definiend>} should be a formal parameter tree, as described 67 below; otherwise, an error is signaled. 68 69 The @code{$define!} operative evaluates @code{<expression>} in the 70 dynamic environment and matches @code{<definiend>} to the result in 71 the dynamic environment, binding each symbol in definiend in the 72 dynamic environment to the corresponding part of the result; the 73 matching process will be further described below. The ancestors of the 74 dynamic environment, if any, are unaffected by the matching process, 75 as are all bindings, local to the dynamic environment, of symbols not 76 in @code{<definiend>}. The result returned by @code{$define!} is 77 inert. 78 79 A formal parameter tree has the following context-free structure: 80 @example 81 ptree:: symbol | #ignore | () | (ptree . ptree) 82 @end example 83 84 That is, a formal parameter tree is either a symbol, or ignore, or 85 nil, or a pair whose car and cdr referents are formal parameter trees. 86 A formal parameter tree must also be acyclic, and no one symbol can 87 occur more than once in it. It is not an error for a pair in the tree 88 to be reachable from the root by more than one path, as long as there 89 is no cycle; but if any particular symbol were reachable from the root 90 by more than one path, that would count as occurring more than once. 91 Thus, if a pair is reachable by more than one path, there must be no 92 symbols reachable from it. 93 94 Matching of a formal parameter tree @code{t} to an object @code{o} 95 in an environment @code{e} proceeds recursively as follows. If the 96 matching process fails, an error is signaled. 97 @itemize @bullet 98 @item 99 If @code{t} is a symbol, then @code{t} is bound to @code{o} in 100 @code{e}. 101 102 @item 103 If @code{t} is @code{#ignore}, no action is taken. 104 105 @item 106 If @code{t} is nil, then @code{o} must be nil (else matching fails). 107 108 @item 109 If @code{t} is a pair, then @code{o} must be a pair (else matching 110 fails). The car of @code{t} is matched to the car of @code{o} in 111 @code{e}, and the cdr of @code{t} is matched to the cdr of @code{o} in 112 @code{e}. 113 @end itemize 114 @end deffn 115 116 @deffn Operative $let ($let <bindings> . <objects>) 117 @c TODO add xref to formal parameter tree 118 @code{<bindings>} should be a finite list of 119 formal-parameter-tree/expression pairings, each of the form 120 @code{(formals expression)}, where each @code{formals} is a formal 121 parameter, and no symbol occurs in more than one of the 122 @code{formals}. 123 124 The following equivalence holds: 125 126 @example 127 ($let ((form1 exp1) ... (formn expn)) . objects) @equiv{} 128 (($lambda (form1 ... formn) . objects) exp1 ... expn) 129 @end example 130 131 @c TODO add xref to tail context 132 Thus, the @code{expk} are first evaluated in the dynamic environment, 133 in any order; then a child environment @code{e} of the dynamic 134 environment is created, with the @code{formk} matched in @code{e} to 135 the results of the evaluations of the @code{expk}; and finally the 136 subexpressions of @code{objects} are evaluated in @code{e} from left 137 to right, with the last (if any) evaluated as a tail context, or if 138 @code{objects} is empty the result is inert. 139 @end deffn 140 141 @deffn Operative $binds? ($binds? <exp> . <symbols>) 142 Operative @code{$binds} evaluates @code{<exp>} in the dynamic 143 environment; call the result @code{env}. @code{env} must be an 144 environment. The operative is a predicate that returns true iff all 145 its later operands, @code{<symbols>}, are visibly bound in @code{env}. 146 @end deffn 147 148 @deffn Applicative get-current-environment (get-current-environment) 149 The @code{get-current-environment} applicative returns the dynamic 150 environment in which it is called. 151 @end deffn 152 153 @deffn Applicative make-kernel-standard-environment (make-kernel-standard-environment) 154 @c TODO add xref to ground environment/standard environment 155 The @code{make-kernel-standard-environment} applicative returns a 156 standard environment; that is, a child of the ground environment with 157 no local bindings. 158 @end deffn 159 160 @deffn Operative $let* ($let* <bindings> . <body>) 161 @c TODO add xref to formal ptree 162 @code{<bindings>} should be a finite list of 163 formal-parameter-tree/expression pairings, each of the form 164 @code{(formals expression)}, where each @code{formals} is a formal 165 parameter tree; @code{<body>} should be a list of expressions. 166 167 The following equivalences hold: 168 169 @example 170 ($let* () . body) @equiv{} ($let () . body) 171 172 ($let* ((form exp) . bindings) . body) @equiv{} 173 ($let ((form exp)) ($let* bindings . body)) 174 @end example 175 @end deffn 176 177 @deffn Operative $letrec ($letrec <bindings> . <body>) 178 @c add xref for $let 179 @code{<bindings>} and @code{<body>} should be as described for 180 @code{$let}. 181 182 The following equivalence holds: 183 @example 184 ($letrec ((form1 exp1) ... (formn expn)) . body) @equiv{} 185 ($let () ($define! (form1 ... formn) (list exp1 ... expn)) . body) 186 @end example 187 @end deffn 188 189 @deffn Operative $letrec* ($letrec* <bindings> . <body>) 190 @c TODO add xref to $let* 191 @code{<bindings>} and @code{<body>} should be as described for 192 @code{$let*}. 193 194 The following equivalences hold: 195 @example 196 ($letrec* () . body) @equiv{} ($letrec () . body) 197 198 ($letrec* ((form exp) . bindings) . body) @equiv{} 199 ($letrec ((form exp)) ($letrec* bindings . body)) 200 @end example 201 @end deffn 202 203 @deffn Operative $let-redirect ($let-redirect <exp> <bindings> . <body>) 204 @c TODO add xref to $let 205 @code{<bindings>} and @code{<body>} should be as described for 206 @code{$let}. 207 208 The following equivalence holds: 209 210 @example 211 ($let-redirect exp ((form1 exp1) ... (formn . body) expn)) @equiv{} 212 ((eval (list $lambda (form1 ... formn) body) exp) expn ... expn) 213 @end example 214 @end deffn 215 216 @deffn Operative $let-safe ($let-safe <bindings> . <body>) 217 @c TODO add xref to $let 218 @code{<bindings>} and @code{<body>} should be as described for 219 @code{$let}. 220 221 The following equivalence holds: 222 223 @example 224 ($let-safe bindings . body) @equiv{} 225 ($let-redirect (make-kernel-standard-environment) bindings . body) 226 @end example 227 @end deffn 228 229 @deffn Operative $remote-eval ($remote-eval <exp1> <exp2>) 230 @c TODO add xref to tail context 231 Operative @code{$remote-eval} evaluates @code{<exp2>} in the dynamic 232 environment, then evaluates @code{<exp1>} as a tail context in the 233 environment that must result from the first evaluation. 234 @end deffn 235 236 @deffn Operative $bindings->environment ($bindings->environment . <bindings>) 237 @c TODO add xref to $let 238 @code{<bindings>} should be as described for @code{$let}. 239 240 The following equivalence holds: 241 242 @example 243 ($bindings->environment . bindings) @equiv{} 244 ($let-redirect (make-environment) bindings (get-current-environment)) 245 @end example 246 @end deffn 247 248 @deffn Applicative eval-string (eval-string string environment) 249 @code{string} should be the external representation of a single 250 object. If none or more than one external representation is found in 251 @code{string} then an error is signaled. 252 253 Applicative @code{eval-string} reads an external representation from 254 string, and evaluates the resulting object in @code{environment}, as a 255 tail context, returning the resulting value. 256 @c TODO add xref to tail context. 257 @end deffn 258 259 @deffn Operative $set! ($set! <exp1> <formals> <exp2>) 260 @c TODO add xref to $define! 261 @c TODO add xref to matching algo 262 @code{<formals>} should be as described for the @code{$define!} 263 operative. The @code{$set!} operative evaluates @code{<exp1>} and 264 @code{<exp2>} in the dynamic environment; call the results @code{env} 265 and @code{obj}. If @code{env} is not an environment, an error is 266 signaled. Then the operative matches @code{<formals>} to @code{obj} 267 in environment @code{env}. Thus, the symbols of @code{<formals>} are 268 bound in @code{env} to the corresponding parts of @code{obj}. 269 The result returned by @code{$set!} is inert. 270 @end deffn 271 272 @deffn Operative $provide! ($provide! <symbols> . <body>) 273 @code{<symbols>} must be a finite list of symbols, containing no 274 duplicates. @code{<body>} must be a finite list. 275 276 The @code{$provide!} operative constructs a child @code{e} of the 277 dynamic environment @code{d}; evaluates the elements of @code{<body>} 278 in @code{e}, from left to right, discarding all of the results; and 279 exports all of the bindings of symbols in @code{<symbols>} from 280 @code{e} to @code{d}, i.e., binds each symbol in @code{d} to the 281 result of looking it up in @code{e}. The result returned by 282 @code{$provide!} is inert. 283 284 The following equivalence holds: 285 286 @example 287 ($provide! symbols . body) @equiv{} 288 ($define! symbols ($let () ($sequence . body) (list . symbols))) 289 @end example 290 @end deffn 291 292 @deffn Operative $import! ($import! <exp> . <symbols>) 293 @code{<symbols>} must be a list of symbols. 294 295 The @code{$import!} operative evaluates @code{<exp>} in the dynamic 296 environment; call the result @code{env}. @code{env} must be an 297 environment. Each distinct symbol @code{s} in @code{<symbols>} is 298 evaluated in @code{env}, and @code{s} is bound in the dynamic 299 environment to the result of this evaluation. 300 301 The following equivalence holds: 302 303 @example 304 ($import! exp . symbols) @equiv{} 305 ($define! symbols ($remote-eval (list symbols) exp)) 306 @end example 307 @end deffn 308 309