Tail Recursion with GCC, Church-Numbers with clang

Wed, 30 Sep 2009 00:58:27 +0000

I just noticed that it is possible to do tail-recursion in C with gcc. Now that is really nice! For example, the following (comparably useless) program can be made working properly:

#include <stdio.h>

int evenp (int x) {
return (x < 2) ? x : evenp (x-2);
}

int main (void) {
printf("%d\n", evenp(10000001));
}

when compiled with the -O2 flag. Without that flag, it causes a segmentation fault, because the compiler doesnt do tail-call-optimization. Well, I am not sure whether this is really useful, and you can really begin to think functional, because C is still very low level.

Since clang is gcc-compatible, it also has the -O2 flag, and also optimizes tail calls away. And it has this cool new language extension, called Blocks. Its a sort of function pointers. The following is a bit hard to compile, but it works:

#include <Block.h>
#include <stdio.h>

void* (^churchZero) (void*) =  ^ (void* x) {
void* (^id) (void*) = ^ (void* y) { return y; };
return (void*) Block_copy(id);
};

void* (^churchSucc) (void*) = ^ (void* n) {
void* (^nf) (void*) = ^ (void* f) {
void* (^nfx) (void*) = ^ (void* x) {
return (void*)(((void*(^)(void*))f)
(((void*(^)(void*))(((void*(^)(void*))n)(f)))(x)));
};
return (void*) Block_copy(nfx);
};
return (void*) Block_copy(nf);
};

void*(^toChurchNumber(int i, void*(^begin)(void*)))(void*) {
if (i == 0)
return begin;
else
return toChurchNumber(i-1, (void*(^)(void*)) churchSucc ((void*) begin));
}

int main (void) {
int(^incf) (int x) = ^ (int x) { return x+1; };
void*(^tentimes)(void*) = toChurchNumber(10, churchZero);
int (^plus100) (int) = (int(^)(int))tentimes(tentimes(incf));

printf("%d\n", plus100(0));
}

Very Nice!

Advertisements