Lispを作ってみる、ただしC++テンプレートで

なんか、こじらせた。
これだけではLispになりませんが、もだった材料はそろうみたいなので、できそうな気がします。たぶん。

#include <iostream>

// 等値
template<typename T, typename U> struct Eq       { static const bool condition = false; };
template<typename T>             struct Eq<T, T> { static const bool condition = true;  };

// 論理和
template<typename T, typename U, bool cond = T::condition> struct Or;
template<typename T, typename U> struct Or<T, U, true>  { static const bool condition = true;         };
template<typename T, typename U> struct Or<T, U, false> { static const bool condition = U::condition; };

// 論理積
template<typename T, typename U, bool cond = T::condition> struct And;
template<typename T, typename U> struct And<T, U, true>  { static const bool condition = U::condtion; };
template<typename T, typename U> struct And<T, U, false> { static const bool condition = false;       };

// 分岐
template<bool Condition, typename T, typename U> struct If              { typedef T type; };
template<typename T, typename U>                 struct If<false, T, U> { typedef U type; };

// 終端
struct Nil {};

// リスト
template<typename T, typename U>
struct List
{
    typedef T head;
    typedef U tail;

    static std::ostream& value(std::ostream& out)
    {
        return out << head::value << tail::value;
    }
};

template<typename T>
struct List<T, Nil>
{
    typedef T   head;
    typedef Nil tail;

    static std::ostream& value(std::ostream& out)
    {
        return out << head::value;
    }
};

// 構築
template<typename Head, typename List> struct Cons;
template<typename Head, template<typename, typename> class List, typename H, typename T>
struct Cons<Head, List<H, T>>
{
    typedef List<Head, List<H, T>> type;
};

// CAR
template<typename List> struct Car;
template<template<typename, typename> class List, typename H, typename T>
struct Car<List<H, T>>
{
    typedef H type;
};

// CDR
template<typename List> struct Cdr;
template<template<typename, typename> class List, typename H, typename T>
struct Cdr<List<H, T>>
{
    typedef T type;
};

// 包含検査
template<typename X, typename List>
struct Member
{
    static const bool condition = Or<Eq<X, typename List::head>, Member<X, typename List::tail>>::condition;
};

template<typename _>
struct Member<_, Nil>
{
    static const bool condition = false;
};

// 挿入
template<typename X, typename List> struct Insert;
template<typename X, template<typename, typename> class List, typename H, typename T>
struct Insert<X, List<H, T>>
{
    typedef typename If<
        Member<X, List<H, T>>::condition,
        List<H, T>,
        typename Cons<X, List<H, T>>::type
    >::type type;
};

// 利用例

template<char C> struct Char { static const char value = C; };

typedef List<Char<'A'>, List<Char<'B'>, List<Char<'C'>, Nil>>> ABC;

typedef Insert<Char<'A'>, ABC>::type ABC_;
typedef Insert<Char<'D'>, ABC>::type DABC;

int main(int, char* [])
{
    std::cout << ABC::value << std::endl;
    std::cout << ABC_::value << std::endl;
    std::cout << DABC::value << std::endl;

    return 0;
}

実行結果。

ABC
ABC
DABC