問題3.27-3.37

今回はデジタル回路のシミュレーションと、制約システムの作り方です。
制約システムは4章でやる論理プログラミングに関わるような印象を受けます(関係ないかもしれないですが)。

3.27

環境図は省略。
memo-fibがfibonacci数列の第n項をnステップで計算できるのは、その定義から、第n-1項,第n-2項の値を覚えているから。つまり、以前計算した値をtable上に保持しているので、同じ項を計算し直すという事態が避けられるため。再帰的プロセスの定義そのものは、同じ項を計算し直すという効率の悪い事態を引き起こしてしまう。
また、memo-fibを単に(memoize fib)と定義すると、結局全ての値をfibで計算することになるので、これも効率が悪い。

3.28

せっかくなのでlogical-and, logical-orも作ります。

(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)))))
  (and-action! a1 or-action-procedure)
  (and-action! a2 or-action-procedure)
  'ok)

(define (logical-and a1 a2)
  (cond ((and (= a1 1) (= a2 1))
         1)
        ((or (and (= a1 0) (= a2 1))
             (and (= a1 1) (= a2 0))
             (and (= a1 0) (= a2 0)))
         0)
        (else (error "Invalid signal" a1 a2))))
(define (logical-or a1 a2)
  (cond ((and (= a1 0) (= a2 0))
         0)
        ((or (and (= a1 0) (= a2 1))
             (and (= a1 1) (= a2 0))
             (and (= a1 1) (= a2 1)))
         1)
        (else (error "Invalid signal" a1 a2))))

3.29

ド・モルガン則を使い、andと等価な回路を構成すればよい。

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

遅延時間は回路図を作れば簡単に分かって、2 inverter-delay + and-gate-delayになる。はず。

3.30

(define (ripple-carry-adder a b s c)
  (define (iter a b s c-in c-out)
    (if (null? a)
        'ok
        (let ((output (make-wire)))
          (begin (full-adder (car a) (car b) (car s) c-in c-out)
                 (iter (cdr a) (cdr b) (cdr s) output)))))
  (let ((output (make-wire)))
    (iter a b s c-in output)))

たぶんこんな感じだと思う。まだ動かせないから分からない。
これがn bitの繰上り伝播加算器であるならば、and-gate-delay, or-gate-delay, inverter-delayを使って遅延時間を書くことができる。

full-adder-delay = 2 half-adder-delay + or-gate-delay
half-adder-delay = and-gate-delay + inverter-delay + and-gate-delay
                 = 2 and-gate-delay + inverter-delay

なので、
n bitの繰上り伝播加算器の遅延時間は

n * full-adder-delay = 2n half-adder-delay + n or-gate-delay
                     = n(4 and-gate-delay + 2 inverter-delay + or-gate-delay)

となる。たぶん。

3.31

よく分からなかったのでググりました。大体理解したのでまとめます。

