Sam Ruby: Continuations for Curmudgeons

This essay is for people who, in web years, are older than dirt. More specifically, if there was a period of time in which you programmed in a language which did not have garbage collection, then I mean you. For most people these days, that means that you had some experience with a language named C.

It is a pretty safe bet that -- despite your deep technical background -- you find that you have some genetic defect that makes it completely impossible for you to understand articles with titles like Continuations Made Simple and Illustrated. And for some reason, that bothers you.

A nice blog post that explains a number of basic PL concepts (value vs. reference, continuations, closures, coroutines) using examples from a bunch of popular languages (C, Javascript, Ruby, Python, BASIC, Java).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Nice articles

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

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.