笔记仓库

正常人的正常笔记集

约束传播

在之前的文章中我们试着利用可变数据建模完成了数字电路模拟系统,Structure and Interpretation of Computer Programs在紧随其后的小节Propagation of Constraints中用类似的方法实现了一个与之类似的约束系统(constraints system)用于加深对可变数据结构的理解。

数字电路模拟系统本身和其他大多数计算机程序体现一部分单向约束的性质,即给定足够的输入值即可约束输出值。而在实际的建模中,约束关系往往是双向的,给定一个等式关系,已知其中足够的变量值,就可以推导出其中未知变量的值。比如书中给的一个机械结构相关的方程:$$dAE=Fl$$其中$d$是金属杆的偏转(deflection),$A$为金属杆的横截面积(cross-sectional area),$E$为弹性模量(elastic modulus),$F$是作用于金属杆的力(force),$l$为杆的长度(length)。这个等式关系保证了获得了其中任意四个变量的值即可求得到剩下的那个变量的值,无论这些量在等式的左边还是右边。但传统的程序设计语言迫使我们把这些量的计算表达为单向的赋值(assignment),同一个程序无法用于计算在等式两边的量,当然也无法用于计算在等式一边的两个量。

在本文中,我们的目标是给约束系统的实现提供一些简单的支持,就像前文所设计的电路模拟系统,我们在此也用scheme设计一个能添加变量约束并使用它们来完成一些变量求值的系统。很容易想象,需要解决的问题是某个值确定后,它参与的约束关系中的其他值是否也会被确定?而它们被确定后它们参与的其他约束中的其他值是否也会被确定?这样如同多米诺骨牌的坍塌来自于约束关系本身之间的连接,环境中的约束关系们形成了一个约束网络(constraint network),而痛点在于如何实现新设置的值在这个网络中无向的传播。

正如前文所说,这里的实现非常类似于数字电路模拟器,但约束系统却不要求约束传播(constraint propagation)的行为存在延迟,比起电路更纯粹的地方便是不用agenda来规划值的变化,只需即时反馈。而相比电路复杂的地方,在于值的传播是在整个网络中无向的。接下来,我们就要一步步用scheme去完成这样的系统。

Connector

连接器connector可以类比为数字电路的wire对象,可以看成一个“装载”变量值的容器,是参与约束的基本元素,比如上式的五个变量分别可以看成一个connector。除了要求能容纳变量值的信息,它能被放置到约束网络,也同时要求它记录着自己参与了哪些约束。

更具体的去考虑它应该满足的性质,还需要能够实现以下针对它的操作:

  • (has-value? <connector>) 这个变量的值是否已知
  • (get-value <connector>) 返回这个变量当前的值
  • (set-value! <connector> <new-value> <informant>) 把当前变量connector的值根据informat的指令设置为新值new-value,这里的informat泛指一切有权改变connector值的对象,比如直接来自用户'user的命令,或者它参与的约束,可以在收集了关于其他变量的足够信息后来确定它的值。
  • (forget-value! <connector> <retractor>)connector根据retractor的要求丢弃掉现在的值。这是与前一个函数相对的操作,retractor同样可以是用户或者约束
  • (connect <connector> <new-constraint>)connector参与新的约束new-constraint

如果选择模仿wire的实现,把connector表达为message-passing风格的,带有局部状态变量的过程对象,那么封装在每个connector的局部变量应该有这样的三个:

  • valueconnector当前装载的变量值,初始化为#f表示当前没有值,在被设置后为具体的变量值
  • constraints: connector参与的所有约束,是一个由constraint构成的list,初始化为空列表
  • informant:最后一次改变connector值时的对象

