((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.
((((lambda (x)
(lambda (y)
(lambda (z)
some-big-expression-with-lots-of-xs-ys-and-zs)))
1)
2)
3)
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.
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))
env)
((lambda (env)
(apply-env env 'x))
env)))
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.