Rubyで構文木に対するパターンマッチを実装する

こんにちは。nushioです。実はRubyは私の2番めに好きな言語で、よく使っています。

本業では言語処理系を実装するのが仕事なのですが、言語処理系を作っていると抽象データ型（Abstract Data Type, ADT）を操作したり評価したりする処理をよく書くので、Haskellのような言語に備わっているパターンマッチはとても便利です。とても便利なので、PythonやRubyにも似たようなパターンマッチがあればうれしいよね、ということでいろんな人が作っています。

Rubyだと例えば

• https://github.com/whitequark/ast
• http://qiita.com/egisatoshi/items/38f7f8aef32ac67ccd4b

Pythonだと、例えば

• http://www.grantjenks.com/docs/pypatt/ (and references therein)

などがあるようです。ですが、どうもしっくりくるものがなかったので、自分で作ってみることにしました。

#!/usr/bin/env ruby

class ADT
  attr_accessor :constructor, :argv, :metadata
  def =~(pattern)
    pattern.match(self)
  end
end

class Pattern
  attr_accessor :accept_continuation, :alternative
  def match(x)
    if self === x
      return @accept_continuation.call(*x.argv)
    elsif @alternative
      return @alternative.match(x)
    else
      raise("unexpected constructor: " + x.constructor.to_s)
    end
  end
  def | (other)
    @alternative=other
    return self
  end
end

コアとなる部分はたったこれだけです。=~で構文木にパターンをマッチ。各パターンは===でマッチしているかの判定をし、マッチしていたら@accept_continuationブロックを呼び出します。マッチしていなかったら@alternativeに処理を投げます。このalternativeは|演算子で設定します。

個々の抽象構文木の要素は、ブロックを渡されたときにはパターン、そうでないときにはADTを作って返します。

def Binop(*argv, &block)
  if(block) # used as pattern
    ret = Pattern.new()
    ret.accept_continuation = block
    def ret.===(x)
      return x.constructor == :binop && String === x.argv[0]&&
             ADT === x.argv[1] && ADT === x.argv[2]
    end
    return ret
  else # used as constructor
    ret = ADT.new()
    ret.constructor = :binop
    ret.argv = argv
    return ret
  end
end
def Uniop(*argv, &block)
  if(block) # used as pattern
    ret = Pattern.new()
    ret.accept_continuation = block
    def ret.===(x)
      return x.constructor == :uniop && String === x.argv[0] &&
             ADT === x.argv[1]
    end
    return ret
  else # used as constructor
    ret = ADT.new()
    ret.constructor = :uniop
    ret.argv = argv
    return ret
  end
end

def Imm(*argv, &block)
  if(block) # used as pattern
    ret = Pattern.new()
    ret.accept_continuation = block
    def ret.===(x)
      return x.constructor == :imm
    end
    return ret
  else # used as constructor
    ret = ADT.new()
    ret.constructor = :imm
    ret.argv = argv
    return ret
  end
end

これで、抽象構文木を構築する処理は普通の関数呼び出しのように書けますし、
連続するパターンマッチは次のように、コンストラクタが、束縛先の変数を列挙したブロックを引数に取る形で書けます。

expr = Binop('*', Imm(6), Binop('+', Imm(3), Imm(4)))

def evArith(expr)
  expr =~ Imm {|x|
    x
  } | Binop {|op, x, y|
    case op
    when '+'
      evArith(x) + evArith(y)
    when '*'
      evArith(x) * evArith(y)
    else
      raise( "error: unknown operator " + op + " at position " + expr.metadata)
    end
  }
end



p evArith(expr)

# evalがUniopに対応していない旨のエラーが出る
p evArith(Uniop('-',expr))

と、ここまで書いたところで、実はegisonには抽象構文木に対するパターンマッチもあった！ということを見つけたので、これを調べてみることにしました。
https://github.com/egison/egison-ruby#algebraic-data-types
_name で束縛した値がnameで参照できるみたいですが、これはmethod_missingを使ってPatternVariableを導入しているのですね。
https://github.com/egison/egison-ruby/blob/d0d50081fadb3aab8529e4a96e2e06706b1c28ac/lib/egison/core.rb#L335

method_missingは自分で積極的に使ったことはなかったし、Structというものがあるのも知らなかったので、勉強になりました。egisonという強力なパターンマッチをもつ言語も面白いですね。

ここ数年は静的型付け言語であるHaskellをもっぱら使ってきましたが、最近は動的型付けもいいなと思ってきていて、HaskellでもDynamicを仕事に使ってみたりしています。なので、動的型付け言語で他にもこんなパターンマッチの実装があるよ！とか、上記の実装はもっとこうしたら良くなるよ！というのがあったらぜひ教えてください。