Version 2.1
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.

See the file changes.txt, included with this library, for a history of
changes since version 2.0 of this library.


> (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

> (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.

> (extend-unique keys values env)

extend-unique :: (Listof x) (Listof y) (Env x y) -> (Env x y)

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 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 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.

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.

> (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

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 :: (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)
    (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)
    (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

> (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 "")
    (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

    (env->sexp (env [a 3] [b 4]))
    '((a 3) (b 4))

except that the order of the bindings in the resulting list is

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.

> 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  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
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.