オンラインSICP読書女子会 #50 (3.3.4)

オンラインSICP読書女子会 #50 (3.3.4)

練習問題 3.28 - 3.30.

今回利用しているファイル.
分解したのでこまごまいっぱい＞ｘ＜；

circuit-base.scm
circuit-inverter.scm
circuit-and.scm
circuit-or.scm
circuit-or-2.scm
circuit-full-adder.scm
circuit-half-adder.scm
test-inverter.scm
test-and.scm
test-or.scm
test-or-2.scm
test-full-adder.scm
test-half-adder.scm
ex-3.30.scm

3.3.4. デジタル回路シミュレータ

Wire, function box, Inverter, And gate, Or gate.
Half adder.
Full adder.

基本関数箱

Primitive function boxes.

(get-signal wire), (set-signal! wire new-value), (add-action! wire procedure)
(after-delay delay procedure)

机上でやってもよくわからないので組んでみた. 疲れた…！＞＜

1. circuit-half-adder.scm
2. circuit-full-adder.scm
3. circuit-inverter.scm
4. circuit-and.scm
5. circuit-or.scm
6. circuit-base.scm
7. test-inverter.scm
8. test-and.scm
9. test-or.scm
10. test-half-adder.scm
11. test-full-adder.scm

1. 半加算器 (circuit-half-adder.scm)

p.298 にあるそのまま.

