SICPゼミ第26回
練習問題3.50
(define (stream-map proc . argstreams) (if (null? (car argstreams )) the-empty-stream (stream-cons (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-cdr argstreams))))))
by dolicas
練習問題3.51
gosh> (define x (stream-map show (stream-enumerate-interval 0 10))) 0x gosh> (stream-ref x 5) 1 2 3 4 55 gosh> (stream-ref x 7) 6 77
練習問題3.52
> (define sum 0) >(define (accum x) (set! sum (+ x sum)) sum) > sum 0 > (define seq (stream-map accum (stream-enumerate-interval 1 20))) > sum 1 > (define y (stream-filter even? seq)) > sum 6 > (define z (stream-filter (lambda (x) (= (remainder x 5) 0)) seq)) > sum 10 > (stream-ref y 7) 136 > sum 136 > (display-stream z) 10 15 45 55 105 120 190 210'done > sum 210
メモ化していないと、毎回accumが呼ばれてsumに足されていってしまうのでへんなことになる。
by tube
SICPゼミ第25回
練習問題3.48
ループができないから。
serialized-exchange の実装例
;今までの serialized-exchange と同じやつ (define (serialized-exchange account1 account2) (let (( serializer1 (account1 'serializer )) (serializer2 (account2 'serializer ))) (( serializer1 (serializer2 exchange )) account1 account2 ))) (define (serialized-exchange-renewal account1 account2) (let ((id1 (get-ID account1)) (id2 (get-ID account2))) (if (> id1 id2) (serialized-exchange account2 accoun1) (serialized-exchange account1 account2))))
by tube
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