C with continuations?! A report on a conversation in Cancún
I shared my thoughts on async, async everywhere with my friend Sam while on a bus ride to some ruins in Cancún this past weekend, and his reaction was, “sure, but why not continuations everywhere, why not just add continuations to C?” This floored me: I’d never considered such a thing — it seems so… foreign, out of place, yet so clever. Needless to say, we proceeded to have a lively conversation about this.
What would it mean to add something like Scheme’s call/cc to C? We thought it’d mean this: that all function call frames would be allocated from a heap and would be garbage collected, and that there would be no stack, plus all attendant calling conventions changes. (Such a C might as well also have closures, while we’re at it.)
Such a C would have to deal with alloca() (e.g., by turning alloca()s into heap allocations and recording those in the activation record so they can be freed when the activation record is garbage collected), and setjmp() and longjmp() (which, actually, become much simpler in implementation!), and such things. And probably would have to have a “foreign function call” facility for calling normal C code, to make it easier to start using this weird C.
What would break? Anything that assumes that the addresses of automatic variables in different function call frames in the current code path are ordered in the same way as the function call frames — i.e., code that assumes a stack. And any C code that uses asm() to get at the stack pointer would likely break (a stack pointer could be provided, but its values couldn’t be changed by asm() code). That’s not a whole lot of code, probably, as a percentage of an entire OS, but it’d be a largish amount of code in absolute terms, perhaps even excluding code implementing other languages in C.
The OS would still have to provide async versions of all synchronous system calls, unless, my friend cleverly points out, the kernel itself were built with such a C compiler!
We’re talking about dirt cheap threading here, so cheap that it might outweigh the cost of garbage collection and heap fragmentation (there’s no way to do a copying garbage collector for a language like C, I’m afraid, and any GC would have to be very conservative) — it would have to in order to succeed. With threads this cheap you can start one any time you want, for any reason, and avoid having to write CPS-like code atop lots and lots of async interfaces, each implemented in CPS too.
No, this will never happen. It’s a fantasy of people who wish we could write procedural-looking code with tiny amounts of syntactic sugar to enable lots of cheap parallelization, while retaining source-level compatibility with millions of lines of code.
In reality programmers will always just have to deal with writing async, CPS-like code; we’ll just have to do what should have been the compiler’s job. Scheme lost. Tough beans.
Still, if we want to parallelize code cheaply we’ll need thread creation to be cheap as well, dirt, dirt cheap. What other ways are there to make it so? Pre-creation of threads?