SICPゼミ第24回
練習問題3.46
スレッド1が(car cell)した結果falseが返ってくる→スレッド1が(set-car! cell true)する前にスレッド2が(car cell)してfalseを得る→同時に2つのスレッドがmutexを獲得できたものとして実行されてしまう。
練習問題3.47
(a)
(define (make-semaphore n) (let ((counter 0) (m (make-mutex))) (define (the-semaphore ord) (cond ((eq? ord 'acquire) (begin (m 'acquire) (if (< counter n) (begin (set! counter (+ counter 1)) (m 'release)) (begin (m' release) (the-semaphore 'acquire))) )) ((eq? ord) (begin (m' acquire) (set! counter (- counter 1)) (m' release)))) the-semaphore))
by dolicas
(b)
(define (make-semaphore) (let ((cell (make-cell n))) (define (list-test-and-set! cell) (if (test-and-set! cell) (if (null? (cdr cell)) (the-semaphore 'acquire ) (list-test-and-set! (cdr cell))) #f)) (define (the-semaphore m) (cond ((eq? m 'acquire) (list-test-and-set! cell)) ((eq? m 'release) (clear-cell! cell )))) the-semaphore )) (define (make-cell n) (if (= n 0) '() (cons #f (make-cell (- n 1)) )))
clear-cell! は無理。
by tube
SICPゼミ第23回
練習問題3.38
a.
35 Peter->Mary->Paul
40 Mary->Peter->Paul (後ろ二人順不同)
45 Peter->Paul->Mary (前二人順不同)
50 Paul->Mary->Peter
b.
60
by tube
練習問題3.39
100, 101, 121.
by tube
練習問題3.40
10^k (k = 2,3,4,5,6)
直列化すると10^6だけ
by dolicas
練習問題3.41
'balance はset!しないので変なことはおきない。
by dolicas
練習問題3.42
問題ない。
練習問題3.43
直列化されているので口座1と口座2の交換中に、これら2つの口座に他の処理が行われることはない。よってこの1回交換によって残高が交換される（さらに合計は保存する）ことが示されれば、帰納的に全体でもそのようになると分かる。1回の交換で大丈夫なのは自明。
serializeしなかったとき。
口座1と口座2、口座2と口座3をexchange
合計も破綻してる。
by dolicas
練習問題3.44
Louis は正しくない。
exchange のときは balance にアクセスして得た値を直列化せずに使用していたため問題が発生したが、transfer では、withdraw, deposit それぞれ自体は直列化されているため問題が発生しない。
by tube
練習問題3.45
((serializer1 (serializer2 exchange )) account1 account2 )))
のところで、serializer1が使われる。
その後 (exchange acount1 acount2)が処理されるが、この中で ((account1 'withdraw) difference) が実行される。これは (balance-serializer withdraw) で、serializer1（balance-serializerと同じ）で直列化されているが、
((serializer1 (serializer2 exchange )) account1 account2 )))
ですでにserializer1を使ってしまっているのでこの部分は実行されず待機される。この待機が解消されることはなく永遠に処理が終わらない。
by dolicas
SICPゼミ第22回
練習問題3.32
入力を 0,1 → 1,1 → 1,0 と変化させたとき振る舞いが変わる。
一回目の入力の変化で「出力を1にする」という予定が追加され、その後2回目の入力の変化で「出力を0にする」という予定が追加される。キューだとこの順番に処理されるので出力は最終的に0だが、リスト（要するにスタック）を使うと逆に処理されるので最終出力が1になりおかしい。
by dolicas
SICPゼミ第21回
練習問題3.31
実行環境 DrRacket
> (define input-1 (make-wire )) (define input-2 (make-wire )) (define sum (make-wire )) (define carry (make-wire )) > (probe 'sum sum) > (probe 'carry carry) > (half-adder input-1 input-2 sum carry) 'ok > (propagate) 'done > (set-signal! input-1 1) 'done > (propagate) 'done > (get-signal input-1) 1 > (get-signal sum) 0 > (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done > (get-signal sum) 0 > (get-signal input-1) 1
probeのときに出力が出ないのは、probeでadd-action!が呼ばれても実行はされないというだけなので、それはそう。
こちらの記事
では、アジェンダが空だといっているが、そんなことはない。なぜなら、 set-signal!を実行したときにcall-eachが呼ばれ、アジェンダに手続きが追加はされている。アジェンダの中身を見てみたのだろうか？
しかも、アジェンダの中身が空だとして、set-signal! input-2 1 を実行したときにcarryが更新されているのはなぜだろうか？
以上のことから、アジェンダが空であるという説明は間違っている。ではなぜ実行結果がこうなるのだろうか？
半加算器を設定したときに初期化がされていないので、教科書の図3.25の配線eが0のまま更新されない。そのためset-signal!してアジェンダに手続きが追加されてもワイヤーSの値への入力が間違ったままであるため、サムの値が0のまま更新されない。そのためaction-proceduresが呼ばれず、probe による値の表示も行われないというわけである。
2017/01/09 追記
上で言及したこちらの記事
に追記がなされていたが気づくのが非常に遅れてしまい申し訳ない限りである。
まず、こちらの記事にて言葉足らずであったところを補足させていただく。
大前提として、(propagate) は真っ先にthe-agendaが空であるかどうかの判定をしており、空であると何も実行せずに終わってしまう。つまりwireにセットされた信号が正しく計算されていくにはthe-agendaに各種手続き (outputのwireの値を更新しろ、とか、(probe)した wireの値が更新されたら表示しろ、とか) が追加されていなくてはならない。the-agendaを更新する手続きはafter-delayのみであるため、各種手続きをラムダ閉包として引数にとったafter-delayが実行されなくては(propagate)が正しく作動しない。
さて、
(half-adder input-1 input-2 sum carry)
を実行したとき、つまり半加算器を結線したときに、and-gateや or-gate, inverter の結線によって、各wireのもつaction-proceduresにafter-delayが追加されていく。
ここでaccept-action-procedureが本来の
(define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)) (proc))
であれば、各wireのもつaction-procedureにafter-delayが追加された後、(proc)という実行によってafter-delayが実行され、the-agendaが更新されてゆく。つまり、その後の(propagate)によって正しく計算が進んでゆく。
しかし、問題で述べられているような
(define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)))
であった場合にどうなるのか。after-delayは各wireのもつaction-procedureに追加されるのみで、実行されない。つまりthe-agendaは空のままである。このせいで(propagate)をしても何も起こらない、だからちゃんと(proc)を追加しなければならない、というのはもちろん正しい。
しかし、本記事で述べている例を見てみよう。
> (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done
set-signal!の後、(propagate)することによってちゃんとcarryの値が更新されているのである。
ではこれはなぜか？
実は、set-signal!手続きにカギがある。
下は set-signal!によって呼び出されるset-my-signal!である。
(define (set-my-signal! new-value) (if (not (= signal-value new-value )) (begin (set! signal-value new-value) (call-each action-procedures )) 'done ))
set-my-signal!の中で、「signal-valueとnew-valueが異なれば」call-eachによってaction-proceduresの中身が実行されるのである。つまり、各wireのもつaction-proceduresに追加されていただけのafter-delayたちが順に実行されていき、the-agendaが更新されているということである。
ただし、ここで重要なのはこのset-my-signalの初めに行われているif条件分岐、上で述べた「signal-valueとnew-valueが異なれば」というところである。
本来であれば一度どこかのwireのもつaction-proceduresにafter-delayが追加されれば、それが実行されthe-agendaが更新されるはずなのであるが、今回のように即時実行しないaccept-action-procedure!であると、set-signal!によって「値が変更されたwireのもつaction-proceduresに存在するafter-delayのみ」が実行されていき、これらのみについてthe-agendaが更新されていく、ということになる。
具体例を見ていこう。
上のような半加算器 (初期値は全て0) に対し、A(上の実行例ではinput-1) に値1をsetしたときに何がおこるだろうか。
> (set-signal! input-1 1) 'done > (propagate) 'done > (get-signal input-1) 1 > (get-signal sum) 0
Aに関連したD, C についてはand,orの演算が行われる。
Dはor-gateなので 1 に更新される。しかし C はand-gateなので0のまま更新されない。
本来1となるべき E の値をsetするinverter手続きは C のaction-proceduresに眠ったままでthe-agendaに追加されず、E の値は更新されないままである。
このせいでand-gateである S に対する入力は1,0となり、S は0となる。つまり S も C も更新されない。そのためprobe手続きも呼ばれない。結果返ってくるのは虚しい'doneの文字列だけである。
さて、次に B (上の実行例ではinput-2) に値1をsetするとどうなるか。
> (set-signal! input-2 1) 'done > (propagate) carry 11 New-value = 1'done > (get-signal sum) 0 > (get-signal input-1) 1
B に関連した C, D について演算が行われる。
D は1のまま更新されない。C は1に更新される。C が更新されたためinverterによる値の更新が行われ、 E が 0 に更新される。S は0のまま更新されない。更新された C についてはprobeが呼ばれる。これで全てのつじつまが合う、ということになる。
さて、以上が本記事で述べていた内容であるが、この追記なしでは非常にわかりづらい文章となっていたことに対して深く申し訳ないと思う。
ここで、上で言及したこちらの記事
の説明について、本追記の上半分
after-delayは各wireのもつaction-procedureに追加されるのみで、実行されない。つまりthe-agendaは空のままである。このせいで(propagate)をしても何も起こらない、だからちゃんと(proc)を追加しなければならない
という部分の説明しかなされていないように思ったので指摘させていただいた。もし本追記で述べた内容を全て踏まえた上での説明であったのであれば謝罪させていただく。
SICPゼミ第20回
練習問題3.27
SICPゼミ第19回
練習問題3.24
(define (make-table same-key?) (let ((table (list '*table*))) (define (lookup key) (let ((record (assoc key (cdr table)))) (if record (cdr record) #f))) (define (assoc key records) (cond ((null? records) #f) ((same-key? key (caar records)) (car records)) (else (assoc key (cdr records))))) (define (insert! key value) (let ((record (assoc key (cdr table)))) (if record (set-cdr! record value) (set-cdr! table (cons (cons key value) (cdr table ))))) 'ok) (define (dispatch m) (cond ((eq? m 'lookup) lookup) ((eq? m 'insert!) insert!))) dispatch))
by pine
SICPゼミ第18回
練習問題3.21
(define (print-queue queue) (display (car queue)))
Benはqueueの末尾のポインタを見てはっちゃけてるだけ。
by pine
練習問題3.22
(define (make-queue) (let ( (front-ptr '()) (rear-ptr '()) ) (define (empty-queue?) (null? front-ptr)) (define (insert-queue item) (let ((paired (cons item '()))) (if (empty-queue?) (begin (set! front-ptr paired) (set! rear-ptr paired)) (begin (set-cdr! rear-ptr paired) (set! rear-ptr paired)) ) ) ) (define (delete-queue) (if (empty-queue?) (error "なにもない") (set! front-ptr (cdr front-ptr)) ) ) (define (front-queue) (if (empty-queue?) (error "なにもない") (car front-ptr) ) ) (define (dispatch m) (cond ((eq? m 'insert) insert-queue) ((eq? m 'delete) (delete-queue)) ((eq? m 'front) (front-queue)) ((eq? m 'empty?) (empty-queue?)) (else (error "そんな手続きはない")) ) ) dispatch ) )
by dolicas
