Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!visix!ip2020!adamksh
From: adam@visix.com
Newsgroups: comp.lang.c
Subject: Continuation-passing in C?
Message-ID: <1991Mar28.070649.1667@visix.com>
Date: 28 Mar 91 07:06:49 GMT
Sender: news@visix.com
Reply-To: adam@visix.com
Organization: Visix Software Inc., Reston, VA
Lines: 155


How can I (efficiently) program in a continuation-passing style in C?

This breaks down into two basic questions:

(1) How do I explicitly jump across functions
(2) How do I keep things in registers across functions

Simple example:

main()
{
    register int a, b, c;

    a=1; b=2; c=3;
    foo( a, b, c );
    baz( a, b, c );
    bar( a, b, c );
}

I want the compiler to emit code that

(1) jumps directly from the end of foo to the start of baz, instead of
returning to main only to jump to baz

(2) leaves a, b, and c in registers instead of mucking around on a stack
(or leaves them on the stack instead of popping and pushing them)

Are most compilers smart enough to do this?  Is it possible to trick
most compilers into doing this (how do I get it to emit the right jump?)
Am I being anal about performance?

More complex example:

main()
{
    register int a, b, c;

    a=1; b=2; c=3;
    foo( a, b, c, baz, bar );
    c++;
}

foo( a, b, c, afn, bfn )
register int a, b, c;
int (*afn)();
int (*bfn)();
{
    if (a > b)
	afn( a, b, c );
    else
	bfn( a, b, c );
}

Same questions: can I force a jump from the end of afn back to main
(tail recursion)?  Can I force a, b, and c to stay in registers?
Should I just trust the compiler?  (the compiler is your *friend*...)

I guess I can use setjmp/longjmp for the complex example, except that
if I had a real (long) tail-recursive chain I wouldn't want to be
allocating stack frames in the first place; I should replace them with
each successive call.

But I can't use setjmp/longjmp at all for the simple example.

There are two solutions I can think of.

/* Number 1 */

main()
{
    register int r1, r2, r3, r4, r5, continuation;

    r1 = 1; r2 = 2; r3 = 3; r4 = BAZ; r5 = BAR;
    continuation = FOO
    
    while(1)
    {
        switch (continuation)
        {
        case MAIN2:
	    r3++;
	    continuation = DONE;
	    break;
        case FOO:
	    if (r1 > r2)
                continuation = r4;
	    else
	        continuation = r5;
	    break;
        case BAZ:
	    continuation = MAIN2;
	    break;
        case BAR:
	    continuation = MAIN2;
	    break;
        case DONE:
	    exit(0);
	}
    }
}

/* Number 2 */

static void (*continuation)()
static int r1, r2, r3, r4, r5;

done()
{
    exit(0);
}

main2()
{
    r3++;
    continuation = done;
}

baz()
{
    continuation = main2;
}

bar()
{
    continuation = main2;
}

foo()
{
    if (r1 > r2)
	continuation = r4;
    else
	continuation = r5;
}

main()
{
    r1 = 1; r2 = 2; r3 = 3; r4 = baz; r5 = bar;
    continuation = foo;

    while(1)
    {
	(*continuation)();
    }
}

Okay, it's twisted.  That's the point :-).

Actually, I kind of like Number 2, except that I can't force my
registers to really be registers.

Is there anything better?

Adam