Compile-time Church numerals (C++11)

church.h

// Church numerals
namespace Church {

// zero = \f x -> x
template <template <typename> class f, typename x>
using Zero = x;

// succ = \n -> \f x -> f (n f x)
template <template <template <typename> class, typename> class n> struct Succ {
  template <template <typename> class f, typename x>
  using churchValue = f<n<f, x>>;
};

// sum = \m n -> \f x -> m f (n f x)
template <template <template <typename> class, typename> class m, template <template <typename> class, typename> class n> struct Sum {
  template <template <typename> class f, typename x>
  using churchValue = m<f, n<f,x>>;
};

// mul = \m n -> \f x -> m (\y -> n f y) x
template <template <template <typename> class, typename> class m, template <template <typename> class, typename> class n> struct Mul {
  template <template <typename> class f, typename x> struct churchValue1 {
    template <typename y> using L = n<f, y>;
    typedef m<L, x> value;
  };
  
  template <template <typename> class f, typename x>
  using churchValue = typename churchValue1<f, x>::value;
};

}

// Natural numbers
namespace Naturals {

// Natural n = n
template <int n> struct Natural {
  static const int value = n;
};

// Succ n = Natural (n+1)
template <typename n>
using Succ = Natural<n::value + 1>;

}

// conversion from int to Church numerals and from Church numerals to int
namespace conversion {

// churchToInt n = n succ 0
template <template <template <typename> class, typename> class n> struct churchToInt {
  typedef n<Naturals::Succ, Naturals::Natural<0> > naturalValue;
  static const int value = naturalValue::value;
};

// intToChurch n = \f x -> Church.succ (intToChurch (n-1))
template <int n> struct intToChurch {
  template <template <typename> class f, typename x>
  using previousValue = typename intToChurch<n-1>::template churchValue<f, x>;
  
  template <template <typename> class f, typename x>
  using churchValue = typename Church::Succ<previousValue>::template churchValue<f, x>;
};

// intToChurch 0 = Church.zero
template <> struct intToChurch<0> {
  template <template <typename> class f, typename x>
  using churchValue = Church::Zero<f, x>;
};

}

main.cpp

#include <iostream>
#include "church.h"

// five = conversion.intToChurch 5
template <template <typename> class f, typename x>
using five = conversion::intToChurch<5>::churchValue<f, x>;

// three = conversion.intToChurch 3
template <template <typename> class f, typename x>
using three = conversion::intToChurch<3>::churchValue<f, x>;

// mul_5_3 = Church.mul five three
template <template <typename> class f, typename x>
using mul_5_3 = Church::Mul<five, three>::churchValue<f, x>;

// sum_5_3 = Church.sum five three
template <template <typename> class f, typename x>
using sum_5_3 = Church::Sum<five, three>::churchValue<f, x>;

// int_... = conversion.churchToInt ...
const int int_five = conversion::churchToInt<five>::value;
const int int_three = conversion::churchToInt<three>::value;
const int int_mul_5_3 = conversion::churchToInt<mul_5_3>::value;
const int int_sum_5_3 = conversion::churchToInt<sum_5_3>::value;

int main() {
  std::cout << int_five << " * " << int_three << " = " << int_mul_5_3 << std::endl;
  std::cout << int_five << " + " << int_three << " = " << int_sum_5_3 << std::endl;
}

Результат исполнения:

5 * 3 = 15
5 + 3 = 8