SICPゼミ第21回
練習問題3.31
実行環境 DrRacket
> (define input-1 (make-wire )) (define input-2 (make-wire )) (define sum (make-wire )) (define carry (make-wire )) > (probe 'sum sum) > (probe 'carry carry) > (half-adder input-1 input-2 sum carry) 'ok > (propagate) 'done > (set-signal! input-1 1) 'done > (propagate) 'done > (get-signal input-1) 1 > (get-signal sum) 0 > (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done > (get-signal sum) 0 > (get-signal input-1) 1
probeのときに出力が出ないのは、probeでadd-action!が呼ばれても実行はされないというだけなので、それはそう。
こちらの記事
では、アジェンダが空だといっているが、そんなことはない。なぜなら、 set-signal!を実行したときにcall-eachが呼ばれ、アジェンダに手続きが追加はされている。アジェンダの中身を見てみたのだろうか？
しかも、アジェンダの中身が空だとして、set-signal! input-2 1 を実行したときにcarryが更新されているのはなぜだろうか？
以上のことから、アジェンダが空であるという説明は間違っている。ではなぜ実行結果がこうなるのだろうか？
半加算器を設定したときに初期化がされていないので、教科書の図3.25の配線eが0のまま更新されない。そのためset-signal!してアジェンダに手続きが追加されてもワイヤーSの値への入力が間違ったままであるため、サムの値が0のまま更新されない。そのためaction-proceduresが呼ばれず、probe による値の表示も行われないというわけである。
2017/01/09 追記
上で言及したこちらの記事
に追記がなされていたが気づくのが非常に遅れてしまい申し訳ない限りである。
まず、こちらの記事にて言葉足らずであったところを補足させていただく。
大前提として、(propagate) は真っ先にthe-agendaが空であるかどうかの判定をしており、空であると何も実行せずに終わってしまう。つまりwireにセットされた信号が正しく計算されていくにはthe-agendaに各種手続き (outputのwireの値を更新しろ、とか、(probe)した wireの値が更新されたら表示しろ、とか) が追加されていなくてはならない。the-agendaを更新する手続きはafter-delayのみであるため、各種手続きをラムダ閉包として引数にとったafter-delayが実行されなくては(propagate)が正しく作動しない。
さて、
(half-adder input-1 input-2 sum carry)
を実行したとき、つまり半加算器を結線したときに、and-gateや or-gate, inverter の結線によって、各wireのもつaction-proceduresにafter-delayが追加されていく。
ここでaccept-action-procedureが本来の
(define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)) (proc))
であれば、各wireのもつaction-procedureにafter-delayが追加された後、(proc)という実行によってafter-delayが実行され、the-agendaが更新されてゆく。つまり、その後の(propagate)によって正しく計算が進んでゆく。
しかし、問題で述べられているような
(define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)))
であった場合にどうなるのか。after-delayは各wireのもつaction-procedureに追加されるのみで、実行されない。つまりthe-agendaは空のままである。このせいで(propagate)をしても何も起こらない、だからちゃんと(proc)を追加しなければならない、というのはもちろん正しい。
しかし、本記事で述べている例を見てみよう。
> (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done
set-signal!の後、(propagate)することによってちゃんとcarryの値が更新されているのである。
ではこれはなぜか？
実は、set-signal!手続きにカギがある。
下は set-signal!によって呼び出されるset-my-signal!である。
(define (set-my-signal! new-value) (if (not (= signal-value new-value )) (begin (set! signal-value new-value) (call-each action-procedures )) 'done ))
set-my-signal!の中で、「signal-valueとnew-valueが異なれば」call-eachによってaction-proceduresの中身が実行されるのである。つまり、各wireのもつaction-proceduresに追加されていただけのafter-delayたちが順に実行されていき、the-agendaが更新されているということである。
ただし、ここで重要なのはこのset-my-signalの初めに行われているif条件分岐、上で述べた「signal-valueとnew-valueが異なれば」というところである。
本来であれば一度どこかのwireのもつaction-proceduresにafter-delayが追加されれば、それが実行されthe-agendaが更新されるはずなのであるが、今回のように即時実行しないaccept-action-procedure!であると、set-signal!によって「値が変更されたwireのもつaction-proceduresに存在するafter-delayのみ」が実行されていき、これらのみについてthe-agendaが更新されていく、ということになる。
具体例を見ていこう。
上のような半加算器 (初期値は全て0) に対し、A(上の実行例ではinput-1) に値1をsetしたときに何がおこるだろうか。
> (set-signal! input-1 1) 'done > (propagate) 'done > (get-signal input-1) 1 > (get-signal sum) 0
Aに関連したD, C についてはand,orの演算が行われる。
Dはor-gateなので 1 に更新される。しかし C はand-gateなので0のまま更新されない。
本来1となるべき E の値をsetするinverter手続きは C のaction-proceduresに眠ったままでthe-agendaに追加されず、E の値は更新されないままである。
このせいでand-gateである S に対する入力は1,0となり、S は0となる。つまり S も C も更新されない。そのためprobe手続きも呼ばれない。結果返ってくるのは虚しい'doneの文字列だけである。
さて、次に B (上の実行例ではinput-2) に値1をsetするとどうなるか。
> (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done > (get-signal sum) 0 > (get-signal input-1) 1
B に関連した C, D について演算が行われる。
D は1のまま更新されない。C は1に更新される。C が更新されたためinverterによる値の更新が行われ、 E が 0 に更新される。S は0のまま更新されない。更新された C についてはprobeが呼ばれる。これで全てのつじつまが合う、ということになる。
さて、以上が本記事で述べていた内容であるが、この追記なしでは非常にわかりづらい文章となっていたことに対して深く申し訳ないと思う。
ここで、上で言及したこちらの記事
の説明について、本追記の上半分
after-delayは各wireのもつaction-procedureに追加されるのみで、実行されない。つまりthe-agendaは空のままである。このせいで(propagate)をしても何も起こらない、だからちゃんと(proc)を追加しなければならない
という部分の説明しかなされていないように思ったので指摘させていただいた。もし本追記で述べた内容を全て踏まえた上での説明であったのであれば謝罪させていただく。
