パターンマッチ実装奮闘記(1)

はじめに

パターンマッチが出来る簡単なコンパイラをつくりたいんだけど、作った経験がありません。とにかく１度作ってみたいのですがなかなか簡単に作る事が出来ません。

パターンマッチというと、正規表現がありますが、ここで言うパターンマッチとは、データ構造に対するパターンマッチです。関数型言語の多くに実装されていますが、オブジェクト指向の言語にはあまり実装されていません。

インタプリタは作った事があるし、コンパイラの移植もした事があるので、なんとなくは分かってるのです。しかし、一から作れる気がしないのです。

そこで、どうすればいいかを考えていって、なんとか、簡単なパターンマッチの可能なコンパイラをつくってみようと考えました。

具体的な例

まず、パターンマッチの具体的なソースコードを書いてみましょう。
以下に、作ろうとしているパターンマッチの機能を使っているソースコード例を示します。

typedef DATA = enum {
  A(a:Int,b:Int)
  B(a:Int)
}

var data:Data = A(1,2)
switch(data) {
  case A(x,y): print_i(x); print_i(y);
  case B(x):  print_i(x);
}

上記のコードを以下のCプログラムに変換出来する処理を作れればよいのです。

enum DATA { A,B };
struct A { int a; int b; }
struct B { int a; }
struct Data {
  DATA tag;
  union {
    struct A a;
    struct B b;
  }
};

struct Data data;
data.tag = A;
data.a.a = 1;
data.a.b = 2;
switch(data.tag) {
  case A: print_i(data.a.a); print_i(data.a.b); break;
  case B: print_i(data.b.a); break;
}

Javaなら以下のように変換すればよいでしょう。(コンパイル通してないのでおそらくエラーが出るコードです。)

enum DATA { tagA,tagB };
class Data {
  DATA tag;
}
class A extends Data { int a; int b; }
class B extends Data { int a; }

Data data = new A(1,2);
switch(data.tag) {
  case tagA: A a=(A)data; print_i(a.a); print_i(a.b); break;
  case tagB: B b=(B)data; print_i(b.a); break;
}

必要な機能

コードの例を書いたので、必要そうな機能を上げてみます。

• union
• enum
• typedef
• バインディング
  • 別名
• キャスト
• パターンマッチ用構文
• ヴァリアント定義
• ヴァリアントデータのコンストラクタ
• ヴァリアントデータのパターンマッチ
• 複雑な構造体の扱いが可能である事
• LLVMベースで考えるか、スタックマシンベースで考えるか？
• GCの有無
• 参照

これらの機能について考えていけば、それなりの結論が得られるはずです。

参照

パターンマッチを行う際には、値のバインディングをする必要があります。

コピーを取るのも手ですが、大きなデータのコピーはコストが高いので出来れば、参照するだけにしたい所です。

要するに、アドレスが一緒の変数が扱えると嬉しい訳です。

Javaならオブジェクトは参照で表されているのでバインディングは比較的楽に実装出来そうです。
以下のコードでは、aとbは同じオブジェクトを表しています。

class A { 
  public A(int a) { this.a = a; }
int a; }

A a = new A(2);
A b = a;

JavaのようなGCのついたVM上のスタックマシンを出力するコンパイラ作るのであれば、パターンマッチは作りやすいでしょう。

簡単な例ではありませんが、ScalaはJVM上でパターンマッチを実装した言語です。

最終目標とする言語はどんな言語だったか？

最終的に作成する言語は、ネイティブコンパイラです。
だから、ネイティブコンパイラをつくる場合の方法も考えてみましょう。
LLVMはネイティブコンパイラ用のレジスタマシンなバーチャルマシンです。
型付きのレジスタ数の制限がないアセンブラを出力すれば、バックエンドの処理はLLVMに任せて、様々な最適化処理を行った後、CPU個別のアセンブラを出力してくれます。
基本ブロックを意識したアセンブラなので、通常のアセンブラより制限は厳しいです。しかし、楽にコンパイラをつくる事が出来ます。

LLVMを検討する

LLVMを使って、aと書いて、a_.aの事にするような事が出来れば良いかもしれません。
EVar("a")をEField("a_","a")のように変換できればよいのかもしれないのです。
参照しかできないのであれば、値を取得だけしてしまって使えば良いでしょう。

unionとサイズ計算

今作っているコンパイラにunionはありません。
unionが無い場合に困る事は、サイズの計算です。

スタック上にデータ領域を取る事を考えると、サイズの算出は必要なのです。
そこで、LLVMでunionはどのように表現されているかを調べてみる事にしました。
C言語でunionのコードを書き、LLVMのコードに変換して結果を見るのです。
そうすれば、unionのコードがLLVMでどのように表されているかが分かります。
変換してみた所、unionの型はunionされている中で、一番サイズが大きい型になっていました。

