約束傳播
約束傳播
來自專欄最短的咒
9 人贊了文章
原文地址（我的博客）
約束傳播
在之前的文章中我們試著利用可變數據建模完成了數字電路模擬系統，Structure and Interpretation of Computer Programs在緊隨其後的小節Propagation of Constraints中用類似的方法實現了一個與之類似的約束系統（constraints system）用於加深對可變數據結構的理解。
數字電路模擬系統本身和其他大多數計算機程序體現一部分單向約束的性質，即給定足夠的輸入值即可約束輸出值。而在實際的建模中，約束關係往往是雙向的，給定一個等式關係，已知其中足夠的變數值，就可以推導出其中未知變數的值。比如書中給的一個機械結構相關的方程：
其中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的局部變數應該有這樣的三個：
value：connector當前裝載的變數值，初始化為#f表示當前沒有值，在被設置後為具體的變數值constraints:connector參與的所有約束，是一個由constraint構成的list，初始化為空列表informant：最後一次改變connector值時的對象
前兩個變數可以分別類比為wire的局部變數signal-value和action-procedures，而增加的informant是由於約束的傳播是無向的，被要求丟棄當前值時必須確認這個請求是否來自之前設置它的值的對象，保證數據的一致性。
(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-value和forget-my-value這兩個對偶的局部過程中用到的for-each-except定義為
(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-value或inform-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傳遞到c，c的值還是由a和b決定的，不需要理會e值丟失的通知。
me過程的作用相當於我們之前見過的dispatch過程，每個connector實質上也由me過程對象來表示的。接下來還是依循慣例用語法介面把它包裝得更像一個數據對象而非過程對象：
(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的變值操作通過對constraint的inform-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的值
具體如何設置和丟棄約束中其他量，需要根據約束的類型而確定。
複雜的約束也可以通過簡單的約束組合而成，這裡我們使用三種基礎的約束關係adder，multiplier和constant作為primitive constraint，這個選擇並非基於任何理論基礎，只是為了演示方便，你完全可以定義其他的primitive constraint作為基本元件來組裝你自己的約束網路。
Primitive constraints
(adder a1 a2 sum)構造了一個表示a1+a2=sum的加法關係約束，已知其中任意兩個量可以得到第三個量。也用message-passing風格的寫法定義：
(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過程的返回對象是加法約束關係構造完成後的局部過程me，me就代表這個約束關係本身。同時me也充當了其他函數的dispatch角色根據需求調用不同的過程。另外，函數中調用了許多如set-value!等需要一個constraint對象作為一個參數的過程，都使用me代表這個adder實例作為實參傳入了，它就像C++的this指針或者Python的self對象，connector的某些操作需要填入來自於哪個constraint，它就在這裡簽名「是我乾的」，至於「我」是誰，從外部當然能看得到。
局部過程process-new-value根據加法等式關係，確定並設置未知量。局部過程process-forget-value丟棄掉所有根據這個adder關係決定的值，並再次調用(process-new-value)恢復一些根據這個關係和關係中依然已知的值（比如常量）確定的變數值。
當然，還是需要用一直和dispatch連用的語法介面繼續封裝一下：
(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-value和inform-about-no-value過程，但可能在約束中完成的就是完全不同的操作了。
乘法約束與加法約束類似，(multiplier m1 m2 product)構造了m1*m2=product的關係，可以仿照上面的寫法完成multiplier的定義，稍有不同的是，m1和m2只要有一個是0，無論另一個取值為多少，product也必須為0
(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)中會先討論m1或m2為0的情況，這樣也避免了之後方向計算product除以m1或m2時出現除零錯誤的可能性。同樣，我們在上面定義的語法介面對multiplier也可以用，即使它的inform-about-value非常不同於加法。
最後我們來定義常量約束(constant value connector)，把connector的值固定為常量value，不可更改也不可丟失，也就是說I-have-a-value和I-lost-my-value消息的傳入對於這樣的常量是沒有意義的，會產生錯誤[1]。
(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所做的是在wire的action-procedures列表中添加一個列印過程，而這裡connector上的probe需要的也是在connector的constraints列表中添加一個過程對象，保證connector的值發生變化（由於局部過程set-my-value/forget-my-value的調用）時遍歷調用constraints時順便調用一個這樣一個列印過程，probe的行為在形式上與一般的constraint十分相似。因此為了方便起見，也可以把probe定義為一個類似於constraint的過程對象，傳入I-have-a-value和I-lost-my-value時只需要列印新的值而不負責傳播改變其他connector的值。
(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-value和inform-about-no-value調用。
Sample usages
至此，約束系統的基礎環境已經定義結束。我在這裡同樣把上面用到的所有代碼打包，在Scheme Interpreter and Visualizer或Editor可以通過命令
(download 9e52aa9cadce69f251a11fed2b0f0e8a)
直接使用這個簡單的約束系統進行體驗。
下面給出一些簡單的示例演示如何直接使用我們之前定義的約束。
Temperature converter
眾所周知，攝氏（Celsius）溫度C華氏（Fahrenheit）溫度F之間的關係為
由這個關係構造的約束網路如下圖所示
從左到右三個灰色的盒子分別代表multiplier，multiplier和adder三個約束關係。形參連接的終端為某個量（connector）：如C為攝氏溫度的值，F為華氏溫度的值，w，x,y分別被設置為常量9,5,32，這裡還命名和使用了很多沒有在公式中出現的中間量，如u同時參與約束C*w=u和u=v*x，同樣v也是這樣一個中間量表示v+y=F。整個約束中的變數只有C和F，其他都是常量或是由它們決定的中間量。
那麼利用primitives構造的celsius-fahrenheit-converter約束可以表示為
(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的實例
(define C (make-connector))(define F (make-connector))(celsius-fahrenheit-converter C F)
在終端連接器C和F上安置probe以便觀察取值變化
(probe "Celsius temp" C)(probe "Fahrenheit temp" F)
用戶設置C為25可以馬上發現C和F的值被確定了
(set-value! C 25 user);Probe: Celsius temp = 25;Probe: Fahrenheit temp = 77;done
但再次試圖直接設置F時發現取值衝突
(set-value! F 212 user);Error! Contradiction (77 212)
因為F已經被約束關係確定為77了，不能再通過命令直接更改，除非重置清除C的取值
(forget-value! C user);Probe: Celsius temp = ?;Probe: Fahrenheit temp = ?;done
使得F也同時無法被確定，那麼此時再直接設置F為212可以重新獲得一組C和F的值
(set-value! F 212 user);Probe: Fahrenheit temp = 212;Probe: Celsius temp = 100;done
至此，我們分別完成了celsius-fahrenheit-converter兩個方向的約束傳播。
Averager
定義一個約束
(averager a b c)，其中a,b和c都是connector，要求滿足關係c=(a+b)/2
可以像組裝電路一樣用我們剛才定義好的三種primitives直接組合，把關係寫為a+b=2*c
(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)
開始一個實例
(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)
簡單進行操作：
(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]
(define (squarer a b) (multiplier a a b))
這個投機取巧的寫法存在著嚴重的缺陷。不同於普通的乘法約束，平方約束關係隱含著b的值必須非負的限制。而且當b的值為0時，a的值也必然為0。另外，如果有a為非負數的約定，那麼還可以通過b反向傳播得到a的取值。
另一個實現的方法就是從底層開始自己定義squarer約束，把它作為primitive來寫，為了簡單起見，這裡規定a>=0
(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定義內部使用了很多中間變數，然後一句句寫了連接命令，略顯笨拙，我們可以用更簡潔的方式重新定義它
(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
至此，關於約束系統的講解已基本結束。雖然上面的工作看上去像是小孩子拿著玩具在過家家，但真實世界中的約束系統還是有不少實用之處的，如果對此感興趣可以嘗試著做一些擴展閱讀。
約束傳播的概念最早出現在Sutherland[3]在1963年的博士論文中，當然這篇論文網上也很難找了，但容易找到基於相同內容的技術報告材料，不過似乎constraint只是他用以輔助規範graphical language的小工具，並沒有非常側重的去討論。最早實現的一個優雅的基於 Smalltalk語言的約束傳播系統ThinkPad[4]用於模擬。還有一些早期應用於電路分析[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] 傳入這兩個消息直接調用error過程的寫法是SICP給出的，但在實際應用中，嘗試對常量進行修改操作一般並非出於用戶直接的不當操作，而是它參與的其他約束關係傳播過來的變值請求，忽略這些請求返回『ignored即可，沒有必要處理成error消息。
[2] 案例來源於習題3.34，schemewiki社區對此給出的解釋是這個設計的瑕疵在於b獲取值後無法傳播給a，但事實上如果沒有限定a的符號，已知b的值依然無法確定a的值。
[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] 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]: Sussman, Gerald Jay, and Guy Lewis Steele Jr. "CONSTRAINTS—A language for expressing almost-hierarchical descriptions." Artificial intelligence 14, no. 1 (1980): 1-39.
推薦閱讀：
