SICP 3.3.5 Propagation of Constraints - プログラミング再入門

論理回路モデルの応用で制約プログラミング的なモデルを作ります。

ノート

論理回路モデルの様にゲートとしての代わりに演算子と定数、入力・出力やゲート間を繋ぐワイヤを定義して計算回路を作る。回路の外に出ているワイヤはどれも入力としても出力としても機能する。

Using the constraint system

make-connectorは前節のmake-wire相当。
コネクタC、Fをワイヤの様に定義し、外部からCに値を設定したらシステムがFの値を設定する。外部からFに値を設定したらシステムがCの値を設定する。
celsius-fahrenheit-converterは二つのコネクタに回路を接続する。
multiplierは掛け算器を、adderは足し算器を３つのコネクタに接続する。
constantは一つのコネクタの値を定数に決める。
probeはコネクタに接続して、その値が変わった時に表示する。
set-value!には引数が一つ増えて、設定者を識別するシンボルを取る。
外部から設定された値はforget-value!で破棄しないと新たには設定出来ない。外部からはCを与えてFが決まったが、そこでFに値を設定しようとしてもCの値が残っている限り両立はしない。設定した値は設定者以外は破棄出来ない。

この様な１方向ではない計算のモデルがconstraint-based systemの特徴。

Implementing the constraint system

実装は電子回路モデルと似ているが、一つ一つの要素の実装は少し複雑になる。ただしagendaとかdelayとかは考慮しないのでその分は単純になる。
電子回路モデルのゲートに相当する部分を制約として定義する。
コネクタのインターフェースを決めて、制約adderとmultiplierを定義する。
メソッドはprocess-new-valueとprocess-forget-valueの二つのみ。
process-new-valueは二つのコネクタの値が決まっていたらもう一つのコネクタの値を決める。３つのケースが必要。この３つのケースを自動で作れない所が少し残念。
process-forget-valueは３つのコネクタの値を破棄する。

定数も制約として定義。リクエストは何も受付ず、コネクタに値を設定するだけ。
probeも何も制約しないけど制約として定義。コネクタの値が変わった時に呼ばれる。

Representing connectors

コネクタの実装。
コネクタもディスパッチャを持ったオブジェクト。メソッドは値が決まっているかを尋ねる'has-value?、値を尋ねる'value、値を設定する'set-value!、値を破棄させる'forget、ゲートを繋ぐ'connect。
インスタンス変数としては値を保持するvalue、設定者を保持するinformant、接続されている制約のリストconstraints。
informantがfalseの時は値を持っていない事を意味する。値が設定されると何らかのシンボルが設定される。
値を設定する時に既に値が設定されているかを確認した上で値を設定し、設定された値を接続された各制約に送る。ここで値の入力源以外の全ての制約を呼び出す為にfor-each-exceptを使う。制約を登録した時に既に値を持っていた場合は制約側に現在の値を伝える。

設定された値を破棄する仕組みが巧妙。まずコネクタに対して(forget-value! a 'user)の様に外部から設定された値が破棄されると、そのコネクタのforget-my-valueからにconstraintsに登録されている制約のうちforget-valu!と言った人（ここでは'user)以外に対してinform-about-no-valueを呼び出す。この手続きは制約に対してメッセージ'I-lost-my-valueを送る。'I-lost-my-valueを送られた制約は自分が設定したコネクタの値を破棄する。繋がっているコネクタ全てに自分（me）をretractorとしてforget-value!を呼び出せば、自分が設定した値は破棄され、自分以外が設定した値は保存される。
制約が自分のディスパッチャをmeと命名しているのは、informantやretractorとして自分を登録している事をコード上で示す為だと思われる。

これで全て揃ったので実行してみる。

