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

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
		    f
		    (funcall
		     (funcall n f) x)))))
(defun get-church-number (n)
	   (if (zerop n)
	       #'church-zero
	       (succ (get-church-number (1- n)))))
(dotimes (i 10)
	   (format t "~d~%"
		   (funcall
		    (funcall (get-church-number i) #'1+)
		    0)))

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 {
private:
  void* (*callFunc) (void* Object, void* scope);
  void* scope;
public:
  CallableWithArg
  (
   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;
  }
}