TIM Labs

SICP読書会(Exercise 3.31 - Exercise 3.32)

| コメント(0) | トラックバック(0)

今回のあらすじ

SICP3.3.4 A Simulator for Digital CircuitsRepresenting 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」に載っている例の場合、シミュレーター全体の状態は以下のように変動していきます:

時刻input-1 (a)input-2 (b)desum (s)carry (c)agenda補足
000--00入出力用wireを作成した直後
0000-00half-adder: dをmake-wire
0000000half-adder: eをmake-wire
00000005: d=0half-adder: (or-gate a b d)でaにadd-action!
00000005: d=0, d=0half-adder: (or-gate a b d)でbにadd-action!
00000003: c=0; 5: d=0, d=0half-adder: (and-gate a b c)でaにadd-action!
00000003: c=0, c=0; 5: d=0, d=0half-adder: (and-gate a b c)でbにadd-action!
00000002: e=1; 3: c=0, c=0; 5: d=0, d=0half-adder: (inverter c e)でcにadd-action!
00000002: e=1; 3: c=0, c=0, s=0; 5: d=0, d=0half-adder: (and-gate d e s)でdにadd-action!
00000002: e=1; 3: c=0, c=0, s=0, s=0; 5: d=0, d=0half-adder: (and-gate d e s)でeにadd-action!
01000002: e=1; 3: c=0, c=0, s=0, s=0, c=0 ; 5: d=0, d=0, d=1(set-signal! input-1 1)
21001003: c=0, c=0, s=0, s=0, c=0; 5: d=0, d=0, d=1, s=0propagate: 時刻2のagendaを消化
31001005: d=0, d=0, d=1, s=0propagate: 時刻3のagendaを消化(全てsignalの変化無し)
51001005: d=1, s=0propagate: 時刻5のagendaを消化(d=0を2回; 変化無し)
51011005: d=1, s=0; 8: s=1propagate: 時刻5のagendaを消化(d=1)
51011008: s=1propagate: 時刻5のagendaを消化(s=0; 変化なし)
8101110propagate: 時刻8のagendaを消化(s=1)
811111011: c=1; 13: d=1(set-signal! input-2 1)
1111111113: d=1, e=0propagate: 時刻11のagendaを消化(c=1)
1311111113: e=0propagate: 時刻13のagendaを消化(d=1; 変化なし)
1311101116: s=0propagate: 時刻13のagendaを消化(e=0)
16111001propagate: 時刻16のagendaを消化(s=0)

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

時刻input-1 (a)input-2 (b)desum (s)carry (c)agenda補足
000--00入出力用wireを作成した直後
0000-00half-adder: dをmake-wire
0000000half-adder: eをmake-wire
0000000half-adder: (or-gate a b d)でaにadd-action!
0000000half-adder: (or-gate a b d)でbにadd-action!
0000000half-adder: (and-gate a b c)でaにadd-action!
0000000half-adder: (and-gate a b c)でbにadd-action!
0000000half-adder: (inverter c e)でcにadd-action!
0000000half-adder: (and-gate d e s)でdにadd-action!
0000000half-adder: (and-gate d e s)でeにadd-action!
01000003: c=0; 5: d=1(set-signal! input-1 1)
31000005: d=1propagate: 時刻3のagendaを消化(c=0; 変化なし)
51010008: s=0propagate: 時刻5のagendaを消化(d=1)
8101000propagate: 時刻8のagendaを消化(s=0; 変化なし)
811100011: c=1; 13: d=1(set-signal! input-2 2)
1111100113: d=1, e=0propagate: 時刻11のagendaを消化(c=1)
1311100113: e=0propagate: 時刻13のagendaを消化(d=1; 変化無し)
13111001propagate: 時刻13のagendaを消化(e=0; 変化無し)

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 をバリバリ読みます。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/449

コメントする

このブログ記事について

このページは、kanaが2014年12月17日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「テストコードは、どの程度かけば良いものなの?」です。

次のブログ記事は「SICP読書会(Section 3.3.5 - Exercise 3.33)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。