SICP
SICPようやく読み終わりました。 2014年5月から読み始めたので、 足かけ丸2年。愛娘も1才から3才に成長。 練習問題やブログの記事を上げていたGitHubのコミットグラフを見ると、 サボっていた期間も結構あり、実働は1年ちょっとくらいかな。 他のSICPブログ…
いよいよ最後のセクション。練習問題はやってないです。 5.5.7 翻訳したコードと評価器のインターフェース (compile)でコンパイルしたコードを積極制御評価器で動作させる。 いつものように、まずはRacketで動かせるようにした。 https://github.com/uents/s…
今回は「5.5.6 文面アドレス」から。 5.5.6 文面アドレス 「文面」とはlexicalの直訳のよう。 これまでの評価機は変数の値を探す際に、実行時にenvフレームを 都度探索していたので、それなりに計算コストがかかっていたはず。 Schemeはレキシカルスコープな…
前回に続き翻訳系のセクションを読み進めて行きました。 5.5.2 式の翻訳 defineやset!などの特殊形式のコンパイルの話。ざっと読んだ。 5.5.3 組み合わせの翻訳 主に手続き適用のコンパイルの話。簡単にまとめると、 compile-applicationでは、演算子と非演…
いよいよ最後のセクション。 これまでレジスタマシン、積極制御評価機(解釈系=インタプリタ)と来て、 ここでは翻訳系(=コンパイラ)について学びます。 翻訳系の概観 ひとことで言うと「環境をenvに保持し、引数リストをarglに集積し、 適用する手続きをproc…
積極制御評価機 (explicit-control evaluator) とは、 レジスタマシンシミュレータ上で動作する マシン語で実装されたScheme処理系のことのよう。 Schemeプログラム→積極制御評価機→レジスタマシン→Scheme処理系 と、さらに抽象化が増してきた。 実装として…
「§5.3 記憶の割当てとごみ集め」から。以下を順に読みました。 ベクターとしてのメモリ Lispデータの表現 基本リスト演算の実装 スタックの実装 無限メモリーの幻想の維持 ストップアンドコピーごみ集めの実装 メモリ管理とガベージコレクションの話。無限…
「§5.2.4 計算機の性能の監視」から。 レジスタ計算機シミュレータにinspectorやdebuggerを実装していくみたい。面白そう。 まずはテキスト通り、スタックの状況をチェックするコマンドを実装する。 ;;;; stack (define (make-stack) - (let ((s '())) + (le…
テキストを読んでも文字ばかりで全然頭に入ってこないので、まずはシミュレータをがっと実装した。 https://github.com/uents/sicp/blob/master/ch5-register-simulator いつものようにRacketで動かせるように修正してます。 他にもデバッグのために実行手続…
色々と忙しくてサボってましたが、約半年ぶりに再開します。 Schemeを忘れていないかと心配でしたが、 4章までの苦労が染み付いてたせいか案外そうでもなかった。よかった！ 5章を学ぶ意味 5章の冒頭にまとめてあります。 4章ではLispの言語解釈について学ぶ…
途切れ途切れながらも半年かかって4章が終わりました。終盤はゴニョゴニョしましたが… あらためてSICPがどのような本か、高橋征義さんのブログでの以下の言及が素晴らしいです。 少なくとも私にとってSICPとは、「プログラム」そして「プログラミング」とい…
§4.4.4の練習問題から。 問題 4.70 以下のadd-assertion!の実装の何が悪いかを説明せよ。 (define (add-assertion! assertion) (store-assertion-in-index assertion) (set! THE-ASSERTIONS (cons-stream assertion THE-ASSERTIONS)) 'ok) オリジナルの実装…
重い腰をあげてquery systemの評価の流れをかんたんに追いました。 それとtraceとDrRacketによるデバッグ実行が便利だった。後でブログにまとめよう。 REPL query-syntax-processでクエリをパースする パースしたクエリがassert!の場合は、そのassertionまた…
§4.4.4に入り質問システムの実装を追っていたのですが、詰まってしまいました。 stream-append-delayedやinterleave-delayedのストリーム操作がよくわからない 「§3.5.3 ストリームパラダイムの開発」の前半部で登場していたようだが、思いっきり読み飛ばし…
一気に流し読みしましたが、説明ばかりでいまいち頭に入ってこない。 気になる記述を適当にメモ書き。 質問システム pattern matchingとunificationを中心に構成される パターンマッチング pattern matcherはあるデータが指定されたパターン(例：(job ?x ?y)…
§4.4.1の続き「プログラムとしての論理」から。 プログラムとしての論理 規則は一種の論理的包含(logical implication)と見ることが出来る: 値のパターン変数への代入が, 本体を満足すれば, それは結論を満足する. 従って質問言語を, 規則に基づいて論理的推…
いよいよ4章の最後のセクション「論理型プログラミング」に入りました。 ここでのキーワードは「一方向性計算から多方向性計算へ」と「ユニフィケーション」のようです。 また、本文のappendの定義について (define (append x y) (if (null? x) y (cons (car…
この節ではamb評価器の内部に迫ります。 個人的には自前でambオペレータを作った際に、継続やバックトラックと散々戯れたので、ここはさらっと読み流します。 amb評価器で重要そうなのは、やはりamb式の評価ですよね。 (define (analyze-amb exp) (let ((cpr…
§4.3.2 の続き「自然言語の構文解析」から。 「そもそもこれ自前のambオペレータで動く？」という疑問はありますが、コードを書いてみます。 ambの引数に式を与える際、自前のambオペレータは単なる手続きなのでdelayさせます。 (define nouns '(noun studen…
前回に引き続きambオペレータを使って色々な論理パズルを解いていきます。 問題 4.39 解そのものには影響しない 解が出るまでの時間（計算回数には）影響する →問題 4.37 のようにバックトラックの回数をカウントすればよい (define *backtrack-count* 0) (d…
前回のエントリで実装したambオペレータを使って練習問題を解いていきます。 問題 4.35 二つの境界値の間の整数を返す手続き an-integer-between を実装する。いくつか方法はあると思うが、§2で登場した enumerate-interval を流用してみた。 (define (enume…
前回で継続やcall/ccの振る舞いはつかめたので、今回はambオペレータをcall/ccで実装します。 ソースコードは以下に置いています。 https://github.com/uents/sicp/blob/master/ch4.3-amb-operator amb評価器を動作させる まずは動かしてみないとambが何者か…
「§4.3 Schemeの変形---非決定性計算」に入りました。 最初はテキストの内容の全貌が掴めず、サンプルコードをロードしてambを叩きまくっていたのですが、だんだん何がわからないかが頭の中で整理できてきました。 →ambの振る舞いがどういうことなのかわから…
遅延評価器では手続きの引数が全て遅延されるので、consセルをcompound procedureとして定義すれば、リストとストリームは同義となる。 consの手続きは§2でも出たあれだ。 (define (cons first rest) (lambda (pair) (pair first rest))) (define (car pair)…
前節の正規順序による評価を実現するために、Scheme評価器に遅延評価を組み込みます。 ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.2-lazy-evaluator thunkとは？ thunk(サンク)とは遅延評価オブジェクトそのもの…
「§4.2 Schemeの変形---遅延評価」から。 §4.1の超循環評価器に遅延評価を組み込んでいきます。 正規順序と作用的順序 よくごっちゃになるので整理。 作用的順序 (applicative order) 手続きを作用させるときに、引数をすべて評価する この手続きは引数に対…
久しぶりの更新です。 恐ろしいことにSICPを読み始めて１年が経ってしまいました。ここの進みの遅さ。激しく自省。。 特にサボっていたわけではなく、§4.3の非決定性計算を読んでいるうちに継続と戯れていたらこっちの更新が滞ってしまってました。継続の概…
「§4.1.6 内部定義」を読みました。手続きの内部定義とその評価について考察します。 問題 4.19 変数を評価すると行っても色んなポリシーがあるという話。 自前の処理系 自前の処理系での実行結果は、(define b (+ a x))の評価の時点でローカル環境にaがない…
前回悩んでいたquoteのバグはparserが原因でした。 % git diff diff --git a/ch4-ruby-evaluator/parser.rb b/ch4-ruby-evaluator/parser.rb index f3a74f6..130c78d 100644 --- a/ch4-ruby-evaluator/parser.rb +++ b/ch4-ruby-evaluator/parser.rb @@ -14,…
derived expression（導出された式）や§4.1.1〜4.1.4の練習問題を解いていきます。 問題 4.1 関数適用の際の引数の評価は左から？右から？という問題。 自前の処理では以下のようにoperands.mapとしているので左から。右からとするならイテレーションの順序…
