This SRFI is currently in final status. Here
is an
explanation of each status that a SRFI can hold. To provide
input on this SRFI, please send email
to srfi-165@nospamsrfi.schemers.org.
To subscribe to the list,
follow these
instructions. You can access previous messages via the
mailing
list archive.
The environment monad is useful whenever code has to be suspended and executed at a later time (even several times), and whenever code depends (implicitly) on bindings of variables in a shared environment.
SRFI 166, a forthcoming revision of the combinator formatting SRFI 159, is a major use case of the environment monad and a good example of the concept in practice. The formatters in SRFI 166 are computations in the nomenclature of this SRFI. In particular, the properties for computations apply to formatters as well and the primitive and the derived procedures of this SRFI can be used to construct sophisticated formatters of SRFI 166.
Nonetheless, SRFI 165 is an independent SRFI and not a proper part of SRFI 166 for two reasons: Firstly, SRFI 166's combinator formatters are just one use case for the environment monad of SRFI 165, so one wants to be able to use the procedures and syntax specified in this SRFI independently of formatting. Secondly, this SRFI exports more primitive and derived procedures for the environment monad and computations than are usually needed to write simple SRFI 166 formatters, so including them all in SRFI 166 would shift away the focus of SRFI 166 too much from its genuine purpose, formatting.
In category theory, a monad on a category C is nothing but a monoid in the monoidal category of endofunctors [C, C] over C. This rather abstract notion has become a well-understood design pattern in functional programming, having been popularized notably by the lazy functional programming language Haskell.
As there are already many good explanations for monads in computer science, and as understanding the mathematical concept in detail is not necessary to work with this SRFI, we refrain from repeating the theoretical foundations. We just want to remark that the environment monad considered here is roughly a monad on the category whose objects are natural numbers n and whose morphisms m → n are Scheme procedures taking m values and returning n values. Moreover, what is called the environment monad here and elsewhere is called the Reader monad in Haskell.
This SRFI introduces two new concepts, environments and computations.
The computations are the monadic values of the environment monad described in this SRFI.
A computation can be thought of as suspended code much like promises but with the difference that a computation can be executed more than once and that its results are not cached.
When executed, a computation yields results, which can be arbitrary Scheme values.
The simplest computation
is (computation-pure val1 …),
which just yields the results val1 …
when executed.
This SRFI provides a number of combinators that combine
computations. For
example (computation-each computation1
… computationn) is the computation
formed by applying each computation1,
…, computationn in sequence and eventually
yielding the results of the last one.
Another combinator known from monads in functional programming
is the computation
(computation-bind computation proc),
which is the computation formed by feeding the results yielded
by computation to proc and yielding the
results of the computation returned by the invocation
of proc.
Computations are executed by computation-run. The
expression (computation-run computation)
returns the values yielded by the execution
of computation.
The primary constructor for computations
is make-computation. For example,
(make-computation
(lambda (compute)
(if (compute a) 42 (compute b)))
returns a computation that, when executed, first
computes a. If that computation yields a true
value, 42 is yielded, otherwise the result of
computing b is yielded.
The computations of the environment monad are executed on an environment. Environment variables can be bound to values in these environments.
Fresh environment variables are created by invoking the
procedure make-computation-environment-variable.
Each environment variable has a default value.
Environments can be extended non-destructively to new environments or can be modified in place (for subsequent computations).
The computation-run procedure creates a new empty environment
that is then threaded through the computation.
This SRFI provides the
computation (computation-ask), which yields the
current environment. Executing the
computation (computation-local updater computation)
on an environment env means
executing computation on the
environment (updater env).
(make-computation-environment-variable name default
immutable?)
Returns a Scheme object that can be used as an environment
variable, whose default value is default and
which is immutable if immutable? is
not #f. The symbol or string name is
solely for debugging purposes. The type of the returned object
is unspecified. Each invocation returns an environment variable
different to any previously returned environment variable.
(make-computation-environment)
Returns a new environment, in which environment variables can be bound to values. The type of the returned object is unspecified.
(computation-environment-ref env var)
If the variable var is bound to a value in the environment env, returns that value, and the environment variable's default value otherwise.
(computation-environment-update env arg
…)
The arguments arg … alternate between environment variables var and values val. Returns a new environment that extends the environment env by binding each environment variable var to the respective value val.
(computation-environment-update! env var val)
Updates the environment env in place by binding the environment variable var to val, and returns an unspecified value.
(computation-environment-copy env)
Returns a fresh copy of the environment env.
(make-computation proc)
Takes a procedure proc, which takes one argument, and
returns a computation. The Scheme type of a
computation is disjoint from any type, as if created by
define-record-type, except possibly procedures.
When the computation is later executed on an environment, the procedure proc is called with an argument compute, which is a procedure taking one argument. Whenever compute is invoked on another computation, the other computation is executed on the environment and its results are returned. The results yielded by the execution are the results of the invocation of proc.
(computation-run computation)
Executes the computation computation and returns the results it yields.
(computation-ask)
Returns a computation that, when executed on an environment, yields that environment.
(computation-local updater computation)
Returns a computation that, when executed on an environment env, invokes the procedure updater on env, executes the computation computation on the result of the invocation of updater, which must be an environment, and yields its results.
(computation-pure obj1 …)
Returns a computation that, when executed, yields the values obj1 ….
(computation-each computation1
… computationn)
Returns a computation that, when executed, sequentially executes the computations computation1, …, computationn and yields the results yielded by the last computation.
(computation-each-in-list list)
Equivalent to (computation-each computation1
… computationn)
if list is a list whose elements
are computation1,
…, computationn.
(computation-bind computation proc1 …)
(computation-bind computation) is equivalent
to computation. (computation-bind computation
proc1 proc2
…) is equivalent to (computation-bind
(computation-bind computation proc1)
proc2 …).
The invocation of (computation-bind computation proc)
returns a computation that, when executed, executes the
computation computation, on which results the
procedure proc is then invoked, resulting in
a computation that is then executed and whose results are yielded.
(computation-sequence list)
When invoked on a list list of computations, returns a computation that, when executed, executes the computations in sequence and yields a list whose elements are the results yielded by the computations.
(computation-forked computation1
… computationn)
Returns a computation that, when executed on an environment, executes each of the computations computation1, … on fresh copies of the environment, and finally executes computationn on the original environment and yields its results.
(computation-bind/forked computation proc1 …)
As (computation-bind computation proc1
…), but executes computation on a fresh copy
of the environment.
(computation-fn ((〈variable1〉 〈init1〉) …) 〈body〉)
Evaluates the expressions 〈init1〉 … to environment
variables var1 … in an unspecified order and
returns a computation that, when executed, lexically binds the
variables 〈variable1〉 … to the values to which the
environment variables var1, … are bound,
and evaluates the body 〈body〉 in the resulting lexical environment.
The value of the last expression in 〈body〉 has to be a computation,
which is then executed and its results yielded.
A clause of the form (〈variable〉 〈variable〉)
(i.e. the expression 〈init〉
is the variable reference 〈variable〉) can be
abbreviated by 〈variable〉.
An unbound environment variable behaves as if it were bound to its default value.
(computation-with ((〈variable1〉 〈init1〉) …) 〈expr1〉 …
〈exprn〉)
Evaluates the expressions 〈expr1〉 … 〈exprn〉 to computations computation1, …, computationn, the expressions 〈variable1〉 … to environment variables var1 … and the expressions 〈init1〉 … to values val1 … in an unspecified order, and returns a computation that, when executed on an environment, extends that environment non-destructively by binding var1, … to val1 …, sequentially executes the computations computation1, … computationn on that extended environment, and then yields the results of the last computation.
(computation-with! (〈variable1〉 〈init1〉) …)
Evaluates the expressions 〈variable1〉 … to mutable environment variables var1 … and the expressions 〈init1〉 … to values val1 … in an unspecified order, and returns a computation that, when executed on an environment, modifies this environment in place by binding var1, … to val1 … and which yields an unspecified value.
default-computation
This SRFI exports the
identifier default-computation, which is bound to a
location holding a mutable environment variable (as if created
by (make-computation-environment-variable)) in the
sense of this SRFI. In each fresh computation
environment, default-computation is initially
unbound. Whenever a computation computation is to be
executed on an environment and is neither a computation nor a
procedure, the value to which default-computation
is bound in the environment has to be a procedure, which is then
invoked on computation to return a computation, which
is then executed on the environment.
The complexity for accessing environment variables is O(n) where n is the number of variables bound in the environment.
In use cases where a few environment variables are accessed often and can be defined statically, the following syntax can be used, which guarantees an access time of O(1) for predefined environment variables.
(define-computation-type 〈make-environment〉 〈run〉 〈clause〉 …)
This syntax may appear wherever other definitions may
appear. Each 〈clause〉 is of the form (〈variable〉 〈default〉),
(〈variable〉 〈default〉 "immutable"),
or 〈variable〉. The latter form is equivalent
to (〈variable〉 #f).
〈make-environment〉, 〈run〉,
and each 〈variable〉 are identifiers.
An instance of define-computation-type is equivalent
to the following definitions:
〈make-environment〉 is bound to a procedure that takes no
arguments. Invoking the procedure is equivalent to
invoking make-computation-environment except
that the environment variables defined below can be used with
the resulting environment.
〈run〉 is bound to a procedure that takes one argument.
Invoking the procedure is equivalent to
invoking computation-run except for that the
initial environment is created by invoking the procedure bound
to 〈make-environment〉.
Each 〈variable〉 is bound to an environment
variable, which can only be used with an environment created
by invoking the procedure bound
to 〈make-environment〉. Its default value is
the result of evaluating 〈default〉. The
environment variable is immutable if the (〈variable〉
〈default〉 "immutable") form is used.
The (higher order) procedures described in this SRFI are fully compatible with non-local control flow, in particular with first-class continuations.
For example, the behavior is well-defined if the
argument proc of make-computation
returns multiple times.
Computations can be executed in tail context. A
tail context is always determined with respect to a particular
call to computation-run.
The following rules apply inductively:
If computation-run is invoked, its
argument computation is executed in tail context
with respect to that call.
If the computation returned by make-computation
is executed in tail context, the argument proc is
tail-called with respect to the call
to computation-run.
If the computation returned by computation-local
is executed in tail context, its argument computation
is executed in tail context.
If the computation returned by computation-each
is executed in tail context, its
argument computationn
is executed in tail context.
If the computation returned by computation-bind
is executed in tail context, the computation returned by its
argument proc is executed in tail context.
If the computation returned by computation-forked
is executed in tail context, its
argument computationn is executed in
tail context.
If the computation returned by computation-fn is
executed in tail context, the last expression
in 〈body〉 is executed in tail context.
If the computation returned by computation-with
is executed in tail
context, computationn is executed in
tail context.
In a Scheme system that supports both SRFI 165 and SRFI 166, the implementation of SRFI 166 shall be compatible with the implementation of SRFI 165. This means, in particular, the following:
SRFI 166 formatters are SRFI 165 computations. In
particular, they yield values (often an undefined one) to
support functional programming. SRFI
166's show executes the computations in a SRFI
166-specific environment.
The bindings of the
identifiers fn, with, with!,
each, each-in-list, forked,
and make-state-variable of SRFI 166 are the same
as the bindings
of computation-fn, computation-with,
computation-with!,
computation-each, computation-each-in-list,
computation-forked,
and make-computation-environment-variable of SRFI 165,
respectively.
Further details can be found in the upcoming SRFI 166.
The sample implementation is coded in portable R7RS scheme. It makes use of the (portable) SRFI 1, SRFI 111, SRFI 125, SRFI 128, and SRFI 146. The testing code also uses SRFI 64.
Source for the sample implementation.
This SRFI has been inspired by the (chibi monad
environment) library distributed by Alex Shinn's Chibi
Scheme and by SRFI 159, also by Alex Shinn.
The environment monad is called the Reader monad in Mark P. Jones' Functional Programming with Overloading and Higher-Order Polymorphism, Advanced School of Functional Programming, 1995.
The notion of monads was invented by Roger Godement under the name standard construction. They are also known as triples. The term monad is due to Saunders Mac Lane.
The author of this SRFI wants to thank Alex Shinn and John Cowan for their valuable comments during its draft period.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.