Lazily evaluated type-level lambda calculus in C++

lambda-template-unary.cpp

template<typename T, T x>
struct Value
{
    static constexpr T value() { return x; }
};

template<int n>
using Int = Value<int, n>;

template<bool b>
using Bool = Value<bool, b>;

template<template<typename> class>
struct Template { };

template<typename T>
using result = typename T::Result;



template<typename T>
struct Void
{
    using Result = void;
};

template<typename T, typename X = void>
struct Eval
{
    using Result = T;
};

template<typename T>
struct Eval<T, result<Void<result<T>>>>
{
    using Result = result<Eval<result<T>>>;
};

template<typename T>
using eval = result<Eval<T>>;




template<typename F, typename T>
struct app
{
    using Result = result<app<eval<F>, T>>;
};

template<template<typename> class F, typename T>
struct app<Template<F>, T>
{
    using Result = result<F<T>>;
};



// y :: (a -> a) -> a
// y f = (\x -> f (x x)) (\x -> f (x x))

template<typename F>
struct Fix
{
    template<typename X>
    struct Help
    {
        using Result = app<F, app<X, X>>;
    };
    using Result = app<Template<Help>, Template<Help>>;
};

// test f 0 = 0
// test f n = n + f(n - 1) 

template<typename If, typename Then, typename Else>
struct IfThenElse
{
    using Result = result<IfThenElse<eval<If>, Then, Else>>;
};

template<typename Then, typename Else>
struct IfThenElse<Bool<true>, Then, Else>
{
    using Result = Then;
};

template<typename Then, typename Else>
struct IfThenElse<Bool<false>, Then, Else>
{
    using Result = Else;
};

template<typename N>
struct Add
{
    template<typename M>
    struct Helpme
    {
        using Result = Int<eval<N>::value() + eval<M>::value()>;
    };
    using Result = Template<Helpme>;
};

template<typename F>
struct Test
{
    template<typename N>
    struct Helper
    {
        using Result = IfThenElse<Bool<N::value() <= 0>, 
                                  Int<0>,
                                  app<app<Template<Add>, N>, app<F, Int<N::value() - 1>>>>;
    };
    using Result = Template<Helper>;
};

#include <cstdio>

int main(int, char**)
{
    printf("%d\n", eval<app<app<Template<Fix>, Template<Test>>, Int<9>>>::value());
}

lambda-template-variadic.cpp

template<typename T, T x>
struct Value
{
    static constexpr T value() { return x; }
};

template<int n>
using Int = Value<int, n>;

template<bool b>
using Bool = Value<bool, b>;

template<typename T>
using result = typename T::result;



template<typename T>
struct Void
{
    using result = void;
};

template<typename T, typename X = void>
struct Eval
{
    using result = T;
};

template<typename T>
struct Eval<T, result<Void<result<T>>>>
{
    using result = ::result<Eval<::result<T>>>;
};

template<typename T>
using eval = result<Eval<T>>;



template<template<typename...> class, typename...>
struct Template { };

template<typename Template, typename = void>
struct app_impl
{
    using result = Template;
};

template<template<typename...> class F, typename... Ts>
struct app_impl<Template<F, Ts...>, result<Void<result<F<Ts...>>>>>
{
    using result = ::result<F<Ts...>>;
};

template<typename F, typename... Ts>
struct app
{
    using result = ::result<app<eval<F>, Ts...>>;
};

template<template<typename...> class F, typename... Xs, typename T1, typename T2, typename... Ts>
struct app<Template<F, Xs...>, T1, T2, Ts...>
{
    using result = ::result<app<::result<app_impl<Template<F, Xs..., T1>>>, T2, Ts...>>;
};

template<template<typename...> class F, typename... Xs, typename T>
struct app<Template<F, Xs...>, T>
{
    using result = ::result<app_impl<Template<F, Xs..., T>>>;
};




// y :: (a -> a) -> a
// y f = (\x -> f (x x)) (\x -> f (x x))

/*template<typename F>
struct Fix
{
    template<typename X>
    struct Lambda
    {
        using result = app<F, app<X, X>>;
    };
    using result = app<Template<Lambda>, Template<Lambda>>;
};*/

template<typename F>
struct Fix
{
    template<typename T>
    using ClangFix = Fix<T>; // http://llvm.org/bugs/show_bug.cgi?id=9551
    using result = app<F, app<Template<ClangFix>, F>>;
};

// test f 0 = 0
// test f n = n + f(n - 1) 

template<typename N, typename M>
struct Add
{
    using result = Int<eval<N>::value() + eval<M>::value()>;
};

template<typename F, typename N>
struct Test
{
    using result = ::result<Test<F, eval<N>>>;
};

template<typename F, int n>
struct Test<F, Int<n>>
{
    using result = app<Template<Add>, Int<n>, app<F, app<Template<Add>, Int<n>, Int<-1>>>>;
};

template<typename F>
struct Test<F, Int<0>>
{
    using result = Int<0>;
};

// main = print (fix test 9)

#include <cstdio>

int main(int, char**)
{
    printf("%d\n", eval<app<Template<Fix>, Template<Test>, Int<9>>>::value());
}