[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[jfriends:00442] 「計算機プログラムの構造と解釈第二版」を読む会 第14回議事録
こんにちは
鈴木＠二村研究室です．
まず第1点．
10月の読書会予定開催日は27日でよろしいでしょうか？
最後に書いていただいたものをメモするのを忘れてしまいました．
すいません．
次に2点目．
午前中悩んでいた
p171,172
adder, multiplier 中の process-forget-value で
なぜ一番最後に process-newvalue を呼び出しているのか？
解説を読んでもいまいちわからない．
ことに関してですが，
process-newvalue があるのとないのとでは違いが
出てきそうなものを見つけました．
(define (show-info)
(for-each
(lambda (x)
(let ((name (car x))
(connector (cdr x)))
(newline)(display "name = ")(display name)
(display ", value = ")(display (connector 'value))
(display ", informant = ")(display (connector 'informant-name))))
(list (cons 'a a) (cons 'b b) (cons 'avg avg))))
(define a (make-connector))
(define b (make-connector))
(define avg (make-connector))
(probe 'a a)
(probe 'b b)
(probe 'avg avg)
(set-value! a 100 'user)
(set-value! b 200 'user)
(set-value! avg 300 'user)
(averager a b avg)
(forget-value! a 'user)
(show-info)
1. process-new-value を最後に記述した場合
表示している informant-name は informantの設定元を表したものです．
==> (forget-value! a 'user)
Probe: sum = ?, informant-name = #f
Probe: sum = 300, informant-name = multiplier
Probe: a = 100, informant-name = adder
Probe: a = ?, informant-name = #f
Probe: a = 100, informant-name = adder
Probe: a = ?, informant-name = adder
done
==> (show-info)
name = a, value = 100, informant = adder
name = b, value = 200, informant = user
name = avg, value = 150, informant = user
#<unspecified>
a に対して新たにに加算器から値が設定される．
2. process-new-value を最後に記述しない場合
==> (forget-value! a 'user)
Probe: sum = ?, informant-name = #f
Probe: a = ?, informant-name = #f
done
==> (show-info)
name = a, value = 100, informant = #f
name = b, value = 200, informant = user
name = avg, value = 150, informant = user
#<unspecified>
a の値はないことになっている．
(has-value? a) = false
これをちゃんとトレースするのはさすがに
大変そうなのであきらめました．
そして議事録です．
;;2001/09/29
横山さん 山下さん
遠 --------------------
藤 | |
さ | |
ん --------------------
和田先生 鈴木
;;sicp 読書会議事録
;;[誤植一覧]
p168
(方程式の下)
の関係があるとう → の関係があるという
p169
（制約システムの使い方の上）
それば F を 77 に設定する → それは F を 77 に設定する
p179
(並列性の制御機構の下)
順序の3つの事象を持つの2つの → 順序の3つの事象を持つ2つの
p183
（問題3．43の最後）
こうの条件さえも → この条件さえも
;;[問題一覧]
問題3．33
___________ __________
a - |a1 | d | m1 |-- C
| + sum |------|p * |
b - |a2 | | m2 |-- 2
|__________| |_________|
(define (averager a b c)
(let ((sum (make-connector))
(m (make-connector)))
(adder a b sum)
(constant 2 m)
(multiplier m c sum)
'ok))
(define a (make-connector))
(define b (make-connector))
(define c (make-connector))
(probe 'a a)
(probe 'b b)
(probe 'c c)
(averager a b c)
問題3．34
(define (squarer a b)
(multiplier a a b))
(define hoge (make-connector))
(define funi (make-connector))
(squarer hoge funi)
(probe 'hoge hoge)
(probe 'funi funi)
==> (set-value! a 100 'user)
Probe: b = 10000
Probe: a = 100
done
==> (forget-value! a 'user)
Probe: b = ?
Probe: a = ?
done
==> (set-value! b 100 'user)
Probe: b = 100
done
==> (has-value? a)
#f
問題3．35
(define (squarer a b)
(define (process-new-value)
(if (has-value? b)
(if (< (get-value b) 0)
(error "square less than 0 -- SQUARER" (get-value b))
(set-value! a (sqrt (get-value b)) me))
(if (has-value? a)
(set-value! b (expt (get-value a) 2) me))))
(define (process-forget-value)
(forget-value! a me)
(forget-value! b me)
(process-new-value))
(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 -- MULTIPLIER" 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 900 'user)
Probe: b = 900
Probe: a = 30.0
done
==> (forget-value! b 'user)
Probe: b = ?
Probe: a = ?
done
問題3．36
本文中に b に対して評価を行なう所がなかったので
(squarer a b) を行なうとして考えてみた．
(define a (make-connector))
(define b (make-connector))
(squarer a b)
(set-value! a 10 'user)
よくわかんないアスキーアート
----------------------------------------------------------
a:-|
b:-|----------------------------|
(squarer a b) |
---|----------------------------|-------------------------
| ___________________ | ______________________
| | |set,forget,con | | | |set,forget,con |
| | |val=0,info=nil | | | |val=0,info=nil |
[*][*] |constraints=nil| [*][*] |constraints=nil |
| |_______________| | |__________________|
|___________|___|____________| | |
| | | | e5---------------
| | | | |value = 100 |
__|_______ | e1------------------------------- | -----------------
| make | | |constraints = squarer.request| |
|-connector| | ------------------------------ |
|__________| | e2-------------------------------
| |constraints = squarer.request|
__________ | -------------------------------
|squarer | e3--------------------
|a b | | value = 10 |
|__________| ---------------------
|
|
|
e4-------------------------
| request = I have a value|
---------------------------
問題3．37
(define (c+ x y)
(let ((z (make-connector)))
(adder x y z)
z))
(define (c* x y)
(let ((z (make-connector)))
(multiplier x y z)
z))
(define (c- x y)
(let ((z (make-connector)))
(adder x z y)
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-converter x)
(c+ (c* (c/ (cv 9) (cv 5))
x)
(cv 32)))
(define C (make-connector))
(define F (celsius-fahrenheit-converter C))
(probe 'C C)
(probe 'F F)
;;実行結果
==> (set-value! C 25 'user)
Probe: c = 25
Probe: f = 77.0
done
==> (forget-value! C 'user)
Probe: c = ?
Probe: f = ?
done
==> (set-value! F 212 'user)
Probe: f = 212
Probe: c = 100.0
done
==> (forget-value! F 'user)
Probe: f = ?
Probe: c = ?
done
問題3．38
(a)
1.Peter -> Paul -> Mary
(100 + 10 - 20) / 2 = 45
2.Peter -> Mary -> Paul
(100 + 10 / 2) - 20 = 35
3.Paul -> Mary -> Peter
(100 - 20) / 2 + 10 = 50
4.Paul -> Peter -> Mary
(100 - 20 + 10) / 2 = 45
5.Mary -> Peter -> Paul
100 / 2 - 20 + 10 = 40
6.Mary -> Paul -> Peter
100 / 2 + 10 - 20 = 40
この6通り．
(b)
(define (concat lls)
(fold-right append '() lls))
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
(define (fold-right op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op (car rest) result)
(cdr rest))))
(iter initial (reverse sequence)))
(define (manhattan av st)
(cond ((null? av) (list st)) ;もう通るべきavenueのblockはない
((null? st) (list av)) ;もう通るべきstreetのbloakはない
(else (append
(map (lambda (x) (cons (car av) x)) ;最初に東へ向かう
(manhattan (cdr av) st))
(map (lambda (x) (cons (car st) x)) ;最初に北へ向かう
(manhattan av (cdr st)))))))
(define (hyper-manhattan streets)
(fold-left (lambda (xs y) (concat (map (lambda (x) (manhattan x y)) xs)))
(list '())
streets))
(define (for-each proc list)
(cond ((null? list) 'the-value-returned-by-the-call-to-for-each)
(else (proc (car list)) (for-each proc (cdr list)))))
(map
(lambda (x)
(let ((balance 100) (peter 0) (paul 0) (mary 0))
(for-each
(lambda (y)
(cond ((eq? y 'a) (set! peter balance))
((eq? y 'b) (set! balance (+ peter 10)))
((eq? y 'c) (set! paul balance))
((eq? y 'd) (set! balance (- paul 20)))
((eq? y 'e) (set! mary balance))
((eq? y 'f) (set! balance (/ mary 2))))) x)
(list x balance)))
(hyper-manhattan '((a b) (c d) (e f))))
;;実行結果
(((a b c d e f) 45) ((a b c e d f) 55) ((a b c e f d) 90) ((a b e c d f) 55)
((a b e c f d) 90) ((a b e f c d) 35) ((a e b c d f) 50) ((a e b c f d) 90)
((a e b f c d) 30) ((a e f b c d) 90) ((e a b c d f) 50) ((e a b c f d) 90)
((e a b f c d) 30) ((e a f b c d) 90) ((e f a b c d) 40) ((a c b d e f) 40)
((a c b e d f) 55) ((a c b e f d) 80) ((a c e b d f) 50) ((a c e b f d) 80)
((a c e f b d) 80) ((a e c b d f) 50) ((a e c b f d) 80) ((a e c f b d) 80)
((a e f c b d) 30) ((e a c b d f) 50) ((e a c b f d) 80) ((e a c f b d) 80)
((e a f c b d) 30) ((e f a c b d) 30) ((a c d b e f) 55) ((a c d e b f) 40)
((a c d e f b) 110) ((a c e d b f) 50) ((a c e d f b) 110) ((a c e f d b) 110)
((a e c d b f) 50) ((a e c d f b) 110) ((a e c f d b) 110) ((a e f c d b) 110)
((e a c d b f) 50) ((e a c d f b) 110) ((e a c f d b) 110) ((e a f c d b) 110)
((e f a c d b) 60) ((c a b d e f) 40) ((c a b e d f) 55) ((c a b e f d) 80)
((c a e b d f) 50) ((c a e b f d) 80) ((c a e f b d) 80) ((c e a b d f) 50)
((c e a b f d) 80) ((c e a f b d) 80) ((c e f a b d) 80) ((e c a b d f) 50)
((e c a b f d) 80) ((e c a f b d) 80) ((e c f a b d) 80) ((e f c a b d) 30)
((c a d b e f) 55) ((c a d e b f) 40) ((c a d e f b) 110) ((c a e d b f) 50)
((c a e d f b) 110) ((c a e f d b) 110) ((c e a d b f) 50) ((c e a d f b) 110)
((c e a f d b) 110) ((c e f a d b) 60) ((e c a d b f) 50) ((e c a d f b) 110)
((e c a f d b) 110) ((e c f a d b) 60) ((e f c a d b) 60) ((c d a b e f) 45)
((c d a e b f) 40) ((c d a e f b) 90) ((c d e a b f) 40) ((c d e a f b) 90)
((c d e f a b) 50) ((c e d a b f) 50) ((c e d a f b) 90) ((c e d f a b) 60)
((c e f d a b) 90) ((e c d a b f) 50) ((e c d a f b) 90) ((e c d f a b) 60)
((e c f d a b) 90) ((e f c d a b) 40))
よって生じる値は
(60 110 80 40 30 50 35 90 55 45)
問題3．39
1． 101
2． 121
3． 100
問題3．40
P1: (set! x (* x x)) x1,x2
P2: (set! x (* x x x)) x3,x4,x5
値が揃った時にすぐ代入する場合の
値のパターン．
1.
x1 x2 x3 x4 x5
2 3
1000000
2.
x1 x3 x4 x5 x2
3 2
10 * 1000 = 10000
3.
x1 x3 x2 x4 x5
2 3
10 * 100 * 100 = 100000
4.
x1 x3 x4 x2 x5
2 3
10 * 10 * 100 = 10000
5.
x3 x1 x2 x4 x5
2 3
10 * 100 * 100 = 10000
6.
x3 x1 x4 x2 x5
2 3
10 * 10 * 100 = 10000
7.
x3 x1 x4 x5 x2
3 2
10 * 1000 = 10000
8.
x3 x4 x5 x1 x2
3 2
1000 * 1000 = 1000000
9.
x3 x4 x1 x2 x5
2 3
10 * 10 * 100 = 10000
10.
x3 x4 x1 x5 x2
3 2
10 * 1000 = 10000
これに，最後にセットが行なわれる場合を加えて
100
1000
10000
100000
1000000
が出力されうる値である．
で，直列化すると1000000だけが残る．
問題3．41
プログラムの動作の上では何の変化もない．
問題3．42
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((protected (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (protected withdraw))
((eq? m 'deposit) (protected deposit))
((eq? m 'balance)
((protected (lambda () balance))))
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
(define (make-account balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((protected (make-serializer)))
(let ((protected-withdraw (protected withdraw))
(protected-deposit (protected deposit)))
(define (dispatch m)
(cond ((eq? m 'withdraw) protected-withdraw)
((eq? m 'deposit) protected-deposit)
((eq? m 'balance) balance)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch)))
よくわからないので，MIT-Schemeで試してみようとしたが，
parallel-execute が入っていないと怒られたので
誰か探してやってみて下さい．
問題3．43
口座Aの残高を A，
口座Bの残高を B，とする．(A > B)
差は A - B
これを Aの残高から引出し，Bの残高に預金すると，
口座Aの残高は A - (A - B) = B
口座Bの残高は B + (A - B) = A
よって2つの口座の残高が交換されるだけだから，
任意の回数逐次的に交換処理を行なった場合は
値はある順序で，10ドル，20ドル，30ドルである．
口座Aの残高をA
口座Bの残高をB
口座Cの残高をCとする．
このとき，Aの口座に対してBとC両方の口座からexchangeが行なわれたとする．
A と C の差額は A - C
A と B の差額は A - B
口座Cに対して交換が行なわれ，
口座A = A - (A - C) = C
口座C = C + (A - C) = A
口座Bに対して交換が行なわれ，
口座A = C - (A - B) = C - A + B
口座B = B + (A - B) = A
この合計を足すと
口座A + 口座B + 口座C
= (C - A + B) + A + A = A + B + C
となり，残高の合計は保存されていることが証明された．
また，各口座の取り引きを直列化しない場合には，
(A) と (B)の計算は，
A - (A - B) = B
A - (A - C) = C
のうち，後で処理された方の値が，A の残高に設定されてしまう．
となると，合計金額は保存されない．
問題3．44
二つの口座に対して一方は amount 分だけ引き落とす．
もう一方は amount 分だけ預けるという動作をしているだけ
なのでこの問題のやりかたで順分だと思う．
より巧妙な方法を使う必要はない．
問題3．45
serialized-exchange を呼び出した時に，
serializer 宣言の中に serializer 宣言が入った形になってしまう．
account1 の serializer を s1,
account2 の serializer を s2,とした時，serialized-exchangeを展開すると，
p183のバージョン
((s1 (s2 exchange)) a1 a2)
==> ((s1 (s2 (lambda (a1 a2)
(let ((difference (- (a1 'balance)
(a2 'balance))))
((a1 'withdraw) difference)
((a2 'deposit) difference)))))
a1 a2)
==> ((s1 (s2 (lambda (a1 a2)
(let ((difference (- (a1 'balance)
(a2 'balance))))
(a1-withdraw difference)
(a2-deposit difference)))))
a1 a2)
この問題の場合
((s1 (s2 exchange)) a1 a2)
==> ((s1 (s2 (lambda (a1 a2)
(let ((difference (- (a1 'balance)
(a2 'balance))))
((a1 'withdraw) difference)
((a2 'deposit) difference)))))
a1 a2)
==> ((s1 (s2 (lambda (a1 a2)
(let ((difference (- (a1 'balance)
(a2 'balance))))
((s1 a1-withdraw) difference)
((s2 a2-deposit) difference)))))
a1 a2)
で，
ロックされる順番は
1．外側の s2
2．外側の s1
3. 内側の s1
4．内側の s2
だが，3.の時点でデッドロックがおこり，
((s1 a1-withdraw) difference) の withdrawをする直前で，
無限ループに陥ってしまう．(make-mutex 参照)
;;実行結果
==> (define a (make-account-and-serializer 100))
a
==> (define b (make-account-and-serializer 200))
b
==> (serialized-exchange a b)
100
==> (a 'balance)
200
==> (b 'balance)
100
==> (define c (make-account-and-serializer-louis 700))
c
==> (define d (make-account-and-serializer-louis 800))
d
==> (serialized-exchange c d)
[無限ループに陥る．]
問題3．46
こんな感じか．
Process1 Cell Process2
nil
access Cell---------------------------------------------
|
-----|----------------------------------access Cell-----
| |
Cell is nil-----------------------------------|---------
| |
-----|----------------------------------Cell is nil-----
| |
set Cell = #t---------------------------------|---------
| |
|________________>#t |
| set Cell = #t
| #t<____________________|
| |
| |
execute Process1 execute Process2
問題3．47
(a) 相互排除器 (mutex)を用いてセマフォを実装する
(define (create-semaphoe num)
(define (make-mutexes num)
(if (= 0 num)
nil
(cons (make-mutex) (make-mutexes (- n 1)))))
(let ((mutexes (make-mutexes))
(index 0))
(lambda (p)
(define (serialized-p . args)
((list-ref mutexes index) 'acquire)
(set! index (+ index 1))
(let ((val (apply p args)))
(set! index (- index 1))
((list-ref mutexes index) 'release)
val))
serialized-p)))
これはよくわかりませんでした．
(b) test-and-set! を用いてセマフォを実装する
(define (create-semaphore num)
(let ((cells (replicate num (list #f))))
(define (iter lst)
(if (null? lst)
#t
(if (test-and-set! (car lst))
(iter (cdr lst))
#f)))
(define (clear-cells! lst)
(if (not (null? lst))
(if (caar lst)
(set-car (car lst) #f)
(clear-cells! (cdr lst)))))
(define (the-semaphoe m)
(cond ((eq? m 'acquire)
(if (iter cells)
(the-semaphoe 'acquire)))
((eq? m 'release)
(clear-cells! cells))))
the-semaphore))
こんな感じでしょうか．
問題3．48
(define (create-idgenerator)
(let ((seq 0))
(define (get-id)
(set! seq (+ seq 1)))
(define (dispatch m)
(cond ((eq? m 'get-id) (get-id))))
dispatch))
(define id-gen (create-idgenerator))
(define (get-id) (id-gen 'get-id))
(define (make-account-and-serializer balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((balance-serializer (make-serializer))
(id (get-id)))
(define (dispatch m)
(cond ((eq? m 'withdraw) withdraw)
((eq? m 'deposit) deposit)
((eq? m 'balance) balance)
((eq? m 'serializer) balance-serializer)
((eq? m 'get-id) id)
(else (error "Unknown request -- MAKE-ACCOUNT"
m))))
dispatch))
(define (serialized-exchange account1 account2)
(let ((serializer1 (account1 'serializer))
(serializer2 (account2 'serializer))
(id1 (account-1 'get-id))
(id2 (account-2 'get-id)))
(cond ((> id1 id2)
((serializer1 (serializer2 exchange))
account1
account2))
((< id2 id1)
((serializer2 (serializer1 exchange))
account2
account1))
((eq? account1 account2))
(else
(error "Different accounts have same ID")))))
同じ2つの口座に対して2者が交換を行なおうとした場合，
ロックする順番が決定されているので，以下のような振舞をし，
デッドロックが発生しない．
A <-> B | B <-> A |
----------------|--------------------|
A.id < B.id |B.id > A.id |
lock A |lock A -> wait |
lock B |wait |
exchange |wait |
release A |wait |
release B |lock A |
done |lock B |
|exchange |
|release A |
|release B |
|done |
問題3．49
よくわかりませんでした．
------------------------------------------------------------------------
これは『欲』しいっ!!
http://house2.infoseek.co.jp/?svx=971122