# 3.2 The Environment Model of Evaluation
# 3.2.1 The Rules for Evaluation
(define square (lambda (x) (* x x)))
(square 5) => (* 5 5) => 25Environment diagram:
; _____________
; global env --> | square: --+ |
; |___________|_|<-+
; ^ | |
; | V |
; E1 -->[x: 5] [*|*]--+
; V
; parameters: x
; body: (* x x)# 3.2.2 Applying Simple Procedures
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
(f 5) => (sum-of-squares (+ 5 1) (* 5 2)) => (+ (square 6) (square 10)) => 136Environment diagram:
; _____________________
; global env --> | sum-of-squares: ... |
; | square: ... |
; | f: ... |<------------+
; |_____________________|<+ |
; (f 5) ^ ^ | |
; | | | |
; E1->[a: 5] E2->[x: 6] E3->[x: 6] E4->[x:10]
; [y: 7]
; (sum-of-squares (+ (square x) (* x x) (* x x)
; (+ a 1) (square y))
; (* a 2)# Exercise 3.9
(define (factorial n)
(if (= n 1) 1 (* n (factorial (- n 1)))))Six environments are created in the recursive version:
(factorial 6) ; E1 -> [n: 6]
=> (* 6 (factorial 5)) ; E2 -> [n: 5]
=> (* 6 (* 5 (factorial 4))) ; E3 -> [n: 4]
=> (* 6 (* 5 (* 4 (factorial 3)))) ; E4 -> [n: 3]
=> (* 6 (* 5 (* 4 (* 3 (factorial 2))))) ; E5 -> [n: 2]
=> (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1)))))) ; E6 -> [n: 1]
=> 720
(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)))Eight environments are created in the iterative version:
(factorial 6) ; E1 -> [n: 6]
=> (fact-iter 1 1 6) ; E2 -> [p: 1, c: 1, m: 6]
=> (fact-iter 1 2 6) ; E3 -> [p: 1, c: 2, m: 6]
=> (fact-iter 2 3 6) ; E4 -> [p: 2, c: 3, m: 6]
=> (fact-iter 6 4 6) ; E5 -> [p: 6, c: 4, m: 6]
=> (fact-iter 24 5 6) ; E6 -> [p: 24, c: 5, m: 6]
=> (fact-iter 120 6 6) ; E7 -> [p: 120, c: 6, m: 6]
=> (fact-iter 720 7 6) ; E8 -> [p: 720, c: 7, m: 6]
=> 720# 3.2.3 Frames as the Repository of Local State
# Exercise 3.10
With or without the explicit state variable, make-withdraw creates objects with the same behaviour. The only difference with the explicit variable in the let-form is that there is an extra environment. Applying make-withdraw creates E1 to bind 100 to initial-amount, and then the let-form desugars to a lambda application, creating a new environment E2. This environment holds balance, beginning with the same value as initial amount. When we evaluate (W1 20), we create the environment E3 that binds amount to 20. The assignment in the code for W2 changes the value of balance from 100 to 80. The value of initial-amount remains the same, because it was never changed in a set! assignment. The behaviour is no different with the let-form because, although we are now saving the original balance, we aren’t doing anything with it. We can’t access it outside of the procedure.
; ____________________
; global env -->| make-withdraw: ... |
; | W2: ---------+ |
; | W1: | |<--------------------+
; |_|____________|_____| E3 |
; | ^ | [initial-amount: 100]
; | E1 | +--------------->[*|*] ^
; | [initial-amount: 100] | | E4 |
; | ^ | +--->[balance: 60]
; V E2 | | ^
; [*|*]-->[balance: 80] | |
; V ^ | |
; parameters: amount }<---|----------------+ |
; body: ... } | |
; | (W2 40) [amount: 40]
; |
; (W1 20) [amount: 20]-----+# 3.2.4 Internal Definitions
# Exercise 3.11
First, we just have a procedure bound in the global environment.
; global env --> [make-account: ...]
(define acc (make-account 50))Now, we have acc in the global frame as well. It is bound to a procedure whose environment pointer points to E1, the environment created when we evaluated (make-account 50). It first bound the formal parameter balance to 50, and then three internal procedures were defined and bound in the same frame. One of them, dispatch, points to the same procedure as acc.
; __________________
; global env --> | make-account: ...|
; | acc: |
; |__|_______________|
; | ^
; V E1___|____________
; [*|*]---->| balance: 50 |<-----+
; V | withdraw:------|-->[*|*]
; parameters: m | deposit:-------|-+ +-----> parameters: amount
; body: ... | dipspatch:-+ | | body: ...
; ~~~~~~~~~~~~<---------------+ | +->[*|*]
; |________________|<----|-+
; +----> parameters: amount
; body: ...
((acc 'deposit) 40) => 90First we evaluate (acc 'deposit). We create E2 to bind m to the symbol deposit, and then we evaluate the body of acc, which is the same as the body of dispatch. The enclosing environment of E2 is E1, because that is pointed to by the procedure. This application returns the value of deposit
;;;;; [TODO: The #<deposit> on next line trips schemehl assertion.]
;;;;; from E1. Now we evaluate `((#<deposit> 40)`. We create E3 to bind `amount` tothe value 40, and the enclosing environment is E1 (pointed to by the procedure deposit). This finally assigns 90 to balance in E1, and then returns that value.
; E2 [m: deposit]--+
; +----> E1 [balance:90, ...]
; E3 [amount: 40]--+
((acc 'withdraw) 60) => 30This is almost the same, except the procedure returns the withdraw procedures instead. I am reusing the names E2 and E3 because they have been used and are no longer relevant, since nothing poitns to them.
; E2 [m: withdraw]--+
; +---> E1 [balance: 30, ...]
; E3 [amount: 60]---+All this time, the local state for acc is kept in E1, the environment originally created to apply the make-account procedure. If we define another account with (define acc2 (make-account 100)), it will have its own environment containing balance and bindings for the internal procedures. The only thing shared between acc and acc2 is (possibly) the code for the internal procedures, including dispatch, which the accounts really are. This sharing is an implementation detail, though.