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

rowl

Rowlの動的なパターンマッチエンジンの構成について書きます。
まず、インタプリタ内にfuntableという関数テーブル(関数名 × 引数の数 → 関数実体)があります。
関数の実体は

からなるconsセルです。
関数がコールされるとcar部のバイトコードに処理が移ります。

説明の為に以下のプログラムを考えます。
フィボナッチ数を出力するプログラムですが途中のブロック内だけ再定義してリュカ数を出力します。再定義はブロックローカルでだけ有効で、外側には影響しません。

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

まず最初の3行の実行直後では以下の図の様な状態になります。
fib(arity=1)のconsセルのcdr部に各パターンが登録されます。そして、car部に自分自身をコンパイルするバイトコードが入ります。

一番最初のfib(10)のコールではこのコードが実行される為、自分自身のJITコンパイル処理が走り、car部を上書きするので、2度目以降のfibのコールではコンパイル済みコードが実行される事になります。今回の例のfibの定義では、テーブルジャンプを使ったマッチングを行うバイトコードが生成されます。
このような仕組みにしたのは以下の理由からです。

  • 関数定義を追加する度にリコンパイルするのは無駄。
  • 関数コールの度にコンパイル済みかチェックするオーバヘッドは嫌(だったので自己上書き式に)。


ブロック内でfibを再定義すると下図の様に新たな関数実体が作られて、最初のコールでコンパイルが走ります。ブロックから抜けると、識別子表からpopされるので、再び外側の定義が有効になるという仕組みです。

性能についてのメモ

とりあえずfib(36)だけ。以下のコードでCore 2 Duoマシンで4.66秒程度だった。JITコンパイルに0.1秒未満のオーバヘッド。

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

print_int(fib(36))

以前の結果に比べ5倍ほど遅くなっています。原因は整数加減算が外部関数のコールになっている事で解決策はプリミティブ関数のインライン化とネイティブJITです。次の世代のコンパイラで多分やります。