2010-11-14

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

rowl

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

関数本体(バイトコード)
関数定義のリスト(ASTではなくコンパイルした形)

からなる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です。次の世代のコンパイラで多分やります。

2010-11-14

追記

以下の記事の「ブロックローカルで関数定義を再定義できる」という仕組みには問題がありましたのでやめることにしました。
何か別の形で矛盾なく同様の機能が使えるようにしたいと思います。

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  (←×。外側のfib(n-1)、fib(n-2)がブロック内のfib(0)を参照してしまう。)
}

2010-11-06

パターンマッチの実装(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

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

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

2010-10-27

JITアセンブラを作った

rowl

とはいってもx86の機械語を生成するのではなく、VMのバイトコードを生成するやつを作りました。x86のJIT アセンブラは次の世代で作る予定です。
このJIT アセンブラは現在実装中のインタプリタに内蔵するJIT コンパイラで用います。
以下はフィボナッチを計算するコードを動的に生成する例。

(fun jit_fib (n) (
    (var c (make_jitassembler))

    (var ifelse (fresh_label c))
    (var fib    (fresh_label c))

    (set_label c fib)
    (put_arg0 c)
    (put_imm_i3 c)
    (put_if_ge c ifelse)
    (put_imm_i1 c)
    (put_ireturn c)
    (set_label c ifelse)
    (put_arg0 c)
    (put_imm_i1 c)
    (put_isub c)
    (put_call c fib 4)
    (put_arg0 c)
    (put_imm_i2 c)
    (put_isub c)
    (put_call c fib 4)
    (put_iadd c)
    (put_ireturn c)

    (return (int (jitcall (get_code c) (get n))))
    ))

現在のVMだとfib(36)の計算がCore 2 Duoのマシンで0.98秒程度だったのでかなり速いと思います。
後で多機能にしていく分もっと遅くなる筈ですが、ネイティブJITによる高速化の余地があるので最終的には0.5秒くらいを目指します。

実装についてですが、このJIT アセンブラは大部分を自動生成していて100行くらいです。
インストラクション定義にオペランドの型も書いておいて↓

(var vm_instructions `(
    (nop       () @true ())
    (imm_i0    () @true ((vmpush %edx))) ; also used for 'nil'
　  ...
    (call (addr byte)  @nil  (
        (asm "movl %ebx, %eax")
        (asm "addl $4, %eax")
        (vmpush %eax) ; store return point
        (vmpush %edi) ; store base pointer
    ...

こんな感じで関数を自動生成しています↓

(var put_func `(
    (byte   . put_byte)
    (short  . put_short)
    (ushort . put_short)
    (int    . put_int)
    (prim   . put_prim)
    (addr   . put_label)
    ))

(var code 0)
(foreach i vm_instructions (do
    (var args `(c))
    (var body `((put_byte c @code)))
    (var name (symbol2s (car i)))
    (var operands (cadr i))
    (var j 0)
    (foreach opd operands (do
        (var arg (tosym (++ `arg j)))
        (push body `(@(assoc opd put_func) c @arg))
        (push args arg)
        (incr j)
        ))
    (= body (reverse body))
    (= args (reverse args))
    (push code-base `(export fun @(tosym (++ `put_ name)) @args @body))
    (incr code)
    ))

あと、JIT アセンブラは高速に動いてほしいという関係上、ラベルのアドレス計算はバックパッチによる実装を行います。

2010-10-18

演算子順位法によるパーサ

rowl

リンカが問題なく動くようになったので、ようやく次の処理系(rowl1)作りを開始しました。
レキサはこれまでと同じく状態遷移図を手で作成しました。rowl2の開発時にはレキサの自動生成が出来るくらい、言語が高級になっていると良いなぁと思っています。

現在はパーサを作っていますが、試みに演算子順位法を中心にして作っています。演算子順位法は一般的なLALR法より扱える文法が少ないのですが構文解析器の構造がシンプルなので実装が簡単で効率が良いという特徴があります。また、言語の文法は演算子の種類(前置・後置・中置・・)とその演算子順位のみ与えれば決まるので、例えばユーザレベルで新しい構文を追加する機能などを容易に提供できるという利点もあります。

構文はできるだけシンプルにしたいという気持ちがあったのだけど、S式だと見た目が最悪なので試しに演算子順位法でやってみるかというのが動機です。

演算子順位法

演算子順位法は演算子順位文法で記述された文法しか解析できません。つまりA、B、Cを非終端記号として、以下の文法規則が含まれてはなりません。

A → ε
A → …BC…

前者については例えばC言語の

return;

や

for(;;) {
    ...
}

のような物が空式(ε)を含むのでダメです。
後者に関しては、例えばC言語の

int x;

等がダメで、他にはHaskellやO'Camlなどの関数適用

f a

などがダメです。

演算子順位法は上向き構文解析法の一種で、LALR法などと同じくシフト・還元動作を繰り返す事により行われます。
詳しくはhttp://www.amazon.co.jp/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%81%AE%E6%A7%8B%E6%88%90%E3%81%A8%E6%9C%80%E9%81%A9%E5%8C%96-%E4%B8%AD%E7%94%B0-%E8%82%B2%E7%94%B7/dp/4254121393やWeb上の資料を参照してください。

