Environments the easy way
What is the result of evaluating the following expression in Scheme?
1 2 | (let ((a 9)) (* a 3)) |
If you answered 27, then think again. In actuality, this question does not make any sense, or partially at least. In Scheme, as well as in other programming languages, an expression is evaluated with respect to an environment that assigns values to its variables. In our example, this includes a and *.
But, what is an environment? There are several ways to explain and represent those, but let’s focus on the functional approach. Say 
is the finite set of all Scheme symbols, and 
is the set of all Scheme values, then an environment is a function:
That is, given a symbol that represents a variable, env returns a value for that variable. In an environment env1 where the symbol x is associated or bound to the value 10, the straightforward expression:
1 | (+ x 4) |
is further evaluated to (+ env1(x) 4), that is 14. Such an environment can be easily represented with a diagram:
Here, envempty represents a function that returns an unspecified value, or rather, more commonly, raises an error for any symbol in the input. On top of that, env1 simply augments envempty with a new association or binding for x. Such extension implies the existence of another function:
extendenv takes an environment, 
symbols and values for some 
, and returns an environment that augments the initial with the new bindings. Environments are constructed by starting with envempty, and repeatedly extending it with extendenv. In diagrams like the one above, the vertical arrows, created by the application of extendenv, relate an environment with its enclosing environment.
Note that, by definition of a function, a symbol cannot be bound to more than one value. This is quite interesting, for it is usual to extend an environment by including bindings for new and existing symbols. To illustrate this, if we want to extend env1 with new bindings for y and z, we would have:
With this new environment env2, the previous example expression is evaluated to (+ env2(x) 4), which is still 14. The procedure works as follows:
- Starting from env2(x), we look up the first binding for the symbol x in the sequence of frames (the colored boxes containing the associations).
- We eventually find a value for x or reach envempty and get a nasty error. In the latter, we would say that x is unbound in env2.
Now, we extend env2 with a new binding for x:
In this last environment configuration, our expression is evaluated to (+ env3(x) 4), but now the result is 23, not 14. We consciously shadowed the previous binding for x in env1, retrieving 19 instead of 10.
Therefore, in our initial example:
1 2 | (let ((a 9)) (* a 3)) |
If we evaluate it in an environment that shadows the symbol * to return (λ (x y) (+ ( * x y) 4)), then the result would be 31, not 27. Such is the importance of environments.
In a forthcoming article, we shall explain how this concept of environment can be used to implement lexical scoping through the creation of closures.
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution 2.0 UK: England & Wales License.
Tags: programming, scheme