「§4.3 Schemeの変形---非決定性計算」に入りました。 最初はテキストの内容の全貌が掴めず、サンプルコードをロードしてambを叩きまくっていたのですが、だんだん何がわからないかが頭の中で整理できてきました。 →ambの振る舞いがどういうことなのかわからない →非決定性計算が何なのかがわからない →継続が何なのかがわからない おそらく、継続に関する説明がないままにambを使った例題が続いた後に、ambの実装で唐突に継続が出てくるところがわかりにくい原因だと思います。さらに、Schemeでは継続を作り出すcall/cc (call-with-current-continuation) があるのに、この章では登場しません。 そこで、まずは「継続」とは何かから学びました。 継続とは何か 例えば、jQueryのajaxメソッドで、 $.ajax({ url: "ajax.html", })

遅延評価器では手続きの引数が全て遅延されるので、consセルをcompound procedureとして定義すれば、リストとストリームは同義となる。 consの手続きは§2でも出たあれだ。 (define (cons first rest) (lambda (pair) (pair first rest))) (define (car pair) (pair (lambda (f r) f))) (define (cdr pair) (pair (lambda (f r) r))) §3のストリームは遅延されるのはcdrだけだったのに対し、この遅延リストはcarもcdrも同様に遅延ができる。これを「遅延度が高い」と言うらしい。 問題 4.32 この遅延度の高さのおかげで未定義の対が定義できる。 ;;; L-Eval input: (define a-stream (cons x y)) ;

前節の正規順序による評価を実現するために、Scheme評価器に遅延評価を組み込みます。 ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.2-lazy-evaluator thunkとは？ thunk(サンク)とは遅延評価オブジェクトそのものです。 Racketでもdelayでthunkをつくることができる。(promiseという名前だが) racket@> (define x (delay (+ a b))) racket@> x #<promise:x> この時点でxはthunkそのものであり、(+ a b)はまだ評価されていない。 racket@> (define a 1) racket@> (define b 2) racket@> (force x) 3 この(force x)でthunkが持っ

「§4.2 Schemeの変形---遅延評価」から。 §4.1の超循環評価器に遅延評価を組み込んでいきます。 正規順序と作用的順序 よくごっちゃになるので整理。 作用的順序 (applicative order) 手続きを作用させるときに、引数をすべて評価する この手続きは引数に対してstrictともいう われわれが普段用いている処理系はコレ 正規順序 (normal order) 手続きを作用させるときに、実際に引数の値が必要になるため評価を遅らせる 言い換えれば、引数が評価される前に、手続きの本体に入る この手続は引数に対してnon-strictともいう 引数の評価を遅らせる手法として、遅延評価 (lazy evaluation) を用いる 問題 4.25 unlessは手続きで実装されているので… 作用的順序では、unlessの引数が先に評価されてしまい上手く動かない usual-v

久しぶりの更新です。 恐ろしいことにSICPを読み始めて１年が経ってしまいました。ここの進みの遅さ。激しく自省。。 特にサボっていたわけではなく、§4.3の非決定性計算を読んでいるうちに継続と戯れていたらこっちの更新が滞ってしまってました。継続の概念はようやくぼんやり理解できたので、元に戻って進めたいと思います。 SchemeによるScheme評価器 前回までRubyで実装していましたが、§4.2 遅延評価、§4.3 非決定性計算までそれでついて行くのは大変だなと思い、Schemeでいちから実装し直す。 環境の実装をRacket組み込みのHash Tableで書き直したりと、自分なりにいくつか修正。 https://github.com/uents/sicp/tree/master/ch4.1-scheme-evaluator 構文解析と実行の分離 構文解析と実行の分離はRubyでの実装で

「§4.1.6 内部定義」を読みました。手続きの内部定義とその評価について考察します。 問題 4.19 変数を評価すると行っても色んなポリシーがあるという話。 自前の処理系 自前の処理系での実行結果は、(define b (+ a x))の評価の時点でローカル環境にaがないため外側の環境を参照しに行く。至ってシンプル。 > (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) => 16 Racket 実行結果はAlyssaの見方と同じ。 racket@> (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) a: undefined; cannot use before initializati

