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> {...};

であり、にはそれぞれ, Cons,Cons,Cons,nil>>>, 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>