Environment

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