SICP問題3.32
次第書きの各時間区分内で走るべき手続きがキューになっている理由を述べよ。
同じ区分の中で入力が0,1から1,0に変わったアンドゲートの振る舞いをトレースし、区分内の手続きを先頭で挿入,削除する(最後に入ったものが最初に出る)通常のリストに格納した時との振る舞いの違いを述べよ。
とのことですが、正直、問題の意味がさっぱり分からないので色々ググってみました。が、結局良く分からないままです。
そもそも「同じ区分の中で入力が0,1から1,0に変わったアンドゲートの振る舞い」という意味が良く分からないので、お手上げ。
ということでトレースだけでも…。
まずはFIFOのqueue でのアンドゲートの振る舞い
(define a (make-wire)) ; a (define b (make-wire)) ; b (define c (make-wire)) ; c ; -- probe (probe 'c c) ; c 0 New-value = 0#<undef> ; -- and-gate (and-gate a b c) ; ok ; -- (0, 1) (set-signal! a 0) ; done (set-signal! b 1) ; done ; -- (1, 0) the-agenda ; (0 (3 (#<closure (and-gate and-action-procedure #f)> #<closure (and-gate and-action-procedure #f)> . #0=(#<closure (and-gate and-action-procedure #f)>)) . #0#)) (propagate) ; done (set-signal! a 1) ; done (set-signal! b 0) ; done the-agenda ; (3 (6 (#<closure (and-gate and-action-procedure #f)> . #0=(#<closure (and-gate and-action-procedure #f)>)) . #0#)) (propagate) ; c 6 New-value = 1 ; c 6 New-value = 0done
次に queue を LILO に変更した場合のアンドゲートの振る舞い
LILOにするためにいい加減に直したqueueの定義
(define (front-ptr queue) queue) (define (empty-queue? queue) (null? (car queue))) (define (make-queue) '(())) (define (front-queue queue) (if (empty-queue? queue) (error "FRONT called with an empty queue" queue) (car (car queue)))) (define (insert-queue! queue item) (let ((new-pair (cons item (car queue)))) (set-car! queue new-pair))) (define (delete-queue! queue) (cond ((empty-queue? queue) (error "DELETE! called with an empty queue" queue)) (else (set-car! queue (cdr (car queue))) queue))) (define (print-queue queue) (car queue))
で、実行
(define a (make-wire)) ; a (define b (make-wire)) ; b (define c (make-wire)) ; c ; -- probe (probe 'c c) ; c 0 New-value = 0#<undef> ; -- and-gate (and-gate a b c) ; ok ; -- (0, 1) (set-signal! a 0) ; done (set-signal! b 1) ; done ; -- (1, 0) the-agenda ; (0 (3 (#<closure (and-gate and-action-procedure #f)> #<closure (and-gate and-action-procedure #f)> #<closure (and-gate and-action-procedure #f)>))) (propagate) ; done (set-signal! a 1) ; done (set-signal! b 0) ; done the-agenda ; (3 (6 (#<closure (and-gate and-action-procedure #f)> #<closure (and-gate and-action-procedure #f)>))) (propagate) ; c 6 New-value = 1done
ということで、確かに動きが違う。
動きが違う理由はそれぞれの回線状態の変化であり、それぞれ以下のようになる。
FIFOの場合は(0, 1) => (1, 0)の際のa,bの回線状態は
[a(0), b(0)] => b(1), a(1), b(0) の順番で変化し、この時のcの回線状態は以下のように変化する。
a(0), b(1), c(0)
a(1), b(1), c(0) => c(1)
a(1), b(0), c(1) => c(0)
LILOの場合は(0, 1) => (1, 0)の際のa,bの回線状態は
[a(0), b(0)] => b(0), a(1), b(1)の順番で変化し、この時のcの回線状態は以下のように変化する。
a(0), b(0), c(0)
a(1), b(0), c(0)
a(1), b(1), c(0) => c(1)
このためLILOの場合は正しくシミュレートされない。
という答えで良いのかなぁ?