理系学生日記

おまえはいつまで学生気分なのか

問題3-31 (3.3.4 A Simulator for Digital Circuits)

関数 make-wire 中の関数 accept-action-procedure! では,関数のリスト action-procedures に引数で渡された関数 proc を追加する際に,なぜ proc を一度実行しているのかという問題.題材になった accept-action-procedure! の定義はこちら.最後の (proc) が関数呼び出しになってますね.

(define (make-wire)
  (let ((signal-value 0)
	(action-procedures '()))
    ; シグナルの値が変わっていれば,各 action procedure を実行する
    (define (set-my-signal! new-value)
      (if (not (= signal-value new-value))
	  (begin (set! signal-value new-value)
		 (call-each action-procedures))
	  'done))
    ; 実行される procedure に加える
    (define (accept-action-procedure! proc)
      (set! action-procedures (cons proc action-procedures))
      (proc))
    (define (dispatch m)
      (cond ((eq? m 'get-signal) signal-value)
	    ((eq? m 'set-signal!) set-my-signal!)
	    ((eq? m 'add-action!) accept-action-procedure!)
	    (else (error "Unknown operation -- WIRE" m))))
    dispatch))

In particular, trace through the half-adder example in the paragraphs above

ということですが全部トレースするのはメンドいな.とりあえず half-adder を見よう.関数 half-adder の定義はこれ.

(define (half-adder a b s c)
  (let ((d (make-wire)) (e (make-wire)))
    (or-gate a b d)
    (and-gate a b c)
    (inverter c e)
    (and-gate d e s)
    'ok))

単に配線してるだけですね.
では,この中の一要素,or-gate を見てみる.

(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)

じつは add-action! はヘルパ関数で,単にwire に対する 'add-action! メッセージの発行です.冒頭の make-wire 関数を見ると,結局 add-action! は accept-action-procedure! の呼び出しに置き換えられます.

(define (add-action! wire action-procedure)
  ((wire 'add-action!) action-procedure))

では本題で,なぜ accept-action-procedure! では proc の呼び出しが必要なのか.
実は各ゲート出力の変更は,accept-action-procedure! 中にある関数が行うことになっている.or-gate であれば,or-action-procedure が行っています.そして,それを行うタイミングは通常,ゲート入力が変更されたとき,もっと具体的に言うと,ゲート入力に接続された wire に対して set-signal! が呼び出されたときです.このあたりは,冒頭の関数のこの部分を見るとわかります.

    (define (set-my-signal! new-value)
      (if (not (= signal-value new-value))
	  (begin (set! signal-value new-value)
		 (call-each action-procedures))
	  'done))

call-each で action-procedures 中の全関数が呼ばれる仕様です.


ところが,これはあくまで入力が変更された際のフックなので,最初に接続された状態では呼び出されない.つまり初期状態においては,明示的に proc を呼び出しておかないと,ゲートには入力信号が入っているのに,ゲートの出力信号には反映されていないということになってしまうのです.たぶん.