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 procedure function objects created by evaluating the definitions of f, square, and sum-of-squares sum_of_squares in the global program environment. Each procedure function object consists of some code, together with a pointer to the global program environment.

Original		JavaScript
Figure 3.7 Procedure objects in the global frame.		Figure 3.8 Function objects in the program frame.

Original		JavaScript
Figure 3.9 Environments created by evaluating (f 5) using the procedures in figure 3.7.		Figure 3.10 Environments created by evaluating f(5) using the functions in figure 3.8.

In figure 3.9 figure 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 procedure 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. sum_of_squares. Then we proceed to the enclosing environment, i.e., the global program 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 procedure function object sum-of-squares sum_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 global 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 (* 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 global program environment, since this is the environment indicated by the square procedure 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, 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 procedures functions 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); }

and an iterative version

Original	JavaScript
(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))	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) factorial(6) using each version of the factorial procedurefunction.[1]

Add solution

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.