Church Numerals in C++

Posted by & filed under c++, haskell, math.

Church numerals are a representation of natural numbers {0,1,2,…}. The representation encodes each number as a function. Let’s call the function corresponding to natural number N as C(N). C(N) has the following properties :

  • It takes as input, another function f.
  • Its result is a function g.
  • The property of g is such that g(x) = f(f(… N times …(x))

In other words, C(N) takes as input a function and returns another function that just applies the input function N times. It’s easy to represent C(N) in Haskell. Here is a Haskell function ‘church’, that takes an integer ‘n’ as input and produces the Church numeral for ‘n’.

type Church a = (a -> a) -> a -> a

church :: Integer -> Church a
church 0 = \f -> \x -> x
church n = \f -> \x -> f (church (n-1) f x)

The reverse operation, namely taking a church numeral and producing an integer, is also straightforward. Just pass the function f(x)=x+1 to the church numeral (remember, a church numeral itself is a function taking another function as input), and to the resulting function, pass 0. The result of the application of the latter function should be the integer corresponding to the Church numeral.

unchurch :: Church Integer -> Integer
unchurch n = n (\x -> x + 1) 0

Now, how can we represent Church numerals in C++? First, we need a suitable representation for a “function”. I am sure that there are many ways to do this. I choose to use the “Metafunction class” method in the Abrahams-Gurtovoy book. I represent a function as a C++ (non-templated) class, that has a nested templated class called “apply”. The “apply” class defines a nested type called “result”. As an illustration, here is the “identity” function (f(x) = x) :

struct identity {
  template <typename X>
  struct apply {
    typedef X result;
  };
};

Now, its easy to see that the “apply” of the Church encoding of zero should be the identity function. Here is zero, represented as a C++ Church numeral:

struct Zero {
  template <typename F>
  struct apply {
    typedef identity result;
  };
};

Note the subtlety here. The apply of Zero takes as input, a “function” F, and produces the identity function as result. How do we represent one? The apply function in Church encoding of one should just apply the input function once. So apply can just define result to be the input F as shown below :

struct One {
  template <typename F>
  struct apply {
    typedef F result;
  };
};

It gets interesting for two. The apply of Church encoding of two should apply the input function twice. In this case, instead of using a typedef, we have to define the result explicitly, as shown below :

struct Two {
  template <typename F>
  struct apply {
    struct result {
      template<typename X>
      struct apply {
        typedef typename One::template apply<F>::result::template apply<X>::result prev;
        typedef typename F::template apply<prev>::result result;
      };
    };
  };
};

As Michael Witten points out in the comments, ‘prev’ above can also be simplified to

typedef typename F::template apply<X>::result prev;

But I showed it the long way because it naturally leads to the definition of Church<N>. Just define prev from Church<N-1> as below.

Now we are ready to define the generic version of Church encoding (namely Church<N>), that takes the number to be encoded as a template parameter. We can just extrapolate Two. Instead of applying “One” first to define prev, we can recursively apply Church<N-1> :

template<int N>
struct Church {
  template <typename F>
  struct apply {
    struct result {
      template<typename X>
      struct apply {
        typedef typename Church<N-1>::template apply<F>::result::template apply<X>::result prev;
        typedef typename F::template apply<prev>::result result;
      };
    };
  };
};

The case to terminate recursion, namely Church<0> can be defined as

template<>
struct Church<0> : Zero {};

We need the corresponding Unchurch too, to actually make sense out of the representation. I choose to use the Boost library’s MPL int for this purpose. First, I define the function ‘plusone’, whose apply just increments its input mpl::int_<>:

struct plusone {
  template <typename T>
  struct apply {
    typedef mpl::plus<T, mpl::int_<1> > result;
  };
};

I make Unchurch contain a nested enum that just holds the integer corresponding to the Church numeral ‘N’.

template <typename N>
struct Unchurch {
  enum {value = N::template apply<plusone>::result::template apply<mpl::int_<0> >::result::value };
};

Here is how Unchurch works :

  • First, ‘plusone’ is passed to N to get back the result.
  • result now is a function that applies ‘plusone’ ‘N’ times.
  • I apply this result function on mpl::int_<0>.
  • I define value of Unchurch as the result::value got from the previous application.

Simple, no? With this representation of Church numerals in C++, operations like addition, multiplication, and exponentiation become straightforward, almost one to one mapping from the Haskell implementation. Here is the addition representation is Haskell :

plus m n = \f -> \x -> m f (n f x)

and the implementation in C++ :

template <typename M, typename N>
struct Plus {
  template <typename F>
  struct apply {
    struct result {
      template<typename X>
      struct apply {
        typedef typename N::template apply<F>::result::template apply<X>::result tmp1;
        typedef typename M::template apply<F>::result::template apply<tmp1>::result result;
      };
    };
  };
};

Similarly, the implementations of multiply and exponentiation in Haskell :

mult m n = \f -> n (m f)
exp m n = n m

and in C++ :

template <typename M, typename N>
struct Mult {
  template <typename F>
  struct apply : N::template apply<typename M::template apply<F>::result> {};
};

template <typename M, typename N>
struct Exp : N::template apply<M>::result {};

Spend some time looking at Mult and Exp. It is amazing how functional programming is quite straightforward in C++, once you have the right representation of things. Go ahead and try out the following :

cout << Unchurch<Church<42> >::value << endl;
cout << Unchurch<Plus<Church<1>, Church<41> > >::value << endl;
cout << Unchurch<Mult<Church<6>, Church<7> > >::value << endl;
cout << Unchurch<Exp<Church<2>, Church<9> > >::value << endl;

You might have to pass -ftemplate-depth-1024 to g++ to get this compiled.

7 Responses to “Church Numerals in C++”

  1. Michael Witten

    For the C++ implementation, you’ve chosen a compile-time-evaluated (“template metaprogramming”) version; does the Haskell version also evaluate the results at compile-time?

    Also, you should use “\n” rather than std::endl because the latter (std::endl) is essentially the exact same thing as “\n” except that the output stream is also flushed (and NO, “\n” is not platform specific).

    Also, I realized after the fact that the definition of Two was meant to motivate the definition of the gernalized Church; however, you never made that point explicit, so I got stuck on Two for a bit, and I think you should present only a simplified version first. In particular, look at the two typedef lines of the inner-most ‘apply’ struct:

    typedef typename One::template apply<F>::result::template apply<X>::result prev;
    typedef typename F::template apply<prev>::result result;

    I got distracted by thinking that the first line could be simplified by removing the first ‘template’ qualifier (the compiler knows the members of One), giving:

    /* (0) */ typedef typename One::apply<F>::result::template apply::result prev;

    Then I thought it’s possible to simplify that further, since it is known that One::apply<F>::result is just F, yielding:

    /* (1) */ typedef typename F::template apply<X>::result prev;

    I think a lot of people will be able to follow your development better if you present (1) first as an ‘obvious’ definition of Two, then present (0) as a more generalized form (don’t even bother with the original version that uses a superfluous ‘template’ qualifier), and then present the general Church.

  2. Manjunath

    @Michael : Good observations. Haskell does evaluate it at run time. And I do agree that there are spurious “template apply” in many places. Will clean up the code and the exposition a little shortly.

  3. Michael Witten

    @Manjunath

    Unfortunately, my comment was stripped of angle brackets (‘<’ and ‘>’ — I hope those are interpreted properly). Perhaps you could add them in for me properly, so that my comment makes more sense. Thanks!

  4. Speaker-to-Animals

    The set you’ve described is the set of whole numbers, not the set of natural numbers. Natural numbers are the set of {1,2,3,…} and do not include zero.

Leave a Reply

  • (will not be published)

XHTML: You can use these tags: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*