SICP 3.2 The Environment Model of Evaluation
2023-12-25 Mon
The notions of frames and environments are introduced.
Despite the switch to the environment model of evaluation, the rules for evaluating a combination remain the same:
- To evaluate a combination:
- Evaluate the subexpression of the combination.
- Apply the value of the operator subexpression to the value of the operand subexpression. (p. 238)
The environment model of evaluation changes, though, what it means to apply a procedure.
The environment model of procedure application can be summarized by two rules:
- A procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the arguments of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure object being applied.
- A procedure is created by evaluating a
lambdaexpression relative to a given environment. The resulting procedure object is a pair consisting of the text of thelambdaexpression and a pointer to the environment in which the procedure was created. (p. 240)
Exercise 3.9
Exercise:
In section 1.2.1 we used the substitution model to analyze two procedures for computing factorials, a recursive version
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))and an iterative version
(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)))Show the environment structures created by evaluating
(factorial 6)using each version of the `factorial' procedure.
Answer:
Recursive version:
+------------------------------------------------------------------------------------+
global -->| |
env +------------------------------------------------------------------------------------+
^ ^ ^ ^ ^ ^
(factorial 6) | | | | | |
+------+ +------+ +------+ +------+ +------+ +------+
E1 ->| n: 6 | E2 ->| n: 5 | E3 ->| n: 4 | E4 -->| n: 3 | E5 ->| n: 2 | E6 -->| n: 1 |
| | | | | | | | | | | |
+------+ +------+ +------+ +------+ +------+ +------+
(if (= n 1)
1 same same same same same
(* n factorial (- n 1)))
Iterative version:
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
global -->| |
env +------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
^ ^ ^ ^ ^ ^ ^ ^
(factorial 6) | | | | | | | |
+------+ +-------------+ +-------------+ +-------------+ +-------------+ +--------------+ +--------------+ +--------------+
E1 ->| n: 6 | E2 ->| product: 1 | E3 ->| product: 1 | E4 ->| product: 2 | E5 ->| product: 6 | E6 ->| product: 24 | E7 ->| product: 120 | E8 ->| product: 720 |
| | | counter: 1 | | counter: 2 | | counter: 3 | | counter: 4 | | counter: 5 | | counter: 6 | | counter: 7 |
| | | max-count: 6| | max-count: 6| | max-count: 6| | max-count: 6| | max-count: 6 | | max-count: 6 | | max-count: 6 |
+------+ +-------------+ +-------------+ +-------------+ +-------------+ +--------------+ +--------------+ +--------------+
(fact-iter 1 1 n) (if (> counter max-count) same same same same same same
product
(fact-iter (* counter product)
(+ counter 1)
max-count))
Exercise 3.10
Exercise:
In the
make-withdrawprocedure, the local variablebalanceis created as a parameter ofmake-withdraw. We could also create the local state variable explicitly, usinglet, as follows:(define (make-withdraw initial-amount) (let ((balance initial-amount)) (lambda (amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds"))))Recall from section 1.3.2 that
letis simply syntactic sugar for a procedure call:(let ((<VAR> <EXP>)) <BODY>)is interpreted as an alternate syntax for
((lambda (<VAR>) <BODY>) <EXP>)Use the environment model to analyze this alternate version of
make-withdraw, drawing figures like the ones above to illustrate the interactions(define W1 (make-withdraw 100)) (W1 50) (define W2 (make-withdraw 100))Show that the two versions of
make-withdrawcreate objects with the same behavior. How do the environment structures differ for the two versions?
Answer:
Environments created by evaluating (define w1 (make-withdraw 100)):
GLOBAL ENV
+---------------------------------------------------------------------------------------------------------+
| make-withdraw:---+ w1:---+ |
| | | |
| | | |
| | +------------+ |
| | | |
| | | |
+------------------+------------+-------------------------------------------------------------------------+
| ↑ | E1
+----------------+ | | +----------------------+
| | | | initial-amout: 100 |
↓ | | | |
+-+-+---+ | | | |
| | +--------------+ | +----------------------+
+-+-+---+ | ↑ ↑
↓ | | |
λ | | |
| +---+---+ | |
| | | +--+ |
| +-+-+---+ |
| ↓ |
| λ |
| |
| |
| |
| |
| E2 |
| +-----------------+-----+
| | balance: 100 |
| | |
| | |
| +-----------------------+
| ↑ ↑
| | |
| | |
| +---+---+ | |
+------→| | +--+ |
+-+-+---+ |
↓ |
λ |
|
|
|
|
|
E3 |
+-----------------+------+
| amount: 50 |
| |
| |
+------------------------+
After the evaluation:
GLOBAL ENV
+---------------------------------------------------------------------------------------------------------+
| make-withdraw:---+ w1:---+ |
| | | |
| | | |
| | +------------+ |
| | | |
| | | |
+------------------+------------+-------------------------------------------------------------------------+
| ↑ | E1
+----------------+ | | +----------------------+
| | | | initial-amout: 100 |
↓ | | | |
+-+-+---+ | | | |
| | +--------------+ | +----------------------+
+-+-+---+ | ↑ ↑
↓ | | |
λ | | |
| +---+---+ | |
| | | +--+ |
| +-+-+---+ |
| ↓ |
| λ |
| |
| |
| |
| |
| E2 |
| +-----------------+-----+
| | balance: 50 |
| | |
| | |
| +-----------------------+
| ↑
| |
| |
| +---+---+ |
+------→| | +--+
+-+-+---+
↓
λ
Evaluating (define w2 (make-withdraw 100)):
GLOBAL ENV
+---------------------------------------------------------------------------------------------------------+
| make-withdraw:---+ w1:---+ w2:---+ |
| | | | |
| | | | |
| | +------------+ +----------+ |
| | | | |
| | | | |
+------------------+------------+------------------------------------------+------------------------------+
| ↑ | E1 | E4
+----------------+ | | +----------------------+ | +----------------------+
| | | | initial-amout: 100 | | | initial-amout: 100 |
↓ | | | | | | |
+-+-+---+ | | | | | | |
| | +--------------+ | +----------------------+ | +----------------------+
+-+-+---+ | ↑ ↑ | ↑ ↑
↓ | | | | | |
λ | | | | | |
| +---+---+ | | | +---+---+ | |
| | | +--+ | | | | +--+ |
| +-+-+---+ | | +-+-+---+ |
| ↓ | | | |
| λ ←-------------+---------------+---------+ |
| | | |
| | | |
| | | |
| | | |
| E2 | | E5 |
| +-----------------+-----+ | +-----------------+-----+
| | balance: 50 | | | balance: 100 |
| | | | | |
| | | | | |
| +-----------------------+ | +-----------------------+
| ↑ | ↑
| | | |
| | | |
| +---+---+ | | +---+---+ |
+------→| | +--+ +------→| | +--+
+-+-+---+ +-+-+---+
↓ |
λ←-----------------------=---------------+
The environment structures of the two versions of make-withdraw
differ in that the second version creates one frame more than the
first version. That's the frame holding the initial-amount binding.
Exercise 3.11
Exercise:
In section 3.2.3 we saw how the environment model described the behavior of procedures with local state. Now we have seen how internal definitions work. A typical message-passing procedure contains both of these aspects. Consider the bank account procedure of section 3.1.1:
(define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (define (dispatch m) (cond ((eq? m 'withdraw) withdraw) ((eq? m 'deposit) deposit) (else (error "Unknown request -- MAKE-ACCOUNT" m)))) dispatch)Show the environment structure generated by the sequence of interactions
(define acc (make-account 50)) ((acc 'deposit) 40) 90 ((acc 'withdraw) 60) 30Where is the local state for
acckept? Suppose we define another account(define acc2 (make-account 100))How are the local states for the two accounts kept distinct? Which parts of the environment structure are shared between
accandacc2?
Answer:
global env
+---------------------------------------------------------------------------------------------------------+
| make-account:---+ acc:-------------------------------------------------------------+ |
| | | |
| | | |
| | | |
| | | |
| | | |
+------------------+-----------------------------------------------------------------------------------+--+
| ↑ |
+----------------+ | |
| | +-------------------------------------------------------------+ |
↓ | | balance: 50 withdraw:. deposit:. dispatch:. | |
+---+---+ | | | | | | |
| | |--------------+ | | | | | |
+-+-+---+ | | ---------+ | | |
↓ |+----------------------+ | | | |
λ || | | | |
|| | | | |
++------------------------+--------------------+--------------- |
| ↑ ↑ ↑ | | ↑ ↑ | ↑ |
+-+ | | | | | | | | | |
| | | | | | | | +--+ +--+------------+
| | | | | | | | | | |
↓ | | | ↓ | | | ↓ ↓ |
+---+---+ | | +---+---+ | | +---+---+
| | | | | | | | | | | | |
+---+---+ | | +---+---+ | | +---+---+
↓ | | ↓ | | ↓
λ | | λ | | λ
| | +--------+ |
| | | |
+----------+-------+ | | +----------+-------+
|m: 'deposit | | | |amount: 40 |
| | | | | |
| | | | | |
+------------------+ | | +------------------+
| |
| |
+-----------+ +------------+
| |
+--------+---------+ +---------+--------+
|m: 'withdraw | |amount: 60 |
| | | |
| | | |
+------------------+ +------------------+
The local state for acc is kept in the frame created by calling
make-account. If we define another account with (define acc2
(make-account 100)), then the local states for the two accounts are
kept distinct, because each call to make-account creates a frame (and
that is the frame where, as we we have seen, we keep the local state
of an account).
acc and acc2 share the text of the procedure objects widthdraw,
deposit, and dispatch.