_Environment_ _environment_ Version 3.0 Richard Cobbe <cobbe at ccs dot neu dot edu> NOTE: Version 3 of this library requires MzScheme version 301.7 or greater. For earlier versions of MzScheme, please use version 2. I do not currently intend to add new functionality to version 2 of this library, though I will fix bugs in older versions. This collection provides one file, _environment.ss_, which implements a standard functional rib-cage environment structure. This ADT implements the `type' (Env ?a ?b), a standard functional environment that maps keys of type ?a to values of type ?b. The interface below is designed around the assumption that, in the common case, ?a = Symbol. WARNING: after you have inserted a key into an environment, you may not modify that key (as with set-car!) in a manner that is visible to the environment's equality predicate. If you do, the behavior of these operations on any environments containing the mutated keys is undefined. See the file changes.txt, included with this library, for a history of changes since version 2.0 of this library. ACKNOWLEDGEMENTS: Many thanks to Dave Herman and Ryan Culpepper for their help in working out the design issues of this interface. Dave's feedback on version 1.0 of this library was especially helpful. ====================================================================== For each provided value, I give its "type" using an odd combination of Haskell's syntax and HtDP's comment-contract notation. Particular notes: - ?a, ?b, etc denote type variables - For a list of ?a, I write (Listof ?a), rather than [?a] - Square brackets surround optional arguments - The type "Boolean*" indicates an arbitrary value that is interpreted as a boolean; "Boolean" is restricted to {#t, #f}. ====================================================================== > (make-empty-env [key-eq?]) make-empty-env :: [(?a ?a -> Boolean*)] -> (Env ?a ?b) 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 ?a) (Listof ?b) (Env ?a ?b) -> (Env ?a ?b) 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. One binding can shadow another only when the two keys are equivalent according to env's key-equality predicate. The new environment shares the unshadowed keys and values from the old environment. Rationale: the environment argument is last, by analogy with cons. This makes nested extend-env calls much easier to read. > (extend-unique keys values env) extend-unique :: (Listof ?a) (Listof ?b) (Env ?a ?b) -> (Env ?a ?b) Like extend-env, but throws an exn:env:shadow exception if either of the following occurs: - one of the new bindings shadows an existing binding in env - the same key (according to env's equality predicate) appears multiple times in keys. > (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 ?a ?b) (?a ?a -> Boolean*) -> (Env ?a ?b) 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. Weakening an environment's predicate can shadow some bindings that were visible in the original environment, but it cannot result in previously-shadowed bindings becoming visible again. The new environment shares the unshadowed keys and values from the original environment. > default-unbound-behavior default-unbound-behavior :: (Parameter (?a -> ?b)) This parameter specifies the default action that lookup and lookup/eq (below) take when the requested key is not present in the environment. The value of this parameter must be a function that expects the key as its only argument; this function may return a value, raise an exception, or return multiple values. The default value of this parameter raises an exn:env:unbound exception. > (lookup env key [fk]) lookup :: (Env ?a ?b) ?a [(?a -> ?c)] -> (Union ?b ?c) 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, lookup invokes fk in tail context, passing it the specified key. If fk is not supplied, lookup defaults to the current value of default-unbound-behavior. > (lookup/eq env key key-eq? [fk]) lookup/eq :: (Env ?a ?b) ?a (?a ?a -> Boolean*) [(?a -> ?c)] -> (Union ?b ?c) 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 :: (?b -> ?c) (Env ?a ?b) -> (Env ?a ?c) Applies f to every value in the environment's active bindings (i.e., those that are not shadowed) and produces an environment with the same equality predicate and with the results bound to the original keys (which are shared with the original environment). The order in which f is applied is unspecified. For example, (env-map f (symbol-env (a 3) (b 4))) ==> (symbol-env (a (f 3)) (b (f 4))) > (env-foldr f init env) env-foldr :: (?b ?c -> ?c) ?c (Env ?a ?b) -> ?c 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 :: (?b ?c -> ?c) ?c (Env ?a ?b) -> ?c 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 ?a ?b) ?a -> Boolean Returns #t if key is bound in env; #f otherwise. > (env-domain env) env-domain :: (Env ?a ?b) -> (Listof ?a) 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 are 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 ?a ?b) (?a -> Boolean*) -> (Env ?a ?b) 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)) All bindings in the restricted environment are shared with the original. > (env->alist env) env->alist :: (Env ?a ?b) -> (Listof (Pair ?a ?b)) 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)) The keys and values in the resulting alist are shared with the original environment. > (env->sexp env) env->sexp :: (Env ?a ?b) -> (Listof (List ?a ?b)) 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? x) env? :: ?a -> Boolean 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. > exn:env:shadow This structure type is a substructure of exn:fail:contract. The extend-unique function raises this exception if the new bindings would shadow something. It adds one additional field: - key : the identifier that would be shadowed. ====================================================================== Environment: a functional environment ADT Copyright (C) 2005,2006 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 constrain the terms of the license under which you release your client program.