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

前回は悩みまくった結果、リファクタリングをすることにしました。今回はリファクタリングをした結果どうなるのでしょうか？うまくいったんでしょうか？

## リファクタリング

ここ数日はリファクタリングもかねてパターンマッチの作り方をもう一度書いていました。

リファクタリングの内容は以下の通りです。

- 無駄な処理は消す
- 構文木のメソッドは消す。toStringはただの関数にする
- 構造体の登録処理が何処で行われるかはっきりする

まだまだ、分かりにくい部分はあると思うのですが、前よりはずっと分かりやすくなったと思います。そして、LLVM用レジスタマシンコンパイラの作成経験が１回から２回になりました。経験値が２倍になったわけで大きな自信に繋がりました。

## 構造体の初期化

改めて、構造体の初期か処理を作りました。処理がスッキリして、頭もスッキリしました。まず、初期化の値はETupleで初期化します。

### 型の宣言

```Scala
case class ETuple(t:T,ls:List[E]) extends E
```

### テストの追加

```Scala
EPrint(Ti(32), EField(Ti(32), "aa", "b")),
// 構造体初期化リテラル
EVal(TStr(List(("a", Ti(32)), ("b", Ti(32)))), "ab",
  ETuple(TStr(List(("a", Ti(32)), ("b", Ti(32)))),
    List(ELdc(Ti(32),123),ELdc(Ti(32),456)))),
EPrint(Ti(32), EField(Ti(32), "ab", "a")),
EPrint(Ti(32), EField(Ti(32), "ab", "b"))
```

kNormalのEValの修正

```Scala
case EVal(t:TStr, id, null) =>
```
の箇所を以下に書き換えました。

```Scala
       case EVal(t:TStr, id, tpl) =>
           :
         tpl match {
           case ETuple(_,ls) =>
             for((e,(name,t)) <- ls.zip(t.types)) {
               f(EAssign(t, EField(t, id, name), e))
             }
           case null =>
         }
```

以上！簡単でした。なんで、こんなに悩んでたんだろうと思うくらい簡単でした。リファクタリングしてよかった。

## ヴァリアントの初期化


この勢いで、ヴァリアント型の初期化も作ってしまいましょう。ヴァリアントの初期化については新しく書いている作り方のほうに書きながら作業しました。

ASTを定義します。

```
case class ETag(t:T,id:String,ls:List[E]) extends E
```

ポインタの型を追加します。

```
case class Tp(t:T) extends T
```

次に、テストコードに以下のコードを追加します。

```
EVal(TVariant(List(
    "A"->TStr(List("a"->Ti(32))),
    "B"->TStr(List("a"->Ti(32), "b"->Ti(32)))
  )),
  "data2",
  ETag(TVariant(List(
    "A"->TStr(List("a"->Ti(32))),
    "B"->TStr(List("a"->Ti(32), "b"->Ti(32)))
    )),
    "B",
    List(
      ELdc(Ti(32), 555),
      ELdc(Ti(32), 777)
  ))
)
```

そして、kNormalの ```case EVal(t:TVariant,…)```の箇所を修正します。構造体のときの追加内容と似たような感じですが、やっつけなので大分複雑になってしまいました。ということでここのソースは飛ばします。

LLBitCastの追加

```
case class LLBitCast(did: Id, st:T, sid:Id, dt:T) extends LL
```

constFoldにLLBitCast追加

```
case (ls, l @ LLBitCast(did, st, sid, dt)) => l.copy(m(did),st,m(sid),dt) :: ls
```

lltにTp(t)を追加

```
case Tp(t) => llt(t) + "*"
```

サイズ計算はTp(t)を追加

```
case Tp(n) => 8
```

emitでLLBitCastの出力処理を追加する。

```
case LLBitCast(did: Id, st:T, sid:Id, dt:T) =>
         asm(llid(did) +" = bitcast " + llt(st) + " " + llid(sid) + " to " + llt(dt))  
```

以上がヴァリアントの作成でやった事です。最も重要なのは汚くてもまずは作るということでした。

## モチベーション

この奮闘記はモチベーションが下がったとき用の物というか、悩みを書く感じになっているので非常にまどろっこしいと思うのです。

