理系学生日記

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

忍者TOOLS

SICP

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