compile-time schemeの実装
こないだ作ったやつについて、もう少々。
schemeの基本となるデータ型はconsだけど、これは
template<typename CA,typename CD> struct Cons { typedef CA car; typedef CA cdr; };
という型で表現される。CA,CDには任意の型を指定できるわけだが、int型の値はそのままでは入らないので
template<int n> struct int_{ static const int value=n; };
とかいうクラス(boostにあった)で数値を型に変換してやる。Symbolも同様だがテンプレートパラメータに文字列へのポインタを指定したりはできないようで、シンボル名は一文字限定となったのであった。
(f (+ 1 2) x)
という式はC++上で
Cons<Symbol<'f'>,Cons<Cons<Symbol<'+'>,Cons<1,Cons<2,nil>>>,Cons<Symbol<'x'>,nil>>>
という型へ展開される。
さて、式の評価には環境(変数名-値の表)が必要である。これは
template<char c> struct lookup<Symbol<c>> { typedef ... result; };
というstructを内包する構造体であるが詳細は省略。
さて、(+ 1 2 x)という式の実行過程を見てみよう。
この式は
Cons<Symbol<'+'>,Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>>>
という型として表現される。この型を環境とともにEvaluatorに渡してやると、評価結果が型として返ってくる。
typedef ... env; typedef Evaluator<Cons<Symbol<'+'>,Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>>>,env>::result result; cout << to_dynamic<result>::value() << endl; //値の表示に使用。型を引数に取り、対応する値を返す。int_<1>から1を得る関数。
ってかんじで。
ここで、このresultがどのように展開されるかを見てみる。
Evaluatorの定義は、
//eval constant template<typename S,class Env> struct Evaluator {...}; //eval Symbol template<char c,class Env> struct Evaluator<Symbol<c>,Env> {...}; //eval list template<typename F,typename Arglist,typename Env> struct Evaluator<Cons<F,Arglist>,Env> {...};
である。
Evaluator<Cons<Symbol<'+'>,Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>>>,env>
にマッチするのは、定義
template<typename F,typename Arglist,typename Env> struct Evaluator<Cons<F,Arglist>,Env> {...};
であり、
またresultの定義は
typedef typename apply<apply_target,apply_args>::result result;
であり、apply_targetとapply_argsはそれぞれ
typedef typename Evaluator<F,Env>::result apply_target; typedef typename eval_each<Arglist,Env>::result apply_args;
すなわち、
Evaluator<Cons<Symbol<'+'>,Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>>>,env>::result => Evaluator<...>::apply< Evaluator<Symbol<'+'>,env>::result, eval_each<Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>,env>::result > ::result
となる。同様に展開をつづけると、
Evaluator<...>::apply< env::lookup<Symbol<'+'>>::result, eval_each<Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>,env>::result > ::result => (apply第一引数の展開) Evaluator<...>::apply< PrimitiveProc<op_plus_impl>, eval_each<Cons<int_<1>,Cons<int_<2>,Cons<Symbol<'x'>,nil>>,env>::result > ::result => (apply第二引数の展開) Evaluator<...>::apply< PrimitiveProc<op_plus_impl>, Cons<Evaluator<int_<1>,env>::result, eval_each<Cons<int_<2>,Cons<Symbol<'x'>,nil>>,env>>::result> > ::result => (apply第二引数の展開完了) Evaluator<...>::apply< PrimitiveProc<op_plus_impl>, Cons<int_<1>,Cons<int_<2>,Cons<int_<3>,nil>>> > ::result => (apply<Primitiveproc<Func>,Params> とマッチ) op_plus_impl::exec<Cons<int_<1>,Cons<int_<2>,Cons<int_<3>,nil>>>>::result => (op_plus_impl::exec<Cons<int_<n>,Rest>>とマッチ) int_<1 + op_plus_impl::exec<Cons<int_<2>,Cons<int_<3>,nil>>::result::value> => (op_plus_impl::exec<Cons<int_<n>,Rest>>とマッチ) int_<1 + 2 + op_plus_impl::exec<Cons<int_<3>,nil>::result::value> => (op_plus_impl::exec<Cons<int_<n>,nil>>とマッチ) int_<1 + 2 + 3> => (result) int_<6>