(define s (cons-stream 1 (add-streams s s))) で生成される要素をプログラムを走らせずに予想せよ、という問題。 (1 2 4 8 16 32 64 128 ....)と予想される。一応、確認。 以下は教科書で定義されている手続き ; 明確な(計算によって生成する)ストリームの…

遅延評価の問題。 以下の一連の式について (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 (lambda (x) (…

引数を印字してから返すだけの手続き(教科書で定義) (define (show x) (display-line x) x) 次のそれぞれの式の評価に応じて解釈系は何を印字するか? (define x (stream-map show (stream-enumerate-interval 0 10))) ; 0x (stream-ref x 5) ; 1 ; 2 ; 3 ; 4…

問題はmapのstream版を穴埋めで定義せよ、ということで (define (stream-map proc . argstreams) (if (stream-null? (car argstreams)) the-empty-stream (cons-stream (apply proc (map stream-car argstreams)) (apply stream-map (cons proc (map stream-…

最初にアクセスした口座の内容によって処理を変えるケースだと、デッドロック回避方法はうまくいかない。

口座に番号をつけて、プロセスはより小さい方の番号の方の口座を先に獲得しようとするデッドロック回避方法がうまくいく理由は以下のとおり。 番号の小さい方の口座から獲得するということは順番を固定化することであり、直列化しているということになる。 s…

セマフォの実装 a. 相互排除器を使った実装 (define (make-semaphore n) (let ((acquired 0) (mutex (make-mutex))) (define (the-semaphore m) (cond ((eq? m 'acquire) (mutex m) (if (> acquired n) (begin (mutex 'release) (the-semaphore m)) ; releas…

直列変換器の実装(教科書で定義) (define (make-serializer) (let ((mutex (make-mutex))) (lambda (p) (define (serialized-p . args) (mutex 'acquire) (let ((val (apply p args))) (mutex 'release) val)) seralized-p))) 相互排除器(mutex)の実装(教科…

Louisが定義した払い出し、預け入れの直列化＋直列変換器を輸出する口座の手続き (define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient fun…

Ben Bitdidddleが考えたお金を口座から口座へ移す手続き (define (transfer from-account to-account amount) ((from-account 'withdraw) amount) ((to-account 'deposit) amount)) Louis Reasonerはここに問題があるとしているが、それは正しいか?正しくな…

三つの口座をx, y, zとし、最初の口座の残高を x=10, y=20, z=30とする。残高交換のプロセスを分解すると 1. 口座a1の残高確認 2. 口座a2の残高確認 3. 1時点の口座a1の残高と、2時点の口座a2の残高の差を取得 4. 口座a1からの払い出し 4.1. 口座a1の残高-3.…

withdrawとdepositの呼び出しの度に新しい直列化された手続きを作り出して返すmake-account(教科書で定義)を (define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insuf…

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

(define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (* x x x)))) の実行結果となりうるxの可能性は、以下のようになる P1,P2をそれぞれプロセスに分割すると P1 は X1-1: (* x x)の最初のxへのアクセス X1-2: (* x x)の二番…

(define x 10) (define s (make-serializer)) (parallel-execute (lambda () (set! x ((s (lambda () (* x x)))))) (s (lambda () (set! x (+ x 1))))) とした時は、 (* x x) 中での値の変化と、 (set! x (+ x 1)) の間での値の変化が起こらなくなるので、 1…

Peter, Paul, Mary (ピーター・ポール&マリーのこと?) が最初に100ドルあった共同銀行口座に以下の操作を行った場合の動き ; Peter (set! balance (+ balance 10)) ; Paul (set! balance (- balance 20)) ; Mary (set! balance (- balance (/ balance 2))) a…

Lispは手続きの値として合成オブジェクトを返すことが出来るので、命令形流儀の制約言語を式指導の流儀に変換できるというテーマ。元のcelesius-fahrenheit-converter 手続き(教科書で定義) (define (celsius-fahrenheit-converter c f) (let ((u (make-conn…

(define a (make-connector)) (define b (make-connector)) (set-value! a 10 'user) set-value!評価中時点でコネクタの局所手続きの中の (for-each-except setter inform-about-value constraints) が評価される環境を示す環境図環境図ってどこまで描けば良…

Ben Bitdiddle のsquarer手続き(穴埋め問題) (define (square x) (* x x)) (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 (g…

Louis Reasoner が定義した制約装置である平方器の重要な欠点 (define (squarer a b) (multiplier a a b)) とりあえず実験 (define a1 (make-connector)) ; a1 (define a2 (make-connector)) ; a2 (probe "a1" a1) ; #<closure (probe me)> (probe "a2" a2) ; #<closure (probe me)> (squarer a1 a2) </closure></closure>…

基本乗算, 加算, および定数の制約を使い、入力として三つのコネクタa, b, cをとり、cの値がaとbの平均であるような制約を達成する手続きaveragerを定義する。 averagerのネットワークで表した関係 c = 0.5 * (x + y)は以下のようになる。 ┌────┐ a ─┤a1 │x …

次第書きの各時間区分内で走るべき手続きがキューになっている理由を述べよ。 同じ区分の中で入力が0,1から1,0に変わったアンドゲートの振る舞いをトレースし、区分内の手続きを先頭で挿入,削除する(最後に入ったものが最初に出る)通常のリストに格納した時…

.accept-action-proceduer!に初期化コードが入った状態で実行した場合 (define input-1 (make-wire)) ; input-1 (define input-2 (make-wire)) ; input-2 (define sum (make-wire)) ; sum (define carry (make-wire)) ; carry (probe 'sum sum) ; sum 0 New-…

n個の回線の三つのリスト Ak, Bk, Sk ともう一本の回線 C を引数にとるn個の全加算器をつなげた繰上り伝播加算器(ripple-carry-adder)の定義。 回路図を見ると最後のCn=0になっていて、最初のCになっているので、こんな感じ。 (define (ripple-carry-adder a…

論理和は否定と論理積を用いて ¬((¬A) ∧ (¬B))で表せるので、回路図は a1 ─[¬]┐c └─┐ e output [∧]─[¬]─ ┌─┘ a2 ─[¬]┘dとなる よって or-gate の定義は以下のようになり (define (or-gate a1 a2 output) (let ((c (make-wire)) (d (make-wire)) (e (make-wir…

ディジタル回路のシミュレータでand-gateと似ているor-gateを定義する問題。 まずは論理和(locgical or)の定義 (define (logical-or a b) (cond ((and (= a 0) (= b 0)) 0) ((or (and (= a 1) (= b 1)) (and (= a 1) (= b 0)) (and (= a 0) (= b 1))) 1) (el…

メモ化(memoization)またはテーブル化(tabulation)の問題。 ちょっと手抜きだけど(memo-fib 3)の計算を解析する環境の図。 後でちゃんと直すかも。memo-fibがn番目のFibonacchi数をnに比例したステップ数で計算で出来るのは、(n-1)項, (n-2)項の計算結果をta…

内部の表を順序付けられていないリスト表現から二進木での表現に変更する 二進木での表現は2.3.3節辺りを参考に。 2.3.3節での二進木の表現では (entry left right)だったのを(record left right)にする。 record は (識別子 . entry) とし、entry が値の場…

値が任意個数のキーで格納され、値が異なればキーの個数も異なるかも知れない表の実装 insert!, lookupはアクセスするのにキーのリストを取るということなのでこんな感じで。 (define (make-table same-key?) (let ((local-table (list '*table*))) (define …

equal?でなくsame-key?を使用するassoc手続き(local-assoc)を追加した局所表の定義 (define (make-table same-key?) (let ((local-table (list '*table*))) (define (local-assoc key records) (cond ((null? records) #f) ((same-key? key (caar records)) …