SICP

なんだってー

確かにSICPは入門コースの教科書だけど、最初にあれに触れて全部理解できた 人は選ばれた人って感じがする。Shiro な、なんだってー。 shiroさんとか arinoさんとかそういう人はさらっと読んでいるんだろうなと思っていた。

昨日のできごと

昨日紫色のパーカを来ていたら、会社で「ひげぽんがSICP色パーカを着ている!」とS君ほかにいぢめられました。 SICPを読むのはメリットが多いですが、こんなデメリットもあるんですね。

「計算機プログラムの構造と解釈(SICP)」を読み終えて

約半年をかけて計算機プログラムの構造と解釈(SICP)を読み終わりました。 (途中で、練習問題をスキップしたりしましたが・・・) 半年もかけたのでちょっとだけ振り返って見ます。 SICPを読む過程で得たもの まずはSICPを読む過程で得たものからざっと列挙…

関数型言語の勉強にSICPを読もう - (84) 5章 - レジスタ計算機での計算(339-366ページ)

5.5 翻訳系を一気に読んだ。例のごとく練習問題は解いていない。 Scheme on Scheme の超循環インタプリタから始まり、Schemeレジスタ計算機に行き、最後にコンパイラにやっと到達。 このように過程を見せられると、それぞれの本質とか利点が浮き彫りになって…

関数型言語の勉強にSICPを読もう - (83) 5章 - レジスタ計算機での計算(328-338ページ)

5.4積極評価器 レジスタと演算 5.4.1積極制御評価器の中核 単純式の評価 手続き作用の評価 手続き作用 5.4.2並びの評価と末尾再帰 末尾再帰 5.4.3条件式、代入および定義 代入と定義 5.4.4評価の実行 評価器の性能監視 急激に難しくなった。 5.1.1で学んだ S…

関数型言語の勉強にSICPを読もう - (82) 5章 - レジスタ計算機での計算(324-327ページ)

「ストップアンドコピーごみ集めの実装」を読んだ。 欠点は The costs of the stop-and-copy algorithm are twofold: First, the algorithm requires that all live objects be copied every time garbage collection is invoked. If an application program…

関数型言語の勉強にSICPを読もう - (81) 5章 - レジスタ計算機での計算(320-323ページ)

記憶の割当てとごみ集め ベクタとしてのメモリー 基本リスト演算の実装 スタックの実装 無限メモリーの幻想の維持 あたりを読みました。 GCの話に突入。 今までSICPではメモリアドレスなんて一切気にしていなかったのに突然あらわれます。 僕は馴染み深いの…

関数型言語の勉強にSICPを読もう - (80) 5章 - レジスタ計算機での計算(295-319ページ)

しばらくサボっていたので反省して一気に読み進める。 ちょっと難しいところにさしかかったので、まとめて読んだ方が忘れなくて良い。 レジスタ計算機は、仮想的な話なのだけどコンピュータの奥底を眺めているようで不思議な気持ち。 5.1.2 レジスタ計算機の…

関数型言語の勉強にSICPを読もう - (79) 5章 - レジスタ計算機での計算(293-294ページ)

5章を読みはじめました。 やっぱりこれは大学生の時に読めば、もっと良かったと思う。 Java->C++->C->Asmと進んで経験的に学んできたことが、普通に書いてあるしね。 レジスタ計算機萌え。 「SICPを読もう」の目次はこちら

関数型言語の勉強にSICPを読もう - (78) 4章 - 超言語的抽象(274-292ページ)

「ユニフェイケーション」など4章の最後まで読んだ。 問題は解いていない(ぉ。 「SICPを読もう」の目次はこちら

関数型言語の勉強にSICPを読もう - (77) 4章 - 超言語的抽象(271-273ページ)

「質問システムはどう働くか」の「パターンマッチング」の部分を読みました。 書いてあることは難しくないんだけど記述が難しくて油断すると逃避してしまう。 ※「SICPを読もう」の目次はこちら

関数型言語の勉強にSICPを読もう - (76) 4章 - 超言語的抽象(268-270ページ)

「規則」「プログラムとしての論理」を読みました。 問題はスキップ。

関数型言語の勉強にSICPを読もう - (75) 4章 - 超言語的抽象(266-267ページ)

合成質問 and, or, lisp-value の話。 このあたりは死ぬほどSQLを書かされてきた自分としては親しみやすい題材です。 問題4.56 a. Ben Bididdleが監督している人全ての名前と住所 (and (supervisor ?x (Bitdiddle Ben)) (address ?x . ?y)) b.給料がBen bitd…

関数型言語の勉強にSICPを読もう - (74) 4章 - 超言語的抽象(261-265ページ)

論理型プログラミング amb で一方向性計算(明確に定義した入力と出力を持つ計算)以外のプログラミング言語の存在を知りました。 個人的には結構な衝撃を受けたのですが、amb 以外のパターンを学べるようです。 計算の方向と順序が規定されていないってのが、…

関数型言語の勉強にSICPを読もう - (73) 4章 - 超言語的抽象(248ページ)

1時間ほどまとまった時間をとってSICPの amb あたりを読んだが、amb が有用な例や例題などがならび、その後に amb 評価器の実装へと移る流れ。 評価器がないと実際に動かせない →イメージがわかない。理解が進まない →amb評価器が必要 →でも概念が分かってい…

関数型言語の勉強にSICPを読もう - (72) 4章 - 超言語的抽象(245-248ページ)

非決定計算の話。まだきちんと理解できていない (list (amb 1 2 3) (amb 'a' 'b' 'c'))ambはあいまいに値を返すらしいんだけれども裏側で何が起きているか分からない。 脚注を読んだら分かった 値を処理するプログラムから見ると amb はひとつの値を返す プ…

関数型言語の勉強にSICPを読もう - (71) 4章 - 超言語的抽象(238-244ページ)

遅延評価周りの話を読んだ。 あまり頭に入らなかった。 たまにはこんな日もある。ということで次にすすみます。※「SICPを読もう」の目次はこちら 計算機プログラムの構造と解釈posted with amazlet on 06.05.31ジェラルド・ジェイ サスマン ジュリー サスマ…

関数型言語の勉強にSICPを読もう - (70) 4章 - 超言語的抽象(228-237ページ)

「ブログラムとしてのデータ」 「内部定義」 「構文解析を実行から分離する」 などを読む。 構文解析を実行から分離は、C++でインタプリタを書くときに苦労して自学したのでばっちりな筈。 特記事項なし。 ※「SICPを読もう」の目次はこちら 計算機プログラム…

関数型言語の勉強にSICPを読もう - (69) 4章 - 超言語的抽象228ページ) C++でSchemeインタプリタを作ろう18

