おびなたん☆

■[考][ぷ]C++テンプレートでLisp

一昨日のエントリー（d:id:earth2001y:20060929:p2）でC++のテンプレートがチューリング完全性を備えているということを、見つけた論文から言及した。で、C++テンプレートだけでBrainfuckインタプリタを書こうとして一旦挫折したが、テンプレートの記述が宣言的、関数的な点を考えて、純Lispを書いてみることにした。

純Lispについては、

• はてなキーワードの純Lisp
• 純Lisp - Wikipedia

あたりを、ご参考あれ。ようは、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をしなくて済む方法ないかな・・・。

ツイートする

Permalink | コメント(2) | トラックバック(0)