Two Stories about Environments

Chapter 5 of EOPL suddenly, and without explanation, introduces the notion of environment as a replacement for the beta reduction (i.e., substitution) used in Chapter 4. To see in simplest form what is at issue here, consider evaluating ((lambda (x) (* x x)) 3). Chapter 4 would tell us to evaluate (* 3 3), whereas Chapter 5 tells us to evaluate (* x x), where x = 3. That clause on the end, "where x = 3," is an environment: a finite function from variables to values (here mapping x to 3).

This example should help explain how the two mechanisms (substitution and environment) can be alternative ways of achieving the same end result. But it doesn't answer the larger question: Why, if substitution works fine, are we switching to environments? What is the motivation?

It turns out that there are two different answers to this question: two different stories not only about what motivates the use of environments, but also about the history of the idea. The idea of environments grew up both among practical language implementers and among theoretical computer scientists trying to mathematically explain the meaning of programs. So we have two stories: a story about implementation efficiency, and a story about mathematical elegance. You can read them in either order.

The efficiency story

Suppose we are using beta reduction to evaluate
((((lambda (x)
     (lambda (y)
       (lambda (z)
We'll need to copy the big expression three times -- or rather, not quite copy it. The first time we copy it except that we replace all the xs with 1. Then we copy it all over again, but replacing the ys with 2. And the third time we replace the zs with 3. Clearly this is inefficient: we ought to be able to do all the work in a single pass over the expression. And sure enough, we can, if we use an environment as shown in Chapter 5.

This is part of why practical implementations use environments. However it isn't the only reason. The other reason is that if we never substitute parameter values into the bodies of procedures, then we can more readily make some radical change in how the procedure bodies are represented. For example, we could represent a procedure body as a sequence of machine language instructions that does the procedure's calculation, using an environment it finds using some standardized register.

The mathematical story

It is nice to be able to assign a meaning to a string of symbols. For example, we conventionally say that the digit 1 followed by the digit 2 has as its meaning the number twelve. Similarly, the string of parentheses and letters
(lambda (x) x)
has as its meaning the identity function. The computer science topic called denotational semantics or sometimes mathematical semantics takes this approach to explaining programming languages. Every phrase in the language (such as an expression or a statement) is assigned a denotation: some mathematical value (such as a number or a function) that is the meaning of the phrase.

Our denotational semantics will be most elegant if the denotation of big phrases can be composed out of the denotation of their smaller constituent phrases. Having figured out what (lambda (x) x) and 12 denote, for example, ought to be our first step in figuring out what ((lambda (x) x) 12) denotes. We can say that meaning is compositional: the meaning of the whole is composed out of the meaning of the parts. That way, we can break our expression down into its finest components (the leaves in the abstract syntax tree), find each of their meanings, and then work our way up the tree, finding the meaning of each node in the AST using the meanings we already assigned to its children.

There is a hitch, however: If we break the expression down into its constituent pieces, we'll be looking at variables outside the context that binds them. For example, we would find the meaning of (lambda (x) (x x)) by finding the meaning of (x x), which in turn involves finding the meaning of x. But how can we talk about the meaning of x, or even (x x), in isolation? Without the lambda expression for context, what is x?

The solution to this problem is to assign a slightly more abstract meaning to each expression: not a value, but a function from environments to values. Written in Scheme, the meaning of x is

(lambda (env)
  (apply-env env 'x))
and the meaning of (x x) is
(lambda (env)
  (apply-proc (apply-env env 'x)
              (apply-env env 'x)))
or, making it somewhat more long-winded,
(lambda (env)
  (apply-proc ((lambda (env)
                 (apply-env env 'x))
              ((lambda (env)
                 (apply-env env 'x))
Notice that the meaning of x shows up twice in the meaning of (x x), just as we would expect for a compositional semantics.

If eval were a function that mapped an expression to its meaning, then (eval 'x) and (eval '(x x)) would be the two meanings given above. Note that each meaning is "waiting for an environment" before it returns a value. Thus if we wanted to find out the value of x or (x x) in some particular environment e, we would need to do ((eval 'x) e) or ((eval '(x x)) e). If eval is always used this way, we can "un-curry" it (see Chapter 1) into a two-argument procedure, used as (eval 'x e) or (eval '(x x) e). This is what Chapter 5 does.

Course web site:
Instructor: Max Hailperin <>