そして、unionの値を取得しようとしている所では、castを使う事で切り替えを行うようにしてありました。

%struct.A = type { i32 }
%struct.B = type { i32, i32 }
%struct.Data = type { i32, %union.anon }
%union.anon = type { %struct.B }

この手法を使えば、unionを使わなくても、スタック上にデータ領域を取る事が出来ます。

LLVMにエンコーディングする事を考える。

LLVMを使って簡単にパターンマッチが出来そうです。
C言語でまず、やりたい事を書きます。

#include <stdio.h>
enum DataTag { tagA,tagB };
struct A { int a; };
struct B { int a; int b; };
struct Data {
  enum DataTag tag;
  union {
    struct A a;
    struct B b;
  };
};
void print_i(int i) { printf("%d\n", i); }
int main() {
  struct Data data;
  data.tag = tagB;
  data.b.a = 1;
  data.b.b = 2;
  switch(data.tag) {
    case tagA: print_i(data.a.a); break;
    case tagB: print_i(data.b.a); print_i(data.b.b); break;
  }
  return 0;
}

以上のコードを、LLVMに変換します。
LLVMに変換したものから、必要な所を抜き出してみましょう。

まず、以下の構造体がヴァリアント型を表す為に使われています。

%struct.A = type { i32 }
%struct.B = type { i32, i32 }
%struct.Data = type { i32, %union.anon }
%union.anon = type { %struct.B }

main関数は以下のように、表せるでしょう。

define i32 @main() nounwind ssp {
entry:
  ; dataをスタック上に取る
  %data = alloca %struct.Data                     ; <%struct.Data*> [#uses=7]

  ; data.tagのアドレスを取り出して値1を設定
  %data.tag = getelementptr inbounds %struct.Data* %data, i32 0, i32 0 ; <i32*> [#uses=1]
  store i32 1, i32* %data.tag, align 4

  ; data.tagのb.aに1を設定
  %data.uni = getelementptr inbounds %struct.Data* %data, i32 0, i32 1 ; <%union.anon*> [#uses=1]
  %data.b = getelementptr inbounds %union.anon* %data.uni, i32 0, i32 0 ; <%struct.B*> [#uses=1]
  %data.b.a = getelementptr inbounds %struct.B* %data.b, i32 0, i32 0 ; <i32*> [#uses=1]
  store i32 1, i32* %data.b.a, align 4

  ; data.tagのb.bに2を設定
  %data.b.b = getelementptr inbounds %struct.B* %data.b, i32 0, i32 1 ; <i32*> [#uses=1]
  store i32 2, i32* %data.b.b, align 4

  ; data.tagの値を取り出して
  %data.tag_v = load i32* %data.tag, align 4                      ; <i32> [#uses=1]
  ; switch
  switch i32 %data.tag_v, label %bb2 [
    i32 0, label %bb
    i32 1, label %bb1
  ]

; case Aのとき
bb:                                               ; preds = %entry
  ; キャストして
  %data.a = bitcast %struct.B* %data.b to %struct.A*      ; <%struct.A*> [#uses=1]
  ; 値を取り出し
  %data.a.a = getelementptr inbounds %struct.A* %data.a, i32 0, i32 0 ; <i32*> [#uses=1]
  %data.a.a_v = load i32* %data.a.a, align 4                    ; <i32> [#uses=1]
  ; 関数を呼ぶ
  call void @print_i(i32 %data.a.a_v) nounwind ssp
  ; breakする
  br label %bb2

bb1:                                              ; preds = %entry
  ; b.aの値を取り出して
  %data.b.a_v = load i32* %data.b.a, align 4                    ; <i32> [#uses=1]
  ; 関数呼び出し
  call void @print_i(i32 %data.b.a_v) nounwind ssp
  ; b.bの値を取り出して
  %data.b.b_v = load i32* %data.b.b, align 4                    ; <i32> [#uses=1]
  ; 関数呼び出し
  call void @print_i(i32 %data.b.b_v) nounwind ssp
  br label %bb2

bb2:                                              ; preds = %bb1, %bb, %entry
  br label %return

return:                                           ; preds = %bb2
  ret i32 0
}

以下のプログラムがLLVMの上のプログラムに変換されるようにすれば良いわけです。

typedef Data = enum {
  A(a:Int)
  B(a:Int,b:Int)
}

var data:Data = B(1,2)
switch(data) {
  case A(x,y): print_i(x); break;
  case B(x,y): print_i(x); print_i(y); break;
}

最初は漠然としていたイメージが大分、具体的なものに変わってきました。

まとめ

パターンマッチをどうやって作ると簡単に書けるかを検討してみました。

JVMとLLVMを使う事を検討して、最終目標の言語がC言語と同レベルの言語であることもありLLVMで作ってみる事にしました。
また、LLVMでどのようなコードを出力するかも考えました。

次回以降では、パターンマッチに必要な機能を覚えて行こうと思います。