Coroutines in C (Simon Tatham, 2000) | Hacker News Reader

Coroutines in C (Simon Tatham, 2000)

chiark.greenend.org.uk

58 pointsgjm1116 comments

This is very nice in theory, but in practice you can only do it in assembly language, because no commonly used high level language supports the coroutine call primitive.

This might have been true when the article was written, but things are slightly different today. JavaScript, Python, and C# have picked up generator primitives that can be abused to provide limited coroutine support. Lua, with actual coroutine support, is gaining in popularity. And it will be interesting to see what happens with PyPy, which has support for the Stackless Python coroutine primitive.

There are apparently lots of uncommonly used languages with coroutine support:

http://en.wikipedia.org/wiki/Coroutine#Programming_languages...

You can make coroutines in Scheme via continuations, and you can also make one-shot continuations out of coroutines.

"Revisiting Coroutines" by de Moura and Ierusalimschy (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.4...) is a pretty good paper about using coroutines, with Lua as the example language.

Simon is the guy who wrote PuTTY - he generally know his stuff. Some of this is NSFW, in the sense that you don't want it in commercial code for someone less able to have to support.

However, it's beautifully instructive, and a clever hack.

His collection of little puzzle programs is very nice too. I don't know how the global productivity cost of the puzzles balances off against the global productivity gain from PuTTY.

For all this and more, see his home page: http://www.chiark.greenend.org.uk/~sgtatham/ .

Also available (free) on Android under Simon Tatham's Puzzles.

Note that this hack is actually used in PuTTY. However he points out that it violates standard coding standards left and right.

Outrageous combination of macrology with Duff's device to create a simple coroutine facility in C. You probably don't want to do this in practice, but it's ingenious and amusing.

"This is very nice in theory, but in practice you can only do it in assembly language, because no commonly used high level language supports the coroutine call primitive."

I think you can get a similar effect in a high-level language by transforming the logic inside your normal function into a state machine that effectively runs one line logical line of code per call. You still end up with a call stack, but you don't use it the same way.

I'm currently implementing an approximate search engine this way in a high level language. I've done some proof-of-concepts with this technique and it seems very efficient, because I can just kill the machines without having to run them to completion when I think I've found my answer (or am sure there's no answer to find).

yeah but isn't doing this state machine transformation pretty complicated? i know that this is what C# does to implement its iterator blocks, but they have the compiler write the state machine for you. Do you think that this is practical as a general solution in a language that doesn't provide these tools for you?

Fair point.

Getting to that "a ha!" moment when I figured out that this would help (a lot) was very hard. Forcing my code to behave that way was definitely non-intuitive and challenging. Having merely gotten it working and proving my theory (it works) that it's a huge efficiency gain, I now get another crack at the next version.

I don't think it's necessary for a compiler to do the work for you, or to have it built in as a fundamental feature of a language (that certainly helps). But I do agree that without a library or (dare I say) framework, it is a bit challenging to code from scratch.

Probably the hardest part (for me), is that it breaks so many fundamental notions of programming.

One obvious feature that I'm making heavy use of is that I can get data out of the state machine on every call (that's almost the whole point for me). I can use that data and determine if I want to call it any more or just kill it (or maybe put it aside to get called later).

Perhaps more interesting, I have the opportunity to pass data into the state machine on every call down to it (not just on the initial call). That seems powerful. I already have an idea on how to utilize that.

I do agree, that at some point this technique would be more efficient if implemented in assembly than in a high-level language. My approach is probably similar to implementing a binary search in a high-level language and comparing it so a linear search in C. At this point I'll take the flexibility of the high-level language. Almost certainly a lower level implementation of the same pattern would kick butt.

Simon's guide on How To Report Bugs is also well worth a read. Circulate to your test team if they haven't already got a copy! http://www.chiark.greenend.org.uk/~sgtatham/bugs.html

The C# compiler does something very similar to this when it compiles iterators (the yield return, yield break feature to quickly implement IEnumerable without writing a class), although it takes care of capturing state automatically etc.

Adam Dunkels also has some interesting ideas with his protothreads package: http://www.sics.se/~adam/pt/

My personal favourite is using a simple wrapper around makecontext()/swapcontext() [1]. Allows for some truly mindbending code.

[1] http://www.opengroup.org/onlinepubs/009695399/functions/make...

Thanks Simon, but I'll use Russ Cox's (co-author of Go)

http://swtch.com/libtask/

Reply on news.ycombinator.com