TICS

What is the result of evaluating the following expression in Scheme?

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 env₁ where the symbol x is associated or bound to the value 10, the straightforward expression:

is further evaluated to (+ env₁(x) 4), that is 14. Such an environment can be easily represented with a diagram:

Here, env_empty 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, env₁ simply augments env_empty with a new association or binding for x. Such extension implies the existence of another function:

extend_env 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 env_empty, and repeatedly extending it with extend_env. In diagrams like the one above, the vertical arrows, created by the application of extend_env, 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 env₁ with new bindings for y and z, we would have:

With this new environment env₂, the previous example expression is evaluated to (+ env₂(x) 4), which is still 14. The procedure works as follows:

• Starting from env₂(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 env_empty and get a nasty error. In the latter, we would say that x is unbound in env₂.

Now, we extend env₂ with a new binding for x:

In this last environment configuration, our expression is evaluated to (+ env₃(x) 4), but now the result is 23, not 14. We consciously shadowed the previous binding for x in env₁, retrieving 19 instead of 10.

Therefore, in our initial example:

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.

From left to right:

From right to left:

Not sure if this works. Cannot test without rand-update: