Scheme
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…
以下のような関数適用のコードが動くようになりました。 > ((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のコードを処理系へどうつなぐかで壁にあたりました。 色々と調べたところ、インタプリタの動作は主に以下のステップを踏むよう…
途中まで作っていた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),…
いよいよ4章。 metacircular (超循環評価器) というものがいきなり登場しました。 被実装言語と実装言語が同じインタプリタのことをそう呼ぶらしく、冒頭からSchemeで実装したSchemeインタプリタが例として登場します。 ただ id:higepon さんが指摘されてい…
ところどころ飛ばしましたが、3章をひと通り読み終えました。この章で学んだことを上手くまとめるのは相当難しいですが、自分なりに整理したいと思います。 1章〜2章では手続きやデータによる抽象化について学びましたが、3章はそれらのモジュールをいかに組…
「§3.5.5 関数プログラムの部品度とオブジェクトの部品化」から。 §3.1で乱数を生成する手続きrandが出たが、それを応用して乱数の無限ストリームrandom-numberを定義する。random-initは定数なので何度やっても結果は同じになる。 ;; §3.1から転用 (define …
(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…
前半はある一定の値に収束していく無限ストリーム(数列)の収束を加速させる手法や、対のストリームについて。数学的なトピックが中心だと思うので、バッサリ飛ばします。早く4章に行きたいのも大きいけど… 後半の「信号としてのストリーム」の節はストリーム…
問題 3.59 べき級数、聞き覚えはあるから習ったことはあるんだろうけど、さっぱり思い出せない。こんな時はWikipedia。先生いつもありがとう。 冪級数 - Wikipedia (a) べき級数の項のストリームを引数に取り、それを積分した結果の項のストリームを返すinte…
“To inifity and beyond” トイ・ストーリーでのBuzz Lightyearの決め台詞です。 無限ストリーム(infinite streams)を極めると、さらにその先の世界が見えるかもしれない :) トイ・ストーリー MovieNEX [ブルーレイ+DVD+デジタルコピー(クラウド対応)+MovieNE…
いよいよストリームへ。 生まれて初めてその概念に触れたけど驚きの連続。特にdelayとforceによる実装が何とも直截的で素敵すぎる。やはりSICPはもっと早くに読むべきだった… ストリームを使うには (2015/08/20追記) 実行環境がRacketの場合、ストリームを使…
前節までに局所状態を持つオブジェクトを取り入れたけれど、局所状態とは即ち「時」を意識することになる。ここでは異なるタイミングで複数のプロセスから共有オブジェクトの状態を参照したり変更したりする場合に、どういった課題があるかといったことを検…
「§3.3.5 制約の拡散」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.5.scm 原本のタイトルは "Propagation of Constraints" なので「拡散」というよりかは「伝播」の方が適切かもしれない。 前…
「§3.3.4 ディジタル回路のシミュレータ」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.4.scm 回路の実装 論理回路の実装 テキストのこの章のコードを写経しないとシミュレーションを走らせるこ…
「§3.3.3 表の表現」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.3.scm 問題 3.24 解答は省略。 make-table にテスト関数を引数で渡せるようにし、 assoc-tree 内の equal? の代わりに そのテ…
「§3.3.2 キューの表現」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.2.scm ところで、最近の1カ月半は通勤時間もコードを書くほど忙しかったので、 Schemeを忘れてないか心配だったけど、意…
「§3.3 可変データのモデル化」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch3/ch3.3.1.scm 可変リスト構造 構成子、選択子とは別にオブジェクトを修正する変更子(mutator)を導入する。 例えばpairの場…
前回からずいぶん間が空いてしまった。 今回は「§3.2 評価の環境モデル」から。 初出じゃないけど用語がいろいろと出てくる。 環境(environments) フレーム(frames) 束縛(bindings) 大域(global) 外側の環境(enclosing environment) 変数の値(value of a var…
いよいよ3章。キーワードは、 モジュール化 オブジェクトによるプログラムの組織化 代入(assignment)と局所状態(local state) 環境モデル(enviroment model) ストリーム(streams)と遅延評価(delayed evaluation) あたりのようです。 代入と局所状態 これまで…
最後は端折ってしまいましたが、長い長い2章がようやく終わったので、 自分なりにまとめたいと思います。(1章でもまとめておけばよかったorz) *** ところで、この章で学ぶべきものは何でしょうか? それは「§2.1.3 データとは何か」の以下の一節を理解す…
すみません、さくっとパスします。おそらくこの章の本質ではないと思うので。 必要ならまた戻ってくると思います。。 ※「SICP読書ノート」の目次はこちら
「§2.5.2 異なる型のデータ統合」から。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch2/ch2.5.2.scm 異なる型のデータ統合 前回のエントリで汎用演算システムを構築したが、 異なる型同士の計算はできなかった…
「§2.5 汎用演算システム」から。 この章は2章でこれまで学んだことの応用問題といった感じ。データ主導を使って汎用演算システムを構築して行きます。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch2/ch2.5.1.…
「§2.4.3 データ主導プログラミングと加法性」の続き。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch2/ch2.4.3.3.scm メッセージパッシング §2.1.3 データとは何か で見た、 クロージャの特性を利用したアクセ…
「§2.4.3 データ主導プログラミングと加法性」の続きから。 全体のソースコードはGitHubに置いています。 https://github.com/uents/sicp/blob/master/ch2/ch2.4.3.2.scm 問題 2.74 アキナイ有限会社 (Insatiable Enterprises, Inc.) のデータベースを統合す…