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

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

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


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 constraint the terms of the license under which you release
your client program.