Lisp Evaluator C++ TMP

lisp.cpp

template <typename T> auto declval() -> T&&;
template <class... Args> using eval = decltype(evaluate(declval<Args>()...));
template <class... Args> using eval2 = decltype(evaluate2(declval<Args>()...));
template <class... Args> using eval3 = decltype(evaluate3(declval<Args>()...));

template <class...>
struct L{};

// the datatype cons (not the keyword)
template <class, class>
struct cons{};
// a number
template <auto Val>
struct Number {
    constexpr static auto value = Val;
};

struct T{};
struct NIL{};
struct QUOTE{};
struct CONS{};
struct LIST{};
struct CAR{};
struct CDR{};
using REST = CDR;
using FIRST = CAR;
struct NULL{};
struct ATOM{};
struct LISTP{};
struct NUMBERP{};
struct IF{};
struct COND{};
struct EQUAL{};
struct AND{};
struct OR{};
struct NOT{};

auto evaluate(T) -> T;
auto evaluate(NIL) -> NIL;
template <auto Val>
auto evaluate(Number<Val>) -> Number<Val>;
template <class Inner>
auto evaluate(QUOTE, Inner) -> Inner;
template <class Car, class Cdr>
auto evaluate(CONS, Car, Cdr) -> cons<Car,Cdr>;

auto evaluate(LIST) -> NIL;
template <class First, class... Rest>
auto evaluate(LIST, First, Rest...) -> cons<eval<First>, eval<LIST, Rest...>>;

auto evaluate(CAR, NIL) -> NIL;
template <class List>
auto evaluate(CAR, List) -> eval<CAR, eval<List>>;
template <class Car, class Cdr>
auto evaluate(CAR, cons<Car, Cdr>) -> Car;

auto evaluate(CDR, NIL) -> NIL;
template <class List>
auto evaluate(CDR, List) -> eval<CDR, eval<List>>;
template <class Car, class Cdr>
auto evaluate(CDR, cons<Car, Cdr>) -> Cdr;

auto evaluate2(NULL, NIL) -> T;
template <class Any>
auto evaluate2(NULL, Any) -> NIL; 
template <class Any>
auto evaluate(NULL, Any) -> eval2<NULL, eval<Any>>;

auto evaluate2(ATOM, NIL) -> T;
template <class Car, class Cdr>
auto evaluate2(ATOM, cons<Car,Cdr>) -> NIL;
template <class Any>
auto evaluate(ATOM, Any) -> eval2<ATOM, eval<Any>>;

template <class Any>
auto evaluate2(LISTP, Any) -> NIL;
auto evaluate2(LISTP, NIL) -> T;
template <class Car, class Cdr>
auto evaluate2(LISTP, cons<Car, Cdr>) -> T;
template <class Any>
auto evaluate(LISTP, Any) -> eval2<LISTP, eval<Any>>;

template <class Any>
auto evaluate2(NUMBERP, Any) -> NIL;
template <auto V>
auto evaluate2(NUMBERP, Number<V>) -> T;
template <class Any>
auto evaluate(NUMBERP, Any) -> eval2<NUMBERP, eval<Any>>;

template <class Then, class Else>
auto evaluate2(IF, T, Then, Else) -> eval<Then>;
template <class Then, class Else>
auto evaluate2(IF, NIL, Then, Else) -> eval<Else>;
template <class Check, class Then, class Else>
auto evaluate(IF, Check, Then, Else) -> eval2<IF, eval<Check>, Then, Else>;

template <class Value, class... Rest>
auto evaluate3(COND, NIL, Value, Rest...) -> eval2<COND, Rest...>;
template <class Value, class... Rest>
auto evaluate3(COND, T, Value, Rest...) -> Value;
template <class Test, class Val, class... Rest>
auto evaluate2(COND, L<Test, Val>, Rest...) -> eval3<COND, eval<Test>, Val, Rest...>;
template <class... List>
auto evaluate(COND, L<List...>) -> eval2<COND, List...>;

auto evaluate(AND) -> T;
template <class... Rest>
auto evaluate2(AND, T, Rest...) -> eval<AND, Rest...>;
template <class... Rest>
auto evaluate2(AND, NIL, Rest...) -> NIL;
template <class First, class... Rest>
auto evaluate(AND, First, Rest...) -> eval2<AND, eval<First>, Rest...>;

auto evaluate(OR) -> NIL;
template <class... Rest>
auto evaluate2(OR, T, Rest...) -> T;
template <class... Rest>
auto evaluate2(OR, NIL, Rest...) -> eval<OR, Rest...>;
template <class First, class... Rest>
auto evaluate(OR, First, Rest...) -> eval2<OR, eval<First>, Rest...>;

auto evaluate2(NOT, NIL) -> T;
template <typename Any>
auto evaluate2(NOT, Any) -> NIL;
template <class Elem>
auto evaluate(NOT, Elem) -> eval2<NOT, eval<Elem>>;

template <class A, class B>
auto evaluate(EQUAL, A, B)
-> eval<COND, L<
    L<L<AND, L<NUMBERP, A>, L<NUMBERP, B>>, T>,
    L<L<AND, L<ATOM, A>, L<ATOM, B>>, T>,
    L<L<AND, L<LISTP, A>, L<LISTP, B>>, eval2<EQUAL, A, B>>>>;

template <class... Inner>
auto evaluate(L<Inner...>) -> eval<Inner...>;
auto evaluate(L<>) -> NIL;

template <class>
struct Q{};
template <class Inner>
auto evaluate(Q<Inner>) -> Inner;

template <typename, typename> struct is_same {
  static constexpr bool value = false;
};
template <class A> struct is_same<A,A> {
  static constexpr bool value = true;
};
template <class A, class B> static inline constexpr bool is_same_v = is_same<A,B>::value;


using answer = eval<
    L<COND,
      L<
        L<NIL, Number<1>>,
        L<NIL, Number<2>>,
        L<T, Number<3>>,
        L<T, Number<4>>
    >>>;

static_assert(is_same_v<answer, Number<3>>);

struct APPEND{};
struct PLUS{};
struct MINUS{};
struct MULTIPLIES{};
struct DIVIDES{};
struct MODULUS{};
struct EQ{};
struct NEQ{};
struct GT{};
struct GTE{};
struct LT{};
struct LTE{};