fibだとphpやrubyより速いバイナリツリー処理系

MegLevとかで使われてるバイナリツリーのベンチマークでJavaがかなり速かったりします。
ってことで、Javaでバイナリツリー言語を作れば速いんじゃなかろうか？
ってことで、作ってみました。
フィボナッチ関数の計算では、phpやruby1.8.7より速い処理系が出来ました。
パーサはついてませんけど。

import java.util.*;

class BinTree {
	int item;
	Object left;
	Object right;
	BinTree(int item, Object left, Object right) {
		this.left = left;
		this.right = right;
		this.item = item;
	}
	public String toString() {
		switch(item) {
		case INT: return ""+left;
		case SYMBOL: return ""+left;
		case STRING: return "\""+escape(""+left)+"\"";
		case NIL: return "nil";
		default: return i2sym.get(new Integer(item)) + "{"+left+","+ right+"}";
		}
	}

	static final Env sym2i = new Env();
	static final Env i2sym = new Env();
	static final void set(String s, int i) {
		Integer in = new Integer(i);
		sym2i.put(s, in);
		i2sym.put(in, s);
	}
	static final int INT = 0;
	static final int OPADD = 1;
	static final int OPSUB = 2;
	static final int OPMUL = 3;
	static final int OPDIV = 4;
	static final int OPPER = 5;
	static final int OPEQ = 6;
	static final int OPLT = 7;
	static final int OPGT = 8;
	static final int OPLTEQ = 9;
	static final int OPGTEQ = 10;
	static final int OPEQEQ = 11;
	static final int OPNOTEQ = 12;
	static final int OPCRN = 13;
	static final int OPCMM = 14;
	static final int SYMBOL = 15;
	static final int OPSIFP = 16;
	static final int OPMB = 17;
	static final int OPSFUNCTIONP = 18;
	static final int OPMP = 19;
	static final int NIL = 20;
	static final int OPELSE = 21;
	static final int STRING = 22;
	static final int DEFFUN = 23;
	static int symmax;
	public static final BinTree Nil = new BinTree(NIL, null, null);
	static {
		set("INT", INT);
		set("opAdd", OPADD);
		set("opSub", OPSUB);
		set("opMul", OPMUL);
		set("opDiv", OPDIV);
		set("opPer", OPPER);
		set("opEq", OPEQ);
		set("opLt", OPLT);
		set("opGt", OPGT);
		set("opLtEq", OPLTEQ);
		set("opGtEq", OPGTEQ);
		set("opEqEq", OPEQEQ);
		set("opNotEq", OPNOTEQ);
		set("opCrn", OPCRN);
		set("opCmm", OPCMM);
		set("SYMBOL", SYMBOL);
		set("opSifP", OPSIFP);
		set("opMB",OPMB);
		set("opSfunctionP", OPSFUNCTIONP);
		set("opMP",OPMP);
		set("Nil",NIL);
		set("opelse", OPELSE);
		set("STRING", STRING);
		set("DEFFUN", DEFFUN);
		symmax = DEFFUN;
		Nil.left = Nil;
		Nil.right = Nil;
	}
	static final int sym(String s) {
		if (sym2i.containsKey(s)) return ((Integer)sym2i.get(s)).intValue();
		set(s, ++symmax);
		return symmax;
	}

	final int i() {
		if(left instanceof Integer) return ((Integer)left).intValue();
		return 0;
	}
	final boolean b() {
		if(left instanceof Integer) return ((Integer)left).intValue() != 0;
		return false;
	}

	final BinTree l() { return (BinTree)left; }
	final BinTree r() { return (BinTree)right; }


