読者です 読者をやめる 読者になる 読者になる

SICP 3.3.4

3.28

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

3.29

OR を and-gate と inverter で実現すると f:id:linus404:20170212110016p:plain

aをa1, bをb1, fをoutputと見なせば

(define (or-gate a1 b1 output)
  (let ((c make-wire)
        (d make-wire)
        (e make-wire))
    (inverter a1 c)
    (inverter b1 d)
    (and-gate c d e)
    (inverter e output)
    'ok))

遅延時間は inverter-dalay2 + and-delay1

3.30

full-adderの定義

(define (full-adder a b c-in sum c-out)
  (let ((s (make-wire))
        (c1 (make-wire))
        (c2 (make-wire)))
    (half-adder b c-in s c1)
    (half-adder a s sum c2)
    (or-gate c1 c2 c-out)
    'ok))

これを使って

; aとbは同じ桁と仮定
; aとbは(a1,a2,...,an) のような順序で格納されたリスト
(define (ripple-carry-adder a b s c)
  (let ((c-tmp make-wire))
    (if (null? (cdr a))
        (set-signal! c-tmp 0) ;最下位桁のcarry
        (ripple-carry-adder (cdr a) (cdr b) (cdr s) c-tmp))
    (full-adder (car a) (car b) c-tmp (car s) c)))

全体の遅延は full-adder-delay * n

全加算器1段の遅延は half-adder-delay * 2 + or-delay

半加算器の遅延は and-gate-delay * 2 + or-gate-delay * 1 + inverter-daly

よって、

and-gate-dlay * 4n + or-gate-delay * 3n + inverter-dlay * 2n

3.31

本文の実装

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

問題の実装

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

(proc)の実行有無で何が変わるか。

半加算器の例

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

全部追う時間が無いのでカンニング http://labs.timedia.co.jp/2014/12/sicp-ex-3.31-ex-3.32.html

ポイントは、 set時に初期値を正しく評価できるか。 単にsetした値をそのまま使うのであれば、procなしでも問題ない。 しかし、invertを含む場合、初期値を反転して評価する必要がある。 そのため、procを走らせる必要がある。

3.32

キューイングされた処理をFIFOで行わなければならない理由。 先に入ったイベントに後の処理が依存していれば、当然先のイベントを評価した後で無いと、 依存する後発処理は正しく評価できない。という話かと。。。

問題文

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

and-gateのinputが 0,1 -> 1,0 と変わった場合 FIFO:

初期時点 (a=0, b=1) -> 0 and 1 -> 0
a変更   (a=1, b=1) -> 1 and 1 -> 1
b変更  (a=1, b=0) -> 1 and 0 -> 0

LIFO:

初期時点 (a=0, b=1) -> 0 and 1 -> 0
b変更  (a=0, b=0) -> 0 and 0 -> 0
a変更   (a=1, b=0) -> 1 and 0 -> 0

適用中の値の変化が変わる。 が、、、FIFOが正しい、という確信が得られず。。。