Nov 27, 2017
Delimited continuations in a statement-oriented language

I've been periodically wrestling with the concept of continuations for several years now, and have somehow never gotten comfortable with them. Looking back, I think this was for two reasons:

  1. Continuations are usually explained in the context of high-level languages with higher-order functions and lots of nested function calls. But continuations fundamentally subvert the notion of “function”. Operators like ‘reset’ looked like functions, but had “spooky action at a distance” effects that were hard to reason about.
  2. I had trouble finding real-world programs where continuations are more expressive than regular recursive function calls with well-designed data structures. For example, classic back-tracking problems like the N-queens problem have elegant solutions that don't require continuations. Were continuations just a low-level primitive for building more high-level tools like generators (‘yield’) and exceptions? Building fluency with a concept requires developing an instinct for when it's applicable.

In response to the first issue, I've been adding delimited continuations to Mu (my experimental testbed for ways to make the big picture of codebases more comprehensible, and for ways to teach programming without dwelling on syntax). And indeed, implementing continuations did seem to help me understand them better. And they did seem more comprehensible in a statement-oriented language where the mind was already accustomed to running into jump instructions. In Mu it becomes more obvious that that continuation operators are just stack manipulations.

However, I still didn't have confidence that I actually had built delimited continuations. Perhaps in translating them from Scheme to Mu I'd hamstrung them in some subtle way? This question connected up with the second issue: I had a hammer, but no non-trivial nails to use it on.

Recently, I remembered an old favorite of mine: “Coroutines in C” by Simon Tatham. Coroutines are known to be implementable using continuations, and Simon's essay had a nice example program using coroutines.

One thing led to another, and I ended up porting Simon's essay: “Coroutines in Mu”.

I'm probably just weird and brain damaged for preferring to see continuations in a sort of Assembly language rather than a high-level one. But if you've tried to understand continuations in the past and not gotten comfortable with them, try working through my essay and see if coming at the idea from a different angle helps. Prerequisites: knowledge of C and Simon's original.

Grateful appreciation to Simon Tatham for generously permitting me to remix his essay, and to Stephen Malina for closely reading my version and carefully checking all the code examples.

Making the big picture easy to see, in software and in society at large.
Prose (shorter; favorites)