DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT _Environment_ _environment_ Version 2.0 Richard Cobbe <cobbe at ccs dot neu dot edu> This collection provides one file, _environment.ss_, which implements a standard functional rib-cage environment structure. This ADT implements the `type' (Env x y), a standard functional environment that maps keys of type x to values of type y. The interface below is designed around the assumption that, in the common case, x = Symbol. WARNING: do not mutate the keys (as with set-car!) once they have been inserted into the environment. If you do, the behavior of these operations on any environments containing the mutated keys is undefined. ====================================================================== > (make-empty-env [key-eq?]) make-empty-env :: (x x -> Boolean) -> (Env x y) Creates an environment with no bindings. The optional argument is used as the equality predicate on the keys; it defaults to eq? if it is not specified. The relation implied by this function should be an equivalence relation; the behavior of the resulting environment is undefined otherwise. > (extend-env keys values env) extend-env :: (Listof x) (Listof y) (Env x y) -> (Env x y) Returns a new environment containing all bindings in env, but extended with the specified bindings. For example, (extend-env '(a b) '(3 4) (make-empty-env)) produces an environment in which 'a is bound to 3 and 'b is bound to 4. The bindings added by this function shadow those in env, as one would expect, and bindings earlier in the argument lists shadow those later in the same lists. > (env key-eq? (key val) ...) This macro creates an environment that uses key-eq? as its equality predicate and contains exactly the specified bindings. As with extend-env, earlier keys shadow later ones. > (symbol-env (key val) ...) This macro is a variant of env (defined above) that is intended for the common case where the keys are symbols. As such, it uses the eq? primitive as its equality predicate and implicitly quotes the keys. > (weaken-env env key-eq?) weaken-env :: (Env x y) (x x -> Boolean) -> (Env x y) Returns a copy of env but with the new equality predicate. The new equality predicate must be coarser than the old one. That is, if two keys are equal under env's predicate, then they must be equal under key-eq? as well. If the supplied predicate does not satisfy this condition, then operations on the weakened environment may raise exn:fail:contract. Note that weakening the predicate can shadow some bindings that were visible in the original environment, but it cannot result in previously-shadowed bindings becoming visible again. > (lookup env key [fk]) lookup :: (Env x y) x (-> z) -> (Union y z) Looks up the identifier key in env, using the environment's equality predicate to compare the supplied key with those in the environment. If the key is not found, invokes the thunk fk in tail context. The default fk raises an exn:env:unbound exception. > (lookup/eq env key key-eq? [fk]) lookup/eq :: (Env x y) x (x x -> Boolean) (-> z) -> (Union y z) A convenience function, equivalent to (lookup (weaken-env env key-eq?) key fk). Note that weaken-env's restriction on the new equality predicate also applies here. > (env-map f env) env-map :: (y -> z) (Env x y) -> (Env x z) Applies f to every value in the environment's active bindings (i.e., those that are not shadowed) and produces an environment with the results bound to the original identifiers. The order in which f is applied is unspecified. For example, (env-map f (env (a 3) (b 4))) ==> (env (a (f 3)) (b (f 4))) > (env-foldr f init env) env-foldr :: (y z -> z) z (Env x y) -> z This is right-to-left fold for environments. It applies the function f to each value in the environment and the accumulator, in reverse scope order. That is, earliest `rib' first, then right-to-left within each rib, but skipping shadowed bindings. (Here, a `rib' consists of all of the bindings added by a single call to extend-env; similarly, all of the bindings in an application of the env macro constitute a single rib.) So, for example, (env-foldr cons null (extend-env '(c b d c) '(3 4 5 6) (extend-env '(a b) '(1 2) (make-empty-env))))) ===> (list 3 4 5 1) > (env-foldl f init env) env-foldl :: (y z -> z) z (Env x y) -> z Same as env-foldr, but applies f to the bindings in the environment in the opposite order. Therefore, (env-foldl cons null (extend-env '(c b d c) '(3 4 5 6) (extend-env '(a b) '(1 2) (make-empty-env)))) ===> (list 1 5 4 3) > (bound? env key) bound? :: (Env x y) x -> Boolean Returns #t if key is bound in env; #f otherwise. > (env-domain env) env-domain :: (Env x y) -> (Listof x) Returns a list containing all identifiers bound in env. The list will not contain any duplicates (according to the environment's equality predicate), but the order of the identifiers in the list is not specified. The elements in this list may or may not be shared by the environment itself, so they are subject to the warning above about not mutating keys in an environment. You may modify the structure of the list (i.e., set-car! and set-cdr!) at your discretion; this will not affect the original environment. > (restrict-domain env pred) restrict-domain :: (Env x y) (x -> Boolean) -> (Env x y) Returns a copy of env with domain restricted restricted to that subset of env's domain for which pred holds. That is, the following two lists will have the same elements in some order, where `same' is defined by the environment's equality predicate: (filter pred (env-domain env)) ;; filter as in (lib "list.ss") (env-domain (restrict-domain env pred)) > (env->sexp env) env->sexp :: (Env x y) -> (Listof (List x y)) This function converts the environment env to an S-expression representation that contains all of env's (unshadowed) bindings. For example, (env->sexp (env [a 3] [b 4])) ===> '((a 3) (b 4)) except that the order of the bindings in the resulting list is unspecified. This is useful for debugging and testing. This is the reason for the departure from the standard association-list representation, incidentally. I personally find it extremely confusing that the dot magically disappears if the value in an alist binding happens to be a list. > (env->alist env) This function converts the environment env to an association list that contains all of env's (unshadowed) bindings, in some order. So, (env->alist (env [a 3] [b 4])) ===> '((a . 3) (b . 4)) > (env? x) Returns #t if its argument is an environment---that is, it was constructed with make-empty-env, extend-env, env, or symbol-env. > exn:env:unbound This structure type (a substructure of exn:fail:contract) is used as an exception to signal an unbound identifier in an environment. It adds one additional field: - key : the unbound identifier. ====================================================================== Environment: a functional environment ADT Copyright (C) 2005 Richard Cobbe This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Clarification: I consider that simply using this library as a client, by specifying its PLaneT module path in a require clause, is "mere aggregation" according to the terms of the GNU LGPL, and therefore this usage does not constraint the terms of the license under which you release your client program. DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT DRAFT