JavaScriptで書いたif if文でのパターンマッチコンパイラ


## はじめに

if if 文でいわゆる関数型言語のパターンマッチングのコンパイラをJavaScriptで作ってみました。

言語処理系を書いてないなぁと思って、JavaScriptでパターンマッチングを書いてみたわけです。関数型言語もいいけど、なんか、飽きたんだよね。最近JavaScriptを書く機会が多いのでJavaScriptが楽しくなって来たのかもしれない。で、なんとなく、パターンマッチのコンパイラ書けないかなと思って挑戦したら書けてしまいました。という事で、ご報告させていただきます。

## 完成までの道のり

最初は、JavaScriptでパターンマッチのインタプリタを書いてみてました。これを展開すれば良いだけのはずなのだけど、難しいんだよなぁ。とりあえず、関数合成だ！みたいに思って、配列に関数を作って突っ込んで呼び出す形にしてみる。でも、肝心のパターンマッチ部分が展開されていない。これでは意味があんまりないぞと思う。結局作り直しで、文字列を吐き出して、evalする方向に方針転換する。ちょっと作っては、修正ちょっと作っては、修正ってやってたら出来た。

おいおい、ゴニョゴニョ弄り回してたら、できちゃったぞ！

## 機能

今回のパターンマッチコンパイラは、複雑な構造を持ったパターンマッチに対応しています。
対応しているデータ構造は、number, string, objectです。また、変数へのバインディングも実装しています。

```javascript
var evl2 = cmatch(
    [{op:"+",left:_("l"),right:_("r")}, function(e) {
        return evl2(e.l) + evl2(e.r);
    }],
    [{op:"*",left:_("l"),right:_("r")}, function(e) {
        return evl2(e.l) * evl2(e.r);
    }],
    [_,function(e){ return e;}]
);
console.log(evl2({op:"+",left:1,right:{op:"*",left:2,right:3}}));
```

いちど、cmatchにパターンマッチを渡してやると、コンパイルされた関数が帰ってくるので、それを使うと色々処理出来るわけです。

コンパイル結果は以下のようになります。

```javascript
var f = function(e) {
	if (typeof e == 'object' && "op" in e && "left" in e && "right" in e && e.op == "+") {
		return (function (e) {
		return evl2(e.l) + evl2(e.r);
	}({l:e.left,r:e.right}));
	}
	if (typeof e == 'object' && "op" in e && "left" in e && "right" in e && e.op == "*") {
		return (function (e) {
		return evl2(e.l) * evl2(e.r);
	}({l:e.left,r:e.right}));
	}
	return (function (e){ return e;}(e));
};
```

## 処理内容

処理内容はやりたい事を書いた引数を受け取って、文字列に変換して出力した後、evalで実行して
結果の関数を返却しています。

細かい処理内容ですが、まず、引数配列をグリグリまわります。
で、パターンマッチの要素を１個ずつ処理します。

マッチ内容がワイルドカード’_’だったら、デフォルト動作ということにしたので、関数を実行する文字列を作って終わりです。
条件配列を作っておいて、条件をまとめて、最後にif文にして出力しています。

構造化されている箇所は再帰呼び出しで、バインディングする変数名を渡す事でスッキリとうまくいけました。
コンパイラは再帰呼び出しするけど、コンパイル結果は再帰も何も無しになります。
あとは、バインディング用の変数があれば、バインディング変数に値を入れて、最後に関数を呼び出せば完了です。

## 何故簡単に書けたのか？

おそらく、構文木を作成するのではなくて、文字列を生成したからではないかと思います。
構文木をいじりまわすとなると、結構難しかったのかもしれません。

また、プログラムを最適化するって考えで作ったほうが得意だし楽しいんですよね。
論文を元に実装って考えると何だか難しく感じる。

やった事は要するに、最適化を進めて行って、インライン展開をしただけなわけです。
ループや、再帰的な、関数呼び出しを最適化して行くと、コンパイラになるという。
そう言う考え方のほうが、プログラマ的に凄く分かりやすいし、簡単なんじゃないかなと思う訳です。

論文を読んで、やりたい事が何となくは分かっていた事も大きいと思います。


## 今後

ガード節がないので、ガードを入れるとよいでしょう。関数を２つ渡して、１つ目の関数が要素を受け取って
判定すると良さそうです。

また、現状は上から順番に処理して行っているので、条件の判定の統合が行うとより高速になるはずです。

今回はJavaScriptで書きましたが、関数型言語でコンパイラに組み込むとよりよいでしょう。
いきなり関数型言語に行っても、難しいかもしれないので、JavaScriptで構文木ベースで先に書いてみると
段階的に進めてよいかもしれません。

## まとめ

いろいろ、説明書きましたが、とにかく、一見は百聞にしかずです。
これだけのことで、パターンマッチのコンパイルが出来るのは、凄いと思うのですけど、いかがでしょうか？



```javascript:match.js
function _(e) {
	return new _P(e);
}
function _P(e) {
	this.e = e;
}

function cmatch() {
	function ts(o) {
		if(o instanceof _P) {
			return '_("'+o.e+'")';
		}
		if(o instanceof Object) {
			var s = [];
			for(var i in o) {
				s.push(i+":"+ts(o[i]));
			}
			return "{"+s.join(",")+"}";
		}
		if(o instanceof Array) {
			var s = [];
			for(var i = 0; i < o.length; i++) {
				s.push(ts(o[i]));
			}
			return "["+s.join(",")+"]";
		}
		return JSON.stringify(o);
	}
	var t = "	throw ('cannot match '+e);\n"
	var str = "var f = function(e) {\n";

	for(var i = 0; i < arguments.length; i++) {
		var a = arguments[i];
		var m = a[0];
		var f = a[1];
		if (m == _) {
			str += "	return ("+f.toString()+"(e));\n"
			t = "";
			break;
		}

		var envs = [];
		var conds = [];
		function mat(m, e) {
			switch (typeof m) {
			case "object":
				if (m instanceof _P) {
					envs.push(m.e+":" + e);
					return;
				}
				conds.push("typeof e == 'object'");
				for(var i in m) {
					conds.push('"'+i+'" in '+e+'');
				}

				for(var i in m) {
					mat(m[i], e+"."+i);
				}
				return;
			case "string":
			case "number":
				conds.push(e+" == "+ts(m));
				return;
			}
		}
		mat(m, "e");
		if(conds.length > 0) {
			str += "	if ("+conds.join(" && ")+") {\n";
		}
		str += "		return ("+f+"({"+envs.join(",")+"}));\n";
		if(conds.length > 0) {
			str += "	}\n"
		}
	}
	str += t;
	str += "};\n"
	console.log(str);
	eval(str);
	return f;
}

var evl2 = cmatch(
	[{op:"+",left:_("l"),right:_("r")}, function(e) {
		return evl2(e.l) + evl2(e.r);
	}],
	[{op:"*",left:_("l"),right:_("r")}, function(e) {
		return evl2(e.l) * evl2(e.r);
	}],
	[_,function(e){ return e;}]
);
console.log(evl2({op:"+",left:1,right:{op:"*",left:2,right:3}}));

```