January 30, 2012

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 throwing 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:

  1. In Continuation-Passing Style as a conventional way of calling the next step in a computation.

  2. In First-Class Continuations as a name for saved computations.

  3. 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:
  1. "next"

  2. "saved stack"

  3. "continuation"

2 comments:

Manuel Simoni said...

What made me really and finally understand them was to implement the Scheme interpreter from Dybvig's Three Implementation Models for Scheme.

Justin Megawarne said...

How about “savepoint” for the 2nd sense?