; [circuit-half-adder.scm]
;
(define (half-adder a b sum carry)
	(let ((d (make-wire)) (e (make-wire)))
		; (print "XXX: d="d" e="e)
		(or-gate a b d)
		(and-gate a b carry)
		(inverter carry e)
		(and-gate d e sum)
		'ok))

2. 全加算器 (circuit-full-adder.scm)

p.298 にあるそのまま.

; [circuit-full-adder.scm]
;
(define (full-adder a b c so co)
	(let ((s1 (make-wire)) (c1 (make-wire)) (c2 (make-wire)))
		; (print "XXX: s="s" c1="c1" c2="c2)
		(half-adder b c s1 c1)
		(half-adder a s1 so c2)
		(or-gate c1 c2 co)
		'ok))

3. NOT 素子 (circuit-inverter.scm)

p.300 にあるそのまま.

; [circuit-inverter.scm]
;

(define inverter-delay 1)


(define (inverter input output)
	(define (invert-input)
		(let ((new-value (logical-not (get-signal input))))
			(after-delay
				inverter-delay
				(lambda ()
					(and debug (print "INVERTER: " input " >> " output " = " new-value))
					(set-signal! output new-value)))))
	(add-action! input invert-input)
	'ok)


(define (logical-not s)
	(cond
		((= s 0) 1)
		((= s 1) 0)
		(else (error "Invalid signal" s))))

4. AND 素子 (circuit-and.scm)

p.300 にあるそのまま.

; [circuit-and.scm]
;

(define and-gate-delay 1)


(define (and-gate a1 a2 output)
	(define (and-action-procedure)
		(define v1 (get-signal a1))
		(define v2 (get-signal a2))
		(let ((new-value (logical-and (get-signal a1) (get-signal a2))))
			(after-delay
				and-gate-delay
				(lambda ()
					(and debug (print "AND " a1":"v1 "/" a2":"v2 " >> " output " = " new-value))
					(set-signal! output new-value)))))
	(add-action! a1 and-action-procedure)
	(add-action! a2 and-action-procedure)
	'ok)


(define (logical-and s1 s2)
	(cond
		((and (= s1 0) (= s2 0)) 0)
		((and (= s1 0) (= s2 1)) 0)
		((and (= s1 1) (= s2 0)) 0)
		((and (= s1 1) (= s2 1)) 1)
		(else (error "Invalid signal" s1 s2))))

5. OR 素子 (circuit-or.scm)

練習問題 3.28 になる部分.
全/半加算器で使ってるので先に実装.

; [circuit-or.scm]
;

(define or-gate-delay 1)


(define (or-gate a b output)
	(define (or-action-procedure)
		(define av (get-signal a))
		(define bv (get-signal b))
		(let ((new-value (logical-or (get-signal a) (get-signal b))))
			(after-delay
				or-gate-delay
				(lambda ()
					(and debug (print "OR " a":"av "/" b":"bv " >> " output " = " new-value))
					(set-signal! output new-value)))))
	(add-action! a or-action-procedure)
	(add-action! b or-action-procedure)
	'ok)


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

6. ベース部分 (circuit-base.scm)

勝手に作成. ベース部分ではあるけれど, でっかいし気力が持ってかれるしなので読み飛ばし推奨.

; [circuit-base.scm]
;

(define debug #f)
(define tick 0)
(define wires '())
(define delays '())


(define (show)
	(print "[show]")
	(show-internal))


(define (show-internal)
	(print ". tick = " tick)
	(print ". wires:")
	(for-each (lambda (wire-data) (print "> " wire-data)) (reverse wires))
	(print ". delays:")
	(for-each (lambda (delay-data) (print "> " delay-data)) delays)
	'ok)


(define (run-actions)
	; result: any action happened
	(fold-left
		(lambda (acc wire-data)
			(if (list-ref wire-data 3)
				(begin
					(list-set! wire-data 3 #f)
					(for-each (lambda(x) (x)) (list-ref wire-data 2))
					#t)
				acc))
		#f
		wires))


(define (step)
	(define (step-iter)
		(cond
			((null? delays) 'ok)
			((<= (list-ref (car delays) 0) tick)
				(let ((head (car delays)))
					(set! delays (cdr delays))
					((list-ref head 1))
					(step-iter)))
			(else 'ok)))

	(set! tick (+ tick 1))
	(and debug (print "[step] tick = " tick))
	(run-actions)
	(step-iter))


(define (run-debug)
	(run-step show-internal))


(define (run)
	(run-step (lambda () 'ok)))


(define (run-step f)
	(and debug (print "BEFORE-STEP"))
	(f)
	(and debug (print "ACTIONS"))
	(and (run-actions) (f))
	(cond
		((null? delays) 'ok)
		(else
			(and debug (print "STEP"))
			(step)
			(run-step f))))


; wire-data:
(define W_NAME    0)
(define W_SIGVAL  1)
(define W_ACTIONS 2)
(define W_CHANGED 3)

(define (make-wire)
	(define name (string->symbol (string-append "w" (number->string (length wires)))))
	(define wire-data (list name 0 '() #f))
	(set! wires (cons wire-data wires))
	name)


(define (get-signal wire)
	(let ((wire-data (assoc wire wires)))
		(and
			wire-data
			(list-ref wire-data 1))))


(define (set-signal! wire sig)
	(let ((wire-data (assoc wire wires)))
		(and
			wire-data
			(begin
				(list-set! wire-data 1 sig)
				(list-set! wire-data 3 #t)
				'ok))))


(define (after-delay delay action)
	(define awake-at (+ tick delay))
	(define delay-data (list awake-at action))
	(set!
		delays
		(sort
			(cons delay-data delays)
			(lambda (a b) (< (list-ref a 0) (list-ref b 0)))))
	'ok)


(define (add-action! wire action)
	(let ((wire-data (assoc wire wires)))
		(and
			wire-data
			(begin
				(list-set! wire-data 2 (cons action (list-ref wire-data 2)))
				'ok))))

7. NOT 素子のテスト (test-inverter.scm)

; [test-inverter.scm]
;
(define (test-inverter)
	(define i (make-wire))
	(define o (make-wire))

	(define (stat-inverter)
		(print "> [stat:inverter]")
		(print "> i = " i ": " (get-signal i))
		(print "> o = " o ": " (get-signal o))
		'ok)

	(inverter i o)

	(newline)
	(print "* (i) = (0)")
	(set-signal! i 0)
	(run)
	(stat-inverter)

	(newline)
	(print "* (i) = (1)")
	(set-signal! i 1)
	(run)
	(stat-inverter)

	'done)


(load "circuit-base")
(load "circuit-inverter")

gosh> (test-inverter)

* (i) = (0)
> [stat:inverter]
> i = w0: 0
> o = w1: 1

* (i) = (1)
> [stat:inverter]
> i = w0: 1
> o = w1: 0
done

8. AND 素子のテスト (test-and.scm)

; [test-and.scm]
;
(define (test-and)
	(define a1 (make-wire))
	(define a2 (make-wire))
	(define o  (make-wire))

	(define (stat-and)
		(print "> [stat:and]")
		(print "> a1 = " a1 ": " (get-signal a1))
		(print "> a2 = " a2 ": " (get-signal a2))
		(print "> o  = " o  ": " (get-signal o ))
		'ok)

	(and-gate a1 a2 o)

	(newline)
	(print "* (a1) = (0)")
	(print "* (a2) = (0)")
	(set-signal! a1 0)
	(set-signal! a2 0)
	(run)
	(stat-and)

	(newline)
	(print "* (a1) = (1)")
	(print "* (a2) = (0)")
	(set-signal! a1 1)
	(set-signal! a2 0)
	(run)
	(stat-and)

	(newline)
	(print "* (a1) = (0)")
	(print "* (a2) = (1)")
	(set-signal! a1 0)
	(set-signal! a2 1)
	(run)
	(stat-and)

	(newline)
	(print "* (a1) = (1)")
	(print "* (a2) = (1)")
	(set-signal! a1 1)
	(set-signal! a2 1)
	(run)
	(stat-and)

	'done)


(load "circuit-base")
(load "circuit-and")

gosh> (test-and)

* (a1) = (0)
* (a2) = (0)
> [stat:and]
> a1 = w0: 0
> a2 = w1: 0
> o  = w2: 0

* (a1) = (1)
* (a2) = (0)
> [stat:and]
> a1 = w0: 1
> a2 = w1: 0
> o  = w2: 0

* (a1) = (0)
* (a2) = (1)
> [stat:and]
> a1 = w0: 0
> a2 = w1: 1
> o  = w2: 0

* (a1) = (1)
* (a2) = (1)
> [stat:and]
> a1 = w0: 1
> a2 = w1: 1
> o  = w2: 1
done

9. OR 素子のテスト (test-or.scm)

; [test-or]
;
(define (test-or)
	(define a (make-wire))
	(define b (make-wire))
	(define o (make-wire))

	(define (stat-or)
		(print "> [stat:or]")
		(print "> a = " a ": " (get-signal a))
		(print "> b = " b ": " (get-signal b))
		(print "> o = " o ": " (get-signal o))
		'ok)

	(or-gate a b o)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(set-signal! a 0)
	(set-signal! b 0)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(set-signal! a 1)
	(set-signal! b 0)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(set-signal! a 0)
	(set-signal! b 1)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(set-signal! a 1)
	(set-signal! b 1)
	(run)
	(stat-or)

	'done)


(load "circuit-base")
(load "circuit-or")

gosh> (test-or)

* (a) = (0)
* (b) = (0)
> [stat:or]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

10. 半加算器のテスト (test-half-adder.scm)

; [test-half-adder.scm]
;
(define (test-half-adder)
	(define a (make-wire))
	(define b (make-wire))
	(define so (make-wire)) ; sum/out.
	(define co (make-wire)) ; carry/out.

	(define (stat-half-adder)
		(print "> [stat:half-adder]")
		(print "> a  = " a  ": " (get-signal a))
		(print "> b  = " b  ": " (get-signal b))
		(print "> so = " so ": " (get-signal so))
		(print "> co = " co ": " (get-signal co))
		'ok)

	(half-adder a b so co)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(set-signal! a 0)
	(set-signal! b 0)
	(run)
	(stat-half-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(set-signal! a 1)
	(set-signal! b 0)
	(run)
	(stat-half-adder)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(set-signal! a 0)
	(set-signal! b 1)
	(run)
	(stat-half-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(set-signal! a 1)
	(set-signal! b 1)
	(run)
	(stat-half-adder)

	'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")

gosh> (test-half-adder)

* (a) = (0)
* (b) = (0)
> [stat:half-adder]
> a  = w0: 0
> b  = w1: 0
> so = w2: 0
> co = w3: 0

* (a) = (1)
* (b) = (0)
> [stat:half-adder]
> a  = w0: 1
> b  = w1: 0
> so = w2: 1
> co = w3: 0

* (a) = (0)
* (b) = (1)
> [stat:half-adder]
> a  = w0: 0
> b  = w1: 1
> so = w2: 1
> co = w3: 0

* (a) = (1)
* (b) = (1)
> [stat:half-adder]
> a  = w0: 1
> b  = w1: 1
> so = w2: 0
> co = w3: 1
done

11. 全加算器のテスト (test-full-adder.scm)

; [test-full-adder.scm]
;
(define (test-full-adder)
	(define a (make-wire))
	(define b (make-wire))
	(define c (make-wire))
	(define so (make-wire)) ; sum/out.
	(define co (make-wire)) ; carry/out.

	(define (stat-full-adder)
		(print "> [stat:full-adder]")
		(print "> a  = " a  ": " (get-signal a))
		(print "> b  = " b  ": " (get-signal b))
		(print "> c  = " c  ": " (get-signal c))
		(print "> so = " so ": " (get-signal so))
		(print "> co = " co ": " (get-signal co))
		'ok)

	(full-adder a b c so co)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(print "* (c) = (0)")
	(set-signal! a 0)
	(set-signal! b 0)
	(set-signal! c 0)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(print "* (c) = (0)")
	(set-signal! a 1)
	(set-signal! b 0)
	(set-signal! c 0)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(print "* (c) = (0)")
	(set-signal! a 0)
	(set-signal! b 1)
	(set-signal! c 0)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(print "* (c) = (0)")
	(set-signal! a 1)
	(set-signal! b 1)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(print "* (c) = (1)")
	(set-signal! a 0)
	(set-signal! b 0)
	(set-signal! c 1)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(print "* (c) = (1)")
	(set-signal! a 1)
	(set-signal! b 0)
	(set-signal! c 1)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(print "* (c) = (1)")
	(set-signal! a 0)
	(set-signal! b 1)
	(set-signal! c 1)
	(run)
	(stat-full-adder)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(print "* (c) = (1)")
	(set-signal! a 1)
	(set-signal! b 1)
	(set-signal! c 1)
	(run)
	(stat-full-adder)

	'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")
(load "circuit-full-adder")

gosh> (test-full-adder)

* (a) = (0)
* (b) = (0)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 0
> c  = w2: 0
> so = w3: 0
> co = w4: 0

* (a) = (1)
* (b) = (0)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 0
> c  = w2: 0
> so = w3: 1
> co = w4: 0

* (a) = (0)
* (b) = (1)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 1
> c  = w2: 0
> so = w3: 1
> co = w4: 0

* (a) = (1)
* (b) = (1)
* (c) = (0)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 1
> c  = w2: 0
> so = w3: 0
> co = w4: 1

* (a) = (0)
* (b) = (0)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 0
> c  = w2: 1
> so = w3: 1
> co = w4: 0

* (a) = (1)
* (b) = (0)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 0
> c  = w2: 1
> so = w3: 0
> co = w4: 1

* (a) = (0)
* (b) = (1)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 0
> b  = w1: 1
> c  = w2: 1
> so = w3: 0
> co = w4: 1

* (a) = (1)
* (b) = (1)
* (c) = (1)
> [stat:full-adder]
> a  = w0: 1
> b  = w1: 1
> c  = w2: 1
> so = w3: 1
> co = w4: 1
done

ex-3.28. OR gate の実装.

ex-3.28. 実装.

上記, (5) OR 素子と (9) OR 素子のテストの部分で実装済み.
以下再掲.

(再掲) 5. OR 素子 (circuit-or.scm)

; [circuit-or.scm]
;

(define or-gate-delay 1)


(define (or-gate a b output)
	(define (or-action-procedure)
		(define av (get-signal a))
		(define bv (get-signal b))
		(let ((new-value (logical-or (get-signal a) (get-signal b))))
			(after-delay
				or-gate-delay
				(lambda ()
					(and debug (print "OR " a":"av "/" b":"bv " >> " output " = " new-value))
					(set-signal! output new-value)))))
	(add-action! a or-action-procedure)
	(add-action! b or-action-procedure)
	'ok)


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

(再掲) 9. OR 素子のテスト (test-or.scm)

; [test-or]
;
(define (test-or)
	(define a (make-wire))
	(define b (make-wire))
	(define o (make-wire))

	(define (stat-or)
		(print "> [stat:or]")
		(print "> a = " a ": " (get-signal a))
		(print "> b = " b ": " (get-signal b))
		(print "> o = " o ": " (get-signal o))
		'ok)

	(or-gate a b o)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(set-signal! a 0)
	(set-signal! b 0)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(set-signal! a 1)
	(set-signal! b 0)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(set-signal! a 0)
	(set-signal! b 1)
	(run)
	(stat-or)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(set-signal! a 1)
	(set-signal! b 1)
	(run)
	(stat-or)

	'done)


(load "circuit-base")
(load "circuit-or")

ex-3.28. 実行結果.

gosh> (test-or)

* (a) = (0)
* (b) = (0)
> [stat:or]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

ex-3.29. AND/NOT 素子を用いた OR gate の実装.

ex-3.29. 実装.

; [circuit-or-2.scm]
;

(define (or-gate-2 a b output)
	; Lisp で書くと,
	;   (lambda (a b)
	;     (not
	;       (and
	;         (not a)
	;         (not b))))
	; といったかんじ.
	(let ((ax (make-wire)) (bx (make-wire)) (cx (make-wire)))
		(inverter a ax)
		(inverter b bx)
		(and-gate ax bx cx)
		(inverter cx output)
		'ok))

; [test-or-2]
;
(define (test-or-2)
	(define a (make-wire))
	(define b (make-wire))
	(define o (make-wire))

	(define (stat-or-2)
		(print "> [stat:or-2]")
		(print "> a = " a ": " (get-signal a))
		(print "> b = " b ": " (get-signal b))
		(print "> o = " o ": " (get-signal o))
		'ok)

	(or-gate-2 a b o)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (0)")
	(set-signal! a 0)
	(set-signal! b 0)
	(run)
	(stat-or-2)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (0)")
	(set-signal! a 1)
	(set-signal! b 0)
	(run)
	(stat-or-2)

	(newline)
	(print "* (a) = (0)")
	(print "* (b) = (1)")
	(set-signal! a 0)
	(set-signal! b 1)
	(run)
	(stat-or-2)

	(newline)
	(print "* (a) = (1)")
	(print "* (b) = (1)")
	(set-signal! a 1)
	(set-signal! b 1)
	(run)
	(stat-or-2)

	'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or-2")

ex-3.29. 実行結果

gosh> (test-or-2)

* (a) = (0)
* (b) = (0)
> [stat:or-2]
> a = w0: 0
> b = w1: 0
> o = w2: 0

* (a) = (1)
* (b) = (0)
> [stat:or-2]
> a = w0: 1
> b = w1: 0
> o = w2: 1

* (a) = (0)
* (b) = (1)
> [stat:or-2]
> a = w0: 0
> b = w1: 1
> o = w2: 1

* (a) = (1)
* (b) = (1)
> [stat:or-2]
> a = w0: 1
> b = w1: 1
> o = w2: 1
done

ex-3.30. 繰り上がり伝播加算器

ripple-carry adder.

ripple はさざなみっていう意味らしい. なんだかおしゃん・ω・*

ex-3.30. 遅延時間:

ここでは素子を抜ける際の遅延時間を |x| として表現する.

• n=1 の場合 |and|
A1-C と B1-C で時間は同じ.

• n=2 の場合 max(|or|, |and| + |inv|) + 2 * |and| + |or|
  full adder の中を通る経路で使われている素子によって, 変化する.

• n>=3 の場合 max(|or|, |and| + |inv|) + 1 * |and| + (n - 1) * (|and| + |or|)
  これ以降は, |and| + |or| 分だけ増加してゆく.

まとまってないけど以下その計算.

half-adder:

|ha:x-s| = max(|or|, |and| + |inv|) + |and|
|ha:x-c| = |and|

full-adder:

|fa:a-s| = |ha:a-s|
         = max(|or|, |and| + |inv|) + |and|
|fa:a-c| = |ha:a-c| + |or|
         = |and| + |or|

|fa:b-s| = |ha:a-s| + |ha:b-s|
         = 2 * max(|or|, |and| + |inv|) + 2 * |and|
|fa:b-c| = |ha:a-s| + |ha:b-c| + |or|
         = (max(|or|, |and| + |inv|) + |and|) + |and| + |or|
         = max(|or|, |and| + |inv|) + 2 * |and| + |or|

|fa:c-s| = |ha:b-s| + |ha:b-s|
         = 2 * max(|or|, |and| + |inv|) + 2 * |and|
|fa:c-c| = |ha:b-c| + |or|
         = |and| + |or|

|fa:a-c| = |fa:c-c| = |and| + |or|
|fa:b-c| = |fa:a-c| + max(|or|, |and| + |inv|) + |and|


ripple-carry-adder:

|ra(1):x{1}-c| = |ha:x-c|
               = |and|

|ra(n):x{n}-c| = max(|ra(n):a{n}-c|, |ra(n):b{n}-c|, |ra(n-1):x{n-1}-c| + |ra(n):c{n}-c|)

|ra(n):a{n}-c| = |fa:a-c| = |and| + |or|
|ra(n):b{n}-c| = |fa:b-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
|ra(n):c{n}-c| = |fa:c-c| = |and| + |or|

n=2:
|ra(2):c1-c| = |ra(1):c1-c| + |ra(2):c2-c|
             = (|and|) + (|and| + |or|)
             = 2 * |and| + |or|
|ra(2):b2-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
             = max(|or|, |and| + |inv|) + |ra(2):c1-c|
             > |ra(2):c1-c|

n=3:
|ra(3):x1-c| = |ra(2):x1-c| + |ra(3):c3-c|
             = (max(|or|, |and| + |inv|) + 2 * |and| + |or|) + (|and| + |or|)
|ra(3):b3-c| = max(|or|, |and| + |inv|) + 2 * |and| + |or|
             < |ra(3):x1-c|

ex-3.30. 実装.

; [ex-3.30.scm]
;
(define (ex-3.30)
	(define a1 (make-wire))
	(define a2 (make-wire))
	(define a3 (make-wire))
	(define b1 (make-wire))
	(define b2 (make-wire))
	(define b3 (make-wire))
	(define s1 (make-wire))
	(define s2 (make-wire))
	(define s3 (make-wire))
	(define c  (make-wire))

	(define as (list a1 a2 a3))
	(define bs (list b1 b2 b3))
	(define ss (list s1 s2 s3))

	(define (my-stat)
		(print "> [stat:ripple-carry-adder:3]")
		(print "> a1 = " a1 ": " (get-signal a1))
		(print "> a2 = " a2 ": " (get-signal a2))
		(print "> a3 = " a3 ": " (get-signal a3))
		(print "> b1 = " b1 ": " (get-signal b1))
		(print "> b2 = " b2 ": " (get-signal b2))
		(print "> b3 = " b3 ": " (get-signal b3))
		(print "> c  = " c  ": " (get-signal c))
		(print "> s1 = " s1 ": " (get-signal s1))
		(print "> s2 = " s2 ": " (get-signal s2))
		(print "> s3 = " s3 ": " (get-signal s3))
		'ok)

	(ripple-carry-adder as bs ss c)

	(newline)
	(print "* (as) = (1,0,1)")
	(print "* (bs) = (1,1,0)")
	(set-signal! a1 1)
	(set-signal! a2 0)
	(set-signal! a3 1)
	(set-signal! b1 1)
	(set-signal! b2 1)
	(set-signal! b3 0)
	(run)
	(my-stat)

	'done)


(load "circuit-base")
(load "circuit-inverter")
(load "circuit-and")
(load "circuit-or")
(load "circuit-half-adder")
(load "circuit-full-adder")


(define (ripple-carry-adder as bs ss c)
	(if
		(eq? (cdr as) '())
		; then
		(half-adder (car as) (car bs) (car ss) c)
		; else
		(let ((d (make-wire)))
			(ripple-carry-adder (cdr as) (cdr bs) (cdr ss) d)
			(full-adder (car as) (car bs) d (car ss) c)
			'done)))

ex-3.30. 実行結果

gosh> (ex-3.30)
* (as) = (1,0,1)
* (bs) = (1,1,0)
> [stat:ripple-carry-adder:3]
> a1 = w0: 1
> a2 = w1: 0
> a3 = w2: 1
> b1 = w3: 1
> b2 = w4: 1
> b3 = w5: 0
> c  = w9: 1
> s1 = w6: 0
> s2 = w7: 1
> s3 = w8: 1
done