Edited at
RubyDay 9

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

More than 3 years have passed since last update.

こんにちは。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を仕事に使ってみたりしています。なので、動的型付け言語で他にもこんなパターンマッチの実装があるよ!とか、上記の実装はもっとこうしたら良くなるよ!というのがあったらぜひ教えてください。