パターンマッチング

http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp22.html
この辺を読んで、javascriptに移植してみました。
これを使えば、うまいことマクロが書けるようになりそうです。
cdrとかの処理がいかにも遅そうなんですが、、、。
とりあえず、動けばいいのよ。動けば。

やっぱり、lispって凄いなぁと思います。
2chのlisp,schemeスレのレベルも高いしなぁ。

<pre>
<script>
// リストの一番最初を返す
function car(list) {
	return list[0];
}

// リストの一番最初を取り除いたものを返す
function cdr(list) {
	var l = [];
	for (var i = 1; i < list.length; i++) {
		l[i - 1] = list[i];
	}
	if (l.length > 1 && l[0] == ".") return l[1];
	return l;
}

//
// 要素はパターン変数か
//
function variablep(pattern) {
	if (pattern == null) return false;
	if (typeof(pattern) == "object") return false;
	return (pattern.charAt(0) == "?");
}

function atom(pattern) {
	if (pattern == null) return true;
	if (typeof(pattern) != "object") return true;
	if (pattern.length == 0) return true;
	return false;
}

function consp(list) {
	if (list == null) return false;
	if (typeof(list) != "object") return false;
	if (list.length == 0) return false;
	return true;
}

//
// パターンマッチング : datum に変数は無し
//
function match (pattern, datum, binding) {
	if (variablep(pattern)) {
		return matchVariable(pattern, datum, binding);
	} else
	if (atom(pattern) && atom(datum)) {
		return matchAtoms(pattern, datum, binding);
	} else
	if (consp(pattern) && consp(datum)) {
		return matchPieces(pattern, datum, binding);
	} else {
		return null;
	}
}

//
// 変数とのマッチング
//
function matchVariable(var_, datum, binding) {
	var value = binding[var_];
	if (value) {
		// 値を使ってもう一度チェック
		return match(cdr(value), datum, binding);
	} else {
		// 変数束縛に追加する
		binding[var_] = datum;
		return binding;
	}
}

//
// アトム同士のマッチング
//
function matchAtoms(pattern, datum, binding) {
	if (pattern == datum ||
		(typeof(pattern) == "object" && pattern.length == 0 && typeof(datum) == "object" && datum.length == 0)) {
		return binding;
	} else {
		return null;
	}
}

//
// リスト同士のマッチング
//
function matchPieces (pattern, datum, binding) {
	var result = match(car(pattern), car(datum), binding);
	if(result == null) {
		return null;
	} else {
		return match(cdr(pattern), cdr(datum), result);
	}
}

Array.prototype.toString = function() {
	var r=[];
	for(var i = 0; i < this.length; i++) {
		if (typeof(this[i]) == "object") {
			r[i] = this[i];
		} else {
			r[i] = "\""+ this[i] + "\"";
		}
	}
	return "[" + r.join(",") + "]";
}

Object.prototype.toString = function() {
	var r=[];
	for(var i in this) {
		if (this[i] instanceof Array) {
			r[r.length] = "\""+ i + "\":"+this[i];
		} else {
			r[r.length] = "\""+ i + "\":\"" + this[i] + "\"";
		}
	}
	return "{" + r.join(",") + "}";
}

function p(str) {
	document.write(str + "\n");
}

function p2(l1,l2) {
	p(l1+","+l2);
	p(match(l1, l2, {})+"<hr />");
}

p2(["太郎","好き", "コーヒー"], ["太郎", "好き", "コーヒー"]);
p2(["太郎","好き", "?x"], ["太郎", "好き", "コーヒー"]);
p2(["太郎","?y", "コーヒー"], ["太郎", "好き", "コーヒー"]);
p2(["花子","?x", "?y"], ["花子", "好き", "紅茶"]);
p2(["太郎","?y", "コーヒー"], ["太郎", "好き", "ココア"]);
p2(["花子","?x", "?x"], ["花子", "好き", "紅茶"]);
p2(["taro","?ou", "ee"], ["taro", "xx", "ee"]);
p2(["for","?a", "?b"], ["for", ["a","b","c"], ["block"]]);
p2(["for",["paren","?a", "?b", "?c"], ["block", "?d"]],
	["for", ["paren", ["=", "i", "0"], "b","c"], ["block", "aa"]]);
p2(["for",["paren","?a", "?b", "?c"], ["block", "?d"]],
	["for", ["paren", ["=", "i", "0"], "b","c"], ["block", "aa", "ee"]]);
p2(["for",["paren","?a", "?b", "?c"], ["block", ".", "?d"]],
	["for", ["paren", ["=", "i", "0"], "b","c"], ["block", "aa", "ee"]]);
</script>
</pre>

結果

["太郎","好き","コーヒー"],["太郎","好き","コーヒー"]
{}
--------------------------------------------------------------------------------
["太郎","好き","?x"],["太郎","好き","コーヒー"]
{"?x":"コーヒー"}
--------------------------------------------------------------------------------
["太郎","?y","コーヒー"],["太郎","好き","コーヒー"]
{"?y":"好き"}
--------------------------------------------------------------------------------
["花子","?x","?y"],["花子","好き","紅茶"]
{"?x":"好き","?y":"紅茶"}
--------------------------------------------------------------------------------
["太郎","?y","コーヒー"],["太郎","好き","ココア"]
null
--------------------------------------------------------------------------------
["花子","?x","?x"],["花子","好き","紅茶"]
null
--------------------------------------------------------------------------------
["taro","?ou","ee"],["taro","xx","ee"]
{"?ou":"xx"}
--------------------------------------------------------------------------------
["for","?a","?b"],["for",["a","b","c"],["block"]]
{"?a":["a","b","c"],"?b":["block"]}
--------------------------------------------------------------------------------
["for",["paren","?a","?b","?c"],["block","?d"]],["for",["paren",["=","i","0"],"b","c"],["block","aa"]]
{"?a":["=","i","0"],"?b":"b","?c":"c","?d":"aa"}
--------------------------------------------------------------------------------
["for",["paren","?a","?b","?c"],["block","?d"]],["for",["paren",["=","i","0"],"b","c"],["block","aa","ee"]]
null
--------------------------------------------------------------------------------
["for",["paren","?a","?b","?c"],["block",".","?d"]],["for",["paren",["=","i","0"],"b","c"],["block","aa","ee"]]
{"?a":["=","i","0"],"?b":"b","?c":"c","?d":["aa","ee"]}
--------------------------------------------------------------------------------