Continuations in C

The language scheme has an interesting feature: the call/cc [4] function, otherwise known as call with current continuation.

A continuation is essentially the state of a process at any moment in time. At any point during execution you can think of it as an extra hidden argument that's always implicitly referred to in your code. We take it for granted that the current state of an executing system is available for our use and so we usually aren't aware it's there at all.

call/cc makes it explicit. The current state of execution can be grabbed and wrapped up as a first class object and it can be reused elsewhere. It's great for implementing things like coroutines where, in effect, you want to flip back and forth between different continuations.

If you read about continuations and it's sometimes pointed out that there is a crude form of call/cc in C, setjmp() and longjmp(). In a sense setjmp() saves the current state of the machine and longjmp() carries on from where you left off. But you can't use longjmp() to jump back into a function you've already come from. longjmp() can only unwind the stack and so you must return further up the call chain. This makes it good for handling exceptions but not for the cool stuff that call/cc can do.

It is possible to simulate call/cc, or something like it, on Unix systems with system calls like fork() that literally duplicate the running process.

But actually there's a way of doing this in C.

Rather than implement something exactly like call/cc I've implemented one of the things call/cc is good for: backtracking. In logic programming languages like Prolog it is possible to reach a point in code execution at which it is no longer possible to proceed. At this point the interpreter backtracks to a suitable point and then carries on from where it left off with something changed. This is great for doing exhaustive searches in combinatorial optimization and theorem proving.

In the following code I have used a continuation in C to implement non-deterministic code. Essentially it's a way of setting points to which execution can backtrack should one avenue of execution fail - like in Prolog. In a way you can think of C code written with backtracking as declarative rather than imperative.

First let's look at how the code is used:


/*
 * integer(m,n) returns an integer from m to n inclusive.
 * You can view i = integer(m,n) as the assertion
 * m<=i<=n.
 */
int integer(int m,int n) {
	int i;

	for (i = m; i<=n; ++i) {
		TRY(i);
	}

	FAIL;
}

/*
 * Solve this problem:
 * 2<=i<=100 and
 * 2<=j<=i and
 * i*j==481.
 * In other words factorise 481.
 */
int my_main() {
	int i,j;

	i = integer(2,100);
	j = integer(2,i);

	if (i*j!=481) {
		/*
		 * If they don't factor 481 then
		 * backtrack.
		 */
		FAIL;
	}

	printf("%d %d\n",i,j);
}

integer(m,n) is a function that returns an integer from m to n inclusive. The first time it returns m using TRY(). TRY() makes a trial return of its argument. If this return value causes a FAIL later then execution backtracks to this point. In this case the loop continues and tries m+1 next. integer() is used twice in the code. If the second one fails all the way up to n then it backtracks to the previous one. In this way it carries out an exhaustive search to factorise 481. Another way of looking at this is to view integer() as a coroutine and FAIL as the command that transfers execution back to the last coroutine that carried out a TRY().

Here are the implementations of TRY() and FAIL:


#include <stdio.h>
#include <setjmp.h>

long *pbos;

/*
 * Continuation datastructure.
 */
typedef struct cont {
	jmp_buf registers;
	int n;
	long *stack;
	/*
	 * Pointer to next continuation in chain.
	 */
	struct cont *next;
} cont;

void save_stack(cont *c,long *pbos,long *ptos) {
	int n = pbos-ptos;
	int i;

	c->stack = (long *)malloc(n*sizeof(long));
	c->n = n;
	for (i = 0; i<n; ++i) {
		c->stack[i] = pbos[-i];
	}
}

cont *getcontext() {
	cont *c = (cont *)malloc(sizeof(cont));
	long tos;
	/*
	 * Save registers
	 */
	if (!setjmp(c->registers)) {
		/*
		 * Save stack
		 */
		save_stack(c,pbos,&tos);

		return c;
	} else {
		return 0;
	}
}

cont *gcont = 0;

/*
 * Save current continuation.
 */
int save_context() {
	cont *c = getcontext();
	if (c) {
		c->next = gcont;
		gcont = c;
		return 0;
	} else {
		return 1;
	}
}

void restore_stack(cont *c,int once_more) {
  long padding[12];
	long tos;
	int i,n;
	/*
	 * Make sure there's enough room on the stack
	 */
	if (pbos-c->n<&tos) {
		restore_stack(c,1);
	}

	if (once_more) {
		restore_stack(c,0);
	}

	/*
	 * Copy stack back out from continuation
	 */
	n = c->n;
	for (i = 0; i<n; ++i) {
		pbos[-i] = c->stack[i];
	}
	longjmp(c->registers,1);
}

void exec_context(cont *c) {
	/*
	 * Restore stack
	 */
	restore_stack(c,1);
}

/*
 * Restore last continuation.
 */
void restore_context() {
	if (gcont) {
		cont *old = gcont;
		gcont = old->next;
		exec_context(old);
	} else {
		exit(1);
	}
}

int my_main();

int main() {
	long bos;
	pbos = &bos;

	my_main();
}

#define FAIL restore_context()
#define TRY(i) if (!save_context()) { return i; }

In order to save a continuation two things need to be grabbed: the state of all registers and the state of the C stack. setjmp() and longjmp() provide a mechanism for saving and restoring the registers. The stack is saved by getting our hands dirty and simply copying it out. It's extent in memory is found by taking the address of variables at the top and bottom of the stack. Unfortunately this isn't 100% portable, and is definitely against the rules. But the code above compiles under Linux, MacOS X, Win32, MSDOS, Irix and probably many other platforms. Incidentally, if you're trying to implement an interpreter for a language with continuations in C then one approach is to implement continuations in C. This is what Aubrey Jaffer did in his Scheme interpreter. If you don't want the stack of the language you're interpreting to be bound up with the C stack then you can implement something like Stackless Python [1]. In fact the example I give above is similar to the generator example given in [1].

References

[1] Continuations and Stackless Python
[2] SCM, a scheme implementation
[3] Continuations Made Simple and Illustrated
[4] A Page About call/cc