SICP 讨论：约束传播器的一个问题

win_hate

我在看 SICP 时碰到的一个问题，开始有点迷惑（现在好像又明白了）。抛块砖头，说一下自己的看法。

相关资料：

• 英文版：http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.5
• 中文版：p202
  

普通约束器件的 process-forget-value 函数最后会调用 process-new-value，中文版的 p202 页第 4 行说道：

如果加法对象被告知自己的一个连接器丧失了值，那么它就会要求其所有连接器丢掉它们的值（实际上，只有那些被该加法对象设置值的连接器会丢掉值），而后在运行它的过程 process-new-value。需要最后这一步的原因是，还可能有些连接器仍然有自己的值（也就是说，某个连接器过去所拥有的值原来就不是由这个加法对象设置的），这些值又可能需要通过这一加法对象传播。

加法器的代码如下

1. 
   
2. (define (adder a1 a2 sum)
   
3.   (define (process-new-value)
   
4.     (cond ((and (has-value? a1) (has-value? a2))
   
5.            (set-value! sum
   
6.                        (+ (get-value a1) (get-value a2))
   
7.                        me))
   
8.           ((and (has-value? a1) (has-value? sum))
   
9.            (set-value! a2
   
10.                        (- (get-value sum) (get-value a1))
    
11.                        me))
    
12.           ((and (has-value? a2) (has-value? sum))
    
13.            (set-value! a1
    
14.                        (- (get-value sum) (get-value a2))
    
15.                        me))))
    
16.   (define (process-forget-value)                            ;; <-- here
    
17.     (forget-value! sum me)
    
18.     (forget-value! a1 me)
    
19.     (forget-value! a2 me)
    
20.     (process-new-value))                                      ;; <-- here
    
21.   (define (me request)
    
22.     (cond ((eq? request 'I-have-a-value)  
    
23.            (process-new-value))
    
24.           ((eq? request 'I-lost-my-value)
    
25.            (process-forget-value))
    
26.           (else
    
27.            (error "Unknown request -- ADDER" request))))
    
28.   (connect a1 me)
    
29.   (connect a2 me)
    
30.   (connect sum me)
    
31.   me)
    

复制代码

英文版对应的文字：

If the adder is told that one of its connectors has lost a value, it requests that all of its connectors now lose their values. (Only those values that were set by this adder are actually lost.) Then it runs process-new-value. The reason for this last step is that one or more connectors may still have a value (that is, a connector may have had a value that was not originally set by the adder), and these values may need to be propagated back through the adder.

一开始，我觉得加法器在 process-forget-value 中不需要调用 process-new-value.



看一下这个 adder，a+b=c。每个连接器既是输入，也是输出。如果其中有两个确定了，则第三个就确定下来了。比如：

• 用户（或器件） A 设置 a=1, b=2 则 c 被 adder 设置为 3，此时我们可以：
  
  • forget 掉 a 的值，则 a 会通知 adder 忘掉它的值，从而 c 的值被清除，因为它的值是 adder 设置；但 b 的值被保留，因为不是 adder 设置的。
    这时调用 proce-new-value 没有意义，因为三个信号中有两个被清除了。
    
  • forget 掉 b 的值与 forget 掉 a 的值类似。
    
  • forget 掉 c 的值，这个是非法的。首先，c 的 informant，也就 adder 中的 me，是个内部标志，我们在外边是看不到的。如果耍些小手段，得到这个值，可以让 c forget。但 c 通知周边约束时，使用的是 for-each-except。也就是说，它不会去通知它的 informant，即 adder。结果变成 a=1, b=2, c 没有值。这是个错误状态。
    
    那么 proce-new-value 不是正好可以解决这个问题吗？可是此时 adder 根本不知道 c 的值已经没有了，因为 c 没哟通知它。
    
  
  
• A 把  a 设置为  1， B 把 b 设置为 2，adder 把 c 设置为 3.
  
  此时情况与上面类似。
  

基于上面的分析，我觉得在 process-no-value 中调用 process-new-value 是多余的。

但后来仔细想了一下，有下面这种罕见的情况：加法器的初始情形为： A 设置 a=1, B 设置 b=2, C 设置 c=3。这是可以做到的，代码如下：

1. 
   
2. (set-value! a 1 'A)
   
3. (set-value! b 2 'A)
   
4. (set-value! c 3 'C)
   
5. 
   
6. (adder a b c)
   
7. (probe 'a a)
   
8. (probe 'b b)
   
9. (probe 'c c)
   

复制代码

交换演示：

1. 
   
2. > (load "test.scm")
   
3. 
   
4. Probe: a = 1
   
5. Probe: b = 2
   
6. Probe: c = 3
   
7. 
   
8. > (forget-value! a 'A)
   
9. 
   
10. Probe: a = ?
    
11. Probe: a = 1done
    

复制代码

a 值被重新计算了出来。这种情形应该不多，一开始的稳定状态不是由约束系统本身计算出来的，而且强行设置的。

这种情形是我在写这个帖子的过程中想到的，之前想到的另一些情况见下贴。

[ 本帖最后由 win_hate 于 2009-1-3 12:50 编辑 ]

win_hate

与加法器不同，在乘法器的 process-forget-value 中调用 process-new-value 看上去是就是合理的。差别在于，加法器的约束很紧，而乘法器在某种情形下，要松一些。

设有乘法器



当 a 为 0 时，即使 b 没有值，乘法器也会把 c 设置为 0.

1. 
   
2. (set-value! a 0 'A)
   
3. (set-value! b 1 'B)
   
4. 
   
5. 
   
6. (multiplier a b c)
   
7. (probe 'a a)
   
8. (probe 'b b)
   
9. (probe 'c c)
   

复制代码

1. 
   
2. > (load "test.scm")
   
3. 
   
4. Probe: a = 0
   
5. Probe: b = 1
   
6. Probe: c = 0
   
7. 
   
8. > (forget-value! b 'B)
   
9. 
   
10. Probe: b = ?
    
11. Probe: c = ?
    
12. Probe: c = 0done
    

复制代码

在这里，尽管 b 值被清除导致  c 值被清除，但 c 值又马上被重新计算出来了。

在乘法器的启发下，不难构造出下面的器件：



其中 d 既可以通过 a,b, c 中的三个值求出，也可以通过两个值求出，甚至可以通过其中一个值求出。一个简单的方法就是让 d 为 a,b,c 的部分和。此时在 process-no-value 中调用  process-new-value 是必须的。

[ 本帖最后由 win_hate 于 2009-1-3 12:44 编辑 ]

win_hate

这个器件的 process-no-value 也是明显需要调用 process-new-value 的。