パターンマッチの実装(1)

rowl

自分はコンパイラの実装言語にはパターンマッチがあると楽だと思っているのでrowlにもパターンマッチエンジンを実装しています。

以下の論文を参考にしています。
http://portal.acm.org/citation.cfm?id=507641&dl=
これまで変数パターン、Dontcareパターン、整数リテラルパターンを実装して以下の様なコードが書けるようになりました。

fib(n): fib(n-1) + fib(n-2)
fib(0): 0
fib(1): 1

print_int(fib(21))

今のところ全ての整数をボックス化しているのと、実装が雑(整数のパターンマッチにテーブル引きを使っていない等)であることもあってちょっと遅いですが、正しく動作します。ただ、GCにバグがある様でfib(22)以上はまだ動きません。

いつの間にか私の中でrowlは動的型付けのインタプリタ言語という方向性になってきているので、O'CamlやHaskellと違ってrowlのパターンマッチエンジンは動的です。
例えば、以下の様に途中で既存のパターンを書き換えたり、新たなパターンを追加したりできます。
従って、O'CamlやHaskellと違って後に定義されたパターンの方が優先的にマッチングされます。
新たなパターンが追加されると、最初にその関数がコールされた時にJITコンパイラがパターンマッチ部のコードを動的に生成する仕組みになっていて、高速なマッチングが出来るようにしています。

fib(n): fib(n-1) + fib(n-2)
fib(0): 0
fib(1): 1
print_int(fib(10)) # -> 55
fib(0): 1          # 既存パターンの再定義
print_int(fib(10)) # -> 89
fib(2): 2          # 新しいパターンの追加
print_int(fib(10)) # -> 89 (上より速い)

また、特定のブロック内でだけ定義を書き換える事が出来るようにする予定です。

fib(n): fib(n-1) + fib(n-2)
fib(0): 0
fib(1): 1
{
    fib(0): 1
    print_int(fib(10)) # -> 89
}
print_int(fib(10)) # -> 55

この仕組みは、既存のコンパイラにユーザが新しい構文要素を追加したり、コード生成部をいじったりといった事が簡単にできるようにすることを目的に作っています。

静的型付けを捨てた代償は、パターンマッチの網羅性チェックが出来ないという点になります。