でも、何を悩んだかってことも、記録に残ってても良いんじゃないかと思うのです。と自分に何回も言い聞かせることで、モチベーションを維持しようとしてます。

## パターンマッチ構文について考える

また、パターンマッチ構文について考えます。

switch構文だけで、パターンマッチが書ければ最高です。でも、最初から今のソースと混ぜて書くと混乱しそうです。そこで、マッチ構文は別に作ることにしました。

とにかく、分けて実装してみて後から整理する作戦です。

```Scala
case class EMatch(t:T, d:E, cases:List[(ETag,E)]) extends E
```
以上の構文木を作ってうまくやることだけを考えます。

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

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

以上のようなプログラムが動けばいい訳です。Scalaのclassで表すと以下のようになります。

```Scala
 EMatch(t, data, List(
   ETag(t, "A", List(EId("x"),EId("y"))) -> EBlock(Tv,List(EPrint(x),EPrint(y))),
   ETag(t, "B", List(EId("x"))) -> EBlock(Tv,List(EPrint(x)))
 ))
```

タグを別なデータで表すことも考えましたが、ETagを使うことにしました。

テーブルジャンプする箇所では以下の処理をします。

1. dataのタグを取り出します。
2. タグの番号でジャンプし、ジャンプ先は0,1と番号を振ります。

AかBかでとび先が変わるわけです。

ジャンプ先では以下の処理を行います。

1. 値を取り出して、変数にバインディングする。
2. 変数をバインディングしたあと、式をコンパイルする。

バインディングの変数名が他の変数名と被った場合も正しく動作するようにしたいところですが、どうするかが問題です。

ローカル変数をCで書いて、LLVMに変換して結果を見て見ましょう。

```C
#include <stdio.h>
void print_i(int a) {
  printf("%d¥n", a);
}
int main() {
  int a = 1;
  {
    int a = 2;
    print_i(a);
  }
  print_i(a);
  return 0;
}
```

そしてコンパイルして、結果のうち必要な所を見て見ます。
名前がどうなってるのかを見る訳です。

```LLVM
define i32 @main() nounwind ssp {
entry:
  %retval = alloca i32                            ; <i32*> [#uses=2]
  %0 = alloca i32                                 ; <i32*> [#uses=2]
  %a = alloca i32                                 ; <i32*> [#uses=2]
  %a1 = alloca i32                                ; <i32*> [#uses=2]
  %"alloca point" = bitcast i32 0 to i32          ; <i32> [#uses=0]
  store i32 1, i32* %a, align 4
  store i32 2, i32* %a1, align 4
  %1 = load i32* %a1, align 4                     ; <i32> [#uses=1]
  call void @print_i(i32 %1) nounwind ssp
  %2 = load i32* %a, align 4                      ; <i32> [#uses=1]
  call void @print_i(i32 %2) nounwind ssp
  store i32 0, i32* %0, align 4
  %3 = load i32* %0, align 4                      ; <i32> [#uses=1]
  store i32 %3, i32* %retval, align 4
  br label %return

return:                                           ; preds = %entry
  %retval2 = load i32* %retval                    ; <i32> [#uses=1]
  ret i32 %retval2
}

```

a1とaと別な名前がついていますね。

```LLVM
  %a = alloca i32                                 ; <i32*> [#uses=2]
  %a1 = alloca i32                                ; <i32*> [#uses=2]
```

このように、同じ名前の変数ですが、スコープに寄って意味の変わる変数に別名を与える事を、α変換といいます。パターンマッチ構文を作るにはα変換が必要だといえるでしょう。

α変換は必要ないと考えていたのですが、残念ながら必要になりました。実は前に作ってみていたものがあるので、それを改造して使う事にします。

前にα変換を作ったのは以下のようなプログラムをかけたらいいなと思って作ってみた物です。

```Scala
val a = 1
val a = a + 2
print_i(a)
```

書き換え不能な変数しか使っていないのだけど、書き換え可能な変数のようにかけたら嬉しいですよね。こんな機能をα変換をすれば作れるのです。

α変換の元のソースはすぐ手に入ったので、改造して行きます。

