guile/doc/sources/env.texi

\input texinfo   @c -*-texinfo-*-
@c %**start of header
@setfilename env.info
@settitle Top-level Environments in Guile
@c %**end of header

@setchapternewpage odd

@c Changes since Jost's implementation:
@c "finite environments" -> "leaf environments"
@c "scm_foo_internal" -> "scm_c_foo"

@c To do:
@c add spec for soft environments

@c When merged into the main manual, add cross-references for:
@c weak references
@c smobs (esp. module's mark and free functions)


[[add refs for all conditions signalled]]

@ifinfo
Copyright 1999, 2006 Free Software Foundation, Inc.
@end ifinfo

@titlepage
@sp 10
@comment The title is printed in a large font.
@center @titlefont{Top-level Environments in Guile}

@c The following two commands start the copyright page.
@page
@vskip 0pt plus 1filll
Copyright @copyright{} 1999, 2006 Free Software Foundation, Inc.
@end titlepage

@node    Top, Motivation, (dir), (dir)

@menu
* Motivation::                  
* Top-Level Environments in Guile::  
* Modules::                     
@end menu

@node Motivation, Top-Level Environments in Guile, Top, Top
@chapter Motivation

@example
$Id: env.texi,v 1.1.10.1 2006-02-12 13:42:50 mvo Exp $
@end example

This is a draft proposal for a new datatype for representing top-level
environments in Guile.  Upon completion, this proposal will be posted to
the mailing list @samp{guile@@cygnus.com} for discussion, revised in
light of whatever insights that may produce, and eventually implemented.

Note that this is @emph{not} a proposal for a module system; rather, it
is a proposal for a data structure which encapsulates the ideas one
needs when writing a module system, and, most importantly, a fixed
interface which insulates the interpreter from the details of the module
system.  Using these environments, one could implement any module system
one pleased, without changing the interpreter.

I hope this text will eventually become a chapter of the Guile manual;
thus, the description of environments in written in the present tense,
as if it were already implemented, not in the future tense.  However,
this text does not actually describe the present state of Guile.

I'm especially interested in improving the vague, rambling presentation
of environments in the section "Modules and Environments".  I'm trying
to orient the user for the discussion that follows, but I wonder if I'm
just confusing the issue.  I would appreciate suggestions if they are
concrete --- please provide new wording.

Note also: I'm trying out a convention I'm considering for use in the
manual.  When a Scheme procedure which is directly implemented by a C
procedure, and both are useful to call from their respective languages,
we document the Scheme procedure only, and call it a "Primitive".  If a
Scheme function is marked as a primitive, you can derive the name of the
corresponding C function by changing @code{-} to @code{_}, @code{!} to
@code{_x}, @code{?} to @code{_p}, and prepending @code{scm_}.  The C
function's arguments will be all of the Scheme procedure's argumements,
both required and optional; if the Scheme procedure takes a ``rest''
argument, that will be a final argument to the C function.  The C
function's arguments, as well as its return type, will be @code{SCM}.
Thus, a procedure documented like this:
@deffn Primitive set-car! pair value
@end deffn

has a corresponding C function which would be documented like this:
@deftypefn {Libguile function} SCM scm_set_car_x (SCM @var{pair}, SCM @var{value})
@end deftypefn

The hope is that this will be an uncluttered way to document both the C
and Scheme interfaces, without unduly confusing users interested only in
the Scheme level.

When there is a C function which provides the same functionality as a
primitive, but with a different interface tailored for C's needs, it
usually has the same name as the primitive's C function, but with the
prefix @code{scm_c_} instead of simply @code{scm_}.  Thus,
@code{scm_c_environment_ref} is almost identical to
@code{scm_environment_ref}, except that it indicates an unbound variable
in a manner friendlier to C code.



@node    Top-Level Environments in Guile, Modules, Motivation, Top
@chapter Top-Level Environments in Guile

In Guile, an environment is a mapping from symbols onto variables, and
a variable is a location containing a value.  Guile uses the datatype
described here to represent its top-level environments.


@menu
* Modules and Environments::    Modules are environments, with bookkeeping.
* Common Environment Operations::  Looking up bindings, creating bindings, etc.
* Standard Environment Types::  Guile has some fundamental environment types.
* Implementing Environments::   You can extend Guile with new kinds of
                                environments.
* Switching to Environments::   Changes needed to today's Guile to
                                implement the features described here.
@end menu

@node Modules and Environments, Common Environment Operations, Top-Level Environments in Guile, Top-Level Environments in Guile
@section Modules and Environments

Guile distinguishes between environments and modules.  A module is a
unit of code sharing; it has a name, like @code{(math random)}, an
implementation (e.g., Scheme source code, a dynamically linked library,
or a set of primitives built into Guile), and finally, an environment
containing the definitions which the module exports for its users.

An environment, by contrast, is simply an abstract data type
representing a mapping from symbols onto variables which the Guile
interpreter uses to look up top-level definitions.  The @code{eval}
procedure interprets its first argument, an expression, in the context
of its second argument, an environment.

Guile uses environments to implement its module system.  A module
created by loading Scheme code might be built from several environments.
In addition to the environment of exported definitions, such a module
might have an internal top-level environment, containing both exported
and private definitions, and perhaps environments for imported
definitions alone and local definitions alone.

The interface described here includes a full set of functions for
mutating environments, and the system goes to some length to maintain
its consistency as environments' bindings change.  This is necessary
because Guile is an interactive system.  The user may create new
definitions or modify and reload modules while Guile is running; the
system should handle these changes in a consistent and predictable way.

A typical Guile system will have several distinct top-level
environments.  (This is why we call them ``top-level'', and not
``global''.)  For example, consider the following fragment of an
interactive Guile session:

@example
guile> (use-modules (ice-9 regex))
guile> (define pattern "^(..+)\\1+$")
guile> (string-match pattern "xxxx")
#("xxxx" (0 . 4) (0 . 2))
guile> (string-match pattern "xxxxx")
#f
guile> 
@end example
@noindent
Guile evaluates the expressions the user types in a top-level
environment reserved for that purpose; the definition of @code{pattern}
goes there.  That environment is distinct from the one holding the
private definitions of the @code{(ice-9 regex)} module.  At the Guile
prompt, the user does not see the module's private definitions, and the
module is unaffected by definitions the user makes at the prompt.  The
@code{use-modules} form copies the module's public bindings into the
user's environment.

All Scheme evaluation takes place with respect to some top-level
environment.  Just as the procedure created by a @code{lambda} form
closes over any local scopes surrounding that form, it also closes over
the surrounding top-level environment.  Thus, since the
@code{string-match} procedure is defined in the @code{(ice-9 regex)}
module, it closes over that module's top-level environment.  Thus, when
the user calls @code{string-match} from the Guile prompt, any free
variables in @code{string-match}'s definition are resolved with respect
to the module's top-level environment, not the user's.

Although the Guile interaction loop maintains a ``current'' top-level
environment in which it evaluates the user's input, it would be
misleading to extend the concept of a ``current top-level environment''
to the system as a whole.  Each procedure closes over its own top-level
environment, in which that procedure will find bindings for its free
variables.  Thus, the top-level environment in force at any given time
depends on the procedure Guile happens to be executing.  The global
``current'' environment is a figment of the interaction loop's
imagination.

Since environments provide all the operations the Guile interpreter
needs to evaluate code, they effectively insulate the interpreter from
the details of the module system.  Without changing the interpreter, you
can implement any module system you like, as long as its efforts produce
an environment object the interpreter can consult.

Finally, environments may prove a convenient way for Guile to access the
features of other systems.  For example, one might export the The GIMP's
Procedural Database to Guile as a custom environment type; this
environment could create Scheme procedure objects corresponding to GIMP
procedures, as the user referenced them.


@node Common Environment Operations, Standard Environment Types, Modules and Environments, Top-Level Environments in Guile
@section Common Environment Operations

This section describes the common set of operations that all environment
objects support.  To create an environment object, or to perform an
operation specific to a particular kind of environment, see
@ref{Standard Environment Types}.

In this section, the following names for formal parameters imply that
the actual parameters must have a certain type:

@table @var

@item env
an environment

@item symbol
a symbol

@item proc
a procedure

@item value
@itemx object
an arbitrary Scheme value

@end table


@menu
* Examining Environments::      
* Changing Environments::       
* Caching Environment Lookups::  
* Observing Changes to Environments ::  
* Environment Errors::          
@end menu

@node Examining Environments, Changing Environments, Common Environment Operations, Common Environment Operations
@subsection Examining Environments

@deffn Primitive environment? object
Return @code{#t} if @var{object} is an environment, or @code{#f} otherwise.
@end deffn

@deffn Primitive environment-ref env symbol
Return the value of the location bound to @var{symbol} in @var{env}.
If @var{symbol} is unbound in @var{env}, signal an @code{environment:unbound}
error (@pxref{Environment Errors}).
@end deffn

@deffn Primitive environment-bound? env symbol
Return @code{#t} if @var{symbol} is bound in @var{env}, or @code{#f}
otherwise.
@end deffn

@deffn Primitive environment-fold env proc init
Iterate over all the bindings in an environment, accumulating some value.

For each binding in @var{env}, apply @var{proc} to the symbol bound, its
value, and the result from the previous application of @var{proc}.  Use
@var{init} as @var{proc}'s third argument the first time @var{proc} is
applied.

If @var{env} contains no bindings, this function simply returns @var{init}.

If @var{env} binds the symbol @var{sym1} to the value @var{val1},
@var{sym2} to @var{val2}, and so on, then this procedure computes:
@example
(@var{proc} @var{sym1} @var{val1}
      (@var{proc} @var{sym2} @var{val2}
            ...
            (@var{proc} @var{symn} @var{valn}
                  @var{init})))
@end example

Each binding in @var{env} is processed at most once.
@code{environment-fold} makes no guarantees about the order in which the
bindings are processed.

If @var{env} is not modified while the iteration is taking place,
@code{environment-fold} will apply @var{proc} to each binding in
@var{env} exactly once.

If @var{env} is modified while the iteration is taking place, we need to
be more subtle in describing @code{environment-fold}'s behavior.
@code{environment-fold} repeatedly applies @var{proc} to a binding which
was present in @var{env} when @code{environment-fold} was invoked and is
still present in @var{env}, until there are no such bindings remaining.
(If no mutations take place, this definition is equivalent to the
simpler one given above.)  By this definition, bindings added during the
iteration will not be passed to @var{proc}.

Here is a function which, given an environment, constructs an
association list representing that environment's bindings, using
@code{environment-fold}:
@example
(define (environment->alist env)
  (environment-fold env
                    (lambda (sym val tail)
                      (cons (cons sym val) tail))
                    '()))
@end example
@end deffn

@deftypefn {Libguile macro} int SCM_ENVP (@var{object})
Return non-zero if @var{object} is an environment.
@end deftypefn

@deftypefn {Libguile function} SCM scm_c_environment_ref (SCM @var{env}, SCM @var{symbol})
This C function is identical to @code{environment-ref}, except that if
@var{symbol} is unbound in @var{env}, it returns the value
@code{SCM_UNDEFINED}, instead of signalling an error.
@end deftypefn

@deftypefn {Libguile function} SCM scm_c_environment_fold (SCM @var{env}, scm_environment_folder *@var{proc}, SCM @var{data}, SCM @var{init})
This is the C-level analog of @code{environment-fold}.  For each binding in
@var{env}, make the call:
@example
(*@var{proc}) (@var{data}, @var{symbol}, @var{value}, @var{previous})
@end example
@noindent
where @var{previous} is the value returned from the last call to
@code{*@var{proc}}, or @var{init} for the first call.  If @var{env}
contains no bindings, return @var{init}.
@end deftypefn

@deftp {Libguile data type} scm_environment_folder SCM (SCM @var{data}, SCM @var{symbol}, SCM @var{value}, SCM @var{tail})
The type of a folding function to pass to @code{scm_c_environment_fold}.
@end deftp


@node Changing Environments, Caching Environment Lookups, Examining Environments, Common Environment Operations
@subsection Changing Environments

Here are functions for changing symbols' bindings and values.

Although it is common to say that an environment binds a symbol to a
value, this is not quite accurate; an environment binds a symbol to a
location, and the location contains a value.  In the descriptions below,
we will try to make clear how each function affects bindings and
locations.

Note that some environments may contain some immutable bindings, or may
bind symbols to immutable locations.  If you attempt to change an
immutable binding or value, these functions will signal an
@code{environment:immutable-binding} or
@code{environment:immutable-location} error.  However, simply because a
binding cannot be changed via these functions does @emph{not} imply that
it is constant.  Mechanisms outside the scope of this section (say,
re-loading a module's source code) may change a binding or value which
is immutable via these functions.

@deffn Primitive environment-define env symbol value
Bind @var{symbol} to a new location containing @var{value} in @var{env}.
If @var{symbol} is already bound to another location in @var{env}, that
binding is replaced.  The new binding and location are both mutable.
The return value is unspecified.

If @var{symbol} is already bound in @var{env}, and the binding is
immutable, signal an @code{environment:immutable-binding} error.
@end deffn

@deffn Primitive environment-undefine env symbol
Remove any binding for @var{symbol} from @var{env}.  If @var{symbol} is
unbound in @var{env}, do nothing.  The return value is unspecified.

If @var{symbol} is already bound in @var{env}, and the binding is
immutable, signal an @code{environment:immutable-binding} error.
@end deffn

@deffn Primitive environment-set! env symbol value
If @var{env} binds @var{symbol} to some location, change that location's
value to @var{value}.  The return value is unspecified.

If @var{symbol} is not bound in @var{env}, signal an
@code{environment:unbound} error.  If @var{env} binds @var{symbol} to an
immutable location, signal an @code{environment:immutable-location}
error.
@end deffn


@node Caching Environment Lookups, Observing Changes to Environments , Changing Environments, Common Environment Operations
@subsection Caching Environment Lookups

Some applications refer to variables' values so frequently that the
overhead of @code{environment-ref} and @code{environment-set!} is
unacceptable.  For example, variable reference speed is a critical
factor in the performance of the Guile interpreter itself.  If an
application can tolerate some additional complexity, the
@code{environment-cell} function described here can provide very
efficient access to variable values.

In the Guile interpreter, most variables are represented by pairs; the
@sc{cdr} of the pair holds the variable's value.  Thus, a variable
reference corresponds to taking the @sc{cdr} of one of these pairs, and
setting a variable corresponds to a @code{set-cdr!} operation.  A pair
used to represent a variable's value in this manner is called a
@dfn{value cell}.  Value cells represent the ``locations'' to which
environments bind symbols.

The @code{environment-cell} function returns the value cell bound to a
symbol.  For example, an interpreter might make the call
@code{(environment-cell @var{env} @var{symbol} #t)} to find the value
cell which @var{env} binds to @var{symbol}, and then use @code{cdr} and
@code{set-cdr!} to reference and assign to that variable, instead of
calling @code{environment-ref} or @var{environment-set!} for each
variable reference.

There are a few caveats that apply here:

@itemize @bullet

@item
Environments are not required to represent variables' values using value
cells.  An environment is free to return @code{#f} in response to a
request for a symbol's value cell; in this case, the caller must use
@code{environment-ref} and @code{environment-set!} to manipulate the
variable.

@item
An environment's binding for a symbol may change.  For example, the user
could override an imported variable with a local definition, associating
a new value cell with that symbol.  If an interpreter has used
@code{environment-cell} to obtain the variable's value cell, it no
longer needs to use @code{environment-ref} and @code{environment-set!}
to access the variable, and it may not see the new binding.

Thus, code which uses @code{environment-cell} should almost always use
@code{environment-observe} to track changes to the symbol's binding;
this is the additional complexity hinted at above.  @xref{Observing
Changes to Environments}.

@item
Some variables should be immutable.  If a program uses
@code{environment-cell} to obtain the value cell of such a variable,
then it is impossible for the environment to prevent the program from
changing the variable's value, using @code{set-cdr!}.  However, this is
discouraged; it is probably better to redesign the interface than to
disregard such a request.  To make it easy for programs to honor the
immutability of a variable, @code{environment-cell} takes an argument
indicating whether the caller intends to mutate the cell's value; if
this argument is true, then @code{environment-cell} signals an
@code{environment:immutable-location} error.

Programs should therefore make separate calls to @code{environment-cell}
to obtain value cells for reference and for assignment.  It is incorrect
for a program to call @code{environment-cell} once to obtain a value
cell, and then use that cell for both reference and mutation.

@end itemize

@deffn Primitive environment-cell env symbol for-write
Return the value cell which @var{env} binds to @var{symbol}, or
@code{#f} if the binding does not live in a value cell.

The argument @var{for-write} indicates whether the caller intends to
modify the variable's value by mutating the value cell.  If the variable
is immutable, then @code{environment-cell} signals an
@code{environment:immutable-location} error.

If @var{symbol} is unbound in @var{env}, signal an @code{environment:unbound}
error.

If you use this function, you should consider using
@code{environment-observe}, to be notified when @code{symbol} gets
re-bound to a new value cell, or becomes undefined.
@end deffn

@deftypefn {Libguile function} SCM scm_c_environment_cell (SCM @var{env}, SCM @var{symbol}, int for_write)
This C function is identical to @code{environment-cell}, except that if
@var{symbol} is unbound in @var{env}, it returns the value
@code{SCM_UNDEFINED}, instead of signalling an error.
@end deftypefn

[[After we have some experience using this, we may find that we want to
be able to explicitly ask questions like, "Is this variable mutable?"
without the annoyance of error handling.  But maybe this is fine.]]


@node Observing Changes to Environments , Environment Errors, Caching Environment Lookups, Common Environment Operations
@subsection Observing Changes to Environments 

The procedures described here allow you to add and remove @dfn{observing
procedures} for an environment.


@menu
* Registering Observing Procedures::  
* Observations and Garbage Collection::  
* Observing Environments from C Code::  
@end menu

@node Registering Observing Procedures, Observations and Garbage Collection, Observing Changes to Environments , Observing Changes to Environments
@subsubsection Registering Observing Procedures

A program may register an @dfn{observing procedure} for an environment,
which will be called whenever a binding in a particular environment
changes.  For example, if the user changes a module's source code and
re-loads the module, other parts of the system may want to throw away
information they have cached about the bindings of the older version of
the module.  To support this, each environment retains a set of
observing procedures which it will invoke whenever its bindings change.
We say that these procedures @dfn{observe} the environment's bindings.
You can register new observing procedures for an environment using
@code{environment-observe}.

@deffn Primitive environment-observe env proc
Whenever @var{env}'s bindings change, apply @var{proc} to @var{env}.

This function returns an object, @var{token}, which you can pass to
@code{environment-unobserve} to remove @var{proc} from the set of
procedures observing @var{env}.  The type and value of @var{token} is
unspecified.
@end deffn

@deffn Primitive environment-unobserve token
Cancel the observation request which returned the value @var{token}.
The return value is unspecified.

If a call @code{(environment-observe @var{env} @var{proc})} returns
@var{token}, then the call @code{(environment-unobserve @var{token})}
will cause @var{proc} to no longer be called when @var{env}'s bindings
change.
@end deffn

There are some limitations on observation:
@itemize @bullet
@item
These procedures do not allow you to observe specific bindings; you
can only observe an entire environment.
@item
These procedures observe bindings, not locations.  There is no way
to receive notification when a location's value changes, using these
procedures.
@item
These procedures do not promise to call the observing procedure for each
individual binding change.  However, if multiple bindings do change
between calls to the observing procedure, those changes will appear
atomic to the entire system, not just to a few observing procedures.
@item
Since a single environment may have several procedures observing it, a
correct design obviously may not assume that nothing else in the system
has yet observed a given change.
@end itemize

(One weakness of this observation architecture is that observing
procedures make no promises to the observer.  That's fine if you're just
trying to implement an accurate cache, but too weak to implement things
that walk the environment tree.)

@node Observations and Garbage Collection, Observing Environments from C Code, Registering Observing Procedures, Observing Changes to Environments
@subsubsection Observations and Garbage Collection

When writing observing procedures, pay close attention to garbage
collection issues.  If you use @code{environment-observe} to register
observing procedures for an environment, the environment will hold a
reference to those procedures; while that environment is alive, its
observing procedures will live, as will any data they close over.  If
this is not appropriate, you can use the @code{environment-observe-weak}
procedure to create a weak reference from the environment to the
observing procedure.

For example, suppose an interpreter uses @code{environment-cell} to
reference variables efficiently, as described above in @ref{Caching
Environment Lookups}.  That interpreter must register observing
procedures to track changes to the environment.  If those procedures
retain any reference to the data structure representing the program
being interpreted, then that structure cannot be collected as long as
the observed environment lives.  This is almost certainly incorrect ---
if there are no other references to the structure, it can never be
invoked, so it should be collected.  In this case, the interpreter
should register its observing procedure using
@code{environment-observe-weak}, and retain a pointer to it from the
code it updates.  Thus, when the code is no longer referenced elsewhere
in the system, the weak link will be broken, and Guile will collect the
code (and its observing procedure).

@deffn Primitive environment-observe-weak env proc
This function is the same as @code{environment-observe}, except that the
reference @var{env} retains to @var{proc} is a weak reference.  This
means that, if there are no other live, non-weak references to
@var{proc}, it will be garbage-collected, and dropped from @var{env}'s
list of observing procedures.
@end deffn


@node Observing Environments from C Code,  , Observations and Garbage Collection, Observing Changes to Environments
@subsubsection Observing Environments from C Code

It is also possible to write code that observes an environment in C.
The @code{scm_c_environment_observe} function registers a C
function to observe an environment.  The typedef
@code{scm_environment_observer} is the type a C observer function must
have.

@deftypefn {Libguile function} SCM scm_c_environment_observe (SCM @var{env}, scm_environment_observer *proc, SCM @var{data}, int weak_p)
This is the C-level analog of the Scheme function
@code{environment-observe}.  Whenever @var{env}'s bindings change, call
the function @var{proc}, passing it @var{env} and @var{data}.  If
@var{weak_p} is non-zero, @var{env} will retain only a weak reference to
@var{data}, and if @var{data} is garbage collected, the entire
observation will be dropped.

This function returns a token, with the same meaning as those returned
by @code{environment-observe}.
@end deftypefn

@deftp {Libguile data type} scm_environment_observer void (SCM @var{env}, SCM @var{data})
The type for observing functions written in C.  A function meant to be
passed to @code{scm_c_environment_observe} should have the type
@code{scm_environment_observer}.
@end deftp

Note that, like all other primitives, @code{environment-observe} is also
available from C, under the name @code{scm_environment_observe}.


@node Environment Errors,  , Observing Changes to Environments , Common Environment Operations
@subsection Environment Errors

Here are the error conditions signalled by the environment routines
described above.  In these conditions, @var{func} is a string naming a
particular procedure.

@deffn Condition environment:unbound func message args env symbol
By calling @var{func}, the program attempted to retrieve the value of
@var{symbol} in @var{env}, but @var{symbol} is unbound in @var{env}.
@end deffn

@deffn Condition environment:immutable-binding func message args env symbol
By calling @var{func}, the program attempted to change the binding of
@var{symbol} in @var{env}, but that binding is immutable.
@end deffn

@deffn Condition environment:immutable-location func message args env symbol
By calling @var{func}, the program attempted to change the value of
the location to which @var{symbol} is bound in @var{env}, but that
location is immutable.
@end deffn


@node Standard Environment Types, Implementing Environments, Common Environment Operations, Top-Level Environments in Guile
@section Standard Environment Types

Guile supports several different kinds of environments.  The operations
described above are actually only the common functionality provided by
all the members of a family of environment types, each designed for a
separate purpose.

Each environment type has a constructor procedure for building elements
of that type, and extends the set of common operations with its own
procedures, providing specialized functions.  For an example of how
these environment types work together, see @ref{Modules of Interpreted
Scheme Code}.

Guile allows users to define their own environment types.  Given a set
of procedures that implement the common environment operations, Guile
will construct a new environment object based on those procedures.

@menu
* Leaf Environments::           A simple set of bindings.
* Eval Environments::           Local definitions, shadowing
                                        imported definitions.
* Import Environments::         The union of a list of environments.
* Export Environments::         A selected subset of an environment.
* General Environments::        Environments implemented by user
                                        functions.
@end menu

@node Leaf Environments, Eval Environments, Standard Environment Types, Standard Environment Types
@subsection Leaf Environments

A @dfn{leaf} environment is simply a mutable set of definitions.  A mutable
environment supports no operations beyond the common set.  

@deffn Primitive make-leaf-environment
Create a new leaf environment, containing no bindings.  All bindings
and locations in the new environment are mutable.
@end deffn

@deffn Primitive leaf-environment? object
Return @code{#t} if @var{object} is a leaf environment, or @var{#f}
otherwise.
@end deffn


In Guile, each module of interpreted Scheme code uses a leaf
environment to hold the definitions made in that module.

Leaf environments are so named because their bindings are not computed
from the contents of other environments.  Most other environment types
have no bindings of their own, but compute their binding sets based on
those of their operand environments.  Thus, the environments in a
running Guile system form a tree, with interior nodes computing their
contents from their child nodes.  Leaf environments are the leaves of
such trees.


@node Eval Environments, Import Environments, Leaf Environments, Standard Environment Types
@subsection Eval Environments

A module's source code refers to definitions imported from other
modules, and definitions made within itself.  An @dfn{eval} environment
combines two environments --- a @dfn{local} environment and an
@dfn{imported} environment --- to produce a new environment in which
both sorts of references can be resolved.

@deffn Primitive make-eval-environment local imported
Return a new environment object @var{eval} whose bindings are the union
of the bindings in the environments @var{local} and @var{imported}, with
bindings from @var{local} taking precedence.  Definitions made in
@var{eval} are placed in @var{local}.

Applying @code{environment-define} or @code{environment-undefine} to
@var{eval} has the same effect as applying the procedure to @var{local}.
This means that applying @code{environment-undefine} to a symbol bound
in @var{imported} and free in @var{local} has no effect on the bindings
visible in @var{eval}, which may be surprising.

Note that @var{eval} incorporates @var{local} and @var{imported}
@emph{by reference} --- if, after creating @var{eval}, the program
changes the bindings of @var{local} or @var{imported}, those changes
will be visible in @var{eval}.

Since most Scheme evaluation takes place in @var{eval} environments,
they transparenty cache the bindings received from @var{local} and
@var{imported}.  Thus, the first time the program looks up a symbol in
@var{eval}, @var{eval} may make calls to @var{local} or @var{imported}
to find their bindings, but subsequent references to that symbol will be
as fast as references to bindings in leaf environments.

In typical use, @var{local} will be a leaf environment, and
@var{imported} will be an import environment, described below.
@end deffn

@deffn Primitive eval-environment? object
Return @code{#t} if @var{object} is an eval environment, or @code{#f}
otherwise.
@end deffn

@deffn Primitive eval-environment-local env
@deffnx Primitive eval-environment-imported env
Return the @var{local} or @var{imported} environment of @var{env};
@var{env} must be an eval environment.
@end deffn


@node Import Environments, Export Environments, Eval Environments, Standard Environment Types
@subsection Import Environments

An @dfn{import} environment combines the bindings of a set of
argument environments, and checks for naming clashes.

@deffn Primitive make-import-environment imports conflict-proc
Return a new environment @var{imp} whose bindings are the union of the
bindings from the environments in @var{imports}; @var{imports} must be a
list of environments.  That is, @var{imp} binds @var{symbol} to
@var{location} when some element of @var{imports} does.

If two different elements of @var{imports} have a binding for the same
symbol, apply @var{conflict-proc} to the two environments.  If the bindings
of any of the @var{imports} ever changes, check for conflicts again.

All bindings in @var{imp} are immutable.  If you apply
@code{environment-define} or @code{environment-undefine} to @var{imp},
Guile will signal an @code{environment:immutable-binding} error.
However, notice that the set of bindings in @var{imp} may still change,
if one of its imported environments changes.
@end deffn

@deffn Primitive import-environment? object
Return @code{#t} if @var{object} is an import environment, or @code{#f}
otherwise.
@end deffn

@deffn Primitive import-environment-imports env
Return the list of @var{env}'s imported environments; @var{env} must be
an import env.
@end deffn

@deffn Primitive import-environment-set-imports! env imports
Change @var{env}'s list of imported environments to @var{imports}, and
check for conflicts.
@end deffn

I'm not at all sure about the way @var{conflict-proc} works.  I think
module systems should warn you if it seems you're likely to get the
wrong binding, but exactly how and when those warnings should be
generated, I don't know.


@node Export Environments, General Environments, Import Environments, Standard Environment Types
@subsection Export Environments

An export environment restricts an environment a specified set of
bindings.

@deffn Primitive make-export-environment private signature
Return a new environment @var{exp} containing only those bindings in
@var{private} whose symbols are present in @var{signature}.  The
@var{private} argument must be an environment.

The environment @var{exp} binds @var{symbol} to @var{location} when
@var{env} does, and @var{symbol} is exported by @var{signature}.

@var{Signature} is a list specifying which of the bindings in
@var{private} should be visible in @var{exp}.  Each element of
@var{signature} should be a list of the form:
@example
(@var{symbol} @var{attribute} ...)
@end example
@noindent
where each @var{attribute} is one of the following:
@table @asis
@item the symbol @code{mutable-location}
@var{exp} should treat the location bound to @var{symbol} as mutable.
That is, @var{exp} will pass calls to @var{env-set!} or
@code{environment-cell} directly through to @var{private}.

@item the symbol @code{immutable-location}
@var{exp} should treat the location bound to @var{symbol} as immutable.
If the program applies @code{environment-set!} to @var{exp} and
@var{symbol}, or calls @code{environment-cell} to obtain a writable
value cell, @code{environment-set!}  will signal an
@code{environment:immutable-location} error.

Note that, even if an export environment treats a location as immutable,
the underlying environment may treat it as mutable, so its value may
change.
@end table

It is an error for an element of @var{signature} to specify both
@code{mutable-location} and @code{immutable-location}.  If neither is
specified, @code{immutable-location} is assumed.

As a special case, if an element of @var{signature} is a lone symbol
@var{sym}, it is equivalent to an element of the form
@code{(@var{sym})}.

All bindings in @var{exp} are immutable.  If you apply
@code{environment-define} or @code{environment-undefine} to @var{exp},
Guile will signal an @code{environment:immutable-binding} error.
However, notice that the set of bindings in @var{exp} may still change,
if the bindings in @var{private} change.
@end deffn

@deffn Primitive export-environment? object
Return @code{#t} if @var{object} is an export environment, or @code{#f}
otherwise.
@end deffn

@deffn Primitive export-environment-private env
@deffnx Primitive export-environment-set-private! env 
@deffnx Primitive export-environment-signature env
@deffnx Primitive export-environment-set-signature! env
Accessors and mutators for the private environment and signature of
@var{env}; @var{env} must be an export environment.
@end deffn


@node General Environments,  , Export Environments, Standard Environment Types
@subsection General Environments

[[user provides the procedures]]
[[A observers B and C; B observes C; C changes; A should only be
notified once, right?]]
[[observation loops?]]

@node Implementing Environments, Switching to Environments, Standard Environment Types, Top-Level Environments in Guile
@section Implementing Environments

This section describes how to implement new environment types in Guile.

Guile's internal representation of environments allows you to extend
Guile with new kinds of environments without modifying Guile itself.
Every environment object carries a pointer to a structure of pointers to
functions implementing the common operations for that environment.  The
procedures @code{environment-ref}, @code{environment-set!}, etc. simply
find this structure and invoke the appropriate function.

[[It would be nice to have an example around here.  How about a
persistent environment, bound to a directory, where ref and set actually
access files?  Ref on a directory would return another
environment... Hey, let's import my home directory!]]


@menu
* Environment Function Tables::  
* Environment Data::            
* Environment Example::         
@end menu


@node Environment Function Tables, Environment Data, Implementing Environments, Implementing Environments
@subsection Environment Function Tables

An environment object is a smob whose @sc{cdr} is a pointer to a pointer
to a @code{struct environment_funcs}:
@example
struct environment_funcs @{
  SCM  (*ref) (SCM self, SCM symbol);
  SCM  (*fold) (SCM self, scm_environment_folder *proc, SCM data, SCM init);
  void (*define) (SCM self, SCM symbol, SCM value);
  void (*undefine) (SCM self, SCM symbol);
  void (*set) (SCM self, SCM symbol, SCM value);
  SCM  (*cell) (SCM self, SCM symbol, int for_write);
  SCM  (*observe) (SCM self, scm_environment_observer *proc, SCM data, int weak_p);
  void (*unobserve) (SCM self, SCM token);
  SCM  (*mark) (SCM self);
  scm_sizet (*free) (SCM self);
  int  (*print) (SCM self, SCM port, scm_print_state *pstate);
@};
@end example

You can use the following macro to access an environment's function table:

@deftypefn {Libguile macro} struct environment_funcs *SCM_ENVIRONMENT_FUNCS (@var{env})
Return a pointer to the @code{struct environment_func} for the environment
@var{env}.  If @var{env} is not an environment object, the behavior of
this macro is undefined.
@end deftypefn

Here is what each element of @var{env_funcs} must do to correctly
implement an environment.  In all of these calls, @var{self} is the
environment whose function is being invoked.

@table @code

@item SCM ref (SCM @var{self}, SCM @var{symbol});
This function must have the effect described above for the C call:
@example
scm_c_environment_ref (@var{self}, @var{symbol})
@end example
@xref{Examining Environments}.

Note that the @code{ref} element of a @code{struct environment_funcs}
may be zero if a @code{cell} function is provided.

@item SCM fold (SCM self, scm_environment_folder *proc, SCM data, SCM init);
This function must have the effect described above for the C call:
@example
scm_c_environment_fold (@var{self}, @var{proc}, @var{data}, @var{init})
@end example
@xref{Examining Environments}.

@item void define (SCM self, SCM symbol, SCM value);
This function must have the effect described above for the Scheme call:
@example
(environment-define @var{self} @var{symbol} @var{value})
@end example
@xref{Changing Environments}.

@item void undefine (SCM self, SCM symbol);
This function must have the effect described above for the Scheme call:
@example
(environment-undefine @var{self} @var{symbol})
@end example
@xref{Changing Environments}.

@item void set (SCM self, SCM symbol, SCM value);
This function must have the effect described above for the Scheme call:
@example
(environment-set! @var{self} @var{symbol} @var{value})
@end example
@xref{Changing Environments}.

Note that the @code{set} element of a @code{struct environment_funcs}
may be zero if a @code{cell} function is provided.

@item SCM cell (SCM self, SCM symbol, int for_write);
This function must have the effect described above for the C call:
@example
scm_c_environment_cell (@var{self}, @var{symbol})
@end example
@xref{Caching Environment Lookups}.

@item SCM observe (SCM self, scm_environment_observer *proc, SCM data, int weak_p);
This function must have the effect described above for the C call:
@example
scm_c_environment_observe (@var{env}, @var{proc}, @var{data}, @var{weak_p})
@end example
@xref{Observing Changes to Environments}.

@item void unobserve (SCM self, SCM token);
Cancel the request to observe @var{self} that returned @var{token}.
@xref{Observing Changes to Environments}.

@item SCM mark (SCM self);
Set the garbage collection mark all Scheme cells referred to by
@var{self}.  Assume that @var{self} itself is already marked.  Return a
final object to be marked recursively.

@item scm_sizet free (SCM self);
Free all non-cell storage associated with @var{self}; return the number
of bytes freed that were obtained using @code{scm_must_malloc} or
@code{scm_must_realloc}.

@item SCM print (SCM self, SCM port, scm_print_state *pstate);
Print an external representation of @var{self} on @var{port}, passing
@var{pstate} to any recursive calls to the object printer.

@end table


@node Environment Data, Environment Example, Environment Function Tables, Implementing Environments
@subsection Environment Data

When you implement a new environment type, you will likely want to
associate some data of your own design with each environment object.
Since ANSI C promises that casts will safely convert between a pointer
to a structure and a pointer to its first element, you can have the
@sc{cdr} of an environment smob point to your structure, as long as your
structure's first element is a pointer to a @code{struct
environment_funcs}.  Then, your code can use the macro below to retrieve
a pointer to the structure, and cast it to the appropriate type.

@deftypefn {Libguile macro} struct environment_funcs **SCM_ENVIRONMENT_DATA (@var{env})
Return the @sc{cdr} of @var{env}, as a pointer to a pointer to an
@code{environment_funcs} structure.
@end deftypefn

@node Environment Example,  , Environment Data, Implementing Environments
@subsection Environment Example

[[perhaps a simple environment based on association lists]]


@node Switching to Environments,  , Implementing Environments, Top-Level Environments in Guile
@section Switching to Environments

Here's what we'd need to do to today's Guile to install the system
described above.  This work would probably be done on a branch, because
it involves crippling Guile while a lot of work gets done.  Also, it
could change the default set of bindings available pretty drastically,
so the next minor release should not contain these changes.

After each step here, we should have a Guile that we can at least
interact with, perhaps with some limitations.

@itemize @bullet

@item
For testing purposes, make an utterly minimal version of
@file{boot-9.scm}: no module system, no R5RS, nothing.  I think a simple
REPL is all we need.

@item
Implement the environment datatypes in libguile, and test them using
this utterly minimal system.

@item
Change the interpreter to use the @code{environment-cell} and
@code{environment-observe} instead of the symbol value slots,
first-class variables, etc.  Modify the rest of libguile as necessary to
register all the primitives in a single environment.  We'll segregate
them into modules later.

@item
Reimplement the current module system in terms of environments.  It
should still be in Scheme.

@item
Reintegrate the rest of @file{boot-9.scm}.  This might be a good point
to move it into modules.

@item
Do some profiling and optimization.

@end itemize

Once this is done, we can make the following simplifications to Guile:

@itemize @bullet

@item
A good portion of symbols.c can go away.  Symbols no longer need value
slots.  The mismash of @code{scm_sym2ovcell},
@code{scm_intern_obarray_soft}, etc. can go away.  @code{intern} becomes
simpler.

@item
Remove first-class variables: @file{variables.c} and @file{variables.h}.

@item
Organize the primitives into environments.

@item
The family of environment types is clearly an abstract class/concrete
subclass arrangement.  We should provide GOOPS classes/metaclasses that
make defining new environment types easy and consistent.

@end itemize



@node Modules,  , Top-Level Environments in Guile, Top
@chapter Modules

The material here is just a sketch.  Don't take it too seriously.  The
point is that environments allow us to experiment without getting
tangled up with the interpreter.

@menu
* Modules of Guile Primitives::  
* Modules of Interpreted Scheme Code::  
@end menu

@node Modules of Guile Primitives, Modules of Interpreted Scheme Code, Modules, Modules
@section Modules of Guile Primitives

@node Modules of Interpreted Scheme Code,  , Modules of Guile Primitives, Modules
@section Modules of Interpreted Scheme Code

If a module is implemented by interpreted Scheme code, Guile represents
it using several environments:

@table @asis

@item the @dfn{local} environment
This environment holds all the definitions made locally by the module,
both public and private.

@item the @dfn{import} environment
This environment holds all the definitions this module imports from
other modules.

@item the @dfn{evaluation} environment
This is the environment in which the module's code is actually
evaluated, and the one closed over by the module's procedures, both
public and private.  Its bindings are the union of the @var{local} and
@var{import} environments, with local bindings taking precedence.

@item the @dfn{exported} environment
This environment holds the module's public definitions.  This is the
only environment that the module's users have access to.  It is the
@var{evaluation} environment, restricted to the set of exported
definitions.

@end table

Each of these environments is implemented using a separate environment
type.  Some of these types, like the evaluation and import environments,
actually just compute their bindings by consulting other environments;
they have no bindings in their own right.  They implement operations
like @code{environment-ref} and @code{environment-define} by passing
them through to the environments from which they are derived.  For
example, the evaluation environment will pass definitions through to the
local environment, and search for references and assignments first in
the local environment, and then in the import environment.



@bye