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

@uents blog

Code wins arguments.

Scheme

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

SICPようやく読み終わりました。 2014年5月から読み始めたので、 足かけ丸2年。愛娘も1才から3才に成長。 練習問題やブログの記事を上げていたGitHubのコミットグラフを見ると、 サボっていた期間も結構あり、実働は1年ちょっとくらいかな。 他のSICPブログ…

SICP 読書ノート#79 - 5.5 翻訳系(4) (pp.362-366)

いよいよ最後のセクション。練習問題はやってないです。 5.5.7 翻訳したコードと評価器のインターフェース (compile)でコンパイルしたコードを積極制御評価器で動作させる。 いつものように、まずはRacketで動かせるようにした。 https://github.com/uents/s…

SICP 読書ノート#78 - 5.5 翻訳系(3) (pp.360-362)

今回は「5.5.6 文面アドレス」から。 5.5.6 文面アドレス 「文面」とはlexicalの直訳のよう。 これまでの評価機は変数の値を探す際に、実行時にenvフレームを 都度探索していたので、それなりに計算コストがかかっていたはず。 Schemeはレキシカルスコープな…

SICP 読書ノート#77 - 5.5 翻訳系(2) (pp.343-360)

前回に続き翻訳系のセクションを読み進めて行きました。 5.5.2 式の翻訳 defineやset!などの特殊形式のコンパイルの話。ざっと読んだ。 5.5.3 組み合わせの翻訳 主に手続き適用のコンパイルの話。簡単にまとめると、 compile-applicationでは、演算子と非演…

SICP 読書ノート#76 - 5.5 翻訳系(1) (pp.339-343)

いよいよ最後のセクション。 これまでレジスタマシン、積極制御評価機(解釈系=インタプリタ)と来て、 ここでは翻訳系(=コンパイラ)について学びます。 翻訳系の概観 ひとことで言うと「環境をenvに保持し、引数リストをarglに集積し、 適用する手続きをproc…

SICP 読書ノート#75 - 5.4 積極制御評価機 (pp.327-338)

積極制御評価機 (explicit-control evaluator) とは、 レジスタマシンシミュレータ上で動作する マシン語で実装されたScheme処理系のことのよう。 Schemeプログラム→積極制御評価機→レジスタマシン→Scheme処理系 と、さらに抽象化が増してきた。 実装として…

SICP 読書ノート#74 - 5.3 記憶の割当てとごみ集め (pp.319-327)

「§5.3 記憶の割当てとごみ集め」から。以下を順に読みました。 ベクターとしてのメモリ Lispデータの表現 基本リスト演算の実装 スタックの実装 無限メモリーの幻想の維持 ストップアンドコピーごみ集めの実装 メモリ管理とガベージコレクションの話。無限…

SICP 読書ノート#73 - 5.2 レジスタ計算機シミュレータ(2) (pp.318-319)

