S-Expression for Ruby 解説

Ruby lisp

ファンクション倶楽部2008秋イベント LT で話した (S-Expression for Ruby) のコードを簡単に説明します。

どなたかがブログに書かれていましたように、S-Expression for Ruby は 簡単なLispの処理系の 65%くらい(??)を実装したものです。

Cell クラス

まずは、lispの基本データであるリスト構造(Cell、pair, cons) のクラス。

class Cell
  def initialize(a = nil, b = nil)
    @car = a
    @cdr = b
  end

  def self.cons(a,b)
    self.new(a,b)
  end

  attr_accessor :car, :cdr
end

Sクラス(基本)

S式のクラス S です。 S式はリスト構造(Cell)または、Rubyのオブジェクトを保持できます(@valueインスタンス変数に)。
S.new(s) には文字列で表現した S式または、Rubyのオブジェクトを与えます。

class S
  def initialize(e = nil, b1 = nil, b2 = nil)
    @value = e.kind_of?(String) ? s_read(e) : e
    @bind1 = b1 == nil ? @@bind1_default : b1
    @bind2 = b2
  end

  def self.bind(b)
    @@bind1_default = b
  end
  attr_accessor :value

  def ruby_env
    @bind1
  end

  def to_s
    s_print(@value)
  end
end

また、S.new(s,b1,b2) のように、第2、第3引数に Rubyの実行環境 Binding を与える事ができます。S式の中ではここで与えた Bindingに定義している変数をアクセスできます。
デモの際に毎回、bindingを与えるのは面倒なので S.bind(binnding)でデフォルトの bindingを指定できるようにしています(現実的には問題あり？)。

Sクラス(入出力)

リスト構造を文字列に変換する s_print、文字列で書かれた S式をリスト構造に変換する s_read。 lispのprint/readの簡易版です。

  TOKEN_PATTERN = /[().]|".*"|\d+|:\w+|[^\s().]+/

  def s_print(e)
    return "nil"  if (e.nil?)
    return  e.to_s  unless (e.instance_of? Cell)

    r = "("
    while (true) 
      r += s_print(e.car)
      e = e.cdr
      break if (e.nil?)
      unless e.instance_of?(Cell)
        r += "."
        r += s_print(e)
        break
      end
      r += " "
    end
    r + ")"
  end

  def s_read(s)
    @tokens = s.scan(TOKEN_PATTERN).map {|e| e =~ /^\d+$/ ? e.to_i : e}
    s_read_body
  end

  def s_read_body
    return @tokens.first  unless (@tokens.first == "(")

    list = nil
    @tokens.shift
    while (true)
      return list  if (@tokens.first == ")")

      car_e = s_read_body
      @tokens.shift
      if  @tokens.first == '.'
        @tokens.shift
        cdr_e = s_read_body
        @tokens.shift
        raise ") excepted "  if (@tokens.first != ")")
        return  Cell.cons(car_e, cdr_e)
      end
      list = concat2(list, Cell.cons(car_e, nil))
    end
  end

  def concat2(a, b)
    return b  if (a == nil)
    return a  if (b == nil)
    
    p = a;
    while p.cdr
      p = p.cdr
    end
    p.cdr = b
    a
  end

read、print共にcarは再帰で、cdrはループで処理しています。

Sクラス(eval)

いよいよ本命の、S式の処理を行う eval/apply。 evalで Sオブジェクトの持つS式がlispのプログラムとして評価し、callでS式として定義された関数(lambda式など)をrubyから利用できます。

  def eval
    s_eval(@value)
  end

  def call(*args)
    if @value.instance_of?(Cell)
      s_apply(@value, args)
    else
      nil
    end
  end

evalの実体