> (define C (make-connector))
> (define F (make-connector))
> (celsius-fahrenheit-converter C F)
ok
> (probe "Celsius temp" C)
#<procedure:me>
> (probe "Fahrenheit temp" F)
#<procedure:me>
> (set-value! C 25 'user)

Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77done
> (set-value! F 212 'user)
. . Contradiction {77 212}
> (forget-value! C 'user)

Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?done
> (set-value! F 212 'user)

Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100done
>

やはりprobeの改行がおかしい。改行を最後にする。

(define (probe name connector)
  (define (print-probe value)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display value)
    (newline))
…

動作確認。

> (define C (make-connector))
> (define F (make-connector))
> (celsius-fahrenheit-converter C F)
ok
> (probe "Celsius temp" C)
#<procedure:me>
> (probe "Fahrenheit temp" F)
#<procedure:me>
> (set-value! C 25 'user)
Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77
done
> (set-value! F 212 'user)
. . Contradiction {77 212}
> (forget-value! C 'user)
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done
> (set-value! F 212 'user)
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done
>

Exercise 3.33

adderとmultiplierを使ってaveragerを実装。
$\frac{a+b}{2}=c$ の関係を $(a+b)\times 0.5=c$ の様にも実装出来るけど、 $a+b=c\times 2$ の実装の方が計算の流れが双方向的で面白い。

(define (averager a b c)
  (let ((x (make-connector))
        (y (make-connector)))
    (adder a b x)
    (multiplier c y x)
    (constant 2 y)
    'ok))

簡単に動作確認。

> (define a (make-connector))
> (probe "a" a)
#<procedure:me>
> (define b (make-connector))
> (probe "b" b)
#<procedure:me>
> (define c (make-connector))
> (probe "c" c)
#<procedure:me>
> (averager a b c)
ok
> (set-value! a 10 'user)
Probe: a = 10
done
> (set-value! b 20 'user)
Probe: c = 15
Probe: b = 20
done
> (forget-value! a 'user)
Probe: c = ?
Probe: a = ?
done
> (set-value! c 25 'user)
Probe: a = 30
Probe: c = 25
done
>

このadder、multiplierをプリミティブとしてaveragerやcelsius-fahrenheit-converterが制約プログラミングのプログラムと言う事になるのか。
それぞれのコネクタの値を誰が設定したのかをちゃんと管理する事がポイントの様に思える。

Exercise 3.34

a側の値を設定してbの値を求めさせる分には問題無し。
b側を設定してaの値を求めさせようとしても、二つのコネクタの値が決まるまでmultiplierは何もしないのでaの値は計算されない。

Exercise 3.35

process-new-valueでbに対してしかhas-value?のチェックをしない事になってしまうので、ifではなくcondに変更。

(define (squarer a b)
  (define (square x) (* x x))
  (define (process-new-value)
    (cond ((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)))
          ((has-value? a)
           (set-value! b (square (get-value a)) me))
          (else 'ignored)))
  (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)

動作確認

> (define a (make-connector))
> (probe "a" a)
#<procedure:me>
> (define b (make-connector))
> (probe "b" b)
#<procedure:me>
> (squarer a b)
#<procedure:me>
> (set-value! a 2 'user)
Probe: b = 4
Probe: a = 2
done
> (forget-value! a 'user)
Probe: b = ?
Probe: a = ?
done
> (set-value! b 9 'user)
Probe: a = 3
Probe: b = 9
done
>

Exercise 3.36

for-each-exceptが呼ばれた時の環境。

listすなわちconstraintsは空なのでこれ以上何も起きない。

Exercise 3.37

必要なコネクタや制約を作ってそれらを接続するプログラムよりは、演算子の様に見える制約を作って値同士の関係を演算式の様に記述した方が分かりやすい。
引数を取り結果を返す演算子の様に見える『制約構築子』を作る。引数は値ではなくコネクタ、関数値は演算結果そのものではなく引数のコネクタと演算によって関連付けられた値を持つコネクタ。

(define (c+ x y)
  (let ((z (make-connector)))
    (adder x y z)
    z))

(define (c- x y)
  (let ((z (make-connector)))
    (adder y z x)
    z))

(define (c* x y)
  (let ((z (make-connector)))
    (multiplier x y z)
    z))

(define (c/ x y)
  (let ((z (make-connector)))
    (multiplier y z x)
    z))

(define (cv v)
  (let ((z (make-connector)))
    (constant v z)
    z))

引き算、割り算のadder、multiplierに渡す引数の順番がポイント。
x-y=zとするとx=y+zの関係なので、adderをその様に接続するとx-yとしての値がzに設定される。割り算も同様。
動作確認

> (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))
> (probe "Celsius temp" C)
#<procedure:me>
> (probe "Fahrenheit temp" F)
#<procedure:me>
> (set-value! C 25 'user)
Probe: Celsius temp = 25
Probe: Fahrenheit temp = 77
done
> (forget-value! C 'user)
Probe: Celsius temp = ?
Probe: Fahrenheit temp = ?
done
> (set-value! F 212 'user)
Probe: Fahrenheit temp = 212
Probe: Celsius temp = 100
done
>

Farenheitは『Celsiusとしてのxに9/5を掛けて32を足す』と言う関係がストレートに表現されている。
これから読み取るのはちょっと辛い

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