haXeで作るプログラミング言語(3)

こんにちは。今日は３回目になりますね。
RubyのGCを弄り回しているid:authorNariさんがついにRuby1.8のGCの高速化を実現したそうです。
構文木の寿命が基本長いので隔離することで高速化できたようです。
すばらしいですね。継続は力なりだなぁっと思います。

第３回目は、構文木の表現を変えて汎用的にします。
少しふつうの作り方ではなくなって来ますね。
基本的に式は演算子によって式と式をつないだ物として表現します。
演算子はLISPでいうところのCONSセルです。
というような形にします。
今回作ったのは以下のプログラムです。

enum Exp {
	nil;
	num(d:Int);
	op(l:Exp, tag:String, r:Exp);
}

class Calc3 {
	static function main() {
		var c = new Calc3();
		trace(c.eval("1+2*3"));
	}
	function new(){}
	var src:String;
	var token:String;
	var token2:String;

	function lex():String {
		var r : EReg = ~/^[\r\n\t ]*([0-9]+|[+*\-\/])/;
		token2 = token;
		if(r.match(src)){
			token = r.matched(1);
			src = src.substr(r.matched(0).length);
			return token2;
		}
		token = "";
		return token2;
	}
	function eval(str:String):Int {
		var exp = parse(str);
		return execute(exp);
	}
	function parse(str:String):Exp {
		src = str;
		lex();
		return exp();
	}

	function exp():Exp {
		var t = term();
		while(token=="+"||token=="-") {
			var tag = lex();
			t = op(t, tag, term());
		}
		return t;
	}

	function term():Exp {
		var t = fact();
		while(token=="*"||token=="/") {
			var tag = lex();
			t = op(t, tag, fact());
		}
		return t;
	}

	function fact():Exp {
		var t = lex();
		if(t == "(") {
			var t2 = exp();
			if(lex() != ")") throw ("error");
			return t2;
		} else {
			return num(Std.parseInt(t));
		}
	}
	
	function execute(exp:Exp):Int {
		switch(exp) {
		case nil: return 0;
		case num(d): return d;
		case op(l, tag, r):
			switch(tag){
			case "+": return execute(l)+execute(r);
			case "-": return execute(l)-execute(r);
			case "*": return execute(l)*execute(r);
			case "/": return cast(execute(l)/execute(r),Int);
			default: return 0;
			}
		}
	}
}

Calc3.hxml

-swf Calc3.swf
-main Calc3

enum Exp {
	nil;
	num(d:Int);
	op(l:Exp, tag:String, r:Exp);
}

まず、enum Expの定義が減りました。tagに演算子をあらわす文字列を入れます。
1+2*3は

op(num(1),"+", op(num(2), "*", num(3)))

とあらわすようにします。
これに伴い、パーサも短くなります。

	function exp():Exp {
		var t = term();
		while(token=="+"||token=="-") {
			var tag = lex();
			t = op(t, tag, term());
		}
		return t;
	}

このように、構文木を作る箇所のswitch文が除去できます。
termも同様です。

	function term():Exp {
		var t = fact();
		while(token=="*"||token=="/") {
			var tag = lex();
			t = op(t, tag, fact());
		}
		return t;
	}

このようにswitch文が消えました。
もうひとつ変わったのがexecuteです。

	function execute(exp:Exp):Int {
		switch(exp) {
		case nil: return 0;
		case num(d): return d;
		case op(l, tag, r):
			switch(op1){
			case "+": return execute(l)+execute(r);
			case "-": return execute(l)-execute(r);
			case "*": return execute(l)*execute(r);
			case "/": return cast(execute(l)/execute(r),Int);
			default: return 0;
			}
		}
	}

こちらは、このように変えました。
switch文が２つになっています。この辺はhaxeの言語能力不足を感じますけど仕方ありません。
出来れば以下のように書きたかったんですけど、できませんでした。

	function execute(exp:Exp):Int {
		switch(exp) {
		case nil: return 0;
		case num(d): return d;
		case op(l, "+", r): return execute(l)+execute(r);
		case op(l, "-", r): return execute(l)-execute(r);
		case op(l, "*", r): return execute(l)*execute(r);
		case op(l, "/", r): return cast(execute(l)/execute(r),Int);
		default: return 0;
		}
	}

ということで、今回は、構文木の構造を一般化して簡略化しました。
いまのところ数式しか表せませんがシンボル、文字列、を加えることでさまざまな式を表すことが
できるようになります。演算子はオブジェクト指向であれば、メソッドのような役割を担います。
オブジェクト指向はすべてをプリミティブな値かハッシュで表すことができるように、
LISPがCONSセルとプリミティブな値であらわすことが出来るように、
式指向な言語なので式のみですべてを表すことが出来ます。
最適化のためには、いろいろ必要でしょうけど最適化をし始めるときりがありません。
まずは、最小の構成で、言語を作ることを目指して頑張りましょう。