C++テンプレートでLisp
一昨日のエントリー(d:id:earth2001y:20060929:p2)でC++のテンプレートがチューリング完全性を備えているということを、見つけた論文から言及した。で、C++テンプレートだけでBrainfuckインタプリタを書こうとして一旦挫折したが、テンプレートの記述が宣言的、関数的な点を考えて、純Lispを書いてみることにした。
純Lispについては、
あたりを、ご参考あれ。ようは、McCarthyがLispを発明したときのオリジナルで、最小のLisp関数セット。
PL.CT - Pure Lisp on C++ Template
とりあえず、テンプレートの実装。
// cat purelisp.h class NIL { public: typedef NIL eval; }; class T { public: typedef T eval; }; template<class C1, class C2> class CONS { public: typedef typename C1::eval car; typedef typename C2::eval cdr; typedef CONS<C1,C2> eval; }; template<class C> class CAR { public: typedef typename C::car eval; }; template<class C> class CDR { public: typedef typename C::cdr eval; }; template<class C> class ATOM { public: typedef NIL eval; }; template<> class ATOM<T> { public: typedef T eval; }; template<> class ATOM<NIL> { public: typedef T eval; }; template<class C1, class C2> class EQ { public: typedef NIL eval; }; template<class C1, class C2> class EQ<CONS<C1,C2>, CONS<C1, C2> > { public: typedef T eval; }; template<> class EQ<T,T> { public: typedef T eval; }; template<> class EQ<NIL,NIL> { public: typedef T eval; };
分岐と等価、あるいは等価な概念を内包する atom や eq は、そのパラメータの組み合わせごと特殊化テンプレートを与えてあげなきゃいけないのが、やっぱり面倒いのだな。あと、値と関数がクラス、関数適用がインスタンス化(コンパイル)なので、やっぱりデバッグができない。
で、こいつを実際に使ってみるわけだが、ひとつ注意点。テンプレートはインスタンス化しただけではまだ関数のままで、評価がされていない。例えば、
(eq #t (car (cons #t #t)))
というLispの関数をそのまま、
EQ<T,CAR<CONS<T,T> > >
としてもだめで、
EQ<T, CAR<CONS<T,T> >::eval >::eval
と、evalを使って関数を明示的に評価しなければならない。ただし、アトムとコンスセルについては、evalをしてもしなくてもどちらでもよい。(Lispのeval関数とは違います)
先述したように値はクラスなので、結果を可視化するにはC++型情報による何かしらの操作が必要になる。これは、目的に応じて実装すれば良いが、単純に typeid と出力ストリームを使うだけでも使えない事は無い。
上述の関数を実際に使ってみると、
// cat purelisp.cpp #include <iostream> #include "purelisp.h" using namespace std; int main(int argc, char* argv[]) { EQ<T, CAR<CONS<T,T> > > f1(); EQ<T, CAR<CONS<T,T> >::eval >::eval f2(); cout << typeid(f1).name() << endl; cout << typeid(f2).name() << endl; return 0; }
% g++ purelisp.cpp % ./a.out F2EQI4CONSI1TS0_IS1_3NILEES0_IS1_S0_IS1_S1_EEEvE F1TvE %
てな具合。こうすると、eval で明示的評価をしてあげないといけないのがよく分かるかな。
というわけで、純LispをC++テンプレートで書くことで、C++テンプレートがチューリング完全だということが実感できた。純Lispがチューリング完全な理由がよく分かっていないけど。とりあえず、これを出発点にいろいろやってみることもできるわけですね。
evalをしなくて済む方法ないかな・・・。