When we introduced the substitution model in
section 1.1.5 we showed how the
combination (f 5)application
f(5)
evaluates to 136, given the following
procedure definitions:function declarations:
Original
JavaScript
(define (square x)
(* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
(define (f a)
(sum-of-squares (+ a 1) (* a 2)))
function square(x) {
return x * x;
}
function sum_of_squares(x, y) {
return square(x) + square(y);
}
function f(a) {
return sum_of_squares(a + 1, a * 2);
}
We can analyze the same example using the environment model.
Figure 3.8 shows the three
procedurefunction
objects created by evaluating the definitions of
f, square, and
sum-of-squaressum_of_squares
in the
globalprogram
environment. Each
procedurefunction
object consists of some code, together with a pointer to the
globalprogram
environment.
Original
JavaScript
Original
JavaScript
In
figure 3.9figure 3.10
we see the environment structure created by evaluating the expression
(f 5).f(5).
The call to f creates a new environment, E1,
beginning with a frame in which a, the
formal parameter of
f, is bound to the argument 5. In E1, we
evaluate the body of f:
Original
JavaScript
(sum-of-squares (+ a 1) (* a 2))
return sum_of_squares(a + 1, a * 2);
To evaluate
this combination,
we first evaluate the subexpressions.
the return statement, we first evaluate the
subexpressions of the return expression.
The first subexpression,
sum-of-squares,sum_of_squares,
has a value that is a
procedurefunction
object. (Notice how this value is found: We first look in the first frame
of E1, which contains no binding for
sum-of-squares.sum_of_squares.
Then we proceed to the enclosing environment, i.e., the
globalprogram
environment, and find the binding shown in
figure 3.7.)
figure 3.8.)
The other two subexpressions are evaluated by applying the primitive
operations + and *
to evaluate the two combinations
(+ a 1)a + 1
and
(* a 2)a * 2
to obtain 6 and 10, respectively.
Now we apply the
procedurefunction
object
sum-of-squaressum_of_squares
to the arguments 6 and 10. This results in a new environment, E2, in which
the formal parameters
x and y are bound
to the arguments. Within E2 we evaluate
the combination
(+ (square x) (square y)).
the statement
return square(x) + square(y);
This leads us to evaluate
(square x),square(x),
where square is found in the
globalprogram
frame and x is 6. Once again, we set up a
new environment, E3, in which x is bound to 6,
and within this we evaluate the body of square,
which is
(* x x).return x * x;.
Also as part of applying
sum-of-squares,sum_of_squares,
we must evaluate the subexpression
(square y),square(y),
where y is 10. This second call to
square creates another environment, E4, in
which x, the
formal parameter of
square, is bound to 10. And within E4 we must
evaluate
(* x x).return x * x;.
The important point to observe is that each call to
square creates a new environment containing a
binding for x. We can see here how the
different frames serve to keep separate the different local variables all
named x. Notice that each frame created by
square points to the
globalprogram
environment, since this is the environment indicated by the
squareprocedurefunction
object.
After the subexpressions are evaluated, the results are returned. The
values generated by the two calls to square are
added by
sum-of-squares,sum_of_squares,
and this result is returned by f.
Since our focus here is on the environment structures, we will not
dwell on how these returned values are passed from call to call;
however, this is also an important aspect of the evaluation process,
and we will return to it in detail in chapter 5.
Exercise 3.9
In section 1.2.1
we used the substitution model to analyze two
proceduresfunctions
for computing
factorials, a recursive version
Original
JavaScript
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
function factorial(n) {
return n === 1
? 1
: n * factorial(n - 1);
}
Show the environment structures created by evaluating
(factorial 6)factorial(6)
using each version of the factorialprocedurefunction.[1]
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
[1]
The environment model will not clarify our claim in
section 1.2.1 that the
interpreter can execute a
procedurefunction
such as
fact-iterfact_iter
in a constant amount of space using tail recursion. We will discuss
tail recursion when we
deal with the control structure of the interpreter in
section 5.4.