SICP 习题参考答案 3.3

win_hate

下面我们看一个具体的例子。用 probe 函数测试实际延迟，并手工计算延迟进行对比。

为简明起见，这里 ripple-carry-adder 的输入设置为两个比特。前面提到过，初始系统是不稳定的，分析起来很罗唆。所以我先用 (0 0) 跟 (1 1) 加一次。最后的结果是稳定的。此时设置时刻为 0，然后把 (0 0) 改为 (1 0)，这样将从最低位引发一个进位，并传播到最终进位上。

代码

1. 
   
2. (define A (make-wires 2))
   
3. (define B (make-wires 2))
   
4. (define S (make-wires 2))
   
5. (define c (make-wire))
   
6. (set-signals! A '(0 0))
   
7. (set-signals! B '(1 1))
   
8. 
   
9. 
   
10. (ripple-carry-adder A B S c)
    
11. (propagate)
    
12. 
    
13. (set-car! the-agenda 0)
    
14. 
    
15. (set-signals! A '(1 0))
    
16. (probe 'c c)
    
17. (probe 's1 (cadr S))
    
18. (propagate)
    

复制代码

输出：

1. 
   
2. c 0 New-value = 0
   
3. s1 0 New-value = 1
   
4. 
   
5. c 16 New-value = 1
   
6. s1 24 New-value = 0
   

复制代码

前两行是第一次 propagate 后 c, s1 的状态。此时系统是稳定的。

把 A 设置为 (1 0) 后，计算结果为 (1 0) + (1 1) = (0 0 1)  ;; 左边是最低位

c 在时刻 16 稳定为 1， 而 s1 在时刻 24 稳定为 0



c 和 s1 见上面的图。由于此时是两比特加两比特，所以上图中 n 为 2，s2 是最低位。

在时刻 0， A2 变为 1，看下面的半加器和全加器。



半加器的 A 在时刻 0 变为 1，所以 C 在时刻 3 改变， S 在时刻 8 改变。后面会看到，S 的改变对我们的分析没有影响。

再看全加器，现在是全加器中上面那个半加器的输出改变了。我们只关心这个全加器的 C(out) ，它在 5 个时刻后，也就是时刻 8 它的值从 0 变为 1。

于是我们看到，在时刻 8， 全加器 s2 产生的进位输出变为 1。

再看下面的半加器和全加器:



半加器的输入 C(in)  在时刻 8 从 0 变为 1。于是在 3 个时刻后，or-gate 靠下方的输入变为 1，5 个时刻后 or-gate 的输出 C(out) 变为 1。
由于 or-gate 有一个输入为 1，所以输出永远为 1，从而其输出稳定下来。这个时刻为 8+3+5=16

那么 SUM 呢？ 在时刻 8, C(in) 从 0 变为 1， 在 8 个时刻后，全加器中靠上的半加器的下方输入发生改变，又过 8 个时刻，SUM 发生改变。稳定时刻为 8+8+8 = 24.

这个分析与实际运行是一致的。

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

win_hate

Exercise 3.31.   The internal procedure accept-action-procedure! defined in make-wire specifies that when a new action procedure is added to a wire, the procedure is immediately run. Explain why this initialization is necessary. In particular, trace through the half-adder example in the paragraphs above and say how the system's response would differ if we had defined accept-action-procedure! as

(define (accept-action-procedure! proc)
  (set! action-procedures (cons proc action-procedures)))

win_hate

如果在 accept-action-procedure! 时不马上把函数执行一次(其实是插入 the-agenda 表)，则这个函数只被放进了线(wire)的函数列表，没有被放到 the-agenda 中。直到此线上信号改变时，这些函数才被插入到 the-agenda 中，排期执行。这会使整个系统中存在错误状态。以最简单的 inverter 为例，它对应的代码为：

1. 
   
2. (define (inverter input output)
   
3.   (define (invert-input)
   
4.     (let ((new-value (logical-not (get-signal input))))
   
5.       (after-delay inverter-delay
   
6.                    (lambda ()
   
7.                      (set-signal! output new-value)))))
   
8.   (add-action! input invert-input)
   
9.   'ok)
   

复制代码

线的初始值都是 0， 那么这个 inverter 的输入、输出都是 0，显然是不对的。如果 add-actions! 的时候把 invert-input 放到 the-agenda 中排队，那么两个时刻后，这个 inverter 的输入、输出就合乎逻辑了。如果 add-actions! 的时候，invert-input 没有马上排期，则 0 反转为 0 的错误状态将一直保持，直到这个 inverter 的输入发生变化才能更正。

书本上半加器的例子：

1. 
   
2. (define input-1 (make-wire))
   
3. (define input-2 (make-wire))
   
4. (define sum (make-wire))
   
5. (define carry (make-wire))
   
6. (probe 'sum sum)
   
7. sum 0  New-value = 0
   
8. (probe 'carry carry)
   
9. carry 0  New-value = 0
   
10. 
    
11. (half-adder input-1 input-2 sum carry)
    
12. ok
    
13. (set-signal! input-1 1)
    
14. done
    
15. (propagate)
    
16. sum 8  New-value = 1
    
17. done
    
18. 
    
19. (set-signal! input-2 1)
    
20. done
    
21. (propagate)
    
22. carry 11  New-value = 1
    
23. sum 16  New-value = 0
    
24. done
    

复制代码

象本题那样把代码改过后，书本上的半加器例子的输出变为：

1. 
   
2. (define input-1 (make-wire))
   
3. (define input-2 (make-wire))
   
4. (define sum (make-wire))
   
5. (define carry (make-wire))
   
6. 
   
7. (probe 'sum sum)
   
8. 
   
9. (probe 'carry carry)
   

复制代码

probe 的时候没有输出，因为对应的函数没有被马上执行。

1. 
   
2. > (half-adder input-1 input-2 sum carry)
   
3. ok
   
4. > (set-signal! input-1 1)
   
5. > (propagate)
   
6. done
   

复制代码

现在半加器的输入是 1， 0，输出是 0，0。这显然是错的。看看下面的半加器



A 变为 1， 这导致最右边的 and-gate 的靠上方的输入为 1，但靠下方的输入呢？ 左边 and-gete 的第一个输入改变为1，导致此 and-gate 的输出我为 0。但由于这个输出初始为 0，所以没有变化。这使得 inverter 的输入没有变化，从而输出也不变！如果当初代码没改动，则 inverter 的输入是会改变的。最终 S 得到一个错误的输出 0.

1. 
   
2. > (set-signal! input-2 1)
   
3. > (propagate)
   
4. carry 11 New-value = 1
   
5. done
   

复制代码

把半加器的 B 也设置为 1，此时 inverter 线上的错误被更正，得到正确的输出 S=0, C=1。但 S 的值没有变化，所以没有相应的 probe 信息。

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

win_hate

Exercise 3.32.  The procedures to be run during each time segment of the agenda are kept in a queue. Thus, the procedures for each segment are called in the order in which they were added to the agenda (first in, first out). Explain why this order must be used. In particular, trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the same segment and say how the behavior would differ if we stored a segment's procedures in an ordinary list, adding and removing procedures only at the front (last in, first out).

win_hate

先进先出使得电路上信号的变化与实际相符合，如果后进先出，会得到一个不同的信号序列。

比如 and 门输入从 0， 1 变为 1，0。尽管是同时发生，但仍有一个先后次序。如果先 0->1 再  1->0，则：

先入先出产生的输出信号为: 0(0), 1(3), 0(3)              ;;括号中的是时刻

如果是后进先出产生的输出信号为：0(0), 0(3)

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

win_hate

Exercise 3.33.  Using primitive multiplier, adder, and constant constraints, define a procedure averager that takes three connectors a, b, and c as inputs and establishes the constraint that the value of c is the average of the values of a and b.

win_hate

1. 
   
2. (define a (make-connector))
   
3. (define b (make-connector))
   
4. (define c (make-connector))
   
5. 
   
6. (define (average a b c)
   
7.   (let ((f (make-connector))
   
8.         (u (make-connector)))
   
9.     (adder a b u)
   
10.     (constant 2 f)
    
11.     (multiplier c f u)
    
12.     'ok))
    
13. 
    
14. (average a b c)
    
15. (probe 'c c)
    
16. (probe 'a a)
    
17. (probe 'b b)
    

复制代码

演示

1. 
   
2. > (set-value! a 10 'zxl)
   
3. 
   
4. Probe: a = 10done
   
5. > (set-value! b 20 'win_hate)
   
6. 
   
7. Probe: b = 20
   
8. Probe: c = 15done
   
9. > (forget-value! b 'zxl)
   
10. ignored
    
11. > (forget-value! b 'win_hate)
    
12. 
    
13. Probe: b = ?
    
14. Probe: c = ?done
    
15. > (set-value! c 20 'zxl)
    
16. 
    
17. Probe: c = 20
    
18. Probe: b = 30done
    

复制代码

[ 本帖最后由 win_hate 于 2009-1-1 11:54 编辑 ]

win_hate

对 Probe 时机的讨论。

如果我们把开始的代码改为：

1. 
   
2. (define a (make-connector))
   
3. (define b (make-connector))
   
4. (define c (make-connector))
   
5. 
   
6. (define (average a b c)
   
7.   (let ((f (make-connector))
   
8.         (u (make-connector)))
   
9.     (adder a b u)
   
10.     (constant 2 f)
    
11.     (multiplier c f u)
    
12.     'ok))
    
13. 
    
14. (probe 'b b)
    
15. (average a b c)
    
16. (probe 'c c)
    
17. (probe 'a a)
    

复制代码

不同之处仅在于 (probe 'b b) 一句提到 (average a b c) 前面了。运行结果变为

1. 
   
2. guile> (load "3.33.scm")
   
3. guile> (set-value! a 10 'zxl)
   
4. 
   
5. Probe: a = 10done
   
6. guile> (set-value! b 20 'win_hate)
   
7. 
   
8. Probe: c = 15
   
9. Probe: b = 20done
   
10. guile> (forget-value! b 'win_hate)
    
11. 
    
12. Probe: c = ?
    
13. Probe: b = ?done
    

复制代码

看上去是先 forget c ，然后才 forget b 的。但我们给出的指令是让 b forget，它 forget 后再通知周边约束，使 forget 指令传播出去。所以现在的输出有点可疑。

仔细分析一下代码，就会发现，连接器把约束存放在一个列表里，使用的方法是后进先出。Probe 也是一个约束器件：

• 设 Probe 是 b 的最后一个约束。b forget 掉自己的值后，以后进先出的方式遍历它的全体约束，并发送 forget 信息。第一个收到信息的约束器件为 b 的 Probe，于是立刻打印出 b 当前值，即 `?'。过一段时间后，连接器 c 收到 forget 信息，它也 forget 掉自己的值，然后它的 probe 打印出 c 的当前值为 `?'。
  
• 设 Probe 是 b 第一个约束。b forget 掉自己的值后，以后进先出的方式遍历它的全体约束，并发送 forget 信息。最后一个收到信息的约束器件为 b 的 Probe，在此之前，forget 信息已经被其它约束传播出去，个系统中应该 forget 的信息都已经 forget 掉了。所以 b 的 Probe 在最后一刻才打印出 '?'。但 b 的值的确是最早 forget 掉的，只是没有机会输出 Probe 信息而已。
  

[ 本帖最后由 win_hate 于 2009-1-2 11:08 编辑 ]

win_hate

Exercise 3.34.  Louis Reasoner wants to build a squarer, a constraint device with two terminals such that the value of connector b on the second terminal will always be the square of the value a on the first terminal. He proposes the following simple device made from a multiplier:

(define (squarer a b)
  (multiplier a a b))

There is a serious flaw in this idea. Explain.

win_hate

乘法器的三个连接器中，有两个确定了，才能求出第三个。

这个 squarer 的实现中，本质上只有两个连接器。在 a 给定时，三个连接器中有两个有值，所以能求出 b。但 b 给定时，另外‘两’ 个连接器 a 没有值。按乘法器的设计，只有一个值是无法求出另外两个值的。