Tail Recursion with GCC, Church-Numbers with clang

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!

5 Antworten zu Tail Recursion with GCC, Church-Numbers with clang

  1. Ivan Tomac sagt:

    clang does not appear to do tail call optimization with -O2.

    The following code prints 1 for gcc with -O2 and 0 for clang.

    Tested with clang 1.0.1 and gcc 4.2.1.

    ————————–

    #include
    #include

    __attribute__((noinline)) void test(ptrdiff_t *mark)
    {
    ptrdiff_t sp;
    *mark = &sp – mark;
    }

    __attribute__((noinline)) void tcotest(ptrdiff_t *mark)
    {
    test(mark);
    }

    int main(void)
    {
    ptrdiff_t diff1;
    ptrdiff_t diff2;
    ptrdiff_t mark;

    tcotest(&mark); diff1 = mark;
    test (&mark); diff2 = mark;

    printf(„%d\n“, diff1 == diff2);

    return 0;
    }

  2. Ivan Tomac sagt:

    That didn’t come out right. Lets see if I can get markup to work.

    
    #include <stdio.h>
    #include <stddef.h>
    
    __attribute__((noinline)) void test(ptrdiff_t *mark)
    {
        ptrdiff_t sp;
        *mark = &sp - mark;
    }
    
    __attribute__((noinline)) void tcotest(ptrdiff_t *mark)
    {
        test(mark);
    }
    
    int main(void)
    {
        ptrdiff_t diff1;
        ptrdiff_t diff2;
        ptrdiff_t mark;
    
        tcotest(&mark); diff1 = mark;
        test   (&mark); diff2 = mark;
    
        printf("%d\n", diff1 == diff2);
    
        return 0;
    }
    
    
  3. dasuxullebt sagt:

    Thank you for your comment. Sorry for the inconvenience with the Markup – I cant change that, since its WordPress … but I will soon host this blog on an own server.

    Anyway, your example is interesting. I think it may have to do with __attribute__((noinline)), because if I remove this, both return 0. But with the example I posted (evenp) it works with both clang and gcc (without -O2 I get a segfault) it also works with __attribute__((noinline)) – this is strange.

    And even more strange:

    int infloop (int x) {
    if (x == 2) return infloop (x+2);
    if (x == 4) return infloop (x-2);
    }

    int main (void) {
    infloop(2);
    }

    when compiled without -O2, this segfaults. When compiled with -O2, this terminates without doing anything. Also, when adding __attribute__((noinline)). Of course, this never terminates, so if the compiler cant optimize it it simply shouldnt, and if it somehow recognizes that the wont terminate, then it should pass a warning, but why is it not telling anything, and just leaving the stuff out?

    Modifying the whole thing to
    #include <stdio.h>

    __attribute__((noinline)) int infloop (int x) {
    printf("%d-", x);
    if (x == 2) return infloop (x+2);
    if (x == 4) return infloop (x-2);
    }

    int main (void) {
    infloop(2);
    }

    Segfaults after some output when compiled normally, and doesnt segfault (at least for a very long time) when compiled with gcc and -O2. Strange. Somehow gcc and clang seem to determine whether the stuff they compile has states or not.

    EDIT: ok. I was mistaken. It simply throws away infloop(2); since infloop doesnt have any side effects in the first example, and the outcome is to be thrown away. The code

    #include <stdio.h>

    int infloop (int x) {
    if (x == 2) return infloop (x+2);
    if (x == 4) return infloop (x-2);
    }

    int main (void) {
    int q = infloop(2);
    printf ("%d\n", q);
    }

    does a segfault without -O2 and does an infinite loop with -O2.

  4. Ivan Tomac sagt:

    Hi,

    Removing __attribute__((noinline)) may cause gcc (and clang) to inline the function, in which case it doesn’t actually call either tcotest or test making the example potentially invalid, depending on how the functions get inlined. You can check the generated code to see if the functions have been inlined by using -S to generate assembly output.

    You are right, it appears clang can optimize tail calls for functions calling themselves, like evenp, but it doesn’t optimize the more general case.

    I came across this paper that explains how gcc does TCO: http://www.complang.tuwien.ac.at/schani/diplarb.ps
    Might find that useful.

  5. dasuxullebt sagt:

    Thank you. Looks indeed interesting (not only because of the topic but also because this looks like a diploma thesis – and I am interesting in how diploma-theses look like at the moment ^^)

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: