Permalink copied!
When we introduced the substitution model in
section 1.1.5 we showed how the
application
f(5)
evaluates to 136, given the following
function declarations:
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
function
objects created by evaluating the definitions of
f, square, and
sum_of_squares
in the
program
environment. Each
function
object consists of some code, together with a pointer to the
program
environment.
Figure 3.8
Function objects in the program frame.
In
figure 3.10
we see the environment structure created by evaluating the expression
f(5).
The call to f creates a new environment, E1,
beginning with a frame in which a, the
parameter of
f, is bound to the argument 5. In E1, we
evaluate the body of f:
return sum_of_squares(a + 1, a * 2);
To evaluate
the return statement, we first evaluate the
subexpressions of the return expression.
The first subexpression,
sum_of_squares,
has a value that is a
function
object. (Notice how this value is found: We first look in the first frame
of E1, which contains no binding for
sum_of_squares.
Then we proceed to the enclosing environment, i.e., the
program
environment, and find the binding shown in
figure 3.8.)
The other two subexpressions are evaluated by applying the primitive
operations + and *
to evaluate the two combinations
a + 1
and
a * 2
to obtain 6 and 10, respectively.
Now we apply the
function
object
sum_of_squares
to the arguments 6 and 10. This results in a new environment, E2, in which
the parameters
x and y are bound
to the arguments. Within E2 we evaluate
the statement
return square(x) + square(y);
This leads us to evaluate
square(x),
where square is found in the
program
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
return x * x;.
Also as part of applying
sum_of_squares,
we must evaluate the subexpression
square(y),
where y is 10. This second call to
square creates another environment, E4, in
which x, the
parameter of
square, is bound to 10. And within E4 we must
evaluate
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
program
environment, since this is the environment indicated by the
square
function
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,
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.
In section 1.2.1
we used the substitution model to analyze two
functions
for computing
factorials, a recursive version
function factorial(n) {
return n === 1
? 1
: n * factorial(n - 1);
}
and an iterative version
function factorial(n) {
return fact_iter(1, 1, n);
}
function fact_iter(product, counter, max_count) {
return counter > max_count
? product
: fact_iter(counter * product,
counter + 1,
max_count);
}
Show the environment structures created by evaluating
factorial(6)
using each version of the factorial
function.
[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.
3.2.2
Applying Simple
Functions