Chris Pollett>Old Classes>PIC 15, Fall 1999>Hw5>HW5 Solution
Problem 3.10 We are asked to draw an event diagram for the following code:
(define (make-withdraw initial-amount)
(let ((balance initial-amount))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))))
(define W1 (make-withdraw 100))
(W1 50)
(define W2 (make-withdraw 100))
The event diagram for make-withdraw would look like:
###############################
# #
# make-withdraw : -- #
# | #
###################|###########
| ^
O O---|
|
V
Parameter: initial-amount
Body: (let ((balance initial-amount))
(lambda (amount)
(if (>= balance amount)
(begin (set! balance (- balance amount)
balance)
"Insufficient funds")))
When we define W1 we get:
###############################
# #
# make-withdraw :... #
# #
# W1:-- #
# | #
######|########################
| ^
| |
| ########################
| # #
| E1-># initial-amount: 100 #
| # #
| ########################
| ^
| |
| ############################
| # #
| E2-># balance: 100 #
| # #
| ############################
| ^ ((lambda (balance) ...) initial-amount)
O O------|
|
V
Parameter: amount
Body: (if (>= balance amount)
(begin (set! balance (- balance amount)
balance)
"Insufficient funds"))
When make-withdraw is evaluated at 100 we create a frame for the variable initial-amount and bind it to 100. We then try to evaluate the body of make-withdraw and bind the global variable W1 to the result. The body of make-withdraw is (let ((balance initial-amount)) ...) which we are told should be interpreted as ((lambda (balance) ...) initial-amount) . Thus, to evaluate the body of make-withdraw we need to evaluate the lambda expression (lambda (balance) ...) at initial-amount. So we create a new a new frame when we bind balance to the value of initial-amount . i.e., 100. The function we return is (lambda (amount) ...) where the current binding of balance is 100.
Next doing (W1 50) produces:
STEP: 1
###############################
# #
# make-withdraw :... #
# #
# W1:-- #
# | #
######|########################
| ^
| |
| ########################
| # #
| E1-># initial-amount: 100 #
| # #
| ########################
| ^
| |
| ############################
| # #
| E2-># balance: 100 #
| # #
| ############################
| ^ ^
| | |
| | ############################
| | # #
| | E3-># amount: 50 #
| | # #
| | ############################
| | (if (>= balance amount)
| | (begin (set! balance (- balance amount)
| | balance)
| | "Insufficient funds")
| |
| |
O O------|
|
V
Parameter: amount
Body: (if (>= balance amount)
(begin (set! balance (- balance amount)
balance)
"Insufficient funds"))
STEP: 2
###############################
# #
# make-withdraw :... #
# #
# W1:-- #
# | #
######|########################
| ^
| |
| ########################
| # #
| E1-># initial-amount: 100 #
| # #
| ########################
| ^
| |
| ############################
| # #
| E2-># balance: 50 #
| # #
| ############################
| ^
O O------|
|
V
Parameter: amount
Body: (if (>= balance amount)
(begin (set! balance (- balance amount)
balance)
"Insufficient funds"))
Finally, (define W2 (make-withdraw 100)) produces:
###########################################################
# #
# make-withdraw :... #
# #
# W2:------------------------------------------- #
# | #
# W1:-- | #
# | | #
######|########################################|###########
| ^ | ^
| | | |
| ######################## | ######################
| # # | # #
| E1-># initial-amount: 100 # | E3-># initial-amount 100 #
| # # | # #
| ######################## | ######################
| ^ | ^
| | | |
| ############### | ################
| # # | # #
| E2-># balance: 50 # | E4-># balance: 100 #
| # # | # #
| ############### | ################
| ^ | ^
O O------| O O-------|
|----------------------------------------|
V
Parameter: amount
Body: (if (>= balance amount)
(begin (set! balance (- balance amount)
balance)
"Insufficient funds"))
The difference between this and the previous version of make-withdraw is that calls to this version produce an extra frame.
Problem 3.27 We are asked to consider the following code:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
(define (memoize f)
(let ((table (make-table)))
(lambda (x)
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x)))
(insert! x result table)
result))))))
(define memo-fib
(memoize (lambda (n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (memo-fib (- n 1))
(memo-fib (- n 2))))))))
We are then asked to draw an environment diagram to analyze (memo-fib 3) . To understand (memo-fib 3) it is important to understand what is going on when we do (define (memo-fib n) ...):
###############################
# #
# memoize :... #
# #
# memo-fib:-- #
# | #
############|##################
| ^
| |
| #####################
| # #
| E1-># f: -------| #
| # | #
| ############|########
| ^ | ^
| | O O--|
| | |
| | V
| | Parameter: n
| | Body: (cond ((= n 0) 0)
| | ((= n 1) 1)
| | (else (+ (memo-fib (- n 1))
| | (memo-fib (- n 2))))))
| |
| |
| #####################
| # #
| E2-># table: (*table*) #
| # #
| #####################
| ^
| |
O O----------|
|
V
Parameter: x
(let ((previously-computed-result (lookup x table)))
(or previously-computed-result
(let ((result (f x))
(insert! x result table)
result))
The basic idea is the first frame is created when we bind f to the function we passed memoize . The second frame is created when we evaluate the (let ((table (make-table)) ...) form in the definition of memoize.
When we compute (memo-fib 3) we would first create a frame E3 referencing E2 where x is bound to 3. We then create a frame E4 referencing E3 which contains the value previously-computed-result equal to #f. For sake of brevity I am not giving the frames which would appear when we do (lookup x table). Next we create a frame E5 which references E4 which has result bound to the value (+ (memo-fib 2) (memo-fib 1)). (We skipped a frame attached to E2 where n gets bound to the value of x and f is evaluated.) In computing (memo-fib 2) we create a frame E6 referencing E5 with a variable x bound to the value 2. We then create a frame E7 referencing E6 which contains the value previously-computed-result equal to #f. Next we create a frame E8 which references E7 which has result bound to the value (+ (memo-fib 1) (memo-fib 0)). We would create two more frames in evaluating (memo-fib 1). However, in this case we can compute a value for (memo-fib 1) as 1 and we insert 1:1 into the table in frame E2. These two frames then die. Next we create two frames to calculate (memo-fib 0) as 0 and insert 0:0 into the table in frame E2. So result in frame E8 gets bound to 1 and 2:1 is inserted into the table in frame E2. The frames E6, E7, and E8 disappear but in E5 we now have result bound to (+ 1 (memo-fib 1)). So we now try to evaluate (memo-fib 1). We create a frame E9 where x is bound to 1. The we create a frame E10 where previously-computed value gets bound to 1 since lookup can find an entry for x. So as previously-computed-result is the first expression in the subsequent or and is non-zero we immediately return this value up to E5 where result now gets value 2. The frames E9 and E10 disappear we put 3:2 in the table and the value 2 gets returned. Frame E5, E4 and E3 disappear and we are done the computation.
We can show by induction that (memo-fib n) is \Theta(n). In the n=1 and n=0 case it is trivial. Next notice once we have done (memo-fib (- n 1)) it take only a constant amount of time to compute (memo-fib (-n 2)) since we look it up in the table. So for any n, (memo-fib n) takes time (memo-fib (- n 1)) + k which is time \theta(n-1)+k which is \Theta(n).
Just using (memoize fib) would not work because when we do the binding (result (f x)) in memoize, we would actually completely compute fib without the table at the value of x.
Non-book problem Below is some code to answer the non-book problem. Code from the book needed to run this code can be found on the hw4 page. Also, should type in accumulate from the book.
;Name: threshold-gate
;=====
;Purpose:
;========
;Takes a list of wires called [inputs], a single wire called [output]
;and an integer [thresh-value]. It then adds to the list of procedures
;of each wire in [inputs] the procedure threshold-action-procedure
;which is defined using the values of [inputs],[output], and [thresh-value]
;When one of the wires listed in inputs value changes and propagate is called
;then threshold-action-procedure will be called. It gets the signal-value
;of each wire in [inputs] and checks if the sum of the signals
;is greater than thresh-value. If it is [output]'s signal-value is changed ;after the appropriate delay.
;
;Known Bugs:
;===========
;none
(define (threshold-gate inputs output thresh-value)
(define (threshold-action-procedure)
(let ((new-value
(logical-threshold (map get-signal inputs) thresh-value)))
(after-delay threshold-gate-delay
(lambda ()
(set-signal! output new-value)))))
(for-each (lambda (x) (add-action! x threshold-action-procedure)) inputs)
'ok)
;Name: logical-threshold
;=====
;Purpose:
;========
;Takes as inputs as list called [inputs] of signal values and a integer
;called [thresh-value]. It outputs one if the number of entries equal to 1
; in the list is greater than thresh-value.
;
;Known Bugs:
;===========
; none
(define (logical-threshold inputs thresh-value)
(let ((on-lines (acummulate + 0 inputs)))
(if (< on-lines thresh-value) 0 1)))
;Name: threshold-gate-delay
;=====
;Purpose:
;========
;Delay time between when input wires to threshold gate change value and
;and when the output would change if it does
;
;Known Bugs:
;===========
;none
(define threshold-gate-delay 5)