はじめての処理系実装 その３

リストの実装

ここは結構、肝となる部分かな。
素直に実装するならConsセルクラスを作って、carとcdrプロパティを持たせて、
セル同士を繋いでいくという実装になるだろう。
つまりリストアルゴリズムの自力実装なわけだけど、問題点があって、
評価器の実行時に再帰だらけになる事が容易に想像できること。

普通の処理系の場合は性能を要求されると思うので、
ループで処理した方がいいんだろう。
まぁしかし今回は実用的なものを求めてるわけじゃないので素直な実装にする。

ついでにここで実装ポリシーとして
　「性能度外視で可読性を最重要視する」
というのを決めておこう。
再帰もシンプルに書く。無理に末尾再帰にしようとはしない。
とはいっても綺麗なコードを書ける方でもないので
あくまでも自分の中での事ですが。

では改めてリストの実装。
Listをインターフェースにその実装クラスCons。
ListインターフェースはSymbolExpインターフェースを継承しています。

public class Cons implements List {
	private SymbolExp car = Symbol.NIL;
	private SymbolExp cdr = Symbol.NIL;

	public SymbolExp eval(Context ctx) {
		/* 後回し */
	}
}

とりあえずevalの処理はあとにして保留。

リストの長さを計算するlengthメソッドもあった方が便利かな。

	public int length() {
		return car != Symbol.NIL ? count(this) : 0;
	}
	
	private int count(Cons cons) {
		return (cons.cdr() instanceof Cons)
			? count((Cons)cons.cdr()) + 1 : 1;
	}

デバッグのし易さを考慮してtoStringも実装しておこう。

	public String toString() {
		return "(" + toString(this) + ")";
	}
	
	private String toString(Cons cons) {
		if (cons.cdr instanceof Cons) {
			return cons.car + " " + toString((Cons)cons.cdr);
		} else if (cons.cdr != Symbol.NIL) {
			return cons.car + " . " + cons.cdr;
		}
		
		return cons.car == Symbol.NIL ? "" : cons.car.toString();
	}

さっそく再帰の応酬だが気にしない。

つづいて実行毎の環境（コンテキスト）の実装だけど

このあたりから設計が必要になってるくるかもしれない。
レキシカルスコープのチェインをさせる為に、
親のコンテキストもプロパティとして再帰的に定義。
最初はグローバルスコープのみってのもありだとは思うが。

public class Context {
	private Context parent;
	private Map<Symbol, SymbolExp> namespace = new HashMap<Symbol, SymbolExp>();

	public Context(Context parent) {
		this.parent = parent;
	};

	public SymbolExp set(Symbol sym, SymbolExp value) {
		namespace.put(sym, value);
		return sym;
	}

	public SymbolExp lookup(Symbol sym) {
		if (namespace.containsKey(sym)) {
			return namespace.get(sym);
		} else if (parent != null) {
			return parent.lookup(sym);
		}
		
		return Symbol.createSymbol("nil");
	}
}

とりあえず柔軟に変更する為に最小限で実装。
シンボルの登録と参照のみ。

次は関数かな。