rowl1の文法

演算子文法はさすがに表現力が低すぎるので、一部だけ先読みを行うなどの処理をしています。
とりあえず暫定的に決めた物を書きます。ちゃんとした定義はもう少し出来あがってから。

コメントは#で始まる行
項 (Term)
- リテラル：整数(2進・8進・16進・10進)、浮動小数点数、キャラクタ、文字列、シンボル
- タプル: (Expr, Expr, ...)
  - ただし(Expr)はタプルではなくExprと同じ
- 配列: [Expr, Expr, ...]
- リスト: {Expr Expr ...}
  - カンマはない。演算子文法でないので特別処理。
- 呼び出し: Term(Expr, Expr, ..)
- 添え字: Term[Expr, Expr, ..]
式 (Expr)
- 項
- 中置演算子式 : Expr op Expr
- 前置演算子式 : op Expr
- 後置演算子式 : Expr op
  - 中置演算子は左右どちらかの結合性を持つ。組み込みの演算子はなくユーザが任意に定義する。演算子は"!$%&=^|@*:;/\\?<>~`"を1つ以上並べたものもしくは識別子。前置演算子と中置演算子は文脈で区別可能なので同じシンボルを使っても良い(前置の-と中置の-など)。後置演算子は2手先読みが必要でめんどいので、ユニークでなければならないとする。
- コンストラクト式: constructor
  Expr Expr ... (n個)
  - 組み込みのコンストラクタはなくユーザが任意に定義する。nは引数の数で、後続のExprは必ずn個ちょうどでなければならない。演算子文法ではないので特別処理。

説明中の「配列」とか「呼び出し」とかあるのはただの名前で、実際にそれをどう処理するかは後のフェーズで決定される。

取り合えずこんな感じでやってみて、可読性などで問題が出たらLALRに書きなおすつもりです。
あと、タプルや配列など括弧で囲まれた式は演算子順位法の中で扱えるので、[| 1, 2, 3 |]みたいなのを新しくユーザが定義できるようにするのも可能ですが、すぐには必要にならなそうなので後で考える事にします。

例

現在までに実装したところだと、

constr "def" 2 1    # (引数2つ、順位1)
constr "return" 1 2
constr "if" 2 3
infixl "<" 4
infixl "+" 5
infixl "-" 5

みたいにコンストラクタと演算子を定義すると、下の様なコードが正しく構文木化できます。

def fib(n) {
    if (n < 3)
        return 1
    return fib(n-1) + fib(n-2)
}

上の文法でリストをカンマ区切りにしなかったのは、こんな感じでリストをコードブロックの為に使う用途を想定している為。
次はデフォルトでロードするコンストラクタ・演算子を設計した後、意味解析の実装です。

2010-10-02

ブートストラッピングの中で起きた問題と解決策

rowl

一か月ほど本業に専念していましたが、Rowlの開発を再開しました。
結構忘れているところがあるので、これまでの経過をまとめます。

これまで実装したものの一覧は下図。

問題1: 機能不足

アセンブリ言語で実装したrowl0は機能が貧弱すぎて、次のステップで一気に高級な機能の実装をするのは大変でした。型推論・クロージャの実装は途中までやって断念。

そこで、コンパイラ実装用の内部用インタプリタ言語を作成することにしました。インタプリタはコンパイラに比べはるかに実装が容易なので、少ない労力で高級な機能を実現できます。S式を用いると非常に容易にインタプリタを作成でき、さらにメタプログラミングも容易にできます。3000行程度で書いたインタプリタで、かなり高級な記述が出来るようになりました。例えば、後で述べるVMのインストラクション定義から、VM本体のeval loopやディスアセンブラの定義を自動生成する等といった事ができるようになりました。

問題2: バックエンドの実装労力が多い

内部用インタプリタで内部用コンパイラを作る訳ですが、レジスタ割り当てやスケジューラの実装はかなり面倒です。そこでスタックマシン型のVMを作成しました。スタックマシン用の命令列は構文木をイテレートしつつ直接生成できるので、実装が大変楽になります。また、ブートストラッピングの世代が進んでもしばらくはこのVMを再利用できます。

後々の事を考えて、このVMにはGCを実装しておきました。

問題3: メモリ不足

内部用インタプリタは実装をサボっていて、ヒープメモリを使い捨てています。従って、それで実装された内部用コンパイラはメモリ不足の為大きなファイルをコンパイルできません。そこで、rowl1のコードを分割コンパイルできるようにする必要があります。そして、そのためにはリンカを作成する必要がありました。現在は主に、このリンカの機能追加中。

問題4: デバッグ

処理系が大きくなって来たらデバッグを考え始めなければなりません。とりあえず、ディスアセンブラを作成しました。コンパイラやVMのデバッグ用のディスアセンブラが、同コンパイラでコンパイルされ同VM上で動くという点がブートストラッピングならではの面白さかもしれません。そのうち、デバッガも作らなければならなくなるはずなんですが、大変すぎるのでしばらくはディスアセンブラのみで乗り切ろうという感じです。