Continuations

Continuations give the programmer a way to control the flow of a program. While the concept itself exists in any programming language, continuations are most powerful in languages that treat them as first-class citizens and that include tail-call optimization. This post is an introduction to continuations and will not go into continuation passing style (CPS) or delimited continuations, but if you are interested in learning more these are two areas that you can explore.

What is a continuation?

A continuation can be thought of as the rest of a computation. This statement makes little sense on its own; it is best understood by example.

Take for example the following computation:

5 + (6 * 3) - 12

The current computation is (6 * 3) . The continuation at this moment is the rest of the computation, meaning all of the computation excluding the current computation, i.e. “add five and subtract twelve.” This can be represented as 5 + _ — 12, where _ is a hole in the continuation that will be filled by the result of the current computation. The continuation will change throughout the computation cycle. Once (6 * 3) is computed, the computation effectively becomes 5 + 18 — 12 . The current computation at this moment becomes (5 + 18) and the continuation becomes _ — 12 . Then, the current computation becomes 23 — 12 and the continuation at this moment is empty, as there is no computation to be executed after the current computation returns a value.

Another way to think about continuations is that they provide a way to refer to the state of a program at an arbitrary point in its execution. I especially like the description provided in an email log from Perl programming pro Luke Palmer:

People say continuations are like time
traveling; I like to put it this way:

Say you’re in the kitchen in front of the refrigerator, thinking about a
sandwitch (sic). You take a continuation right there and stick it in your
pocket. Then you get some turkey and bread out of the refrigerator and
make yourself a sandwitch, which is now sitting on the counter. You
invoke the continuation in your pocket, and you find yourself standing
in front of the refrigerator again, thinking about a sandwitch (sic). But
fortunately, there’s a sandwitch (sic) on the counter, and all the materials
used to make it are gone. So you eat it. :-)

A continuation doesn’t save data. It’s just a closure that closes over
the execution stack (and any lexicals associated with it; thus the “I
want a sandwitch” (sic) thought). If things change between the taking and
invoking of the continuation, those things remain changed after
invoking.

Why are continuations useful?

One of the major use-cases of continuations is in nondeterministic programming. Continuations provide a way for a program to make a branching decision at runtime, based on criteria not directly specified by the programmer. The programmer may specify a number of alternatives, and the program chooses at runtime which branch to follow. One example of a method of choice in such a scenario, is backtracking. A backtracking algorithm will incrementally build the solution to a problem, abandoning a potential solution branch if it fails at any point in the branch and backtracking to a previous point in the program to seek a new potential solution branch. Continuations provide a way to return to a previous state in the program; however the things that changed before the application/invocation of the continuation remain changed (i.e. the branch that is known to be a failing branch is cut from potential solutions). Continuations can also be a powerful way to control program flow in web applications. The Seaside web framework makes extensive use of continuations for example.

Getting started with continuations in Scheme

Here is a functional representation of the first continuation in the example from the introduction, written in scheme. (the current computation being (6 * 3) and the current continuation being 5 + _ — 12 .

((lambda (v)
  (- (+ 5 v) 12)) 
 (* 6 3))

The lambda expression is a representation of the continuation. The lambda expression is applied to the multiplication of 6 and 3 which is a representation of the current computation.

Scheme however, allows you to “grab” the current continuation using a procedure call-with-current-continuation or call/cc .

(- (+ 5 (call/cc 
         (lambda (k) 
           (begin
             (set! *k* k)
             (k (* 6 3))))))
 12)

In scheme continuations are first-class citizens, meaning that we can set bang a variable, *k*, to capture the current continuation. In this way, we can apply the captured continuation to any arbitrary value outside of the context in which it was captured (ex. (*k* (* 3 4)) evaluates to 5 ). While this is a simple example, the technique opens the door to some very interesting and powerful programming paradigms.

Another example of using call/cc can be found in chapter 3 of The Scheme Programming Language by Kent Dybvig.

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))
;(product '(1 2 3 4 5)) => 120
;(product '(7 3 8 0 1 9 5)) => 0

This example demonstrates a nonlocal exit from a recursion. This program recursively multiplies the numbers in a list, but will immediately return zero if a zero is detected within the list, without performing any of the pending multiplications. In this example, the current continuation is stored in break . If a zero is the car of the list at the current recursive call, the current continuation is applied to zero. Since the current continuation is the lambda expression within the definition of product, the entire procedure applied to the list immediately evaluates to zero.

Once you start to get the hang of continuations, you can look into delimited continuations, which allow you to implement essentially any control structure in programming. I would point you to the work of Kenichi Asai, a programmer and professor at Ochanomizu University in Japan.

NOTE: Most of the ideas in this post were taken from William Byrd. I highly recommend looking into his talks, videos, google hangouts, and books. This post is based largely off of his google hangouts video on continuations. It is my intent to share these ideas with you, and reflect on the concepts that I have learned.

Other Sources:

http://matt.might.net/articles/by-example-continuation-passing-style/
https://www.youtube.com/watch?v=2GfFlfToBCo
http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/
https://www.scheme.com/tspl4/further.html#g63
https://www.youtube.com/watch?v=QNM-njddhIw
https://marijnhaverbeke.nl/cps/
http://www.cs.toronto.edu/~david/courses/csc324_w15/extra/choice.html
https://groups.google.com/forum/#!msg/perl.perl6.language/-KFNPaLL2yE/_RzO8Fenz7AJ