accept-action-procedure!を機能的にみると、これは(wire 'add-action!)の時に呼び出されており、add-action!はwireと無引数手続きprocを引数としてとる。
add-action!の機能は、wireの信号が値を変えた時、指定した手続き(proc)が走ることを主張するというものになるが、and-gateやor-gateの定義を見れば分かるとおり、このprocの中でafter-delay手続きの呼び出しが書かれている。
なので、add-action!でprocが実行されなければafter-delayも実行されないことになる。
回路操作の手続き群の中で、次第書きとの橋渡しをするのはafter-delayだけなので、次第書きへのスケジュールの書き込みが為されない状態になり、結果シミュレーション上の時間の進み方がおかしくなる。
このため、procedureの呼び出しが一度必要になる。

ということみたいです。

3.32

and-gateの振る舞いを示す。

> (define a (make-wire))
> (define b (make-wire))
> (define c (make-wire))
> (probe 'c c)
c 0 New-value = 0
> (and-gate a b c)
ok
> (set-signal! b 1)
done
> (propagate)
done
> (set-signal! a 1)
done
> (set-signal! b 0)
done
> (propagate)
c 6 New-value = 1
c 6 New-value = 0
done

a, bの順にsignalを変更したので、同一時刻内でもそのように変化しなきゃいけないってことだろうか。
例えばこの例の場合、追加した順序ではなく、最後に追加された手続きから実行されていくという実装だと、(a,b)=(0,1)から(1,0)に変化する際、b=1 --> 0が先に実行されるからcは変化しない。
そうするとcが変化しないから値の変化が回路に伝播しないことになり、ユーザーのa->bの順に実行されるという直感に反するということかな。
同一時刻内でも、先に入力した方が先に回路にも反映されるという前提があるならたぶんこういうことのような気がします。でも実際の回路だと、ほとんど同時ってのは同時とみなしてもいいような気もするけどな。

3.33

ここから制約システム。

(define (averager a b c)
  (let ((d (make-connector)) (e (make-connector)))
    (adder a b d)
    (multiplier c e d)
    (constant 2 e)
    'ok))

3.34

(define (squarer a b)
  (multiplier a a b))

(define a (make-connector))
(define b (make-connector))
(squarer a b)
(probe 'a a)
(probe 'b b)

> (set-value! a 3 'user)
Probe: a = 3
Probe: b = 9
done
> (forget-value! b 'user)
ignored
> (forget-value! a 'user)
Probe: a = ?
Probe: b = ?
done
> (set-value! b 9 'user)
Probe: b = 9
done
> (set-value! a 4 'user)
Probe: a = 4
Contradiction (9 16)

挙動を確認すると、aに値を与えると上手くいくが、bに値を与えると上手く行かない。
これは、bに値を設定するとmultiplierの仮引数のproductにしか値が入らないため、condのどの条件式にも当てはまらないから。
multiplierは3つのコネクタによる制約システムだが、squarerは直感的に考えて2つのコネクタによる制約でかかれていてほしい。
ということで、次の問題でsquarerを基本制約として実装する。

3.35

(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0 -- SQUARE" (get-value b))
            (set-value! a (sqrt (get-value b)) me))
        (set-value! b (sqr (get-value a)) me)))
  (define (process-forget-value)
    (forget-value! a me)
    (forget-value! b me))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- SQUARER" request))))
  (connect a me)
  (connect b me)
  me)

(define a (make-connector))
(define b (make-connector))
(squarer a b)
(probe 'a a)
(probe 'b b)

> (set-value! a 10 'user)
Probe: a = 10
Probe: b = 100
done
> (forget-value! a 'user)
Probe: a = ?
Probe: b = ?
done
> (set-value! b 200 'user)
Probe: b = 200
Probe: a = 14.142135623730951
done
> (set-value! a 3 'user)
Contradiction (14.142135623730951 3)
> (forget-value! a 'user)
ignored
> (forget-value! b 'user)
Probe: b = ?
Probe: a = ?
done

adderやmultiplierではprocess-forget-valueで最後にprocess-new-valueを実行していたけれど、squarerは片方が値をなくしたらもう片方もなくすはずなので、今回はいらない。(いれるとbに値が残ってしまう)

3.36

省略

3.37

(define (c+ x y) (let ((z (make-connector))) (adder x y z) z))
(define (c- x y) (let ((z (make-connector))) (adder y z x) z))
(define (c* x y) (let ((z (make-connector))) (multiplier x y z) z))
(define (c/ x y) (let ((z (make-connector))) (multiplier y z x) z))
(define (cv x) (let ((z (make-connector))) (constant x z) z))
(define (celsius-fahrenheit-converter2 x)
  (c+ (c* (c/ (cv 9) (cv 5))
          x)
      (cv 32)))
(define C (make-connector))
(define F (celsius-fahrenheit-converter2 C))
(probe 'C C)
(probe 'F F)

> (set-value! C 255 'user)
Probe: C = 255
Probe: F = 491
done
> (forget-value! C 'user)
Probe: C = ?
Probe: F = ?
done
> (set-value! F 334 'user)
Probe: F = 334
Probe: C = 1510/9
done
> (forget-value! C 'user)
ignored
> (forget-value! F 'user)
Probe: F = ?
Probe: C = ?
done

命令形流儀の煩雑な制約言語を簡単に式主導の流儀に変換できる、ということみたいです。
確かに、こっちの方がわざわざ制約図を書かなくても簡単にかけて楽です。

今日はここまで。休みなのにあまりできなかった。
水曜から休みなのでそこで頑張って終わらせられるようにします。
とりあえず明日でストリームまでたどり着きたいです。