SICP 読書ノート#50 - RubyでSchemeインタプリタをつくろう(9) - 基本手続き/四則演算/リスト演算 (pp.213-228)

primitive procedure (基本手続き)を実装します。

例えば四則演算のように特殊形式では表現しにくいような基本的な演算を行います。

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.apply(arguments)
      arguments.reduce(:-)
    end
  end

  class Multiply
    def self.apply(arguments)
      arguments.reduce(:*)
    end
  end

  class Devide
    def self.apply(arguments)
      arguments.reduce(:/)
    end
  end

  # ...

  CATALOG = {
    "=" => IsEqual,
    "+" => Add,
    "-" => Sub,
    "*" => Multiply,
    "/" => Devide,
  }
end

グローバル環境へpushします。ついでにtrue、falseも。

class Evaluator
  attr_reader :environment

  def initialize()
    @environment = Environment.new([])
    @environment = @environment.extend_environment(PrimProc::CATALOG.keys,
                                                   PrimProc::CATALOG.values)
    @environment.define_variable!("true", true)
    @environment.define_variable!("false", false)
  end

  # ...
end

これで準備完了。これでプログラムの評価の中でprimitive procedureを見つけた場合はそれが適用されるようになります。Rubyの除算はそのままでは有理数を扱えないので0になってしまいますが…

[3] pry(main)> repl.run
> (+ 1 2 3 4)
=> 10
> (- 1 2 3 4)
=> -8
> (* 1 2 3 4)
=> 24
> (/ 1 2 3 4)
=> 0

> (define add (lambda (x y) (+ x y)))
> (define a 2)
> (define b 3)
> (add a b)
=> 5

この時の環境を見てみると、基本手続きがユーザー変数と同様にグローバル環境に追加されています。(repl.debug()はデバッグ用に用意したメソッド)

> quit
=> "good bye!"

[4] pry(main)> repl.debug(:env)
=> #<Environment:0x007fc1b2876808
 @frames=
  [{"="=>PrimProc::IsEqual,
    "+"=>PrimProc::Add,
    "-"=>PrimProc::Sub,
    "*"=>PrimProc::Multiply,
    "/"=>PrimProc::Devide,
    "add"=>
      #<SpecialFrom::Procedure:0x007fc1b4087aa0
      @body=
        [#<SpecialFrom::Application:0x007fc1b4087b68
          @arguments=[#<Builtin::Variable:0x007fc1b4087af0 @name="x">, #<Builtin::Variable:0x007fc1b4087ac8 @name="y">],
          @procedure=#<Builtin::Variable:0x007fc1b4087b40 @name="+">>],
      @env=#<Environment:0x007fc1b2876808 ...>,
      @params=[#<Builtin::Variable:0x007fc1b4087dc0 @name="x">, #<Builtin::Variable:0x007fc1b4087d98 @name="y">]>,
    "a"=>2,
    "b"=>3}]>

リスト演算

Lispには欠かせない要素ですね。単純に配列でペアを作るなど色んな表現方法があると思いますが、試行錯誤の末、Evaluatorの出力結果のparse処理を楽するためにPairクラスを用意しました。

module Builtin
  class Pair
    def initialize(first, rest)
      @first = first
      @rest = rest
    end

    def car()
      @first
    end

    def cdr()
      @rest
    end

    def to_s(paren=true)
      str = ''
      str += '(' if paren
      if self.car.is_a?(Pair)
        str += self.car.to_s(true)
      else
        str += self.car.to_s
      end
      if self.cdr == nil
        # do nothing
      elsif self.cdr.is_a?(Pair)
        str += ' ' + self.cdr.to_s(false)
      else
        str += ' . ' + self.cdr.to_s
      end
      str += ')' if paren
      str
    end
  end
end 

module PrimProc
  class Cons
    def self.apply(arguments)
      begin
        Builtin::Pair.new(arguments[0], arguments[1])
      rescue
        raise "cons: airty mistatch; " + arguments.to_s
      end
    end
  end

  class Car
    def self.apply(arguments)
      begin
        arguments[0].car
      rescue
        raise "car: contract violation; " + arguments.to_s
      end
    end
  end

  class Cdr
    def self.apply(arguments)
      begin
        arguments[0].cdr
      rescue
        raise "cdr: contract violation; " + arguments.to_s
      end
    end
  end

  class List
    def self.apply(arguments)
      arguments.foldr(nil) { |x, y| Builtin::Pair.new(x, y) }
    end
  end

  CATALOG = {
    "=" => IsEqual,
    "+" => Add,
    "-" => Sub,
    "*" => Multiply,
    "/" => Devide,
    "cons" => Cons,
    "car" => Car,
    "cdr" => Cdr,
    "list" => List,
  }

リストはconsの入れ子で作りますが、Rubyにはfold-rightが無さげだったのでEnumerable#inject()を参考に自前で拡張してそれを使っています。

module Enumerable
  def foldr(*args, &block)
    case args.length
    when 2
      init, proc = args
    when 1
      if block_given?
        init = args.first
      else
        init = :nil
        proc = args.first
      end
    when 0
      init = :nil
    else
      raise "..."
    end

    lst = self.dup
    if init == :nil
      init = self.last
      lst.pop
    end

    memo = init
    lst.reverse_each do |item|
      if proc
        memo = item.send(proc, memo)
      else
        memo = block.call(item, memo)
      end
    end
    memo
  end
end

必要なクラスにto_s()を用意したので、REPLの出力処理は以下のようにシンプルです。

  def pretty_print(output)
    if output != nil
      print @@out_prompt
      print output.to_s + "\n"
    end
  end

テスト。いい感じです。

[3] pry(main)> repl.run
> (cons (cons 1 2) (cons 3 4))
=> ((1 . 2) 3 . 4)

> (list 1 2 3 4 5)
=> (1 2 3 4 5)

> (define x 10)
> (define y 20)
> (define z 30)
> (cons (cons x y) z)
=> ((10 . 20) . 30)

ただ、consセルは§2の最初で見たようにlambdaを使った手続きオブジェクトでも表現できるので、ユーザー関数として追加する方法があると思います。言い換えると、

special form (特殊形式)
primitive prodecure (基本手続き)
その他のユーザー関数

をどういうポリシーで使い分けすればよいかモヤモヤとしているところです。

基本的な部分はおおよそできたので、次からようやく練習問題を解いていきます。

@uents blog

Code wins arguments.

SICP 読書ノート#50 - RubyでSchemeインタプリタをつくろう(9) - 基本手続き/四則演算/リスト演算 (pp.213-228)

四則演算

リスト演算