前回悩んでいた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,7 +14,7 @@ class Parser def self.tokenize(input) tokens = input.strip .gsub(/\n/, ' ') - .gsub('\'(', '(quote (') + .gsub(/\'\(([0-9A-Za-z_\+\-\*\/\<\>\s]*)\)/, '(quote (\1))') .g

derived expression（導出された式）や§4.1.1〜4.1.4の練習問題を解いていきます。 問題 4.1 関数適用の際の引数の評価は左から？右から？という問題。 自前の処理では以下のようにoperands.mapとしているので左から。右からとするならイテレーションの順序を入れ替えればよい。 class Application < Base def eval(env) procedure = @operator.eval(env) arguments = @operands.map { |operand| operand.eval(env) } procedure.apply(arguments) end end defineによる手続き定義 (define (<var> <p1> .. <pn>) <body) は、 (define <var> (lambda (<p1>

primitive procedure (基本手続き)を実装します。 例えば四則演算のように特殊形式では表現しにくいような基本的な演算を行います。 ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4-ruby-evaluator 四則演算 実装としてはapply()メソッドを持つクラスを用意すればよいです。::CATALOGは環境へpushする際に使います。 module PrimProc class IsEqual def self.apply(arguments) arguments[0] == arguments[1] end end class Add def self.apply(arguments) arguments.reduce(:+) end end class Sub def self.

環境および束縛、代入まわりを実装しました。やってみると意外と簡単だった。 > (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) "foo")) => nil > (foo 1) => "foo" ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.1-ruby-evaluator 環境に対する操作 SICPを参考にEnvironmentクラスを実装。変数と値のペアはHashで持たせる。SICPのコードよりはずっとシンプルにできたと思う。

SICPでやっているRubyによるSchemeインタプリタでどうしてもArray#to_hが使いたくなったが、OSX Yosemiteに標準で付属しているRuby 2.0.0にはなかったので、rbenvを使ってみたときのメモ。 環境 Mac OSX Yosemite 10.10.2 Homebrew 0.9.5 rbenvのインストール % brew install rbenv ruby-build .zshrcに以下を追加。 % echo 'eval "$(rbenv init -)"' >> ~/.zshrc % source ~/.zshrc % rbenv --version rbenv 0.4.0 Rubyのインストール インストール可能なRubyのリストを表示。 % rbenv install --list Available versions: 1.8.6-p383 ...

以下のような関数適用のコードが動くようになりました。 > ((lambda (x) "foo") 1) => "foo" ソースコードはGitHubに置いています。 https://github.com/uents/sicp/tree/master/ch4.1-ruby-evaluator 前回までのリファクタリング その前に前回の内容をいくつかリファクタリング。 構文解析にNodeクラスを導入 Hashをベタに使うのはコードが読みにくくなってよくない。素直にNodeクラスを用意した。 class Parser class Node attr_reader :key, :value def initialize(token) @key = token.keys[0] @value = token.values[0] end end # (snip..) def self.parse(t)

前回作った構文木について、そのまま評価器に放り込んで評価させても良いのですが、SICPのテキストのeval()のようにだらだらと長くなるのがいまいちかなと思います。 問題4.3でも取り上げられているように「データ主導」で実装する方がスマートかと思いますので、そのために構文木のノードを実行可能なオブジェクトへ変換します。 具体的には、number,stringのような組み込みオブジェクト、quote,assignment,lambdaのような特殊形式、関数適用であるapplicationといった構文単位でクラスを用意し、構文木のノードをそのクラスの何れかに属するオブジェクトへとマッピングします。 class Generator def self.generate(node) begin case node.key when :NUMBER return Builtin::Number.new

最初はSICPのテキストを見ながら式評価、関数適用、環境まわり（p226付近）までRubyでひと通り実装しましたが、入力されたSchemeのコードを処理系へどうつなぐかで壁にあたりました。 色々と調べたところ、インタプリタの動作は主に以下のステップを踏むようです。 字句解析 構文解析 評価の実行 §4.1の序盤で字句解析/構文解析が出てこないのは、処理系の被実装言語、実装言語がともにSchemeで、さらにS式が構文木にそのまま相当するため構文解析等をせずともいきなり評価できてしまうからだと思います。 いま作っている処理系もS式をRubyの配列にそのまま見立てることで字句解析/構文解析を端折ることもできるのですが、せっかくのインタプリタを実装する機会なので、ある程度きちんとやりたいと思います。 REPL 初めから動くものを作りたいのでREPLループから実装します。SICPのテキストではdri

途中まで作っていたRubyによるScheme処理系ですが行き詰まりました。。。 理由はこんな感じです。 rubyによるschemeインタプリタ、ruby上でcons cellを実装してやってたけどlist iterationあたりの実装で限界がきた。rubyのデータ構造に合わせて実装した方がenumrableの恩恵を受けれるし素直な気がする #sicp— uents (@uents) 2015, 4月 7 当初はSICPのテキスト内容になるべく近づけるために、Rubyの処理系側でも def pair?(p) p.is_a?(Array) && p.length >= 2 end def cons(a, d) [a].push(d) end def car(p) if (pair?(p)) p[0] else raise "car: invalid argument: " + p.to_s

ところどころ飛ばしましたが、3章をひと通り読み終えました。この章で学んだことを上手くまとめるのは相当難しいですが、自分なりに整理したいと思います。 1章〜2章では手続きやデータによる抽象化について学びましたが、3章はそれらのモジュールをいかに組み合わせてプログラムを組織化していくかの戦略がテーマでした。さらに大きな観点で言えば、私達がモデル化しようとする現実世界をプログラム上での計算モデルとして如何に構築していくことがテーマとも言えるでしょう。 3章の冒頭でその具体的な戦略について語られています。 大きいプログラムを組織化する方法は, われわれがモデル化するシステムをどう認識するかにかなりなところまで左右される. 本章では, いくらか異ったシステム構造の二つの「世界観」から生じる顕著な組織化戦略を研究する. 第一の組織化戦略は オブジェクト(objects)に注目するもので, 巨大システム

「§3.5.5 関数プログラムの部品度とオブジェクトの部品化」から。 §3.1で乱数を生成する手続きrandが出たが、それを応用して乱数の無限ストリームrandom-numberを定義する。random-initは定数なので何度やっても結果は同じになる。 ;; §3.1から転用 (define (rand-update x) (modulo (+ (* 13 x) 47) 97)) (define random-init 7) (define random-numbers (cons-stream random-init (stream-map rand-update random-numbers))) ;; test racket@> (map (lambda (i) (stream-ref random-numbers i)) (enumerate-interval 0 20)) =>