「§5.2.4 計算機の性能の監視」から。 レジスタ計算機シミュレータにinspectorやdebuggerを実装していくみたい。面白そう。 まずはテキスト通り、スタックの状況をチェックするコマンドを実装する。 ;;;; stack (define (make-stack) - (let ((s '())) + (le…

SICP 読書ノート#72 - 5.2 レジスタ計算機シミュレータ(1) (pp.306-317)

テキストを読んでも文字ばかりで全然頭に入ってこないので、まずはシミュレータをがっと実装した。 https://github.com/uents/sicp/blob/master/ch5-register-simulator いつものようにRacketで動かせるように修正してます。 他にもデバッグのために実行手続…

SICP 読書ノート#71 - 5.1 レジスタ計算機の設計 (pp.293-306)

色々と忙しくてサボってましたが、約半年ぶりに再開します。 Schemeを忘れていないかと心配でしたが、 4章までの苦労が染み付いてたせいか案外そうでもなかった。よかった! 5章を学ぶ意味 5章の冒頭にまとめてあります。 4章ではLispの言語解釈について学ぶ…

SICP 読書ノート#70 - 第4章 まとめ

途切れ途切れながらも半年かかって4章が終わりました。終盤はゴニョゴニョしましたが… あらためてSICPがどのような本か、高橋征義さんのブログでの以下の言及が素晴らしいです。 少なくとも私にとってSICPとは、「プログラム」そして「プログラミング」とい…

SICP 読書ノート#69 - 4.4.4 質問システムの実装(3) (pp.278-292)

§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) オリジナルの実装…

SICP 読書ノート#68 - 4.4.4 質問システムの実装(2) (pp.278-292)

重い腰をあげてquery systemの評価の流れをかんたんに追いました。 それとtraceとDrRacketによるデバッグ実行が便利だった。後でブログにまとめよう。 REPL query-syntax-processでクエリをパースする パースしたクエリがassert!の場合は、そのassertionまた…

SICP 読書ノート#67 - 4.4.4 質問システムの実装(1) (pp.278)

§4.4.4に入り質問システムの実装を追っていたのですが、詰まってしまいました。 stream-append-delayedやinterleave-delayedのストリーム操作がよくわからない 「§3.5.3 ストリームパラダイムの開発」の前半部で登場していたようだが、思いっきり読み飛ばし…

SICP 読書ノート#66 - 4.4.2-4.4.3 質問システムはどう働くか〜論理プログラミングは数学的論理か (pp.270-278)

一気に流し読みしましたが、説明ばかりでいまいち頭に入ってこない。 気になる記述を適当にメモ書き。 質問システム pattern matchingとunificationを中心に構成される パターンマッチング pattern matcherはあるデータが指定されたパターン(例:(job ?x ?y)…

SICP 読書ノート#65 - 4.4.1 プログラムとしての論理 (pp.269-270)

§4.4.1の続き「プログラムとしての論理」から。 プログラムとしての論理 規則は一種の論理的包含(logical implication)と見ることが出来る: 値のパターン変数への代入が, 本体を満足すれば, それは結論を満足する. 従って質問言語を, 規則に基づいて論理的推…

SICP 読書ノート#64 - 4.4 論理型プログラミング (pp.261-269)

いよいよ4章の最後のセクション「論理型プログラミング」に入りました。 ここでのキーワードは「一方向性計算から多方向性計算へ」と「ユニフィケーション」のようです。 また、本文のappendの定義について (define (append x y) (if (null? x) y (cons (car…

SICP 読書ノート#63 - 4.3.3 amb評価器の実装 (pp.254-261)

この節ではamb評価器の内部に迫ります。 個人的には自前でambオペレータを作った際に、継続やバックトラックと散々戯れたので、ここはさらっと読み流します。 amb評価器で重要そうなのは、やはりamb式の評価ですよね。 (define (analyze-amb exp) (let ((cpr…

SICP 読書ノート#62 - 4.3.2 自然言語の構文解析 (pp.250-253)

§4.3.2 の続き「自然言語の構文解析」から。 「そもそもこれ自前のambオペレータで動く?」という疑問はありますが、コードを書いてみます。 ambの引数に式を与える際、自前のambオペレータは単なる手続きなのでdelayさせます。 (define nouns '(noun studen…

SICP 読書ノート#61 - 4.3.2 非決定性のプログラムの例 (pp.248-250)

前回に引き続きambオペレータを使って色々な論理パズルを解いていきます。 問題 4.39 解そのものには影響しない 解が出るまでの時間(計算回数には)影響する →問題 4.37 のようにバックトラックの回数をカウントすればよい (define *backtrack-count* 0) (d…

SICP 読書ノート#60 - 4.3.1 ambと探索 (pp.246-248)

前回のエントリで実装したambオペレータを使って練習問題を解いていきます。 問題 4.35 二つの境界値の間の整数を返す手続き an-integer-between を実装する。いくつか方法はあると思うが、§2で登場した enumerate-interval を流用してみた。 (define (enume…

SICP 読書ノート#59 - 4.3 非決定性計算 - call/ccによるambオペレータの実装 (pp.245)

前回で継続やcall/ccの振る舞いはつかめたので、今回はambオペレータをcall/ccで実装します。 ソースコードは以下に置いています。 https://github.com/uents/sicp/blob/master/ch4.3-amb-operator amb評価器を動作させる まずは動かしてみないとambが何者か…

SICP 読書ノート#58 - 4.3 非決定性計算 - 継続とは何か (pp.245)

「§4.3 Schemeの変形---非決定性計算」に入りました。 最初はテキストの内容の全貌が掴めず、サンプルコードをロードしてambを叩きまくっていたのですが、だんだん何がわからないかが頭の中で整理できてきました。 →ambの振る舞いがどういうことなのかわから…

SICP 読書ノート#57 - 4.2.3 遅延評価リストとしてのストリーム (pp.243-245)

遅延評価器では手続きの引数が全て遅延されるので、consセルをcompound procedureとして定義すれば、リストとストリームは同義となる。 consの手続きは§2でも出たあれだ。 (define (cons first rest) (lambda (pair) (pair first rest))) (define (car pair)…

SICP 読書ノート#56 - 4.2.2 遅延評価の解釈系 (pp.238-243)

前節の正規順序による評価を実現するために、Scheme評価器に遅延評価を組み込みます。 ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.2-lazy-evaluator thunkとは? thunk(サンク)とは遅延評価オブジェクトそのもの…

SICP 読書ノート#55 - 4.2.1 正規順序と作用的順序 (pp.237-238)

「§4.2 Schemeの変形---遅延評価」から。 §4.1の超循環評価器に遅延評価を組み込んでいきます。 正規順序と作用的順序 よくごっちゃになるので整理。 作用的順序 (applicative order) 手続きを作用させるときに、引数をすべて評価する この手続きは引数に対…

SICP 読書ノート#54 - 4.1.7 構文解析から実行を分離する (pp.234-237)

久しぶりの更新です。 恐ろしいことにSICPを読み始めて1年が経ってしまいました。ここの進みの遅さ。激しく自省。。 特にサボっていたわけではなく、§4.3の非決定性計算を読んでいるうちに継続と戯れていたらこっちの更新が滞ってしまってました。継続の概…

SICP 読書ノート#53 - 4.1.6 内部定義 (pp.230-234)

「§4.1.6 内部定義」を読みました。手続きの内部定義とその評価について考察します。 問題 4.19 変数を評価すると行っても色んなポリシーがあるという話。 自前の処理系 自前の処理系での実行結果は、(define b (+ a x))の評価の時点でローカル環境にaがない…

SICP 読書ノート#52 - 4.1.5 プログラムとしてのデータ (pp.228-230)

前回悩んでいた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,…

SICP 読書ノート#51 - RubyでSchemeインタプリタをつくろう(10) - 導出された式 (pp.213-228)

derived expression(導出された式)や§4.1.1〜4.1.4の練習問題を解いていきます。 問題 4.1 関数適用の際の引数の評価は左から?右から?という問題。 自前の処理では以下のようにoperands.mapとしているので左から。右からとするならイテレーションの順序…

SICP 読書ノート#50 - RubyでSchemeインタプリタをつくろう(9) - 基本手続き/四則演算/リスト演算 (pp.213-228)

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

SICP 読書ノート#49 - RubyでSchemeインタプリタをつくろう(8) - 環境に対する操作 (pp.213-228)

環境および束縛、代入まわりを実装しました。やってみると意外と簡単だった。 > (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 読書ノート#48 - RubyでSchemeインタプリタをつくろう(7) - 関数の評価と適用 (pp.213-228)

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

SICP 読書ノート#47 - RubyでSchemeインタプリタをつくろう(6) - 実行オブジェクトへのマッピング (pp.213-228)

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

SICP 読書ノート#46 - RubyでSchemeインタプリタをつくろう(5) - REPL/字句解析/構文解析 (pp.213-228)

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

SICP 読書ノート#45 - RubyでSchemeインタプリタをつくろう(4) - 最初からやり直します

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

SICP 読書ノート#44 - RubyでSchemeインタプリタをつくろう(3)

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

SICP 読書ノート#43 - RubyでSchemeインタプリタをつくろう(2)

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

SICP 読書ノート#42 - RubyでSchemeインタプリタをつくろう(1)

いよいよ4章。 metacircular (超循環評価器) というものがいきなり登場しました。 被実装言語と実装言語が同じインタプリタのことをそう呼ぶらしく、冒頭からSchemeで実装したSchemeインタプリタが例として登場します。 ただ id:higepon さんが指摘されてい…

SICP 読書ノート#41 - 第3章 まとめ

ところどころ飛ばしましたが、3章をひと通り読み終えました。この章で学んだことを上手くまとめるのは相当難しいですが、自分なりに整理したいと思います。 1章〜2章では手続きやデータによる抽象化について学びましたが、3章はそれらのモジュールをいかに組…

SICP 読書ノート#40 - 3.5.5 関数プログラムの部品度とオブジェクトの部品化 (pp.209-210)

「§3.5.5 関数プログラムの部品度とオブジェクトの部品化」から。 §3.1で乱数を生成する手続きrandが出たが、それを応用して乱数の無限ストリームrandom-numberを定義する。random-initは定数なので何度やっても結果は同じになる。 ;; §3.1から転用 (define …

SICP 読書ノート#39 - 3.5.4 ストリームと遅延評価 (pp.205-209)

(2015/09/15追記) SICPテキストのストリームでは問題3.77のテスト実行で返ってこないため、ここではracket/stream版を使っています。ソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.5.4.scm https://github.com/u…

SICP 読書ノート#38 - 3.5.3 ストリームパラダイムの開発 (pp.198-205)

前半はある一定の値に収束していく無限ストリーム(数列)の収束を加速させる手法や、対のストリームについて。数学的なトピックが中心だと思うので、バッサリ飛ばします。早く4章に行きたいのも大きいけど… 後半の「信号としてのストリーム」の節はストリーム…

SICP 読書ノート#37 - 3.5.2 無限ストリーム(2) (pp.196-197)

問題 3.59 べき級数、聞き覚えはあるから習ったことはあるんだろうけど、さっぱり思い出せない。こんな時はWikipedia。先生いつもありがとう。 冪級数 - Wikipedia (a) べき級数の項のストリームを引数に取り、それを積分した結果の項のストリームを返すinte…

SICP 読書ノート#36 - 3.5.2 無限ストリーム(1) (pp.193-196)

“To inifity and beyond” トイ・ストーリーでのBuzz Lightyearの決め台詞です。 無限ストリーム(infinite streams)を極めると、さらにその先の世界が見えるかもしれない :) トイ・ストーリー MovieNEX [ブルーレイ+DVD+デジタルコピー(クラウド対応)+MovieNE…

SICP 読書ノート#35 - 3.5.1 ストリームは遅延リスト (pp.187-192)

いよいよストリームへ。 生まれて初めてその概念に触れたけど驚きの連続。特にdelayとforceによる実装が何とも直截的で素敵すぎる。やはりSICPはもっと早くに読むべきだった… ストリームを使うには (2015/08/20追記) 実行環境がRacketの場合、ストリームを使…

SICP 読書ノート#34 - 3.4 並列性:時が本質的 (pp.175-187)

前節までに局所状態を持つオブジェクトを取り入れたけれど、局所状態とは即ち「時」を意識することになる。ここでは異なるタイミングで複数のプロセスから共有オブジェクトの状態を参照したり変更したりする場合に、どういった課題があるかといったことを検…

SICP 読書ノート#33 - 3.3.5 制約の拡散 (pp.168-175)

「§3.3.5 制約の拡散」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.5.scm 原本のタイトルは "Propagation of Constraints" なので「拡散」というよりかは「伝播」の方が適切かもしれない。 前…

SICP 読書ノート#32 - 3.3.4 ディジタル回路のシミュレータ (pp.160-168)

「§3.3.4 ディジタル回路のシミュレータ」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.4.scm 回路の実装 論理回路の実装 テキストのこの章のコードを写経しないとシミュレーションを走らせるこ…

SICP 読書ノート#31 - 3.3.3 表の表現 (pp.156-160)

「§3.3.3 表の表現」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.3.scm 問題 3.24 解答は省略。 make-table にテスト関数を引数で渡せるようにし、 assoc-tree 内の equal? の代わりに そのテ…