@uents blog

Code wins arguments.

SICP 読書ノート#48 - RubyでSchemeインタプリタをつくろう(7) - 関数の評価と適用 (pp.213-228)

SICP Scheme Ruby

以下のような関数適用のコードが動くようになりました。

> ((lambda (x) "foo") 1)
=> "foo"

ソースコードはGitHubに置いています。

前回までのリファクタリング

その前に前回の内容をいくつかリファクタリング。

構文解析に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)のように無名関数の本体が指定されるパターンもある。つまり、

  • 関数の名前が指定される場合は、それは関数の実体を束縛する変数なので、Variableオブジェクトにマッピングする
  • 関数の本体が指定される場合は、Lambdaオブジェクトにマッピングする
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"

まとめると関数(手続き)の評価と適用は以下のように動作する。

  1. 関数名が指定された場合、環境から関数の実体(lambda)を取り出す
  2. 関数に環境を与えて評価し、クロージャを生成する
  3. クロージャに引数を適用することで、関数のbodyを順次評価する

試行錯誤でインタプリタを実装したおかげで、このあたりの理解がとても深まりました。やってよかった。

今後は、

  • environmentの設計と実装
  • special formsの各クラスの実装
  • primitive proceduresの実装

をやっていきます。

※「SICP読書ノート」の目次はこちら