	static final String escape(String s) {
		String rc = "";
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			switch (c) {
			case '\\': rc += "\\\\"; break;
			case '\n': rc += "\\n"; break;
			case '\r': rc += "\\r"; break;
			case '\t': rc += "\\t"; break;
			default: rc += c; break;
			}
		}
		return rc;
	}
	static final BinTree b(int i, Object l, Object r) {
		return new BinTree(i,l,r);
	}

	static final BinTree b(String i, Object l, Object r) {
		return new BinTree(sym(i),l,r);
	}

	static final BinTree i(int i) {
		return new BinTree(INT, new Integer(i), null);
	}
	static final BinTree b(boolean b) {
		return new BinTree(INT, new Integer(b ? -1 : 0), null);
	}
	static final BinTree s(String s) {
		return new BinTree(STRING, s, null);
	}
	static final BinTree id(String s) {
		return new BinTree(SYMBOL, s, null);
	}

	static final boolean isSym(Object o, String s) {
		if(!( o instanceof BinTree)) return false;
		BinTree l = (BinTree)o;
		return (l.item == SYMBOL && l.left.equals(s));
	}

	static final BinTree eval(BinTree t) {
		int item = t.item;
		switch (item) {
		case INT:     return t;
		case OPADD:   return i(eval(t.l()).i() + eval(t.r()).i());
		case OPSUB:   return i(eval(t.l()).i() - eval(t.r()).i());
		case OPMUL:   return i(eval(t.l()).i() * eval(t.r()).i());
		case OPDIV:   return i(eval(t.l()).i() / eval(t.r()).i());
		case OPPER:   return i(eval(t.l()).i() % eval(t.r()).i());
		case OPEQ:    return setEnv(t.l(), eval(t.r()));
		case OPLT:    return b(eval(t.l()).i() > eval(t.r()).i());
		case OPGT:    return b(eval(t.l()).i() < eval(t.r()).i());
		case OPLTEQ:  return b(eval(t.l()).i() >= eval(t.r()).i());
		case OPGTEQ:  return b(eval(t.l()).i() <= eval(t.r()).i());
		case OPEQEQ:  return b(eval(t.l()).i() == eval(t.r()).i());
		case OPNOTEQ: return b(eval(t.l()).i() != eval(t.r()).i());
		case OPCRN:   return defEnv(t.l(), eval(t.r()));
		case OPCMM:   return b("opCmm", eval(t.l()), eval(t.r()));
		case SYMBOL:  return getEnv(t);
		case OPSIFP:
			if(eval(t.l()).b()) {
				if (t.r().item == OPELSE) return eval(t.r().l());
				else return eval(t.r());
			} else {
				if(t.r().item == OPELSE) return eval(t.r().r());
				else return Nil;
			}
		case OPMB: if (isSym(t.left, "q")) return t.r(); else return t;
		case OPSFUNCTIONP: return defFun(t); // 関数定義
		case OPMP: return callFun(t); // 関数適用
		default: return t;
		}
	}
	static Env env = new Env();
	static Env pEnv = new Env();
	static final BinTree defEnv(BinTree o, BinTree b) {
		if (o.item == SYMBOL) env.put(o.left, b);
		return b;
	}

	static final BinTree setEnv(BinTree o, BinTree b) {
		if (o.item == SYMBOL) {
			Env env = BinTree.env;
			Env pEnv = BinTree.pEnv;
			Env oEnv = BinTree.env;
			while (env != null) {
				if (env.containsKey(o.left)) {
					env.put(o.left, b);
					return b;
				}
				oEnv = env;
				env = pEnv;
				if(env == null) break;
				pEnv = (Env)env.get("parent");
			}
			oEnv.put(o.left, b);
		}
		return b;
	}

	static final BinTree getEnv(BinTree o) {
		Env env = BinTree.env;
		Env pEnv = BinTree.pEnv;
		Env oEnv = BinTree.env;
		while (env != null) {
			if(env.containsKey(o.left)) {
				return (BinTree)env.get(o.left);
			}
			oEnv = env;
			env = pEnv;
			if(env == null) break;
			pEnv = (Env)env.get("parent");
		}
		return Nil;
	}

	static final BinTree defFun(BinTree o) {// 関数定義
		return b(DEFFUN, o, env);
	}

	static final BinTree callFun(BinTree o) {// 関数定義
		BinTree f = eval(o.l());// 関数
		if(f.item != DEFFUN)
			throw new Error("関数ではないものを関数として呼び出そうとしました。");
		BinTree fn = f.l();
		BinTree arg = eval(o.r());// 引数リストを評価する。,の連続はタプルとして返す。

		Env oldenv = env;
		Env oldpenv = pEnv;
		env = new Env();
		pEnv = (Env)f.right;// 親の環境を設定

		BinTree prm = fn.l();// パラメータリスト
		
		while (prm.item == OPCMM) {
			defEnv(prm.l(), arg.l());
			prm = prm.r();
			arg = arg.r();
		}
		defEnv(prm, arg);
		BinTree rc = eval(fn.r());
		env = oldenv;
		pEnv = oldpenv;
		return rc;
	}

	public static void main(String[] a) {
		System.out.println(eval(b("opAdd", i(1), i(2))));
		System.out.println(eval(b("opAdd", i(1), b("opMul", i(2), i(3)))));
		System.out.println(eval(b("opCrn", id("a"), b("opAdd", i(1), i(2)))));
		System.out.println(eval(s("a")));
		System.out.println(eval(id("a")));
		System.out.println(eval(b("opMB", id("q"),b("opAdd", i(1), i(2)))));
		System.out.println(eval(s("hoge\n")));
		System.out.println(eval(b("opSfunctionP",id("a"), b("opAdd", id("a"), i(1)))));
		System.out.println(eval(b("opMP", b("opSfunctionP",id("a"), b("opAdd", id("a"), i(1))),i(2))));
		System.out.println(eval(b("opMP",
			b("opSfunctionP",
				b("opCmm", id("a"), id("b")), 
				b("opAdd", id("a"), id("b"))
			),
			b("opCmm", i(2),i(3))
		)));

		System.out.println(eval(b("opCrn",
			id("add"),
			b("opSfunctionP",
				b("opCmm", id("a"), id("b")), 
				b("opAdd", id("a"), id("b"))
			)
		)));
		System.out.println(eval(b(OPCRN,
			id("fib"),
			b(OPSFUNCTIONP,
				id("a"),
				b(OPSIFP,
					b(OPEQEQ, id("a"), i(0)),
					b(OPELSE,
						i(0),
						b(OPSIFP,
							b(OPGTEQ, id("a"), i(2)),
							b(OPELSE,
								i(1),
								b(OPADD,
									b(OPMP, id("fib"),
										b("opSub", id("a"), i(1))),
									b(OPMP, id("fib"),
										b(OPSUB, id("a"), i(2))))))))))));
		long start = System.currentTimeMillis();
		System.out.println(eval(b(OPMP, id("fib"), i(30))));
		System.out.println( System.currentTimeMillis() - start + "ms");
	}
}

class Env extends HashMap {
	public String toString() { return "[Env]";}
}