パターンマッチの作り方(1) はじめに

もくじ

1. はじめに
2. LLVM入門
3. 変数
4. 構造体
5. 構造体初期化構文糖
6. ヴァリアントの型と領域取得
7. ヴァリアント初期化構文糖
8. switch構文
9. α変換
10. パターンマッチ構文
11. パーサと型チェック

はじめに

関数型言語のヴァリアントとパターンマッチングはとても便利な機能です。しかし多くの命令型の言語にはパターンマッチングの機能がありません。作り方が難しいのが一因でしょう。筆者もパターンマッチの実装には非常に苦労しました。

パターンマッチ付きのコンパイラ作成の入門記事があれば、もっと簡単に実装できるはずです。この文章では、パターンマッチ付きのコンパイラを作成するのに最小限の機能を使って実装する方法を紹介します。この文章を読めば、今までより簡単にパターンマッチ付きのコンパイラが作成出来るようになるはずです。

パターンマッチとは

パターンマッチというと、正規表現がありますがこの文書で言うパターンマッチとはデータ構造に対するパターンマッチです。関数型言語の多くに実装されていますが、オブジェクト指向の言語にはあまり実装されていません。パターンマッチの具体的なソースコードを以下に示します。

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

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

まず、Dataというenumを定義します。enumはC言語のenumと違って、内部にデータを複数持つ事ができるようにします。Haxeのenumに近いです。

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

そして、enumの値は次のように初期化できます。

var data: Data = B(1, 2) // enum値の初期化

構造を持ったenumに対してswitchする事が出来ます。また、内部のデータを変数に割り当てて参照する事が出来ます。この事をバインディングと呼びます。

switch (data) {
  case A(x): print_i(x); break; 
  case B(x, y): print_i(x); print_i(y); break;// xには 1 yには2が入ります。
}

これらの機能を使う事によって、あるデータ構造から別なデータ構造への変換を非常に短くて分かりやすく書く事が出来るのです。この記事ではこのパターンマッチの機能が使えるコンパイラを作ります。

開発環境

コンパイラを実装するにはLLVMを使います。LLVMはネイティブコンパイラ用のレジスタマシンなバーチャルマシンです。型付きのレジスタ数の制限がないアセンブラを出力すれば、バックエンドの処理はLLVMに任せて、様々な最適化処理を行った後、CPU個別のアセンブラを出力してくれます。基本ブロックを意識したアセンブラなので、通常のアセンブラより制限は厳しいです。しかし、バックエンドを作らずに、非常に素晴らしい機能を使用できます。また、多くの言語がLLVMをバックエンドとして使用しているので、この文章を応用しやすいのではないかと考えています。

また、コンパイラ本体の実装はパターンマッチ構文がありJavaに似た言語のScalaを用います。Javaと同じ文法ではありませんが、見慣れているオブジェクト指向の言語にパターンマッチの機能がついたような言語ですので関数型言語は苦手という方も読みやすいのではないかと思います。

変換例

先ほど上げたパターンマッチを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に変換し、変形すると以下のように書けます。

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

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のコードの例を書いたので使用している機能を以下に示します。

• 変数
• 出力
• ブロック構文
• 構造体
• 構造体の初期化構文糖
• switch文
• α変換
• キャスト
• ヴァリアント定義
• ヴァリアントのコンストラクタ
• ヴァリアントのパターンマッチ構文

変数は構造体の値を保持したり、バインディングした値を保持するのに必要です。出力が出来ないと言語を作っても何がおこったか分かりません。ブロック構文は複数の式を書くのに必要です。構造体の知識はヴァリアントを作る為の基礎になります。構造体の初期化構文糖を作れなければヴァリアントのコンストラクタを作る事は難しいでしょう。α変換はバインディングした値でブロックの外の変数名と同じ変数名を使う為に必要です。キャストはヴァリアントの構造体の切り替えに必要です。ヴァリアントの型の定義が出来ないとヴァリアントは使えません。ヴァリアントのコンストラクタが無ければヴァリアントのデータを作成出来ないので必要ですし、ヴァリアントのパターンマッチ構文が無ければ、パターンマッチが出来る訳がありません。＜最後は当たり前ですけど。

これらの機能があればパターンマッチ構文を作る事が出来ます。

unionとサイズ計算

今作ろうとしているコンパイラでunionは実装しません。unionが無い場合に困る事のはサイズの計算です。スタック上にデータ領域を取る事を考えるとサイズの算出は必要です。ヴァリアントデータのサイズはタグのサイズとヴァリアントの要素を表す構造体の最大のサイズになります。LLVM上で表すには以下のように構造体を作ることで実現出来ます。

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

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

まとめ

パターンマッチ付きのコンパイラをどうやって作ると簡単に書けるかを検討ました。また、LLVMでどのようなコードを出力するかも考えました。次回以降では、パターンマッチに必要な機能を作成していきます。

参考文献

• [1]M.Hiroi: Common Lisp 入門 記号のパターンマッチング
• [2]大堀 淳　纓坂 智: 表示的意味論に基づくパターンマッチ コンパイル方式の構築と実践
• [3]大和谷 潔: パターンマッチ
• [4]LLVM入門
• [5]