Continued Confusion
People have trouble understanding continuations, and this is no surprise when you realize that the term "continuation" is overloaded in all three senses: as a word, as a concept, and as a programming construct.
The confusion comes from two fields where continuations are used as a concept: compiler intermediate representations (where Continuation-Passing Style (CPS) is one possible form of intermediate representation), and First-Class Continuations (FCC), which is a metaprogramming technique for manipulating the stack of a program.
In terms of being a programming construct, continuations only exist in FCC. When it comes to CPS, a continuation is a concept only. In CPS, this concept is easy to understand: a continuation is the next step in a computation - the next instruction in the instruction stream.
For FCC, the concept consists of two parts: saving the current computation, and resuming a saved computation.
The main cause of confusion around FCC is that the First-Class Continuation programming construct is traditionally represented as a function (this has to do with the fact that FCC as an idea was derived from work in CPS). But a First-Class Continuation is not in any way a function. As Christian Queinnec points out in Lisp in Small Pieces, a First-Class Continuation is more like catch
/throw
:
Saving the current computation is like setting up a catch
block, and resuming that computation is like throw
ing a value to that tag - anything that happened between that catch
and throw
is forgotten. The thing that makes a First-Class Continuation special is that you can throw
to it anytime from anywhere, and you end up in the corresponding catch
, with whatever you were doing previously forgotten.
Marc Feeley has proposed an alternative interface for First-Class Continuations that makes invoking First-Class Continuations explicit, which is implemented in Gambit Scheme.
So finally we get to continuation as a word. As a word, "continuation" is used in three contexts:
- In Continuation-Passing Style as a conventional way of calling the next step in a computation.
- In First-Class Continuations as a name for saved computations.
- To indicate the next step in a computation when looking at a particular point in any given piece of code.
Christopher Wadsworth coined the term "continuation" for a way to formally reason about jumps/gotos, but the term can also be used informally when talking about a particular point in a piece of code. If you mentally use a different word in each of the three contexts, I think a lot of the confusion surrounding continuations can be cleared up. Something like the following might work:
- "next"
- "saved stack"
- "continuation"
2 comments:
What made me really and finally understand them was to implement the Scheme interpreter from Dybvig's Three Implementation Models for Scheme.
How about “savepoint” for the 2nd sense?
Post a Comment