Generating Church Numbers with C++, Python and Common Lisp

Thu, 05 Mar 2009 23:27:18 +0000

So. Quite some people seem to be interested in this.

Lets first see python. Well, python is boring, it has a lambda-constructor, it seems. You can sea an implementation of the fac-function with church-numbers here. Church numerals are generated by the line

church = lambda n: reduce(lambda x,y:
  (lambda n: lambda f: lambda x: f(n(f)(x)))(x), range(n), lambda f: lambda x: x)

as far as I see. Well, then, in Common Lisp it is also comparably easy, but since it is a lisp-2, you must use the function „funcall“ for functional objects.

(defun church-zero (f) #'(lambda (x) x))
(defun church-succ (n)
	   #'(lambda (f)
	       #'(lambda (x)
		     (funcall n f) x)))))
(defun get-church-number (n)
	   (if (zerop n)
	       (succ (get-church-number (1- n)))))
(dotimes (i 10)
	   (format t "~d~%"
		    (funcall (get-church-number i) #'1+)

Still, it is easy. It was less easy in C++. I decided to use a similar approach as in Java, because I didnt want something „synthetic“, especially made for this problem, I wanted something „natural“, which could in general be used. So I wrote a class „CallableWithArg“ which has an additional Scope (which you need) and can call a function you give to it in the constructor.

If you happen to meet me, please never never never say anything good about C++. I hate that language! If anybody has a better implementation for Church-Numerals under C++, which are still „natural“ (i.e. not just a for- or while- form or something similar), then feel free to tell me. The problem with the following source is that it shouldnt be used without a garbage collector, since I think a lot must be done to dealloc the Church Numerals after allocation.

#include <iostream>

using namespace std;

class CallableWithArg {
  void* (*callFunc) (void* Object, void* scope);
  void* scope;
   void* (*cF) (void* Object, void* scope),
   void* additional
   ) :
    callFunc (cF),
    scope (additional) {

  void* call (void* Object) {
    return callFunc (Object, scope);

void* c (void* x, void* y) {
  return (void*) (((CallableWithArg*) x)->call(y));

void* elementaryId (void* x, void* scope) {
  return x;

CallableWithArg* id = new CallableWithArg (elementaryId, NULL);

void* elementaryChurchZero (void* x, void* scope) {
  return (void*) id;

CallableWithArg* churchZero =
  new CallableWithArg (elementaryChurchZero, NULL);

void* churchSuccInner (void* x, void* scope) {
  /* expects scope of the form CallableWithArg** with 2 entries n,
     f */
  CallableWithArg** entries = (CallableWithArg**) scope;
  CallableWithArg* n = entries[0];
  CallableWithArg* f = entries[1];
  return c(f, c(c(n, f), x));

CallableWithArg* getChurchSuccInner (void* scope) {
  /* expects scope of the form CallableWithArg** with 2 entries n,
     f */
  return new CallableWithArg(churchSuccInner, scope);

void* churchSuccSecond (void* f, void* scope) {
  /* expects scope of the form CallableWithArg* = n */
  CallableWithArg* n = (CallableWithArg*) scope;
  CallableWithArg** newScope;
  newScope = new CallableWithArg*[2];
  newScope[0] = n;
  newScope[1] = (CallableWithArg*) f;
  return getChurchSuccInner ((void*) newScope);

CallableWithArg* getChurchSuccSecond (void* scope) {
  /* expects scope of the form CallableWithArg* = n */
  return new CallableWithArg(churchSuccSecond, scope);

CallableWithArg* getChurchSucc (CallableWithArg* n) {
  CallableWithArg* newScope = (CallableWithArg*) n;
  return getChurchSuccSecond ((void*)newScope);

void* doIncf (void* n, void* scope) {
  return (void*) (((int) n)+1);

CallableWithArg* getChurchNumber (int n) {
  CallableWithArg* ret = churchZero;
  for (int i = 0; i < n; i++) {
    ret = getChurchSucc(ret);
  return ret;

int main (void) {

  CallableWithArg incf (doIncf, NULL);

  for (int i = 0; i < 100; i++) {
  cout <<
    (int) (c(c((void*) getChurchNumber(i),
		       (void*) &incf),
	     (void*) 0))
       << endl;