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

今回は、switchがそこそこ動くようになったので、パターンマッチを考えます。
1回目ではどのようなコードからどのようなLLVMのコードを出力するかを考えていましたので、そのソースコードを元に考えて行きます。


## コード

１回目で以下のプログラムが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;
}
```

変換後のLLVMのコード

```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
}
```

これを元に、コンパイラ内の内部コードを表現し、コンパイラでどのような処理を行うか考えてみます。


## とにかく、考え始めます。

```
ETypeDef("Data",EEnum(List(
  "A" -> List("a"->TInt(32)),
  "B" -> List("a"->TInt(32),"b"->TInt(32))
))),
```
を以下のコードに変換出来る事がまず必要です。

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

enumを型としてどう取り扱うかは難しい所です。

型の出力が何処で行っているのか、実装を見て見ます。

    T.map.foreach { case (t, n) =>
        asm(n + " = type {" + t.types.map { case (a, b) => b }.mkString(", ") + "}")
    }

こんなコードで今までの構造体は表現されていました。

理屈としては、どこかにコードを埋め込むか、このmapに登録してしまうのが良いんですけど、どっちが良いのか悩みます。
enumは要するに複数の構造体を一気に登録するものと考えるのがいいのかな？


```scala
typedef A = struct { a:Int}
typedef B = struct {a:Int, b:Int }
typedef Data = struct {tag:i32, data:B }
```
でも良いのかな。enumは構造体を複数用意して、順番に並べたもの。
って考えてみるか。

TEnum(t:List[T])

っていう型があって、そこには単純に型名を書くだけで、勝手に展開されればいいのかな。
所詮は、シンタックスシュガーであるとしてしまう。
ちょっと、難しいですよ。一旦休憩しよう。

やっぱり、難航しています。

## もう一度TAPLを見直そう

TAPLではインタプリタではあるけどvariant型を定義していました。

```scala
case class TmCase(sel: Term, branches: List[(String, String, Term)]) extends Term
case class TmTag(tag: String, t: Term, ty: Ty) extends Term
case class TyVariant(els: List[(String, Ty)]) extends Ty
```
パターンマッチ用の型はTyVariantであり、その子となる要素の型も決まっています。
TAPLでは少なくとも、バインドされているレコードの型も別にありました。
だから、EEnumは、複数のTStrと、TVariant(ls:List[(String,T)])を生成する式に変換されるべきなんだろうと思います。


```scala
TmCase(TmTag("c",TmRecord(List("a"->TmZero,"b"->TmString("B")))),List(
  ("a","x",TmVar("x")),
  ("b","k",TmVar("k")),
  ("c","c",TmVar("c"))
))
```

使い方はこんな感じで、"c"タグのレコードを"c"にバインドしています。

うー、混乱しています。
まず、型をうまく変換する事だけ考えよう。
型がうまく変換出来たら、パターンマッチ用の構文を考えよう。switchを拡張するにしても、別シンタックスを用意するにしても。

## まとめ

やっぱりパターンマッチは一筋縄では作れそうにありませんでした。
頭の中がゴチャゴチャしてきたので２つに分けて考える事にしました。

1. 型について
2. パターンマッチ構文について

この回は混乱していた所なので、特に読む必要がないかもしれません。
でも、悩む中でどうやって克服して行ったのかの記録が残っている事は、別の問題があったときにも、応用が利くように思います。
事実だけでは伝わらない、大切な事がこの回では書いたつもりですが、いかがだったでしょうか？

次回は、パターンマッチ用の型についてのみ考えてみたいと思います。