# Title

The Environment Monad

# Author

Marc Nieper-Wißkirchen

# Status

This SRFI is currently in draft 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.

- Received: 2019/2/13
- 60-day deadline: 2019/4/14
- Draft #1 published: 2019/2/13
- Draft #2 published: 2019/4/1
- Draft #3 published: 2019/6/29

# Abstract

Monads model computations. The environment monad models computations that depend on values from a shared environment. These computations can read values from the environment, pass values to subsequent computations, execute sub-computations in an extended environment, and modify the environment for future computations.

# Rationale

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

## Monads

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.

## Computations

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 that is yielded by computing `b`.

## Environments

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

# Specification

## Environment procedures

`(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 … alter 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.

## Primitive monadic procedures

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

## Derived monadic procedures

`(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 and that has to return a computation, which is then executed and which 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 computation 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.

## Derived syntax

`(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 are 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 was 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.

## Environment variables

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

## Extension for predefined environment variables

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 which can be defined statically, the following syntax can be used, which guarantees an accessing 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.

## Non-local control flow

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.

## Proper tail recursion

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

## Relation to other SRFIs

In a Scheme system supporting 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.

# Implementation

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.

# Acknowledgements

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.

# Copyright

Copyright (C) Marc Nieper-Wißkirchen (2019).

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