読者です 読者をやめる 読者になる 読者になる

理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

Scheme の構文解析

構文解析つっても構文チェックとか全くしてないのでとてもアレなかんじなんですけど,Scheme っていったら S 式だし,S 式っていったらリストだし,Scheme のソースコードを与えられたら全部 Perl の array reference として返してやったらとりあえず基本構…

Scheme の字句解析2

前に Scheme の字句 をクソ楽に区切りたいなーとか思って,一行で済ませてみようとしたのでしたが,結果としてうまくいきませんでした. Scheme のコードの字句解析 - 理系学生日記 my @tokens = map { split /(?<=\()|(?=\))/, $_ } split /\s+/, <

Scheme のコードの字句解析

SICP の第 4 章は,Scheme で Scheme の簡単な処理系を実装するような感じみたいなんですけど,higepon さんが C++ で Scheme のインタプリタを作っていっています. 関数型言語の勉強にSICPを読もう - (53) 4章 - 超言語的抽象(216ページ) C++でSchemeイン…

4 章へ

3 章の残りの問題はどうも Gauche だとできない感じなので,4 章に進む.

問題 3-76 (3.5.3 Exploiting the Stream Paradigm)

3-75 のこの回答もやっぱしあんましよろしくなくて,何がよろしくないかというと,この一つの関数の中には「平滑化」を行う部分と「0 をまたがる遷移があるかどうか判断」という二つの機能が混じってしまっています. (define (make-zero-crossings input-st…

問題 3-75 (3.5.3 Exploiting the Stream Paradigm)

問題 3.74 の回答は,センサの出力値がウンコだからだめらしい. Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. だから次のよ…

問題 3-74 (3.5.3 Exploiting the Stream Paradigm)

電気でも何でも良いんですけど,信号が[負の数->正の数] と遷移したときに 1,[正の数->負の数]と遷移したときに -1,その他の遷移のときに 0 を返すような "信号" を作成する問題です. 直感的に書けば,Alyssa が書いた以下のもので OK なんですが, (defi…

問題 3-73 (3.5.3 Exploiting the Stream Paradigm)

遅延評価を使うと電子回路で言うフィードバック回路を構成することができます.時間 のときの値が だから,それを入力として次の時間 のときの値は だなとかいう.こういう現実のモデル化は,まさに,SICP の Section 3.5 冒頭で言われていることですね. Ca…

問題 3-70 - 72

3-70 を解こうと思いましたが,下記のが gosh で暴走してしまって (たぶん無限ループしてる),にっちもさっちもいかない! 飛ばす!! (define (merge-weighted s1 s2 weight) (cond ((stream-null? s1) s2) ((stream-null? s2) s1) (else (let ((s1car (stream…

問題 3-69 (3.5.3 Exploiting the Stream Paradigm)

まずは,三つ組の無限ストリームを作る関数 triples.これであってんのかなー. (define (triples s t u) (cons-stream (list (stream-car s) (stream-car t) (stream-car u)) (interleave (stream-map (lambda (x) (cons (stream-car s) x)) (pairs t u)) (…

問題 3-68 (3.5.3 Exploiting the Stream Paradigm)

この pairs の実装はどこが間違っているのかという問題です. (define (pairs s t) (interleave (stream-map (lambda (x) (list (stream-car s) x)) t) (pairs (stream-cdr s) (stream-cdr t)))) 実際に走らせてみたところ,無限ループにハマってしまいまし…

問題 3-67 (3.5.3 Exploiting the Stream Paradigm)

上の pairs は というものだったんだけど,今度は を作る. (define (pairs s t) (cons-stream (list (stream-car s) (stream-car t)) (interleave (interleave (stream-map (lambda (x) (list (stream-car s) x)) (stream-cdr t)) (stream-map (lambda (x) …

問題 3-66 (3.5.3 Exploiting the Stream Paradigm)

integers ってのは自然数の無限リストです. (dump-stream integers 10) ; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, done 今,pairs って関数がある. という無限ストリームを引数にとって pairs が作るのは,次のようなストリームです. ちなみに定義は以下のように…

問題 3-65 (3.5.3 Exploiting the Stream Paradigm)

今度は, を使って, の真の値を求めるよー.といってもほとんど SICP にやりかたが書いてあるので,ぼくは Scheme を書くだけだ.まずはこれが上記の総和をとってるやつの各項をストリームにしたもの.なるほどとても直感的だ. (define (ln2-summands n) (…

問題 3-64 (3.5.3 Exploiting the Stream Paradigm)

平方根をストリームの力を使って求めてみね?そういうのカッコよくね?って問題. 今回の課題は,ストリーム中の連続する 2 要素が tolerance 以下のものを探して,その 2 番目の要素を返す関数 stream-limit を作るって問題.そしてそれを使って平方根を求…

問題 3-63 (3.5.3 Exploiting the Stream Paradigm)

次に示す,無限ストリームを使って平方根を計算する sqrt-stream の二つの実装は何が違うのか,という問題.後者の方がわりと直感的だけど,実際に SICP の本文で用いられているのは前者である. (define (sqrt-stream x) (define guesses (cons-stream 1.0 …

問題 3-62 (3.5.2 Infinite Streams)

理系の人間は, の級数展開には苦しめられたことだと思います.高次微分とかはメンドくて,しかも とかは とか とかの級数展開と違ってあんまし美しくもない. メンドいのは全部 PC にやらせれば良いと思う.ここでは,べき級数を割り算するというヤバげな問…

問題 3-61 (3.5.2 Infinite Streams)

べき級数にも逆数のような概念がある.べき級数 の逆元は, となるようなべき級数 である,みたいな感じです. 今,,つまり を定数項とそれ以外に分けると,以下のような展開ができます.詳しくは SICP 3.5.2 へ. てわけで,これに従えば を求めることがで…

問題 3-60 (3.5.2 Infinite Streams)

無限ストリームとして表されたべき級数同士をかけ合わせる,mul-series を作成する問題.気付くまで,考え方が難しかった...乗算に用いるべき級数を と とする.このとき, をどう考えるかってことなんだけど,こう考えると失敗する.ていうか失敗した.…

問題 3-59 (3.5.2 Infinite Streams)

課題 a という無限ストリームが与えられたとき, を返す関数 integrate-series を作成します.なんでこの関数が integrate-series という名前になっているかというと, の積分が となり,その積分の係数が返されているからですね (定数項は除く). (define (…

問題 3-58 (3.5.2 Infinite Streams)

関数 expand の解釈が問われています!! (define (expand num den radix) (cons-stream (quotient (* num radix) den) (expand (remainder (* num radix) den) den radix))) 最初からぶっちゃけると,これ割り算してるんですよね.筆算を思い浮かべるといいと…

問題 3-57 (3.5.2 Infinite Streams)

以下のように定義されたフィボナッチ数列 fibs について,第 n 項を計算するのに必要な加算回数はどう増えていくでしょうという問題.ただしメモ化はなし. (define (add-stream s1 s2) (stream-map + s1 s2)) (define fibs (cons-stream 0 (cons-stream 1 (…

問題3-56 (3.5.2 Infinite Streams)

今回は,2,3,5 のみを素因数として持つような数のみによって構成される,昇順かつ重複のない無限ストリームを構成します.ヒントとしては,以下のような無限ストリーム S を構成すれば良いとされていました. S は 1 から始まる (scale-stream S 2) は S …

問題3-55 (3.5.2 Infinite Streams)

今回は,与えられた無限ストリームの部分和を持った無限ストリームを返す関数 partial-sums を作成します.渡された無限ストリームが だったとき, 返す無限ストリーム の要素 は ということになります. (define (partial-sums S) (stream-cons (stream-car…

問題3-54 (3.5.2 Infinite Streams)

目的は n 番目の要素が になるような無限ストリーム factorials を作成すること. まずは,2 つのストリームを掛け合わせる まずは,2 つのストリームを掛け合わせて,新しい無限ストリームを作るような関数 mul-stream をこさえます. (define (mul-stream …

問題3-53 (3.5.2 Infinite Streams)

ストリーム s の要素はどうなっているでしょう,という問題. (define (add-stream s1 s2) (stream-map + s1 s2)) (define s (cons-stream 1 (add-stream s s))) 最初の要素が 1 なのは定義より明らか. 次の要素は,ストリーム s の先頭要素を 2 回足したも…

Infinite Streams が面白すぎる件

遅延評価を利用した無限ストリームの章に入りました (3.5.2). 無限ストリームを利用すると,その名の通り,無限長のものが扱えるようになる.例えば以下は無限長である自然数のリスト. ; SICP と記述を合わせるために,cons-stream を stream-cons のエイ…

問題 3-52 (3.5.1 Streams Are Delayed Lists)

まず,各ステップで 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…

問題 3-51 (3.5.1 Streams Are Delayed Lists)

これまで,Gauche の util.stream を使ってたんですけど,これどうも SICP に書いてあるのとは違う動作をする.実際 higepon さんも同じことを言ってた (関数型言語の勉強にSICPを読もう - (48) 3章 - 標準部品化力、オブジェクトおよび状態 (192ページ) - H…

問題 3-50 (3.5.1 Streams Are Delayed Lists)

ついに遅延評価の話に入りました.問題 3-40 くらいから,早く遅延評価の話にならないかなーと待ち望んでいた章ですね!時間毎に変化する現実世界の事物を抽象化しようとすると,普通のプログラミングだと刻々と変化する状態を持つオブジェクトとして表現する…

問題3-47 (3.4.1 The Nature of Time in Concurrent Systems)

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…

問題3-48 (3.4.1 The Nature of Time in Concurrent Systems)

複数のプロセスが共有資源をアクセスする場合において,各プロセスが資源を確保する順番を同じにしておくと,デッドロックを回避できる(場合がある)がそれはなぜ,という問題.デッドロックは,あるプロセス A がロックをかけた資源 a に対し他のプロセス B …

問題3-47 (3.4.1 The Nature of Time in Concurrent Systems)

n 個までのプロセスがクリティカルセクションに入れるようなセマフォを作成するのが課題.in terms of mutexes って話だと,mutex を n 個用意してやるしかないんじゃねと.in terms of atomic test-and-set! operations って話は,結局 mutex を n 個用意す…

問題3-46 (3.4.1 The Nature of Time in Concurrent Systems)

serializer の実装についての話.ここでは mutex を使って,排他制御を行っている. mutex とセマフォ これまで mutex とセマフォの違いを,かなり曖昧なままにしてきてしまったんだけど, セマフォをクリティカルセクションの排他制御に用いる時、セマフォ…

問題3-45 (3.4.1 The Nature of Time in Concurrent Systems)

Louis Reasoner (人名) は大抵間違っているんですけど,今回も間違いやがったらしい. 今回 Louis Reasoner が作ったのは,自動的に関数を直列化して返す銀行口座. (define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balan…

問題3-44 (3.4.1 The Nature of Time in Concurrent Systems)

2 つの口座の残高を交換する exchange は,直列化しとかないとヒドいことになる. (define (exchange account1 account2) (let ((difference (- (account1 'balance) (account2 'balance)))) ((account1 'withdraw) difference) ((account2 'deposit) differ…

問題3-43 (3.4.1 The Nature of Time in Concurrent Systems)

タイミングダイアグラムは激しくメンドいので略.

問題3-42 (3.4.1 The Nature of Time in Concurrent Systems)

これが make-account なわけだけど,'withdraw とか 'deposit とかのメッセージが送られてくる毎に,毎回直列化された関数を生成するようになってる. (define (make-account balance) (define (withdraw amount) (if (>= balance amount) (begin (set! bala…

問題3-41 (3.4.1 The Nature of Time in Concurrent Systems)

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…

問題3-40 (3.4.1 The Nature of Time in Concurrent Systems)

この場合,x の値としてはどのような可能性があるのか. (define x 10) (parallel-execute (lambda () (set! x (* x x))) (lambda () (set! x (* x x x)))) 乗算が atomic と仮定してのことだけど,x の読み出しと,計算と,代入の間それぞれに,インタリー…

問題3-39 (3.4.1 The Nature of Time in Concurrent Systems)

make-serializer で生成されるオブジェクトは,関数を引数に取って,直列化された関数を返すシリアライザ.直列化された関数は,その実行時にインタリーブされない.そのために, (define x 10) (define s (make-serializer)) (parallel-execute (s (lambda …

問題3-38(a)のみ (3.4.1 The Nature of Time in Concurrent Systems)

プログラムの同時実行に関するよくある銀行口座の問題. Peter や Paul,Mary がそれぞれ勝手に下記のプロセスを実行したときに,結果としての口座残高のパターンをリスティングする. (b)みたいに図を書く問題はメンドいから省略する! # Peter: (set! balan…

問題3-37 (3.3.5 Propagation of Constraints)

摂氏と華氏を相互変換する 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…

問題3-36 (3.3.5 Propagation of Constraints)

environment diagram はさすがにメンドい.

問題3-35 (3.3.5 Propagation of Constraints)

入力を二乗する回路素子(?) squarer をばっちし実装したろやないか! 問題 3-34 だと multiplier とかを組み合わせて Louis がヘンなことしてましたから,新しく,プリミティブな感じで作るみたいです. squarer はこんな感じになる. (define (squarer a b)…

問題3-34 (3.3.5 Propagation of Constraints)

(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 (3.3.5 Propagation of Constraints)

問題3-33 Constraint ベースのものがどんなものかということですが,以下の例が分かりやすい. averager は 2 つの入力端子 (in-A,in-B) に与えられた数値の平均が出力端子 out に出力されるというものです.なんとなく,そんなのすぐできるじゃんみたいな…

3.3.5 (Propagation of Constraints)

この節のタイトルにある "Constraints" というのは,基本的に世の中の関係式全てに相当するもののようです.例えば,摂氏と華氏の変換式(これは実際に SICP に,例題として取り上げられている)は,次のように表せます. (C: 摂氏, F: 華氏)じゃぁこれをプロ…

問題3-32 (3.3.4 A Simulator for Digital Circuits)

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…

問題3-31 (3.3.4 A Simulator for Digital Circuits)

関数 make-wire 中の関数 accept-action-procedure! では,関数のリスト action-procedures に引数で渡された関数 proc を追加する際に,なぜ proc を一度実行しているのかという問題.題材になった accept-action-procedure! の定義はこちら.最後の (proc)…