SICP 习题参考答案 3.3

win_hate

没兴趣，这个题目以后做。

后面的一些题目要有趣得多。

win_hate

Exercise 3.27.  Memoization (also called tabulation) is a technique that enables a procedure to record, in a local table, values that have previously been computed. This technique can make a vast difference in the performance of a program. A memoized procedure maintains a table in which values of previous calls are stored using as keys the arguments that produced the values. When the memoized procedure is asked to compute a value, it first checks the table to see if the value is already there and, if so, just returns that value. Otherwise, it computes the new value in the ordinary way and stores this in the table. As an example of memoization, recall from section 1.2.2 the exponential process for computing Fibonacci numbers:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

The memoized version of the same procedure is

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))

where the memoizer is defined as

(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))))))

Draw an environment diagram to analyze the computation of (memo-fib 3). Explain why memo-fib computes the nth Fibonacci number in a number of steps proportional to n. Would the scheme still work if we had simply defined memo-fib to be (memoize fib)?

win_hate

(memoize f) 返回一个函数，这个函数的参数为自然数。如果 n 对应的函数值（f(n)） 已经在局部表中，则使用表格中的值，避免了计算；如果 n 对应的函数值不存在于表格中，则计算 f(n) 把结果插入到表格中。

f 必须能与 memoize 配合才能提高效率，简单地 (memoize fib) 是不行的。比如

1. 
   
2. (define g (memoize fib))
   

复制代码

假定现在表格中存有 1~n 对应的 fib(n)，在计算 g(n+1) 时，还是会通过 fib (n+1) 来计算， fib 对表格一无所知，不断通过自身进行递归，重新计算出表格中已有的数据。

题目的方法比较 'hack'，

• 把 (memoize f) 返回的函数命名为 memo-fib；
  
• f 是一个匿名函数，其中包含对 memo-fib 的调用。
  
  

这样实际上造出了 memo-fib 通过自身的递归，而它会查找、修改局部表。

下面是我写的带记忆的 fib 函数，比题目的容易理解多了。

1. 
   
2. (define (make-fib)
   
3.   (let ((table (make-table)))
   
4.     (define (fib n)
   
5.       (let ((t1 (lookup n table)))
   
6.         (if t1 t1
   
7.             (let ((t2 (+ (fib (- n 1))
   
8.                         (fib (- n 2)))))
   
9.               (insert! n t2 table)
   
10.               t2))))
    
11.     (insert! 0 0 table)
    
12.     (insert! 1 1 table)
    
13.     fib))
    

复制代码

这个题目有个有趣的地方，书上没提到－－－这个实现可以计算多大的 fib 值？

1. 
   
2. > (memo-fib 250)
   
3. ERROR: Stack overflow
   
4. ABORT: (stack-overflow)
   

复制代码

oops, 250 项都算不出来。但记忆表已经避免了很多递归啊。

避免递归的前提是记忆表中有足够多的数据。按现在的写法，如果表格是空的，或者只有少量数据，仍可能产生很深的递归。

这样一分析，可以看出，计算大的 n 是可行的，只要先计算一些小的 n.

再来：

1. 
   
2. > (memo-fib 200)
   
3. 280571172992510140037611932413038677189525
   
4. 
   
5. > (memo-fib 400)
   
6. 176023680645013966468226945392411250770384383304492191886725992896575345044216019675
   
7. 
   
8. > (memo-fib 600)
   
9. 110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200
   
10. 
    
11. > (memo-fib 800)
    
12. 69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
    
13. 
    
14. > (memo-fib 1000)
    
15. 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
    
16. 
    
17. > (memo-fib 1500)
    
18. ERROR: Stack overflow
    
19. ABORT: (stack-overflow)
    
20. 
    
21. > (memo-fib 1200)
    
22. 27269884455406270157991615313642198705000779992917725821180502894974726476373026809482509284562310031170172380127627214493597616743856443016039972205847405917634660750474914561879656763268658528092195715626073248224067794253809132219056382939163918400
    
23. 
    
24. > (memo-fib 1500)
    
25. ERROR: Stack overflow
    
26. ABORT: (stack-overflow)
    
27. 
    
28. > (memo-fib 1400)
    
29. 17108476902340227241249719513231821477382749898026920041550883749834348017250935801359315038923367841494936038231522506358371361016671790887791259870264957823133253627917432203111969704623229384763490617075388642696139893354058660570399927047816296952516330636633851111646387885472698683607925
    
30. 
    
31. > (memo-fib 1600)
    
