SICP読書会(Exercise 3.31 – Exercise 3.32)

今回のあらすじ

SICPの3.3.4 A Simulator for Digital CircuitsのRepresenting wiresを読んでExercise 3.32まで演習問題を解きます。

Representing wires

前回は電子回路を構成する為のAPIがあると仮定して様々な電子回路をコード上で表現しました。
具体的には、

• 電子回路はwireとwireを様々な回路で結合することで構成され、
• wireに流れるsignalが変化すると流入先の回路によって演算された新しいsignalが別のwireに流れる

という形でした。

実際にシミュレーターを作るにあたってはこのwireもちゃんと実装する必要があります。
とはいえ、上記の2点、特に後者に留意すると

• 現在のsignalの値
• そのsignalが流入する先の回路……の中で行われるであろう処理

を状態として持つオブジェクトとして作ればいいだけの話です。
wireが実装できたら get-signal / set-signal / add-action! も簡単に実装できますね。

ただ、テキストに載ってるwireの実装だと add-action! に対応するwireの内部手続き名が accept-action-procedure! になっています。しかも追加された proc をすぐに呼んでいます。気にはなるのですがこの点についてはExercise 3.31を解く時に考えます。

The agenda

存在を仮定したAPIのうち未実装のものは after-delay なので、
それを実装するために必要なものを定義します。

各回路は入力信号が変わると一定時間の遅延を置いて出力信号が変わるので、
これを実現するには「いつ何をするか」という予定表を作っておく必要があります。
この予定表がagendaで、agendaがあると仮定すると、
テキストの通り after-delay は簡単に実装できますし、
シミュレーションを行う propagate も簡単に実装できます。

A sample simulation

これで電子回路シミュレーターはほぼ完成ですが、
肝心のシミュレーション結果を簡単に把握できるよう probe を用意しておきます。

テキストには half-adder シミュレーション例が載っていますが、
裏で何が起きているかトレースしておきましょう。

Exercise 3.31

The internal procedure accept-action-procedure! defined in make-wire
specifies that when a new action procedure is added to a wire, the procedure
is immediately run. Explain why this initialization is necessary. In
particular, trace through the half-adder example in the paragraphs above and
say how the system’s response would differ if we had defined
accept-action-procedure! as

(define (accept-action-procedure! proc)
  (set! action-procedures (cons proc action-procedures)))

先ずはシミュレーター全体の動きをScheme処理系の気持ちになってトレースしてみましょう。
「A sample simulation」に載っている例の場合、シミュレーター全体の状態は以下のように変動していきます:

accept-action-procedure! が proc を即座に呼ばないバージョンだとシミュレーター全体の状態は以下のように変動していきます:

wireのsignalの初期値は0ですが、 inverter に接続された場合は初期値が1だと考えるべきです。
accept-action-procedure! が proc を即座に呼ぶことで
inverter を含む回路でも正しい初期値が(そのうち)設定されるようになるのですが、
proc が呼ばれないとその設定が呼ばれない為、誤った初期値を元にしたシミュレート結果が出ることになります。
だから proc は即座に呼ぶ必要があります。

Implementing the agenda

最後にagendaの実装です。
まあこれはテキストの通りなので特に言う事は無いですね……

Exercise 3.32

The procedures to be run during each time segment of the agenda are kept in
a queue. Thus, the procedures for each segment are called in the order in
which they were added to the agenda (first in, first out). Explain why this
order must be used. In particular, trace the behavior of an and-gate whose
inputs change from 0,1 to 1,0 in the same segment and say how the behavior
would differ if we stored a segment’s procedures in an ordinary list, adding
and removing procedures only at the front (last in, first out).

以下の例について考えてみます:

(define a (make-wire))
(define b (make-wire))
(define o (make-wire))
(and-gate a b o)
(propagate)

(set-signal! a 0)
(set-signal! b 1)
(propagate)

(set-signal! a 1)
(set-signal! b 0)
(propagate)  ; (X)

(X)の評価直前の時点では

• aが0から1に変わったので、a and b = 1 and 1 = 1をoに設定
• bが1から0に変わったので、a and b = 1 and 0 = 0をoに設定

という予定がagendaに含まれます。
agendaの処理順がFIFOならaの変化を適用した後にbの変化を適用することになるのでo=0になりますが、
agendaの処理順がFILOだとbの変化を適用した後にaの変化を適用することになるのでo=1になってしまいます。

最終的なシミュレーション結果ではなくシミュレーション途中の結果が出力されることになってしまうので、
agendaを消化順序はsignalの変化した順と同じになるようFIFOにしなければなりません。

次回予告

3.3.5 Propagation of Constraintsをバリバリ読みます。