SICP
ストリーム s の要素はどうなっているでしょう,という問題. (define (add-stream s1 s2) (stream-map + s1 s2)) (define s (cons-stream 1 (add-stream s s))) 最初の要素が 1 なのは定義より明らか. 次の要素は,ストリーム s の先頭要素を 2 回足したも…
遅延評価を利用した無限ストリームの章に入りました (3.5.2). 無限ストリームを利用すると,その名の通り,無限長のものが扱えるようになる.例えば以下は無限長である自然数のリスト. ; SICP と記述を合わせるために,cons-stream を stream-cons のエイ…
まず,各ステップで sum の値はどうなっているのか! (define sum 0) (define (accum x) (set! sum (+ x sum)) sum) (define seq (stream-map accum (stream-enumerate-interval 1 20))) (define y (stream-filter even? seq)) (define z (stream-filter (lam…
これまで,Gauche の util.stream を使ってたんですけど,これどうも SICP に書いてあるのとは違う動作をする.実際 higepon さんも同じことを言ってた (関数型言語の勉強にSICPを読もう - (48) 3章 - 標準部品化力、オブジェクトおよび状態 (192ページ) - h…
ついに遅延評価の話に入りました.問題 3-40 くらいから,早く遅延評価の話にならないかなーと待ち望んでいた章ですね!時間毎に変化する現実世界の事物を抽象化しようとすると,普通のプログラミングだと刻々と変化する状態を持つオブジェクトとして表現する…
Exercise 3.49. Give a scenario where the deadlock-avoidance mechanism described above does not work. (Hint: In the exchange problem, each process knows in advance which accounts it will need to get access to. Consider a situation where a p…
複数のプロセスが共有資源をアクセスする場合において,各プロセスが資源を確保する順番を同じにしておくと,デッドロックを回避できる(場合がある)がそれはなぜ,という問題.デッドロックは,あるプロセス A がロックをかけた資源 a に対し他のプロセス B …
n 個までのプロセスがクリティカルセクションに入れるようなセマフォを作成するのが課題.in terms of mutexes って話だと,mutex を n 個用意してやるしかないんじゃねと.in terms of atomic test-and-set! operations って話は,結局 mutex を n 個用意す…
serializer の実装についての話.ここでは mutex を使って,排他制御を行っている. mutex とセマフォ これまで mutex とセマフォの違いを,かなり曖昧なままにしてきてしまったんだけど, セマフォをクリティカルセクションの排他制御に用いる時、セマフォ…
Louis Reasoner (人名) は大抵間違っているんですけど,今回も間違いやがったらしい. 今回 Louis Reasoner が作ったのは,自動的に関数を直列化して返す銀行口座. (define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balan…
2 つの口座の残高を交換する exchange は,直列化しとかないとヒドいことになる. (define (exchange account1 account2) (let ((difference (- (account1 'balance) (account2 'balance)))) ((account1 'withdraw) difference) ((account2 'deposit) differ…
タイミングダイアグラムは激しくメンドいので略.
これが make-account なわけだけど,'withdraw とか 'deposit とかのメッセージが送られてくる毎に,毎回直列化された関数を生成するようになってる. (define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! bala…
Ben がここ変えたらしいんだけど, (define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance am…
この場合,x の値としてはどのような可能性があるのか. (define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (* x x x)))) 乗算が atomic と仮定してのことだけど,x の読み出しと,計算と,代入の間それぞれに,インタリー…
make-serializer で生成されるオブジェクトは,関数を引数に取って,直列化された関数を返すシリアライザ.直列化された関数は,その実行時にインタリーブされない.そのために, (define x 10) (define s (make-serializer)) (parallel-execute (s (lambda …
プログラムの同時実行に関するよくある銀行口座の問題. Peter や Paul,Mary がそれぞれ勝手に下記のプロセスを実行したときに,結果としての口座残高のパターンをリスティングする. (b)みたいに図を書く問題はメンドいから省略する! # Peter: (set! balan…
摂氏と華氏を相互変換する celsius-fahrenheit-converter という関数が,この章の冒頭にありました. (define (celsius-fahrenheit-converter c f) (let ((u (make-connector)) (v (make-connector)) (w (make-connector)) (x (make-connector)) (y (make-co…
environment diagram はさすがにメンドい.
入力を二乗する回路素子(?) squarer をばっちし実装したろやないか! 問題 3-34 だと multiplier とかを組み合わせて Louis がヘンなことしてましたから,新しく,プリミティブな感じで作るみたいです. squarer はこんな感じになる. (define (squarer a b)…
(define (squarer a b) (multiplier a a b)) There is a serious flaw in this idea. Explain. という問題.とりあえずやってみるといいですね. まずは squarer の a に対して値を設定する. (define (squarer a b) (multiplier a a b)) (define a (make-co…
問題3-33 Constraint ベースのものがどんなものかということですが,以下の例が分かりやすい. averager は 2 つの入力端子 (in-A,in-B) に与えられた数値の平均が出力端子 out に出力されるというものです.なんとなく,そんなのすぐできるじゃんみたいな…
この節のタイトルにある "Constraints" というのは,基本的に世の中の関係式全てに相当するもののようです.例えば,摂氏と華氏の変換式(これは実際に SICP に,例題として取り上げられている)は,次のように表せます. (C: 摂氏, F: 華氏)じゃぁこれをプロ…
time segment に置かれているイベントキューが LIFO ではなく FIFO なのはなぜかという問題. 今回はこのヒントに従った方が分かりやすそう. In particular, trace the behavior of an and-gate whose inputs change from 0,1 to 1,0 in the same segment a…
関数 make-wire 中の関数 accept-action-procedure! では,関数のリスト action-procedures に引数で渡された関数 proc を追加する際に,なぜ proc を一度実行しているのかという問題.題材になった accept-action-procedure! の定義はこちら.最後の (proc)…
全加算器を組合せて,ripple carry adder を作る.加算器とか懐しさ満点ですね. これで,何桁の足し算にも対応できて,カンペキです! ;; 電子回路シミュレータに必要な関数定義を読み込み (add-load-path "/Users/ykiri/programming/SICP") (load "section3…
ほぼ一ヶ月 SICP 放置してたんですけど,ディジタル回路シミュレーション,ほとんど写経という体たらくですがとりあえず動いた. 抽象化して,データ構造をブラックボックス化させた話をするのは理解させるという目的の上ではいいんだろうなと思うのですが,…
or-gate を,and-gate と inverter で構成しろという問題. こんな感じかと思われ. (define (or-gate a1 a2 output) (let ((x (make-wire)) (y (make-wire)) (z (make-wire))) (inverter a1 x) (inverter a2 y) (and-gate x y z) (inverter z output)) 'ok)…
電気回路のシミュレーションをする前段階として,基本ゲートを実装していきます. and-gate は以下のような感じで提供されていますから, ;; and-gate (define (and-gate a1 a2 output) (define (and-action-procedure) (let ((new-value (logical-and (get-…
いわゆるメモ化. フィボナッチ数列の計算でメモ化使うと,時間計算量がでできるという話. プログラムは以下の通りで,計算結果をテーブルに蓄積しておいて, もし既に計算済みの計算結果がテーブルにあれば,それを即座に答えとして返す 計算済みの計算結…