Lambda the Ultimate

Nice articles (although a little confusing). Here is my silly contribution to the subject:

//recursive non-continuation factorial
int factorial(int n, void (*func)(int))
{
    int r = n ? n * factorial(n - 1, func) : 1;
    func(r);
    return r;
}


void print(int n)
{
    printf("%i\n", n);
}


//recursive continuation factorial
void factorialcc(int n, int m, int f, void (*func)(...))
{
    n > 0 ? func(n - 1, m, f * (m - n), &factorialcc) : 0;
}


void printcc(int n, int m, int f, void (*func)(...))
{
    printf("%i\n", f);
    func ? func(n, m, f, &printcc) : 0;
}


int main()
{
    //using non-cps factorial
    factorial(7, &print);

    printf("---\n");

    //cps-factorial
    factorialcc(7, 8, 1, (void (*)(...))&printcc);

    getchar();
    return 0;
}

It works like this: The function 'factorialcc' computes the factorial, passing execution to its last parameter. The function 'printcc' prints the result, then continues execution by passing its arguments (and itself) to the function passed as parameter...thus one function calls the other, and none returns.

The output of the above is:

1
1
2
6
24
120
720
5040
---
1
2
6
24
120
720
5040

If it feels like a hack, it's because it is a hack, but it is a general way to do continuation-algorithms in C. It can be done in a much better way in C++ using functor objects. Now if the compiler could optimize it as in functional languages...

(I hope the above is valid CPS, by the way. If it is not, don't shout at me too hard :-) ).

Here is another silly C version:

void factorial(int n, int m, int f, void (*cc)(int))
{
    n <= m ? factorial(n + 1, m, n * f, (cc(f), cc)) : cc(f);
}


void factorial(int n, void (*cc)(int))
{
    factorial(1, n, 1, cc);
}


void print(int n)
{
    printf("%i\n", n);
}


int main()
{
    factorial(5, print);

    getchar();
    return 0;
}

The trick is to exploit the operator ,. The output is:

1
1
2
6
24
120

Still not a real continuation (it does not create a new function!), but a possibility nevertheless.

One could write it as a forward-only recursion

void factorial(int n, int m, int f, void (*cc)(int))
{
    cc(f);
    if (n <= m) factorial(n + 1, m, n * f, cc);
}

which could be optimized by a clever compiler as a forward only code (i.e. do the tail-call optimization: instead of returning, jump to the next computation, and return to the outter call only when there is no other computation left to do. Stack parameters could be replaced)

In C++, templates can be exploited for providing tail-call optimization during compile, like this:

void print(int n)
{
    printf("%i\n", n);
}


template < int n > int factorial(void (*cc)(int))
{
    int r = n * factorial(cc);
    cc(r);
    return r;
}


template <> int factorial<0>(void (*cc)(int))
{
    cc(1);
    return 1;
}


int main()
{
    factorial<5>(print);

    getchar();
    return 0;
}

Without checking it, I assume that GCC will simply create the optimal code, as if the factorial was computed by hand, calling the supplied function at each step.