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-…

いわゆるメモ化． フィボナッチ数列の計算でメモ化使うと，時間計算量がでできるという話． プログラムは以下の通りで，計算結果をテーブルに蓄積しておいて， もし既に計算済みの計算結果がテーブルにあれば，それを即座に答えとして返す 計算済みの計算結…

これまで通り scheme でテーブルを実装するわけですけど，テーブルといっても 2次元ハッシュ(連想配列)としての話になっている． 今回は，それぞれの連想配列のキーを二分木にしてしまおうぜ!って問題だったのでした． テーブル全体を1つの型で作ってしまお…

任意の次元のテーブルに一般化する!! (define (make-table) (let ((local-table (list '*table*))) (define (lookup keys pointer) (let ((record (assoc (car keys) (cdr pointer)))) (if record (if (null? (cdr keys)) (cdr record) (lookup (cdr keys) r…

テーブルを作成するところです! テーブルといっても，perl でいう 2 次元ハッシュですね． その実装は SICP にはっきりばっちり書いてあるんですけど，問題 3-24 はそのテーブルに，c++ とか java みたく，キーの比較関数を与えられるようにしてねーって問題…

キューの両端から追加と削除ができる，deque を作る問題． 追加，削除はで，という制約付き． 本文に書いてある queue の実装をパクればほぼ OK とか思っていたんですけど，それだと終端からの要素の削除がにはならないですね． 結局，双方向線形リストを作…

クロージャでキューを実現する． (define (make-queue) (let ((front-ptr '()) (rear-ptr '())) (define (set-front-ptr! item) (set! front-ptr item)) (define (set-rear-ptr! item) (set! rear-ptr item)) (define (empty-queue?) (null? front-ptr)) (de…