SICP 読書ノート#51 - RubyでSchemeインタプリタをつくろう(10) - 導出された式 (pp.213-228)
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> .. <pn>) <body))
の構文シュガーなのでそのように変換させる。
class Generator def self.generate(node) # snip... when "define" if operands[0].class == Parser::Node variable = self.generate(operands[0]) value = self.generate(operands[1]) else variable = self.generate(operands[0][0]) params = operands[0][1..-1].map { |param| self.generate(param) } body = operands[1..-1].map { |exp| self.generate(exp) } value = SpecialForm::Lambda.new(params, body) end return SpecialForm::Definition.new(variable, value)
テスト。
[3] pry(main)> repl.run > (define (fact n) (if (< n 1) 1 (* n (fact (- n 1))))) > (fact 5) => 120
問題 4.2
a.
Louisの主張は「関数適用(application)をdefineなどの特殊形式(special forms)より前に持ってくれば解釈系の処理効率が上がる」ということだが、そうすると、
- 関数適用の際に
defineの名前を持つ手続きを環境から探す - 探してもヒットせず例外が発生
となり上手くいかない。
b.
面倒なので略。
問題 4.3
すでにデータ主導で実装したつもりなので略。
- https://github.com/uents/sicp/tree/master/ch4.1-ruby-evaluator
- generator.rb のGeneratorクラス
問題 4.4
特殊形式でandとorを実装する。
class And < Base def initialize(predicates) @predicates = predicates end def eval(env) if @predicates.empty? true else @predicates.each do |predicate| return false if predicate.eval(env) == false end @predicates.last end end end class Or < Base def initialize(predicates) @predicates = predicates end def eval(env) if @predicates.empty? false else @predicates.each do |predicate| return predicate if predicate.eval(env) != false end @predicates.last end end end
導出された式
特殊形式へ構文変換できる式をderived expressions(導出された式)と呼ぶ。
例えばcondの構文は、
(cond (<p1> <s1>) (<p2> <s2>) (else <sx>))
以下のifの構文と等価である。
(if <p1> <s1> (if <p2> <s2> <sx>))
そこで処理系でも同じような構文変換を行う。
class Cond def initialize(predicates, sequences) @clauses = predicates.zip(sequences) end def eval(env) cond_to_if(@clauses).eval(env) end private def cond_to_if(clauses) predicate = clauses[0][0] sequence = clauses[0][1] if predicate == nil false elsif predicate.name == "else" sequence else SpecialForm::If.new(predicate, sequence, cond_to_if(clauses[1..-1])) end end end
問題 4.5
letからlambdaへの関数適用の形で構文変換できる。
以下のように実装。われながら良いコードだと思う。
class Let def initialize(variables, expressions, body) @variables = variables @expressions = expressions @body = body end def eval(env) let_to_combination().eval(env) end private def let_to_combination() SpecialForm::Application.new(SpecialForm::Lambda.new(@variables, @body), @expressions) end end
テスト。一発で動いてちょっと感動。
[3] pry(main)> repl.run > (let ((x 1) (y 2)) (+ x y)) => 3 > (let ((addone (lambda (n) (+ n 1)))) (addone 5)) => 6
ただし、factのbodyの環境からはfactが見えないので再帰はできない。
> (let ((fact (lambda (n) (if (< n 1) 1 (* n (fact (- n 1))))))) (fact 5)) "lookup_variable_value: unbound variable; fact"
問題 4.6
condの(<test>=><recipient>)の仕様について。使いどころがよくわからないのでスキップ。
問題 4.7
(let* ((<v1> <e1>) (<v2> <e2>) (<v3> <e3>)) <body>)
は、
(let ((<v1> <e1>)) (let ((<v2> <e2>)) (let ((<v3> <e3>)) <body>)))
と等価であるため、以下のようになる。
module DerivedExp class LetAster def initialize(variables, expressions, body) @clauses = variables.zip(expressions) @body = body end def eval(env) let_aster_to_nested_let(@clauses).eval(env) end private def let_aster_to_nested_let(clauses) if clauses.empty? @body else variable = clauses[0][0] expression = clauses[0][1] DerivedExp::Let.new([variable], [expression], let_aster_to_nested_let(clauses[1..-1])) end end end end
また、Let#new()の引数bodyに対して配列を渡せないためeval_sequenceの修正も必要。（このデバッグが結構大変だった…）
def eval_sequence(seq, env) if seq.class == Array seq.map { |exp| exp.eval(env) }.last else seq.eval(env) ## 追加 end end
問題 4.8
named letの実装。
(let <name> ((<v1> <e1>) (<v2> <e2>) (<v3> <e3>)) <body>)
は、
(begin (define <name> (lambda (<v1> <v2> <v3>) <body>) (<name> <e1> <e2> <e3>)))
と等価であるので、letを以下のように拡張した。
class Let def initialize(name, variables, expressions, body) @name = name @variables = variables @expressions = expressions @body = body end def eval(env) let_to_combination().eval(env) end private def let_to_combination() if @name != nil SpecialForm::Begin.new( [SpecialForm::Definition.new(@name, SpecialForm::Lambda.new(@variables, @body)), SpecialForm::Application.new(@name, @expressions)]) else SpecialForm::Application.new(SpecialForm::Lambda.new(@variables, @body), @expressions) end end end
テスト。
> (define (fib n) (let fib-iter ((a 1) (b 0) (count n)) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))) > fib(10) => 55
問題 4.9
いちばん簡単そうなwhileを実装する。
問題4.8のnamed letを使うことで
(while <predicate> <body>)
は、
(let loop () (if <predicate> (begin <body> (loop)) false))
に変換可能なので、derived expressionとして実装できる。
class While def initialize(predicate, body) @predicate = predicate @body = body end def eval(env) while_to_named_let().eval(env) end private def while_to_named_let() DerivedExp::Let.new(Builtin::Variable.new("loop"), [], [], SpecialForm::If.new( @predicate, SpecialForm::Begin.new( @body + [SpecialForm::Application.new( Builtin::Variable.new("loop"), [])] ), Builtin::Variable.new("false"))) end end
テスト。
> (define i 0) > (while (< i 5) (print i) (set! i (+ i 1))) 1 2 3 4 => false > i => 5
問題 4.10
新しい構文の設計で考えられるのは、
- 中間記法を使う
- S-Expressionから、PythonのようにI-Expressinにする
自前の処理系はすでに構文解析と評価を分離したので、構文解析さえ修正すればできそう。でも面倒なので略。
問題 4.11
Hashテーブル使えって話だよね。§3.3.3で出てきたのでそれを使えばいいと思う。
自前の処理系は最初からHashで実装しているので特になし。
- https://github.com/uents/sicp/tree/master/ch4.1-ruby-evaluator
- evaruator.rb のEnvironmentクラス
問題 4.12
内部手続きscan()を共通化できる。
自前の処理系はすでにframes.eachで走査させていて、これ以上共通化しても過剰かなと思うので略。
問題 4.13
束縛する側のdefineがそうであるようにunbind!も最初のフレームからだけでいいんじゃないのかな。実装はスキップします。
問題 4.14
Evaはユーザー関数としてmapを定義した模様。真っ当だと思う。
Louisは基本手続きとしてどう組み込んだかよくわからないけど、動作がおかしいのはmapが処理系のmapとしてではなく被実装言語側のSchemeのmapとして動いちゃったとかかな？
よくわからないのでググったら以下のような理由らしい。
Louis Reasoner の方法で実行した場合
;; (primitive-proceduresにmap手続きを追加しておく) (map (lambda (x) x) '(1 2 3 4 5)) ; *** ERROR: invalid application: ((procedure (x) (x) (((false true car cdr cons null? map) #f #t (primitive #<subr car>) (primitive #<subr cdr>) (primitive #<subr cons>) (primitive #<subr null?>) (primitive #<subr map>)))) 1) ; Stack Trace: ; _______________________________________ ; 0 (eval input the-global-environment) ; At line 491 of "C:/home/tmurata/scheme/4.Z.scm"
となる。
基盤Lispのmapからは第一引数が手続きでなく通常のリストに見えているため、うまくいっていない。(手続きの先頭に'procedureというタグが付いているため)
自前の処理系ではどうなるかprimitive procedureとして組み込んでみた。
class Map def self.apply(arguments) if arguments.length < 2 raise "map: airty mistatch; " + arguments.to_s end proc = arguments[0] lists = arguments[1..-1] self.iter(proc, lists) end private def self.iter(proc, lists) if lists[0] == nil nil else firsts = lists.map { |list| list.car } rests = lists.map { |list| list.cdr } Builtin::Pair.new(proc.apply(firsts), self.iter(proc, rests)) end end
テスト。特に問題なく動いた。
> (map + (list 1 2 3)) => (1 2 3) > (map + (list 1 2 3) (list 4 5 6) (list 7 8 9)) => (12 15 18) > (map cons (list 1 2 3) (list 4 5 6)) => ((1 . 4) (2 . 5) (3 . 6))
そろそろ次に進みたいけど、自前の処理系のquoteのバグが取れずに苦戦中。。。