バグ修正。 (define a 3) (define a 4)とした場合に a の値がおかしくなってしまう件を調査。 Gaucheで試したところ普通に上書きされたので、たぶん上書きで良いと思ったが、Schemeの仕様上どういう扱いだったか?を調べるためにR5RS(PDF)を読んでみた。 全部…

関数型言語の勉強にSICPを読もう - (68) 4章 - 超言語的抽象(222-228ページ) C++でSchemeインタプリタを作ろう17

4.1.3「評価器のデータ構造」、4.1.4「評価器をプログラムとして走らせる」あたりは自力でC++で書いたのでクリアしているので飛ばす。 今日は現在サポートしている syntax のテストコードを書きました。 書いている中で not, eq などの primitive procedure…

関数型言語の勉強にSICPを読もう - (67) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう16

パフォーマンスが極端に遅い件は、意図せず動的束縛っぽくなっていたのが原因だった。 Environmentのコピーを渡すのが正解なところでリファレンスを渡していたので、ループでFrameががんがん追加されていってひどいことになっていたのが原因。 これがきっか…

関数型言語の勉強にSICPを読もう - (66) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう15

いろいろな構文が動いたので悪ノリしてパフォーマンスを測定してみたら恐ろしい罠が! 計測対象 (begin (define count (lambda (x) (if (= 5000 x) x (begin (count (+ x 1)))))) (display (count 0)))条件分岐・変数の参照・再帰・値の比較などなどの要素を…

関数型言語の勉強にSICPを読もう - (66) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう15

問題4.6 letのサポートを入れようという話。 letはlambdaを使って等価変換ができる。 例えば (let ((a "hello") (b "good bye")) (display a) (display b))は ((lambda (a b) (display a) (display b)) "hello" "goodbye")となる。 なのでTranslatorの時点で…

関数型言語の勉強にSICPを読もう - (65) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう14

問題4.5 (display (cond (1 => plus5))))これを評価すると 6 が表示されます。 この形式の cond をサポートせよという問題。 昨日、この構文が美しくないなあとぼやいたら shiro さんからコメントを頂きました。 (cond (x => a)) はですね。xの評価結果が#f…

関数型言語の勉強にSICPを読もう - (64) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう13

問題4.5の前に condをifに展開する部分は書いてあったのだけど、translateをしてなかったので急いでコードを書く。 translateCondで、こんなCondを new してやります。 Cond::Cond(Clauses* clauses, Objects* elseActions)で、うまく動いています。 (begin …

関数型言語の勉強にSICPを読もう - (63) 4章 - 超言語的抽象(222ページ) C++でSchemeインタプリタを作ろう12

やっとSICPのページが進みました。 問題4.4 特殊形式 and, orをインタプリタに追加せよという問題。 皆さんもご存知の通り、and, orは「ショートサーキット演算子(ショートカット演算子)」なので引数の全てが評価されるとは限りません。 そのあたりがポイ…

関数型言語の勉強にSICPを読もう - (62) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう11

引き続き Primitive Procedureの実装。今日は cons/car/cdr 。 純Lispには欠かせない要素です。 Pairというクラスを用意してあげて、 consのapply時に Pair を返す。 car/cdr は Pair を受け取り、それぞれ first/secondを返す。 という実装です。 例のごと…

関数型言語の勉強にSICPを読もう - (61) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう10

Primitive Procedureの実装をした。 例えば + という手続きがあるがこれはSchemeインタプリタが primitive に持つ手続きである。 Schemeのオブジェクト define/lambda/Variableなどを組み合わせだけでは作れないものである。 このような Primitive Procedure…

関数型言語の勉強にSICPを読もう - (60) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう9

前回の日記(id:higepon:20060719:1153323855)で書いた悩みですが shiro さんから以下のようなコメントをいただきました。いつもありがとうございます。 (define func B)の時点でBを評価しないとまずいです。R5RS 5.2.1節。 その時点で(lambda (a) ”test”) は…

関数型言語の勉強にSICPを読もう - (59) 4章 - 超言語的抽象(220ページ) C++でSchemeインタプリタを作ろう8

実装というか設計に迷いが。 (begin (define func (lambda (a) "test")) (func 3) )まず前提として、上の式を評価すると、"test" が返ることが期待されます。(Gaucheで試しました) SICPによれば(func 3)は以下の順に評価されます。 1. (予約語でない語句 …