C++ templates are Church complete without value parameters or recursive definitions

utlc.cpp

#include <type_traits>
#include <iostream>

struct Unit {};

struct Id {
    template <class X> using V = X;
};

struct True {
    template <class X> struct H {
        template <class Y> using V = X;
    };
    template <class X> using V = H<X>;
};

struct False {
    template <class X> struct H {
        template <class Y> using V = Y;
    };
    template <class X> using V = H<X>;
};

struct If {
    template <class B> struct H1 {
        template <class T> struct H2 {
            template <class F> using V =
                typename B::template V<T>::template V<F>;
        };
        template <class F> using V = H2<F>;
    };
    template <class B> using V = H1<B>;
};

/* Integer related convenience constructs */
struct Z { static constexpr int x = 0; };
struct S { 
    template <class N> struct V {
        static constexpr int x = N::x + 1; 
    };
};

template <int n>
struct N {
    static constexpr int x = n;
};

struct Mul {
    template <class X> struct A0 {
        template <class Y> struct A1 {
            static constexpr int x = X::x * Y::x; 
        };
        template <class Y> using V = A1<Y>;
    };
    template <class X> using V = A0<X>;
};

struct IsZero {
    template <class N> using V = std::conditional_t<N::x==0, True, False>;
};

struct Pred {
    template <class N> struct V {
        static constexpr int x = N::x - 1;
    };
};

/* First implementation */ 

struct FactSelf {
    template <class Self> struct A0 {

        // Both if branches needs to be "lazy" by giving it a dummy argument
        struct TBr {
            template <class Dummy> using V = S::V<Z>; 
        };

        template <class N>
        struct FBr {
            template <class Dummy> using V = 
              typename Mul::V<N>::template V<typename Self::template V<Self>::template V<Pred::V<N>>>;
        };

        template <class N> using V =
            typename If::V< IsZero::V<N> >::template V<TBr>::template V< FBr<N> >::template V<Id>;
    };

    template <class Self> using V = A0<Self>;
};

using Fact = FactSelf::V<FactSelf>;

/* Second implementation through Z Combinator */

struct ZComb {
    /* \x . x x */
    struct Self {
        template <class X> using V = typename X::template V<X>;
    };
    
    /* \x. f (\v. x x v) */
    template <class F>
    struct FSelf {

        /* \u. (x x) u */
        template <class X> struct H {
            template <class U> using V = typename X::template V<X>::template V<U>;
        };
        
        /*\x. f (\u. (x x) u) */
        template <class X> using V = typename F::template V< H<X> > ;
    };

    /* (\x. x x)(\x. f (\u. x x u)) */
    template <class F> using V = Self::V<FSelf<F>>;
};

struct FactProto {
    template <class Self> struct A0 {

        // Both if branches needs to be "lazy" by giving it a dummy argument
        struct TBr {
            template <class Dummy> using V = S::V<Z>; 
        };

        template <class N>
        struct FBr {
            template <class Dummy> using V = 
              typename Mul::V<N>::template V<typename Self::template V<Pred::V<N>>>;
        };

        template <class N> using V =
            typename If::V< IsZero::V<N> >::template V<TBr>::template V< FBr<N> >::template V<Id>;
    };

    template <class Self> using V = A0<Self>;
};

using ZFact = ZComb::V<FactProto>;

int main() {
    std::cout << Fact::V<N<10>>::x << std::endl;
    std::cout << ZFact::V<N<10>>::x << std::endl;
    return 0;
}