途切れ途切れながらも半年かかって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としているので左から。右からとするならイテレーションの順序…

primitive procedure (基本手続き)を実装します。 例えば四則演算のように特殊形式では表現しにくいような基本的な演算を行います。 ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4-ruby-evaluator 四則演算 実装とし…

環境および束縛、代入まわりを実装しました。やってみると意外と簡単だった。 > (define a 1) => nil > a => 1 > (define y 1) => nil > (set! y 2) => nil > y => 2 > (set! z 3) "set_variable_value!: unbound variable; z" > (define foo (lambda (x) "f…

SICPでやっているRubyによるSchemeインタプリタでどうしてもArray#to_hが使いたくなったが、OSX Yosemiteに標準で付属しているRuby 2.0.0にはなかったので、rbenvを使ってみたときのメモ。 環境 Mac OSX Yosemite 10.10.2 Homebrew 0.9.5 rbenvのインストー…

以下のような関数適用のコードが動くようになりました。 > ((lambda (x) "foo") 1) => "foo" ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.1-ruby-evaluator 前回までのリファクタリング その前に前回の内容をいく…

前回作った構文木について、そのまま評価器に放り込んで評価させても良いのですが、SICPのテキストのeval()のようにだらだらと長くなるのがいまいちかなと思います。 問題4.3でも取り上げられているように「データ主導」で実装する方がスマートかと思います…

最初はSICPのテキストを見ながら式評価、関数適用、環境まわり（p226付近）までRubyでひと通り実装しましたが、入力されたSchemeのコードを処理系へどうつなぐかで壁にあたりました。 色々と調べたところ、インタプリタの動作は主に以下のステップを踏むよう…

前の兵庫県知事であり昨年末に不慮の事故でお亡くなりになった 貝原俊民さんを偲ぶ講演会で、iPS細胞で著名な山中伸弥先生のお話をお聞きしました。 (※神戸新聞のウェブサイトより引用) 帰った後でググりましたたが講演の内容は以下のリンク先とおおよそ同じ…

途中まで作っていたRubyによるScheme処理系ですが行き詰まりました。。。 理由はこんな感じです。 rubyによるschemeインタプリタ、ruby上でcons cellを実装してやってたけどlist iterationあたりの実装で限界がきた。rubyのデータ構造に合わせて実装した方が…

久しぶりの更新。行ったり来たり試行錯誤だけど毎日少しづつ進めてます… 式の表現 引き続きSchemeインタプリタの実装。今回は式の評価処理について。 self-evaluating items (自己評価式) 数か文字列の時にtrueを返す。number?()とstring?()は後で実装。 def…

引き続きRubyでSchemeインタプリタを書き起こして行きます。 手続きの引数 引数expsにある式リストからひとつずつ式を取り出し評価したリストを返す。 def list_of_values(exps, env) if no_operands?(exps) nil else cons(_eval(first_operand(exps), env),…