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

前回作った構文木について、そのまま評価器に放り込んで評価させても良いのですが、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(node.value)
      when :STRING
        return Builtin::String.new(node.value)
      when :SYMBOL
        return Builtin::Variable.new(node.value)
      else
        raise "generate: unknown builtin type; " + node.to_s
      end
    rescue
      operator = node[0]
      operands = node[1..-1]

      case operator.value
      when "quote"
        list = operands[0].map { |item| self.generate(item) }
        return SpecialForm::Quote.new(list)
      when "set!"
        variable = self.generate(operands[0])
        value = self.generate(operands[1])
        return SpecialForm::Assignment.new(variable, value)
      when "define"
        variable = self.generate(operands[0])
        value = self.generate(operands[1])
        return SpecialForm::Definition.new(variable, value)
      when "if"
        predicate = self.generate(operands[0])
        consequent = self.generate(operands[1])
        alternative = self.generate(operands[2])
        return SpecialForm::If.new(predicate, consequent, alternative)
      when "lambda"
        p operands[0]
        p operands[1..-1]
        params = operands[0].map { |param| self.generate(param) }
        body = operands[1..-1].map { |exp| self.generate(exp) }
        return SpecialForm::Lambda.new(params, body)
      when "begin"
        exps = operands[0].map { |operand| self.generate(operand) }
        return SpecialForm::Begin.new(exps)
      else
        procedure = Builtin::Variable.new(operator.value)
        arguments = operands.map { |operand| self.generate(operand) }
        return SpecialForm::Application.new(procedure, arguments)
      end
    end        
  end
end

Typeモジュールとそれに属するクラスを用意。とりあえずinitializeだけ実装。

module Type
  class Base
  end

  class Number < Base
    def initialize(value)
      @value = value
    end
  end

  class String < Base
    def initialize(value)
      @value = value
    end
  end

  class Variable < Base
    def initialize(name)
      @name = name
    end
  end

  class Quote < Base
    def initialize(list)
      @list = list
    end
  end

  class Assignment < Base
    def initialize(var, value)
      @variable = var
      @value = value
    end
  end

  class Definition < Base
    def initialize(var, value)
      @variable = var
      @value = value
    end
  end

  class If < Base
    def initialize(predicate, consequent, alternative)
      @predicate = predicate
      @consequent = consequent
      @alternative = alternative
    end
  end

  class Lambda < Base
    def initialize(params, body)
      @params = params
      @body = body
    end
  end

  class Begin < Base
    def initialize(exps)
      @exps = exps
    end
  end

  class Application < Base
    def initialize(procedure, arguments)
      @procedure = procedure
      @arguments = arguments
    end
  end
end

pryで実行してみると、こんな感じになりました。

[1] pry(main)> exp = "(define x 1)"
=> "(define x 1)"
[2] pry(main)> Generator.generate(Parser.parse(Parser.tokenize(exp)))
=> #<Type::Definition:0x007f9902141070 @value=#<Type::Number:0x007f9902140cd8 @value=1>, @variable=#<Type::Variable:0x007f9902140e90 @name="x">>

[3] pry(main)> exp = "((lambda (x) \"foo\") 1)"
=> "((lambda (x) \"foo\") 1)"
[4] pry(main)> Generator.generate(Parser.parse(Parser.tokenize(exp)))
=> #<Type::Application:0x007f9a728e5cb0
@operands=[#<Type::Number:0x007f9a728e5b98 @value=1>],
@operator=#<Type::Lambda:0x007f9a728e5fd0 @body=[#<Type::String:0x007f9a728e5d50 @value="foo">], @params=[#<Type::Variable:0x007f9a728e5f30 @name="x">]>>

あとは各クラスのevalメソッドを実装すれば、REPLループでトップのオブジェクトを順々に評価されるはず。

  tokens = Parser.tokenize(input)
  nodes = Parser.parse(tokens)
  object = Generator.generate(nodes)
  @evaluator.eval(object) # この中でobjects.eval(@environment)を実行