32. 10733451489189611103121609043038710477166925241925645413424099370355605456852169736033991876014762808340865848447476173426115162172818890323837138136782951865054538417494035229785971002587932638902311416018904156170269354720460896363558168129004231138415225204738582550720791061581463934092726107458349298577292984375276210232582438075
    

复制代码

最后，如果初始表是空的，计算 (memo-fib n) 的递归深度是 n，‘宽度’ 是 2，所以是 O(n) 的。

[ 本帖最后由 win_hate 于 2008-12-22 18:39 编辑 ]

win_hate

Exercise 3.28.  Define an or-gate as a primitive function box. Your or-gate constructor should be similar to and-gate.

win_hate

1. 
   
2. (define (or-gate a1 a2 output)
   
3.   (define (or-action-procedure)
   
4.     (let ((new-value
   
5.            (logical-or (get-signal a1) (get-signal a2))))
   
6.       (after-delay or-gate-delay
   
7.                    (lambda ()
   
8.                      (set-signal! output new-value)))))
   
9.   (add-action! a1 or-action-procedure)
   
10.   (add-action! a2 or-action-procedure)
    
11.   'ok)
    

复制代码

演示

1. 
   
2. (define a (make-wire))
   
3. (define b (make-wire))
   
4. (define c (make-wire))
   
5. (or-gate a b c)
   
6. (set-signal! a 1)
   
7. (set-signal! b 0)
   
8. (probe 'a a)
   
9. (probe 'b b)
   
10. (probe 'c c)
    
11. (propagate)
    

复制代码

输出：

1. 
   
2. a 0 New-value = 1
   
3. b 0 New-value = 0
   
4. c 0 New-value = 0
   
5. c 5 New-value = 1
   

复制代码

注意这里的代码需要整个电路包，必须把整节代码完成后，才能运行。

[ 本帖最后由 win_hate 于 2008-12-26 23:40 编辑 ]

win_hate

Exercise 3.29.  Another way to construct an or-gate is as a compound digital logic device, built from and-gates and inverters. Define a procedure or-gate that accomplishes this. What is the delay time of the or-gate in terms of and-gate-delay and inverter-delay?

win_hate

1. 
   
2. (define (my-or-gate a1 a2 output)
   
3.   (let ((b1 (make-wire))
   
4.         (b2 (make-wire))
   
5.         (c (make-wire)))
   
6.     (inverter a1 b1)
   
7.     (inverter a2 b2)
   
8.     (and-gate b1 b2 c)
   
9.     (inverter c output)
   
10.   'ok))
    

复制代码

演示

1. 
   
2. (define a (make-wire))
   
3. define b (make-wire))
   
4. (define c (make-wire))
   
5. (my-or-gate a b c)
   
6. (set-signal! a 1)
   
7. (set-signal! b 0)
   
8. (probe 'a a)
   
9. (probe 'b b)
   
10. (probe 'c c)
    
11. (propagate)
    

复制代码

1. 
   
2. a 0 New-value = 1
   
3. b 0 New-value = 0
   
4. c 0 New-value = 0
   
5. c 2 New-value = 1
   
6. c 7 New-value = 0
   
7. c 7 New-value = 1
   

复制代码

注意 c 在时刻 2 变成了 1。 这是因为 make-wire 得到的线初始值为 0，所以整个系统一般并不处于稳定状态。比如一开始，内部的 c 和外部的 c(接口中的 output) 都是 0，所以在时刻 2，外部的 c 变为 1。

另外，这个 or-gate 不是原生的，而是利用 inverter 和 and-gate 搭起来的，所以延时跟 3.28 中的不一样。3.28 中那个延时是指定的。

[ 本帖最后由 win_hate 于 2008-12-27 16:19 编辑 ]

win_hate

Exercise 3.30.  Figure 3.27 shows a ripple-carry adder formed by stringing together n full-adders. This is the simplest form of parallel adder for adding two n-bit binary numbers. The inputs A1, A2, A3, ..., An and B1, B2, B3, ..., Bn are the two binary numbers to be added (each Ak and Bk is a 0 or a 1). The circuit generates S1, S2, S3, ..., Sn, the n bits of the sum, and C, the carry from the addition. Write a procedure ripple-carry-adder that generates this circuit. The procedure should take as arguments three lists of n wires each -- the Ak, the Bk, and the Sk -- and also another wire C. The major drawback of the ripple-carry adder is the need to wait for the carry signals to propagate. What is the delay needed to obtain the complete output from an n-bit ripple-carry adder, expressed in terms of the delays for and-gates, or-gates, and inverters?


Figure 3.27:  A ripple-carry adder for n-bit numbers.

win_hate

1. 
   
2. (define (full-adder A B Ci S Co)
   
3.   (let ((tmp (make-wire))
   
4.         (or1 (make-wire))
   
5.         (or2 (make-wire)))
   
6.     (half-adder B Ci tmp or2)
   
7.     (half-adder A tmp S or1)
   
8.     (or-gate or1 or2 Co)
   
9.     'ok))
   
10.         
    
11. (define (ripple-carry-adder A B S C)
    
12.   (define (f A B S last-c)
    
13.     (if (null? (cdr A))
    
14.         (full-adder (car A) (car B) last-c
    
15.                     (car S) C)
    
16.         (let ((c (make-wire)))
    
17.           (full-adder (car A) (car B) last-c
    
18.                       (car S) c)
    
19.           (f (cdr A) (cdr B) (cdr S) c))))
    
20.   (let ((c (make-wire)))
    
21.     (f A B S c)))
    
22. 
    
23. (define (make-wires n)
    
24.   (if (= n 0) '()
    
25.       (cons (make-wire) (make-wires (- n 1)))))
    
26. 
    
27. (define (set-signals! ws vs)
    
28.   (cond ((not (null? ws))
    
29.          (set-signal! (car ws) (car vs))
    
30.          (set-signals! (cdr ws) (cdr vs)))))
    
31. 
    
32. (define (get-signals ws)
    
33.   (if (null? ws) '()
    
34.       (cons (get-signal (car ws))
    
35.             (get-signals (cdr ws)))))
    
36. 
    
37. (define (probe-signals ws symb n)
    
38.   (cond ((null? ws) 'ok)
    
39.         (else
    
40.          (probe (cons n symb) (car ws))
    
41.          (probe-signal (cdr ws) symb (- n 1)))))
    

复制代码

演示代码：

1. 
   
2. (define A (make-wires 7))
   
3. (define B (make-wires 7))
   
4. (define S (make-wires 7))
   
5. (define c (make-wire))
   
6. (set-signals! A '(1 1 1 1 1 1 1))
   
7. (set-signals! B '(1 1 1 1 1 1 1))
   
8. (ripple-carry-adder A B S c)
   

复制代码

演示输出：

1. 
   
2. guile> (propagate)
   
3. done
   
4. guile> (get-signals A)
   
5. (1 1 1 1 1 1 1)
   
6. guile> (get-signals B)
   
7. (1 1 1 1 1 1 1)
   
8. guile> (get-signals S)
   
9. (0 1 1 1 1 1 1)
   
10. guile> (get-signal c)
    
11. 1
    

复制代码

[ 本帖最后由 win_hate 于 2008-12-27 16:26 编辑 ]

win_hate

现在讨论延时。把或门，与门，反转器的延迟记为 or, and 和 inv.

• 半加器：
  
  两个输入：A, B
  两个输出：S, C
  
  A->S 的时延为：
  
  max(or, and+inv)+and
  
  A-> C 的时延为:
  
  and
  
  B-> S
  
  max(or, and+inv)+and
  
  B-> C 时延为：
  
  and
  
  所以无论那一个输入发生变化，半加器的输出 s 的延迟为
  
  dhs=max(or, and+inv)+and
  
  半加器的输出 c 的延迟为:
  
  dhc= and
  
• 全加器：
  
  有三个输入 A, B, C(in)，两个输出 SUM, C(out)
  
  A -> SUM：dhs
  
  A-> C(out): dhc+or
  
  B -> SUM: 2 dhs
  
  B -> C(out): max(dhs+dhc, hdc)+or = dhs+hdc+or
  
  C(in) -> SUM: 2 dhs
  
  C(in) -> C(out): max(dhs+dhc, dhc)+or= dhs+dhc+or
  
  SUM 的延迟为 dfs=2dhs, C(out) 的延迟为：dfc=dhs+dhc+or
  
• ripple-carry-adder:
  
  C 的延迟为：n(dfc)
  S1 的延迟为：(n-1)dfc+dfs
  

按书本的设置：or=5, and=3, inv=2

有 dhs=max(or, and+inv)+and=max(5, 5)+3=8
dhc=and=3

dfs = 2dhs = 16
dfc = dhs+dhc+or=8+3+5=16

所以 C 的延迟为 16n, S1 的延迟为 16(n-1)+16=16n

这个只是理论上的最大延迟，但实际未必会达到。比如两个数相加，如果根本没有进位，就不会有进位带来的延迟，大小为 16 的时延就足够了。

[ 本帖最后由 win_hate 于 2008-12-27 16:27 编辑 ]