SICP読書会(Section 3.3.5 – Exercise 3.33)

今回のあらすじ

SICPの3.3.5 Propagation of Constraintsをバリバリ読んでExercise 3.33まで演習問題を解きます。

3.3.5 Propagation of Constraints

華氏と摂氏の関係式

• 9C = 5(F – 32)

のような方程式から、
各項に関する制約の集まりとして表現して、

• Cの値が決まれば自動的にFの値が求まる
• 逆に、Fの値が決まれば自動的にCの値が求まる

ということができる制約システムを作りましょうという話です。

Using the constraint system

制約システムを作るためのAPI

• make-connector
• adder
• multiplier
• constant
• probe
• set-value!
• forget-value!

があるとして、華氏-摂氏の関係式を制約システムの形で表現して、
それを使って温度の変換をする話ですね。

要領としては 3.3.4 A Simulator for Digital Circuits と同じですね。
ただ、値を変更する際に「誰が値を変更したのか」を明示しているところが独特です。
何故これが必要かは後で出てくるでしょう。

Implementing the constraint system

存在を仮定したAPIのうち adder multiplier constant probe を作ろうという話です。
3.3.4 で実装された and-gate や or-gate に似ているようで微妙に違いますね。

電子回路の場合はwireにactionを登録していました。
ところが制約システムの場合はconnectorに制約そのものを登録しています。
電子回路でのactionの呼び出し条件は「signalが変化したら」でしたが、
制約システムの場合は「値が確定した」「値が未確定になった」でやるべきことが異なります。
言わばactionが2種類ある訳です。

種類別にactionをconnectorに登録するのは管理が煩雑なので、
制約自身をconnectorに登録して、値がどうなったかの通知はメッセージパッシングで行おうということですね。

Representing connectors

主に make-connector を実装する話です。
やはり 3.3.4 の make-wire と似ていますが、
「値が確定した」時と「値が未確定になった」時が分かれている点が異なりますね。

「誰が値を変更したか」という情報は set-my-value と forget-my-value で活用されていますね。
例えば以下の制約システムがあるとしましょう:

(define a1 (make-connector))
(define a2 (make-connector))
(define sum (make-connector))
(adder a1 a2 sum)

a1 と a2 の値を set-value! で確定させると、
adder の process-new-value で sum に合計値が設定されます。
sum の値が確定したので、今度は sum に関する制約に「 sum の値が確定した」ことを伝える必要があります。
この例の場合は sum に紐付く制約は adder のみです。

set-my-value が informant を持っていないとすると、
sum に紐付く全ての制約に通知を送ることになります
でも今 sum に値を設定した adder に対して「 sum の値が確定した」と通知する必要はありませんね。
仮に通知されたとすると、 adder の process-new-value が呼ばれることになり、
その中の cond の最初の節で「 a1 と a2 の値が確定しているから sum に値を設定する」ことになります。

既に `sum` に値は設定されているのに再度 `sum` に値が設定されますが、値は同じなので矛盾は生じていません。 ただ、この `sum` の再設定がさらに `sum` の再設定を引き起こすので、無限ループになってしまいますね。 とはいえ二重に通知が来て処理する羽目になるので無駄が多くなります。 より複雑な制約システムを構築した場合はこの無駄がもっとひどいことになるかも知れません。 という訳で `informant` が必須という訳です。

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.

ほうほう。電子回路の時の half-adder のような要領で averager を実装するということですね。
まずは a b c の関係式を書いてみましょう:

• (a + b)/2 = c

割り算が混ざっているとややこしいので割り算を使わない式に変形しましょう:

• a + b = 2c

これならFigure 3.28のような制約ネットワークの図が簡単に書けますね:

     ---------     ---------
a ---|a1     |  e  |     m1|--- c
     |   +  s|-----|p  *   |
b ---|a2     |     |     m2|---.
     ---------     ---------   | d
                             -----
                             | 2 |
                             -----

後はこれをScheme語に翻訳するだけです:

(define (averager a b c)
  (let ([d (make-connector)]
        [e (make-connector)])
    (adder a b e)
    (multiplier c d e)
    (constant 2 d)
    'ok))

次回予告

3.3.5 Propagation of ConstraintsのExercise 3.34からExercise 3.37までサクサク解いていきます。