s_eval
evalの実体です
ruby_value、ruby_variable?
rubyの変数の値を取得する部分です、ruby変数の値はnew()等に渡されたbinding環境でruby_eval(rubyのeval)を実行し取得しますが、"+" 等をruby_evalすると文法エラーになり、それが rescue で捕捉できないので local_variables でローカル変数一覧を取得、そこにあれば ruby_evalしています。
  def s_eval(e)
    e = e.value if (e.instance_of? S)
    return e  if (e.kind_of? Numeric)
    return ruby_value(e)  unless (e.instance_of? Cell)

    s_apply(e.car, e.cdr)
  end

  def ruby_value(e)
    if ruby_variable?(e, @bind2)
      ruby_eval(e, @bind2)
    elsif ruby_variable?(e, @bind1)
      ruby_eval(e, @bind1)
    else
      raise "Undefined variable #{e}"
    end
  end

  def ruby_variable?(name, bind)
    a = ruby_eval("local_variables", bind)
    a.find {|e| e == name}
  end

s_apply

s_apply は関数を評価する関数です、Sクラスの扱う関数には

スペシャルフォーム
Sクラスに組み込まれた関数で、ifやdefineのようにやや特殊な処理を行います。スペシャルフォームは Sformハッシュに Proc として定義します。引数は評価せず関数に渡されます。
Procで定義されたRuby関数
Rubyで関数を定義したい場合は、Proc を使って関数を定義し変数に代入します。この関数への引数は全てLisp側で評価してから渡されます。
Rubyのメソッド
(メソッド名 Rubyオブジェクト1 Rubyオブジェクト2 Rubyオブジェクト3 ....) は Rubyオブジェクト1.メソッド名(Rubyオブジェクト2, Rubyオブジェクト3, ....) として評価されます。
lambda式
Ｓ式内のlambda式は通常のLispのように評価されます。ただし、lambda式に渡す引数、lambda式の内部で使われているRuby変数の両方をバインド(binding)する必要があります。RubyのBindは複数のBindをマージしたり出来ないので S.new(e,b1,b2)と２つのBindを渡せるようにしました。また、lambda式の引数は可変なので Proc を 文字列として組み立て ruby_eval する事で実現しています。
  Sform = {
    "if" => Proc.new{|s, cond, then_e, else_e| 
      s.s_eval(cond) ? s.s_eval(then_e) : s.s_eval(else_e)},
    "lambda" => Proc.new{|s, args, body|
      Cell.cons("lambda", Cell.cons(args, Cell.cons(body, nil)))},
    "define" => Proc.new{|s, var, exp|
      str_exp = s.s_print(exp);
      ruby_eval("#{var} = S.new('#{str_exp}')", s.ruby_env)},
  }

  def s_apply(func, args)
    args = list2array(args)  if (args.instance_of?(Cell))

    if  func.instance_of?(String) && Sform[func]
      Sform[func].call(self, *args)
    else
      func_def = s_eval(func) rescue nil
      func_def = func_def.value  if (func_def.instance_of? S)
      args = eval_array(args)

      if func_def.instance_of?(Proc)
        func_def.call(*args)
      elsif func.instance_of?(String) &&
          args.size > 0 && all_ruby_obj?(args) &&
          args[0].respond_to?(func)
        args.first.send(func, *args[1,100])
      elsif func_def.instance_of?(Cell) && func_def.car == "lambda"
        params = list2array(func_def.cdr.car).join(',')
        body = func_def.cdr.cdr.car
        ruby_eval("Proc.new {|_body,#{params}| S.new(_body,nil,binding).eval}").call(body, *args)
      else
        raise "Undefined function #{func}"
      end
    end
  end

s_applyの下請けとして

list2array
List構造(Cell)をrubyの配列に変換
eval_array
配列の要素を全て eval(lisp側) した値に置き換える
all_ruby_obj?
引数の配列要素が全て Rubyオブジェクト なら true
  def eval_array(array)
    array.map {|e| s_eval(e)}
  end

  def list2array(list)
    array = []
    while  list
      array.push(list.car)
      list = list.cdr
    end
    array
  end

  def all_ruby_obj?(args)
    args.all? {|e| !e.instance_of?(Cell) && !e.instance_of?(S)}
  end


Object クラス

デモし易くする為に、 S式の作成する s 関数, S式を作成し評価する e関数 を定義しています。

class Object
  def s(e)
    S.new(e)
  end
  def e(s)
    S.new(s).eval
  end

  alias :ruby_eval :eval
end

また、evalをSクラスで再定義するので Rubyのeval関数は ruby_evalとしています。