α変換のメインとなる関数fの型は以下のようになります。

```Scala
  def f(e: E, env: Map[String, String]): (E, Map[String, String])
```

α変換の処理内容は以下のようになります。

1. 式と環境を受け取って、式と環境を返します。最初環境は空です。
2. 変数が現れたら、環境に保存します。
3. さらに変数が現れたら、環境に保存し、環境内に既に同じ名前があるので違う名前に付け替え、付け替えた名前を保存しておきます。
4. 変数を参照する箇所があった場合は、環境から値を取り出して、置き換えます。

以上の操作を構文木全てに対して行えばα変換はできます。

パターンマッチや、C言語のブロックは、一時的な名前を作る事になります。
こういう場合は、式が終わった段階でその環境は捨てて、今まで使っていた環境を使う事にします。

```Scala
      case e @ EVal(t: T, id: String, a) =>
        val (a1,env1) = if (a == null) (null, env) else f(a, env)
        val id2 = if (env.contains(id)) genid(".") else id
        (e.copy(t, id2, a1), env1 + (id -> id2))
```

以上のように、EValは変数に値を束縛するので、環境に名前が含むようにしてあります。右辺は前の環境を使い、左辺は新しい環境になるわけです。

EIdは変数の参照なので、```find(id, env)```でenvから値を取り出して使っています。

```Scala
      case e @ EId(t: T, id: String) => (e.copy(t, find(id, env)), env)
```

find関数の定義は以下のようになります。

```Scala
  def find(id: String, env: Map[String, String]): String = {
    if (env.contains(id)) env(id) else id
  }
```

他の式も全てにわたって、環境を受け渡しながら書くだけです。
出来上がったら、以下のようなテストコードを書いてみます。

```Scala
        // alpha test
        EVal(Ti(32), "a", ELdc(Ti(32), 1000)),
        EPrint(Ti(32), EId(Ti(32), "a")),
        EVal(Ti(32), "a", EAdd(Ti(32), EId(Ti(32),"a"), ELdc(Ti(32),2000))),
        EPrint(Ti(32), EId(Ti(32), "a")),
        // alpha block test
        EBlock(Tv, List(
          EVal(Ti(32), "a", ELdc(Ti(32), 5000)),
          EPrint(Ti(32), EId(Ti(32), "a"))
        )),
        EPrint(Ti(32), EId(Ti(32), "a"))
```

疑似コードで書くと以下のようになります。

```Scala
	val a = 1000
	print_i(a)
	val a = a + 2000
	print_i(a)
	{
		val a = 5000
		print_i(a)
	}
	print_i(a)
```

```Scala
1000
2000
5000
2000
```
と表示されたら嬉しい所です。
ところが、最初

```Scala
1000
2000
5000
5000
```
と表示されてしまいました。
なんでかなーと思ってEBlockのところを見てみると、以下のようになっていました。

```Scala
      case e @ EBlock(t: T, ls: List[E]) =>
        val (ls1, env1) = ls.foldLeft(List[E](), env) {
          case ((ls, env), a) =>
            val (a1, env1) = f(a, env)
            ((a1 :: ls), env1)
        }
        (e.copy(t, ls1.reverse), env1)
```

最後の行の```(e.copy(t, ls1.reverse), env1)```でブロックを抜けたときに、ブロック内の変更をそのまま返してます。

envはimmutableなので```env1```を```env```と書き換えて```(e.copy(t, ls1.reverse), env)```とすればブロックを抜けたら元に戻るはずです。

ということで、書き換えて実行してみると、、、。

```Scala
1000
3000
5000
3000
```
と元に戻りました！！なんと、これだけの違いで、スコープの範囲が変えられるんですね。驚きです。

C++の```i```のスコープはforのブロックの外側に影響しましたが、Javaでは内側になったように、スコープはよくよく考えて定義するとより良い言語になるでしょう。

```Scala
for(int i = 0; i < 10;i++) {
}
```

## まとめ

今回は盛りだくさんでリファクタリング、構造体の初期化、ヴァリアントの初期化、そしてα変換を作りました。
次回は、パターンマッチを作ります。

## 参考文献

MinCaml: http://min-caml.sourceforge.net/