SICP 読書ノート#48 - RubyでSchemeインタプリタをつくろう(7) - 関数の評価と適用 (pp.213-228)
以下のような関数適用のコードが動くようになりました。
> ((lambda (x) "foo") 1) => "foo"
前回までのリファクタリング
その前に前回の内容をいくつかリファクタリング。
構文解析に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) tokens = t.dup token = tokens.shift case token when :LEFT_PAREN return make_nodes(tokens) when :RIGHT_PAREN raise "parse: unexpected tokens " + t.to_s else return Node.new(token) end end private def self.make_nodes(tokens) nodes = [] token = tokens.shift while token != nil case token when :LEFT_PAREN nodes.push(make_nodes(tokens)) when :RIGHT_PAREN return nodes else nodes.push(Node.new(token)) end token = tokens.shift end nodes end end
組み込み型と特殊形式を別々のモジュールへ
組み込み型(builtin class)と形式(special forms)でモジュールへ分割。
module Builtin class Number # ... end class String # ... end class Variable # ... end end module SpecialForm class Base # ... end class Quote < Base # ... end class Assignment < Base # ... end # ... end
関数の評価と適用
ここからは関数適用を行わせる際の変更。
operatorには関数の名前(実体と束縛された変数)以外に、((lambda (x) "foo") 1)
のように無名関数の本体が指定されるパターンもある。つまり、
class Generator # snip... case operator.value else if operator.class == Parser::Node procedure = Builtin::Variable.new(operator.value) else params = operator[1].map { |param| self.generate(param) } body = operator[2..-1].map { |exp| self.generate(exp) } procedure = SpecialForm::Lambda.new(params, body) end arguments = operands.map { |operand| self.generate(operand) } return SpecialForm::Application.new(procedure, arguments) end
次にApplicationの評価。lambdaを評価して手続きを生成し、評価した引数を適用させる。
class Application < Base def eval(env) procedure = @procedure.eval(env) arguments = @arguments.map { |arg| arg.eval(env) } procedure.apply(arguments) end end
続いてLambda#eval()
を実装。手続き(クロージャ)を生成する。
class Lambda < Base def eval(env) Procedure.new(@params, @body, env) end end
Procedureオブジェクトは以下の通り。関数と環境を結びつけてクロージャを生成し、適用時に引数を環境にpushしてbodyを順に評価する。
class Procedure < Base def initialize(params, body, env) @params = params @body = body @env = env end def apply(arguments) # env = @env.extend_environment(@params, arguments) self.eval_sequence(@body, env) end end
さらにeval_sequence()
はmapで順に式を評価し、最後に評価した式の値を返す。
class Base def eval_sequence(seq, env) seq.map { |exp| exp.eval(env) }.last end end
これで無名関数への適用が行える。
[1] pry(main)> load "repl.rb" => true [2] pry(main)> repl = REPLServer.new => #<REPLServer:0x007fdb28998918 @evaluator=#<Evaluator:0x007fdb289988c8 @environment=#<Environment:0x007fdb289988a0>>> [3] pry(main)> repl.run > ((lambda (x) "foo") 1) => "foo"
まとめると関数(手続き)の評価と適用は以下のように動作する。
試行錯誤でインタプリタを実装したおかげで、このあたりの理解がとても深まりました。やってよかった。
今後は、
- environmentの設計と実装
- special formsの各クラスの実装
- primitive proceduresの実装
をやっていきます。