前两个变量可以分别类比为wire的局部变量signal-valueaction-procedures,而增加的informant是由于约束的传播是无向的,被要求丢弃当前值时必须确认这个请求是否来自之前设置它的值的对象,保证数据的一致性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(define (make-connector)
(let ((value false) (informant false) (constraints '()))
(define (set-my-value newval setter)
(cond ((not (has-value? me))
(set! value newval)
(set! informant setter)
(for-each-except setter
inform-about-value ;defined differently for different constraint
constraints))
((not (= value newval)) ;has a value different from the designated value
(error "Contradiction" (list value newval)))
(else 'ignored)))

(define (forget-my-value retractor)
(if (eq? retractor informant)
(begin (set! informant false)
(for-each-except retractor
inform-about-no-value ;defined differently for different constraint
constraints))
'ignored))

(define (connect new-constraint)
(if (not (memq new-constraint constraints)) ;ensure the constraint NEW
(set! constraints
(cons new-constraint constraints)))
(if (has-value? me) ;already has a value
(inform-about-value new-constraint)) ;propagate immediately
'done)

(define (me request)
(cond ((eq? request 'has-value?)
(if informant true false))
((eq? request 'value) value)
((eq? request 'set-value!) set-my-value)
((eq? request 'forget) forget-my-value)
((eq? request 'connect) connect)
(else (error "Unknown operation -- CONNECTOR"
request))))
me))

set-my-valueforget-my-value这两个对偶的局部过程中用到的for-each-except定义为

1
2
3
4
5
6
7
(define (for-each-except exception procedure list)
(define (loop items)
(cond ((null? items) 'done)
((eq? (car items) exception) (loop (cdr items)))
(else (procedure (car items))
(loop (cdr items)))))
(loop list))

list中除了exception以外的对象都依次当成参数执行procedure过程。这两个局部过程都是由于值的改变需要传播给参与约束的其他变量,所以调用它参与的约束的inform-about-valueinform-about-no-value过程,这两个过程的定义根据被调用的约束对象constraint的不同会调用不同的过程,这种行为有些类似于面向对象编程的多态(polymorphism)概念,它们的具体实现会在后文定义不同的constraint时详细给出。至于为什么必须把传值的约束排除出列表,很好理解,除了本身没必要以外,还会造成该约束不断地再次传值回来,使得传播无法终止。

forget-my-value会检查retractor是否为informant,因为如果丢弃值的请求并非来自确定值的约束,那么其他约束中缺失了某个值,对确定这个connector实际上是没有影响的。比如a=b+c,c=d*e,如果c的值已经由a=b+c约束确定了,那么e值丢失通过c=d*e传递到cc的值还是由ab决定的,不需要理会e值丢失的通知。

me过程的作用相当于我们之前见过的dispatch过程,每个connector实质上也由me过程对象来表示的。接下来还是依循惯例用语法接口把它包装得更像一个数据对象而非过程对象:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(define (has-value? connector)
(connector 'has-value?))

(define (get-value connector)
(connector 'value))

(define (set-value! connector new-value informant)
((connector 'set-value!) new-value informant))

(define (forget-value! connector retractor)
((connector 'forget) retractor))

(define (connect connector new-constraint)
((connector 'connect) new-constraint))

Constraint

约束constraint类似于数字电路的功能元件(function box),用于规定connector之间的关系。connector之间通过constraint通信,更具体来说,connector的变值操作通过对constraintinform-about-value/inform-about-no-value传递给同一个约束的其他connector,正如前文所给的for-each-except规定的传播关系。那么constraint自然需要有以下过程可供操作

  • (inform-about-value <constraint>) 通知constraint约束关系中有一个connector的值被设置了,需要刷新确定其他参与该约束的connector的值
  • (inform-about-no-value <constraint>)通知constraint约束关系中有一个connector的值被丢弃了,需要刷新丢弃其他参与该约束的connector的值

具体如何设置和丢弃约束中其他量,需要根据约束的类型而确定。

复杂的约束也可以通过简单的约束组合而成,这里我们使用三种基础的约束关系addermultiplierconstant作为primitive constraint,这个选择并非基于任何理论基础,只是为了演示方便,你完全可以定义其他的primitive constraint作为基本元件来组装你自己的约束网络。

Primitive constraints

(adder a1 a2 sum)构造了一个表示a1+a2=sum的加法关系约束,已知其中任意两个量可以得到第三个量。也用message-passing风格的写法定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
(define (adder a1 a2 sum)
(define (process-new-value)
(cond ((and (has-value? a1) (has-value? a2))
(set-value! sum
(+ (get-value a1) (get-value a2)) ;sum=a1+a2
me))
((and (has-value? a1) (has-value? sum))
(set-value! a2
(- (get-value sum) (get-value a1)) ;a2=sum-a1
me))
((and (has-value? a2) (has-value? sum))
(set-value! a1
(- (get-value sum) (get-value a2)) ;a1=sum-a2
me))))

(define (process-forget-value)
(forget-value! sum me)
(forget-value! a1 me)
(forget-value! a2 me)
(process-new-value))

(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- ADDER" request))))

(connect a1 me)
(connect a2 me)
(connect sum me)

me)

adder过程的返回对象是加法约束关系构造完成后的局部过程meme就代表这个约束关系本身。同时me也充当了其他函数的dispatch角色根据需求调用不同的过程。另外,函数中调用了许多如set-value!等需要一个constraint对象作为一个参数的过程,都使用me代表这个adder实例作为实参传入了,它就像C++的this指针或者Python的self对象,connector的某些操作需要填入来自于哪个constraint,它就在这里签名“是我干的”,至于“我”是谁,从外部当然能看得到。

局部过程process-new-value根据加法等式关系,确定并设置未知量。局部过程process-forget-value丢弃掉所有根据这个adder关系决定的值,并再次调用(process-new-value)恢复一些根据这个关系和关系中依然已知的值(比如常量)确定的变量值。

当然,还是需要用一直和dispatch连用的语法接口继续封装一下:

1
2
3
4
(define (inform-about-value constraint)
(constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
(constraint 'I-lost-my-value))

Scheme是动态类型语言,调用inform-about-value/inform-about-no-value时也不会检查constraint是否是adder,甚至不会检查是否是constraint,当然constraint本来就是我们自己定义的一个过程对象而已,也没法检查。它只会检查constraint是不是能被以一个参数调用的过程,这就给我们针对不同的约束定义行为不同的(constraint 'I-have-a-value)/(constraint 'I-lost-my-value)过程留下很大的自由。接下来完成的其他约束定义还可以调用inform-about-valueinform-about-no-value过程,但可能在约束中完成的就是完全不同的操作了。

乘法约束与加法约束类似,(multiplier m1 m2 product)构造了m1*m2=product的关系,可以仿照上面的写法完成multiplier的定义,稍有不同的是,m1m2只要有一个是0,无论另一个取值为多少,product也必须为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
(define (multiplier m1 m2 product)
(define (process-new-value)
(cond ((or (and (has-value? m1) (= (get-value m1) 0))
(and (has-value? m2) (= (get-value m2) 0)))
(set-value! product 0 me))
((and (has-value? m1) (has-value? m2))
(set-value! product
(* (get-value m1) (get-value m2))
me))
((and (has-value? product) (has-value? m1))
(set-value! m2
(/ (get-value product) (get-value m1))
me))
((and (has-value? product) (has-value? m2))
(set-value! m1
(/ (get-value product) (get-value m2))
me))))

(define (process-forget-value)
(forget-value! product me)
(forget-value! m1 me)
(forget-value! m2 me)
(process-new-value))

(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- MULTIPLIER" request))))

(connect m1 me)
(connect m2 me)
(connect product me)

me)

所以在(process-new-value)中会先讨论m1m2为0的情况,这样也避免了之后方向计算product除以m1m2时出现除零错误的可能性。同样,我们在上面定义的语法接口对multiplier也可以用,即使它的inform-about-value非常不同于加法。

最后我们来定义常量约束(constant value connector),把connector的值固定为常量value,不可更改也不可丢失,也就是说'I-have-a-value'I-lost-my-value消息的传入对于这样的常量是没有意义的,会产生错误1

1
2
3
4
5
6
7
8
(define (constant value connector)
(define (me request)
(error "Unknown request -- CONSTANT" request))

(connect connector me)
(set-value! connector value me)

me)

Probe

同样为了观察变量值的变化,需要在connector上安置探针probe回顾数字电路中安置于wire的探针probe所做的是在wireaction-procedures列表中添加一个打印过程,而这里connector上的probe需要的也是在connectorconstraints列表中添加一个过程对象,保证connector的值发生变化(由于局部过程set-my-value/forget-my-value的调用)时遍历调用constraints时顺便调用一个这样一个打印过程,probe的行为在形式上与一般的constraint十分相似。因此为了方便起见,也可以把probe定义为一个类似于constraint的过程对象,传入'I-have-a-value'I-lost-my-value时只需要打印新的值而不负责传播改变其他connector的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(define (probe name connector)
(define (print-probe value)
(newline)
(display "Probe: ")
(display name) ;identifier of the probe
(display " = ")
(display value)
(newline))

(define (process-new-value)
(print-probe (get-value connector)))

(define (process-forget-value)
(print-probe "?")) ;indicates the connector has no value

(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- PROBE" request))))

(connect connector me)

me)

初始化后的probe同样可以作为constraint以语法接口inform-about-valueinform-about-no-value调用。

Sample usages

至此,约束系统的基础环境已经定义结束。我在这里同样把上面用到的所有代码打包,在Scheme Interpreter and VisualizerEditor可以通过命令

1
(download '9e52aa9cadce69f251a11fed2b0f0e8a)

直接使用这个简单的约束系统进行体验。

下面给出一些简单的示例演示如何直接使用我们之前定义的约束。

Temperature converter

众所周知,摄氏(Celsius)温度$C$华氏(Fahrenheit)温度$F$之间的关系为$$9C=5(F-32)$$由这个关系构造的约束网络如下图所示
9C=5(F-32)定义的约束网络
从左到右三个灰色的盒子分别代表multipliermultiplieradder三个约束关系。形参连接的终端为某个量(connector):如C为摄氏温度的值,F为华氏温度的值,wx,y分别被设置为常量9,5,32,这里还命名和使用了很多没有在公式中出现的中间量,如u同时参与约束C*w=uu=v*x,同样v也是这样一个中间量表示v+y=F。整个约束中的变量只有CF,其他都是常量或是由它们决定的中间量。

那么利用primitives构造的celsius-fahrenheit-converter约束可以表示为

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (celsius-fahrenheit-converter c f)
(let ((u (make-connector))
(v (make-connector))
(w (make-connector))
(x (make-connector))
(y (make-connector)))
(multiplier c w u)
(multiplier v x u)
(adder v y f)
(constant 9 w)
(constant 5 x)
(constant 32 y)
'ok))

新建一个celsius-fahrenheit-converter的实例

1
2
3
(define C (make-connector))
(define F (make-connector))
(celsius-fahrenheit-converter C F)

在终端连接器CF上安置probe以便观察取值变化

1
2
(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)

用户设置C为25可以马上发现CF的值被确定了

1
2
3
4
(set-value! C 25 'user)
;Probe: Celsius temp = 25
;Probe: Fahrenheit temp = 77
;'done

但再次试图直接设置F时发现取值冲突

1
2
(set-value! F 212 'user)
;Error! Contradiction (77 212)

因为F已经被约束关系确定为77了,不能再通过命令直接更改,除非重置清除C的取值

1
2
3
4
(forget-value! C 'user)
;Probe: Celsius temp = ?
;Probe: Fahrenheit temp = ?
;done

使得F也同时无法被确定,那么此时再直接设置F为212可以重新获得一组CF的值

1
2
3
4
(set-value! F 212 'user)
;Probe: Fahrenheit temp = 212
;Probe: Celsius temp = 100
;done

至此,我们分别完成了celsius-fahrenheit-converter两个方向的约束传播。

Averager

定义一个约束(averager a b c),其中a,bc都是connector,要求满足关系c=(a+b)/2

可以像组装电路一样用我们刚才定义好的三种primitives直接组合,把关系写为a+b=2*c

1
2
3
4
5
6
7
(define (averager a b c)
(let ((a-plus-b (make-connector))
(const (make-connector)))
(constant 2 const)
(adder a b a-plus-b)
(multiplier const c a-plus-b)) ;a+b=const*c
'ok)

开始一个实例

1
2
3
4
5
6
7
8
9
(define A (make-connector))
(define B (make-connector))
(define C (make-connector))

(averager A B C)

(probe "a" A)
(probe "b" B)
(probe "c" C)

简单进行操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(set-value! A 5 'user)
;Probe: a = 5
;done

(set-value! B 7 'user)
;Probe: b = 7
;Probe: c = 6
;done

(forget-value! A 'user)
;Probe: a = ?
;Probe: c = ?
;done

(set-value! C 20 'user)
;Probe: c = 20
;Probe: a = 33
;done

Squarer

某人想建立一个(squarer a b)约束,变量值满足关系b=a^2,于是他一拍大腿想到利用multiplier写了一个2

1
2
(define (squarer a b)
(multiplier a a b))

这个投机取巧的写法存在着严重的缺陷。不同于普通的乘法约束,平方约束关系隐含着b的值必须非负的限制。而且当b的值为0时,a的值也必然为0。另外,如果有a为非负数的约定,那么还可以通过b反向传播得到a的取值。

另一个实现的方法就是从底层开始自己定义squarer约束,把它作为primitive来写,为了简单起见,这里规定a>=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define (square x) (* x x))

(define (squarer a b)
(define (process-new-value)
(if (has-value? b)
(if (< (get-value b) 0)
(error "square less than 0 -- SQUARER" (get-value b))
(set-value! a (sqrt (get-value b)) me))
(if (has-value? a)
(if (< (get-value a) 0)
(error "a less than 0 -- SQUARER" (get-value a))
(set-value! b (square (get-value a)) me))
'ignore)))
(define (process-forget-value)
(forget-value! a me)
(forget-value! b me)
(process-new-value))
(define (me request)
(cond ((eq? request 'I-have-a-value)
(process-new-value))
((eq? request 'I-lost-my-value)
(process-forget-value))
(else
(error "Unknown request -- SQUARER" request))))
(connect a me)
(connect b me)
me)

Expression-oriented format

前文的celsius-fahrenheit-converter定义内部使用了很多中间变量,然后一句句写了连接命令,略显笨拙,我们可以用更简洁的方式重新定义它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
(define (celsius-fahrenheit-converter x);
(c+ (c* (c/ (cv 9) (cv 5))
x)
(cv 32)))

(define C (make-connector))
(define F (celsius-fahrenheit-converter C))

(define (c+ x y) ;return a connector whose value=x+y
(let ((z (make-connector)))
(adder x y z)
z))

(define (c* x y) ;return a connector whose value=x*y
(let ((z (make-connector)))
(multiplier x y z)
z))

(define (c/ x y) ;return a connector whose value=x/y
(let ((z (make-connector)))
(multiplier z y x)
z))

(define (cv x) ;return a connector whose value=constant x
(let ((z (make-connector)))
(constant x z)
z))

这样的定义中,复合成celsius-fahrenheit-converter所用到的单句表达式更符合纯函数式编程的习惯,在这里更是和Scheme原生的前缀算术表达式高度相似;而原定义则更具指令式编程(imperative programming)的风格。

Lisp允许复合对象作为过程的值返回,所以我们可以轻松转换成上面面向表达式(expression-oriented)的程序写法,而在如Algol, Basic和Pascal(除非熟练指针变量的操作)等不擅长处理复合对象的语言中,处理复合对象就只能用指令式的写法了。当然非面向表达式的写法也同样有不可替代的优势,除了编写时更符合人类自然语言的思维习惯,还有一点是在约束对象和连接器对象上提供了句柄(handle),使得我们在系统中直接用约束扩展的连接扩展更加方便快捷,而不用通过间接变换连接器的操作实现。

Epilogue

至此,关于约束系统的讲解已基本结束。虽然上面的工作看上去像是小孩子拿着玩具在过家家,但真实世界中的约束系统还是有不少实用之处的,如果对此感兴趣可以尝试着做一些扩展阅读。

约束传播的概念最早出现在Sutherland3在1963年的博士论文中,当然这篇论文网上也很难找了,但容易找到基于相同内容的技术报告材料,不过似乎constraint只是他用以辅助规范graphical language的小工具,并没有非常侧重的去讨论。最早实现的一个优雅的基于 Smalltalk语言的约束传播系统ThinkPad4用于仿真。还有一些早期应用于电路分析5的约束系统。如今在更多领域,约束问题都被广泛地讨论着,甚至发展出了约束编程(constraint programming)

当然广义的constraint思想也可以给我们很多问题的启发,比如国内的教科书往往会在提到约束传播时用八皇后问题的求解作为例子。除此以外,也有些很有趣的妙用,如求解数独Solving Every Sudoku Puzzle

在本文的结尾,我想转引SICP第三章用到的两句名言:

Mεταβάλλον ὰναπαύεται
(Even while it changes, it stands still.)
—Heraclitus

以及

Plus ça change, plus c’est la même chose.
—Alphonse Karr

大意为事物变化得越多,他们保留不变得也越多。它们被用在讲述使用mutable data structure进行编程的第三章,是想告诉你即使使用了不那么纯粹的函数式编程的方式去操纵改变数据,我们还是有办法紧紧抓住数据中不变的部分服务于我们的程序。而我在这里引用这两句话,是想说即使我们不断地去尝试和开拓不同的语言在不同的环境中光怪陆离的用法,实现曾经想都没想过的东西,都是从最基础的用法开始一点点编写,每次写不同的东西最终都是加深对同一个体系的理解,一步步找寻住在计算机内的神灵,在追求本质美丽和自由的道路上曲折前行。


  1. 1.传入这两个消息直接调用error过程的写法是SICP给出的,但在实际应用中,尝试对常量进行修改操作一般并非出于用户直接的不当操作,而是它参与的其他约束关系传播过来的变值请求,忽略这些请求返回‘ignored即可,没有必要处理成error消息。
  2. 2.案例来源于习题3.34,schemewiki社区对此给出的解释是这个设计的瑕疵在于b获取值后无法传播给a,但事实上如果没有限定a的符号,已知b的值依然无法确定a的值。
  3. 3.Sutherland, Ivan E. "Sketch pad a man-machine graphical communication system." In Proceedings of the SHARE design automation workshop, pp. 6-329. ACM, 1964.
  4. 4.Borning, Alan. "ThingLab: an object-oriented system for building simulations using constraints." In Proceedings of the 5th international joint conference on Artificial intelligence-Volume 1, pp. 497-498. Morgan Kaufmann Publishers Inc., 1977.
  5. 5.Sussman, Gerald Jay, and Guy Lewis Steele Jr. "CONSTRAINTS—A language for expressing almost-hierarchical descriptions." Artificial intelligence 14, no. 1 (1980): 1-39.