SICP 3.3.4 A Simulator for Digital Circuits
漸く有名なデジタル回路シミュレーション
ノート
イベントドリブンなシミュレーションとの事。入力信号の変化に対して一定のディレイの後アウトプットが変化する。
wireを定義。gateの定義は接続されるwireを引数に取る。half-adder、full-adderを定義するには外部から入る、あるいは外部に出るwire以外に内部のgateの接続の為のwriteを定義して、必要なgateへの接続を定義する。
まだ必要なコードが揃っていないので実行は出来ない。
Primitive function boxes
get-signalはwireに掛かっている電圧、と言うかそれが意味する値を取り出す。
set-signal!はwireに値を設定する。
add-action!はwireの値が変わった時に呼び出す手続きを設定する。ここで呼ばれる手続きは引数を取らない。
inverterの定義。
- 二つのwire、inputとoutputを引数に取る。
- inputに対して、その値が変わった時に呼び出す手続き（invert-input）を設定する。
そのinvert-inputを内部手続きとして定義する。
- inputの信号を取り出して、logical-notに渡す。
- logical-notの返り値をnew-valueとする。
- 信号が変化する時間をシミュレートするafter-delayに、変化するまでの時間と時間が経過した時に呼び出される手続きを設定する。
- 時間が経過したらoutputにnew-valueを設定する。
logical-notは真偽値の否定。booleanの様な型が無いので0,1以外の値が入っていた場合のエラー処理がある。
and-gateも処理の構造は同じ。入力が二つあるのでそれぞれの入力に対してand-action-procedureを設定する。
ここでExercise 3.28が登場するが、まだコードが揃わず動作確認が出来ないので先に進む。
Representing wires
信号線の表現。
make-wireはdispatchを使ってget-signal、set-signal!、add-action!の三つのメソッドを実装するオブジェクトのコンストラクタとして働く。
- アトリビュートとして信号線の状態（signal-value、初期値は０）とactionのリスト（action-procedures）を持つ。
- メッセージget-signalに対してはsignal-valueを返す
- メッセージset-signal!に対応するset-my-signal!は設定される値が現在の値と異なるときのみ、保持している値を変更してactionを呼び出す。値が変化しない場合には何もしない（'doneを返すのみ）。
actionはリストになっているのでcall-eachを使って全てのactionを呼び出す。
- メッセージadd-actionに対応するaccept-action-procedure!はaction-proceduresに引数のactionを追加する。
設定されたアクションはリストになっているので呼び出すにも手続きが必要。手続きcall-eachは引数としてアクションのリストを取って、リストが空になるまで再帰しながらアクションを呼び出す。
ディスパッチャにメッセージを渡して返って来た手続きを呼び出す手続きget-signal、set-signal!、add-action!を定義。
The agenda
To do listの様な予定表をここではagendaと表現する。
グローバル環境にthe-agendaを定義し、after-delayはthe-agendaに新しい項目を追加する。
add-to-adgenda!はthe-agendaの現在の時刻からdelay後に、actionを設定する。
the-agendaを駆動するのは手続きpropagate。agendaに登録されている最初のアクションから順番に呼び出して行く。
A sample simulation
probeはwireの値が変わった時に、その様子をプリントするアクションをwireに設定する。
probeでアクションをすると、add-action!からmake-wire内のaccept-action-procedure!が呼ばれ、これは取り敢えず１回アクションを呼ぶので、その時の状態がプリントされる。
Implementing the agenda
time-segmentは先頭にプロシージャを実行するべき時刻、以降に実行するプロシージャのリストからなる。
agendaは先頭に現在の時刻、以降にtime-segmentの１次元テーブルを持つ。
なので、時間と読んでいるけど実際にはagenda上での実行のサイクルの事を指している。また、time-segmentに登録されているアクションは同時に進行する訳ではなく順番に実行されるので依存関係があるとややこしい事になる可能性がある。
agendaに新規のtime-segmentを追加するには、
- 所望の時刻のtime-segmentが既に存在すれば、そのsegmentにアクションを追加する。
- 所望の時刻のtime-segmentが以降のリストに存在しなければ、新しいtime-segmentを『挿入』する。
これらはadd-to-agenda!の内部関数のadd-to-segments!で実装されている。
time-segmentのリストは時刻順に並んでいる。
add-to-agenda!はtime-segmentを再帰しながら時刻の早い方から順に一つずつ辿り、
- 先頭のtime-segmentが所望の時刻であれば、そのsegmentにアクションを追加
- ２番目のtime-segmentの時刻が所望の時刻よりも後であれば新しいtime-segmentを作って、２番目以降のtime-segmentを後ろに連結して、新しいtime-segmentを先頭のtime-segmentの後ろに連結する。
- ２番目のtime-segmentの時刻が所望の時刻よりも前であれば、再帰する。
remove-first-agenda-item!。else部分が無いifが出て来たのは初めてか？
これで一通りの実装が揃ったので、最初から動作の確認をしながら進める。相変わらずset-cdr!等とerrorを使っているのでモードは
#lang scheme (require r5rs)
logical-andが定義されていないので
(define (logical-and a b) (cond ((and (= a 1) (= b 1)) 1) ((or (and (= a 1) (= b 0)) (and (= a 0) (= b 1)) (and (= a 0) (= b 0))) 0) (else (error "Invalid signal" a b))))
boolean型の様に定義されていないので、取り敢えず0、1以外の値が入って来たらエラーとする。
wireを定義して、and-gateとinverterを動かす。
> (define a (make-wire)) > (define b (make-wire)) > (define c (make-wire)) > (define e (make-wire)) > (and-gate a b c) ok > (inverter c e) ok > (set-signal! a 0) done > (set-signal! b 0) done > (propagate) done > (get-signal c) 0 > (set-signal! a 1) done > (propagate) done > (get-signal c) 0 > (set-signal! b 1) done > (propagate) done > (get-signal c) 1 > (get-signal e) 0 > (set-signal! a 0) done > (propagate) done > (get-signal e) 1 >
Exercise 3.28
or-gate、logocal-orともand-gate、logical-andとそっくりに作ると。
(define (or-gate a1 a2 output) (define (or-action-procedure) (let ((new-value (logical-or (get-signal a1) (get-signal a2)))) (after-delay or-gate-delay (lambda () (set-signal! output new-value))))) (add-action! a1 or-action-procedure) (add-action! a2 or-action-procedure) 'ok) (define (logical-or a b) (cond ((and (= a 0) (= b 0)) 0) ((or (and (= a 1) (= b 0)) (and (= a 0) (= b 1)) (and (= a 1) (= b 1))) 1) (else (error "Invalid signal" a b))))
中身がそっくりと言う事はもう１段抽象化した手続きを定義出来る筈。
動作確認。
> (define a (make-wire)) > (define b (make-wire)) > (define d (make-wire)) > (or-gate a b d) ok > (get-signal d) 0 > (set-signal! a 1) done > (propagate) done > (get-signal d) 1 > (set-signal! a 0) done > (set-signal! b 1) done > (propagate) done > (get-signal d) 1 > (set-signal! a 1) done > (propagate) done > (get-signal d) 1 >
Exercise 3.29
ORは入力のそれぞれを反転させてANDを取り、その結果をもう一度反転させると得られる。
| 入力１ | 入力２ | 反転入力１ | 反転入力２ | AND | 反転 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
half-adderを真似てor-gateを定義する。
(define (or-gate a1 a2 output) (let ((b (make-wire)) (c (make-wire)) (d (make-wire))) (inverter a1 b) (inverter a2 c) (and-gate b c d) (inverter d output) 'ok))
動作確認。
> (define a (make-wire)) > (define b (make-wire)) > (define d (make-wire)) > (or-gate a b d) ok > (get-signal d) 0 > (set-signal! a 1) done > (propagate) done > (get-signal d) 1 > (set-signal! a 0) done > (set-signal! b 1) done > (propagate) done > (get-signal d) 1 > (set-signal! a 1) done > (propagate) done > (get-signal d) 1 >
全体のディレイは、二つの入力の反転は平行して出来るものと仮定して、反転の時間が最初と最後に２回分、ANDの時間が１回分。
Exercise 3.30
まずhalf-adderの動作を確認。
| a | b | s | c |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
> (define a (make-wire)) > (define b (make-wire)) > (define s (make-wire)) > (define c (make-wire)) > (half-adder a b s c) ok > (set-signal! a 0) done > (set-signal! b 0) done > (propagate) done > (get-signal s) 0 > (get-signal c) 0 > (set-signal! b 1) done > (propagate) done > (get-signal s) 1 > (get-signal c) 0 > (set-signal! a 1) done > (set-signal! b 0) done > (propagate) done > (get-signal s) 1 > (get-signal c) 0 > (set-signal! b 1) done > (propagate) done > (get-signal s) 0 > (get-signal c) 1 >
次にfull-adderの動作を確認。
| A | B | Cin | SUM | Cout |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
設定が面倒なので全ての入力をいっぺんに設定するset-signals!と結果を表示するresultを定義して実行する。
> (define a (make-wire)) > (define b (make-wire)) > (define c-in (make-wire)) > (define sum (make-wire)) > (define c-out (make-wire)) > (full-adder a b c-in sum c-out) ok > (define (set-signals! x y z) (set-signal! a x) (set-signal! b y) (set-signal! c-in z)) > (define (result) (display "sum:")(display (get-signal sum))(display " c-out")(display (get-signal c-out))(newline)) > (result) sum:0 c-out0 > (set-signals! 0 0 1) done > (propagate) done > (result) sum:1 c-out0 > (set-signals! 0 0 0) done > (propagate) done > (result) sum:0 c-out0 > (set-signals! 0 1 0) done > (propagate) done > (result) sum:1 c-out0 > (set-signals! 1 0 0) done > (propagate) done > (result) sum:1 c-out0 > (set-signals! 1 1 0) done > (propagate) done > (result) sum:0 c-out1 > (set-signals! 0 0 1) done > (propagate) done > (result) sum:1 c-out0 > (set-signals! 0 1 1) done > (propagate) done > (result) sum:0 c-out1 > (set-signals! 1 0 1) done > (propagate) done > (result) sum:0 c-out1 > (set-signals! 1 1 1) done > (propagate) done > (result) sum:1 c-out1 >
図から引数のリストは最上位ビットから並んでいるものと仮定する。また、図に従いhalf-adderは作らず、最後にダミーのワイヤc0を作る。
引数のcは上位の段への繰り上がりなので、上位の段からadderを作って行くには
- 下段からの繰り上がり用のワイヤを作る
- 引数のaの最初のワイヤ、引数のbの最初のワイヤ、下段からの繰り上がりワイヤ、答えのワイヤ、上段への繰り上がりワイヤでfull-adderを作る
- aの残りのワイヤ、bの残りのワイヤ、答えの残りのワイヤ、下段からの繰り上がりワイヤにripple-carry-adderを再帰適用する。
- ワイヤのリストが空になったら'okを返す。
(define (ripple-carry-adder as bs ss c-out) (if (null? (cdr as)) (half-adder (car as) (car bs) (car ss) c-out) (let ((c-in (make-wire))) (full-adder (car as) (car bs) c-in (car ss) c-out) (ripple-carry-adder (cdr as) (cdr bs) (cdr ss) c-in))))
実行するに当たってwireのリストを作るmake-wires、全てのワイヤに値を設定するset-signals!、全てのワイヤの値をリストにするget-signalsを定義
(define (make-wires n) (if (= n 0) null (cons (make-wire) (make-wires (- n 1))))) (define (set-signals! wires signals) (if (or (null? wires) (null? signals)) 'ok (begin (set-signal! (car wires) (car signals)) (set-signals! (cdr wires) (cdr signals))))) (define (get-signals wires) (if (null? wires) null (cons (get-signal (car wires)) (get-signals (cdr wires)))))
実行してみる。
> (define a (make-wires 8)) > (get-signals a) {0 0 0 0 0 0 0 0} > (set-signals! a '(1 0 1 0 1 0 1 0)) ok > (get-signals a) {1 0 1 0 1 0 1 0} > (set-signals! a '(1 1 1 1 1 1 1 1)) ok > (define b (make-wires 8)) > (set-signals! b '(0 0 0 0 0 0 0 1)) ok > (define sum (make-wires 8)) > (define c (make-wire)) > (ripple-carry-adder a b sum c) ok > (get-signals sum) {0 0 0 0 0 0 0 0} > (get-signal c) 0 > (propagate) done > (get-signals sum) {0 0 0 0 0 0 0 0} > (get-signal c) 1 > (set-signals! a '(0 0 0 1 0 1 0 1)) ok > (set-signals! b '(0 0 0 0 1 0 1 1)) ok > (propagate) done > (get-signals sum) {0 0 1 0 0 0 0 0} > (get-signal c) 0 >
half-adderのディレイはor-gate１回分かand-gate１回とinverter１回の和の長い方にand-gate１回分を加えた長さ。
full-adderのディレイはhalf-adder２回とor-gate１回分の長さ。
全体ではfull-adderがn個分のディレイが必要。
この後で出て来る様にand-gate+inverterのディレイとor-gateのディレイが等しい場合を考えると、
half-adder = 2 and + 1 inverter
full-adder = 2 half-adder + or = 4 and + 2 inverter + or
n-bits ripple carry adder = n full-adder = 4n and + 2n inverter + n or
のディレイとなる。
A sample simulation（再び）
probeを動かしていなかったので、動かしてみる。
> (define input-1 (make-wire)) > (define input-2 (make-wire)) > (define sum (make-wire)) > (define carry (make-wire)) > (probe 'sum sum) sum 0 New-value = 0 > (probe 'carry carry) carry 0 New-value = 0 > (half-adder input-1 input-2 sum carry) ok > (set-signal! input-1 1) done > (propagate) sum 8 New-value = 1done >
どうもnewlineの位置がおかしい。以前はテキストの様に動いていたのかも知れないが。probeを少し変える。
(define (probe name wire) (add-action! wire (lambda () (display name) (display " ") (display (current-time the-agenda)) (display " New-value = ") (display (get-signal wire)) (newline))))
もう一度動かす。
> (define input-1 (make-wire)) > (define input-2 (make-wire)) > (define sum (make-wire)) > (define carry (make-wire)) > (probe 'sum sum) sum 0 New-value = 0 > (probe 'carry carry) carry 0 New-value = 0 > (half-adder input-1 input-2 sum carry) ok > (set-signal! input-1 1) done > (propagate) sum 8 New-value = 1 done > (set-signal! input-2 1) done > (propagate) carry 11 New-value = 1 sum 16 New-value = 0 done >
いい感じに動いた。
Exercise 3.31
各素子が入力のワイヤの信号が変わった時のアクションは２段階になっていて、新しい出力の値を計算してアジェンダに手続きを登録する部分と、アジェンダに登録された手続きが出力に値を反映させる部分からなる。
基本的にはワイヤの値が変わった時にしかアジェンダにアクションを登録される事になる。なのでアクションを設定した段階で一度アクションの前段階を呼んでアジェンダに手続きを登録しておかないと、(propagate)してもワイヤの初期値は何にも反映されない。
inverterでinputのワイヤに対してアクションを登録するが、その時にprocを呼ばないと、そのままpropagateしても値は反映されない。
> (define a (make-wire)) > (define b (make-wire)) > (set-signal! a 0) done > (inverter a b) ok > (propagate) done > (get-signal b) 0 >
hals-adderの例：
> (define a (make-wire)) > (set-signal! a 1) done > (define b (make-wire)) > (set-signal! b 1) done > (define s (make-wire)) > (define c (make-wire)) > (half-adder a b s c) ok > (propagate) done > (get-signal s) 0 > (get-signal c) 0 >
最初にprocを呼べば
> (define a (make-wire)) > (set-signal! a 1) done > (define b (make-wire)) > (set-signal! b 1) done > (define s (make-wire)) > (define c (make-wire)) > (half-adder a b s c) ok > (propagate) done > (get-signal s) 0 > (get-signal c) 1 >
ちゃんと初期値が出力に反映される。
Exercise 3.32
and-gateに入る信号が(0, 1)だった所を(1, 0)に変わる時、プログラム上はその二つの入力の変化は同時には起こらず順番に起きる。例えば入力は(0, 1)から一旦(1, 1)に変わってから(1, 0)に変わるとする。どちらの変化も本来同時に起きる事を想定しているので、アジェンダのアクションは同じ時刻の所に登録される。入力が(1, 1)になった時のアクションは出力を１に設定する。入力が(1, 0)になった時のアクションは出力を０に設定する。入力の最終形は(1, 0)なので(1, 0)になった時のアクションが最後に行われるべきだが、この順番が入れ替わって(1, 1)になった時のアクションが最後に実行されると、入力の最終形と出力の最終形が一致しなくなってしまう。つまり入力側に起きた変化と同じ順番に出力側の変化が起きなければならないので、入力の変化の際に登録されるアクションは登録された順番に実行される必要がある。
*1:Half-adderを使う場合にはワイヤのリストの最後だった場合に、half-adderを作れば良い。
