Pavel Panchekha

By

Share under CC-BY-SA.

(call/cc this-class)

Table of Contents

What is a Continuation?

Continuations are the future of programming.

Literally.

That is, a continuation is some notion of the future of a program. This probably sounds pretty nebulous, so let's look at a particular example.

prod = 1, n = 20

while n > 0:
    prod *= n
    n -= 1

print n
Note

All examples will be in a pseudo-language that looks like Python but acts like Scheme (we'll make one change to standard Python syntax: the last expression in a function will be returned if there is no explicit return). Scheme was the original language with continuations; nowadays, languages like Ruby and Haskell are springing up that support them as well. Smalltalk has continuations, and in fact makes very good use of them in its web framework, Seaside. Even C sort-of has continuations, though they're little-used (and painful).

This very simple factorial program should be easy to trace: first we set some variables, then we loop around 20 times (each time doing two operations, a multiplication and a decrement), and then we print the result.

Now, central to that description was the notion of time. I can, for example, ask you, "When you go through the loop the first time, after you've done the multiplication, what will you do next?" You, of course, answer me that you're thinking of doing a decrement, then loop around another 19 times, and finally print the output. This is the `continuation` of your program at that point. So really, continuations aren't that hard a concept. It's really just a way to grab this notion of a future and discuss it.

How do we use Continuations?

A concept for discussing programs is sort of nice, in a platonic sense. But why is it useful? Well, the simplest use of a continuation is to capture a notion of "future" and keep it around.

For example, suppose we are playing a flash game:

while True:
    play(FLASH_GAME)

This is clearly not a very accurate representation of life, because that would have us play the flash game forever. This is false. For example, we might get hungry:

while True:
    while not hungry:
        play(FLASH_GAME)
    eat()

Note how we had to explicitly break in and out of our main loop. This is ugly, especially if the loop is more complicated than one expression. Instead, let's think about what we want to do. We want to, when we are hungry, remember what we were doing, eat, and then continue doing that thing we remember. Continue… Continuation?

while True:
    if hungry:
        cont = continuation()
        eat()
        continue(cont)
    play(FLASH_GAME)

In this case, we store the "future" of the program, pause it to do something else, and then get back to it.

Note

If you know a bit about operating systems, you'll realize that this is quite similar to how an operating system manages multiple processes — it "interrupts" a process, does something else (that is, runs a different process), and then gets back to continuing the first one. In fact, continuations were added to Scheme to enable the writing of time-sharing (multiple-process) systems in Scheme, as a way of investigating good ways of writing them.

So that's a very simple use of continuations, but hopefully it gives you some understanding of what they are and how they work.

A Problem with Our Example

Here's our example from before:

while True:
    if hungry:
        cont = continuation()
        eat()
        continue(cont)
    play(FLASH_GAME)

There's one problem with this example: how does the call continuation() know that we want the future without the going and eating? We really need a continuation-outside-enclosing-block construct… But of course, that's really clunky. Instead, we're going introduce some sort of "continuation-hander" block, and write this:

while True:
    if hungry:
        cont cc:
            eat()
            continue(cc)
    play(FLASH_GAME)

Here I've changed the name of the continuation to cc because I'm using the word cont to denote a continuation block.

Warning

Again, this is a language that doesn't really exist. There are notes throught this document explaining how to translate various code to Scheme if you want to play with continuations; but Python doesn't have continuations.

Note

Where we write cont cc: ... Scheme users instead write (call/cc (lambda (cc) ...)) This is a difference in design philosophy that will not become relevant in this class. Schemers also make continuations regular callable objects, so that continue(cc) becomes (cc). This is a difference in syntax only.

Now that we have cont blocks, we can correctly represent what parts of the code are "interrupting" the normal flow of the program and which are supposed to happen.

Some Other Uses of Continuations

So far, we've used continuations only to pause program execution. Another use for them is to, instead of pausing the future, discarding it entirely. For example:

def first_positive(arr):
    cont ec:
        for elt in arr:
            if not isinstance(elt, int):
                continue(ec, -1)
            elif elt > 0:
                return elt

You can think of this as pausing the future, which in this case is returning from the function, and then executing the function normally. Then, during the normal flow of execution, we can prematurely exit from the function — that's what the call continue(ec, -1) does: it prematurely exits the function with the return value -1. This is similar to how return works in many languages.

So where's the benefit of continuations? Well, one of the important benefits of continuations is that we can take this ec continuation and pass it around to other functions. For example, we can do the following:

def first_positive(arr, ec=None):
    for elt in arr:
        if not isinstance(elt, int):
            if ec:
                continue(ec, -1)
            else:
                return -1
        elif elt > 0:
            return elt

Now we accept the ec continuation as a paramter, meaning we can write another function like so:

def elements_until_first_positive(arr):
    cont ec:
        accum = []
        f_pos = first_positive(arr, ec)
        for i in arr:
            if i == f_pos:
                return accum
            else:
                accum.append(i)

Now we see the first_positive function exit not to its own cont block, but to the cont block inside elements_until_first_positive. In this way it acts a lot like an exception (in fact, Scheme's exception system is implemented using continuations). Exceptions are really just a very limited form of continuations; you can't use them to implement something like the "pause to eat" functionality we did above.

Continuations are for Communication

There's an element above that I glossed over, and that's the continue(ec, -1) call: what's that -1 doing there?

Continuations have an added feature: they can be passed values. How does this work? well, when we call continue(ec, -1), we can act as if the cont block returned the value -1. So consider this code:

print (cont cc: continue(cc, 3))

This code will print 3, since when we call continue(cc, 3), we act as if 3 were returned from the cont block. In this way, we can use continuations to communicate between objects in our code. For example, consider the problem of picking out all perfect squares which end in 9 (up to some upper bound, presumably). We might write the following code:

def perfect_square_ends_in_9(max):
    n = 0
    while n < max:
       val = n**2
       if str(val).endswith("9"):
           print max
       n += 1

This is fine enough code for this case, but imagine the problem were slightly harder; the fact that we are mixing the perfect-square generation code with the selecting numbers that end in 9 is pretty ugly. We can do better. How about:

def generate_perfect_squares(consumer):
    n = 0
    while True:
        consumer = (cont cc: continue(consumer, cc, n**2))
        n += 1

def filter_for_last_digit_nine(producer, max):
    while True:
        producer, val = (cont cc: continue(producer, cc))
        if val > max:
            return
        elif str(val).enswith("9"):
            print val

Now, this is some pretty clever code, so don't feel bad if you don't immediately get it. We have two functions, a "producer" and a "consumer'. Each is passed a continuation to the other. Now here comes the tricky part. Let's look where we use cont blocks. In each function, we have one, which pauses the execution of the current function, and then starts the other function (passing along the paused state). In other words, each hands, we hand off execution between the producer and consumer. Here, let's look at which lines of code are run, in time order:

01 c  continue(producer, cc)
02 p  n = 0
03 p  continue(consumer, cc, n**2)
04 c  producer, val = <some-continuation>, 0
05 c  if val > max:
06 c  elif str(val).endswith("9"):
07 c  continue(producer, cc)
08 p  consumer = <some-continuation>
09 p  n += 1
10 p  continue(consumer, cc, n**2)
11 c  producer, val = <some-continuation>, 1
12 c  if val > max:
13 c  elif str(val).endswith("9"):
14 c  continue(producer, cc)
15 p  consumer = <some-continuation>
16 p  n += 1
17 p  continue(consumer, cc, n**1)
18 c  producer, val = <some-continuation>, 4
19 c  if val > max:
20 c  elif str(val).endswith("9"):
21 c  continue(producer, cc)
22 p  consumer = <some-continuation>
23 p  n += 1
24 p  continue(producer, cc, n**2)
25 c  producer, val = <some-continuation>, 9
26 c  if val > max:
27 c  elif str(val).endswith("9"):
28 c  print val
...

That printout isn't an exact demonstration of what our hypothetical language does, but it should give you some idea of what goes on in the code. The number is just the time and the letter p or c denotes whether we are in the producer function or the consumer function.

The technique we saw above is called a "coroutine", and it can be powerfully used to represent lots of programming problems. The crucial idea is that we have two systems that communicate back and forth using continuations to act as a "pipe" over which the communication happens. We can extend this a bit to represent a time-sharing system, where instead of two functions swapping off, we'll have many functions swapping with some "kernel" function, which will determine (using some mechanism usually called the scheduler) which "process" should run next.

Note

Some language (such as, actually, real Python) have a feature called "generators", which are a form of coroutines. These are a weak form of continuations that duplicate only the "pausing" behavior, just as exceptions are a weak form of continuations that duplicate only the "jump to somewhere else in the code". We'll see in a bit why continuations are so powerful.

Continuations are Asynchronous

Lots of languages support "asynchronous IO". What that means is, say I need to read from a file. Well, this is going to take the computer some time — for example, it might need to spin its hard drive to the right place. More sophisticated examples might require the computer to fetch the file over the network or decrypt some other file first. Anyway, while the computer is doing this, we can go do something else while we wait. But how do we know that we're done reading the file? A very popular way of doing that is with "callback functions". Here, when we ask to read the file, we pass along a function to execute when we're done reading. We'll pretend the standard Python read function does this. (Instead, it just blocks you from doing anything. How rude!):

def print_file_length(fname):
    file(fname).read(callback=(lambda text: print len(text)))
    print "Please wait... reading file"

Here, we ask the computer to read the file and, when it's done reading it, call the function (lambda text: print len(text)) with the text as an argument. Meanwhile, we print the text Please wait... reading file. The word lambda just means that we are making a little function. Well, alright, but what if we need to read multiple files? We end up writing code like this:

def total_length_three_files(fname1, fname2, fname3):
    file(fname1).read(callback=(lambda text1:
        file(fname2).read(callback=(lambda text2:
            file(fname3).read(callback=(lambda text3:
                print len(text1) + len(text2) + len(text3)))))))

This code is clearly absolutely horrible.

What we need here to to pause execution and pass that to read. But how could we do that? Oh, right…

def total_length_three_files(fname1, fname2, fname3):
    text1 = (cont cc: file(fname1).read(callback=cc))
    text2 = (cont cc: file(fname2).read(callback=cc))
    text3 = (cont cc: file(fname3).read(callback=cc))

    print len(text1) + len(text2) + len(text3)

This makes perfect sense when reading, is easy to edit, and even avoid the problem of the function marching off to the right edge of the screen.

Note

Node.js is a pretty popular framework for writing server-side JavaScript code. Its IO system is entirely asynchronous (in fact, almost everything you can do in Node.js is asynchronous), which leads to many many continuations. I advise against reading Node.js code; it very often has this problem of marching off to the right (since JavaScript requires close braces, it then painfully marches back…). I've heard Node.js programmers support using one space for indentation to fight this.

In proper languages like Scheme, we have more civilized solutions.

Continuations are Re-Entrant

So far, we've called each continuation we created at most once. Let's get really crazy.

def ceiling_sqrt(n):
    big_continuation = None
    a = (cont cc:
        big_continuation = cc
        return 0)

    if a**2 > n:
       return a
    else:
        continue(big_continuation, a + 1)

Woah! This is like looping… without looping! Let's work through this step-by step.

The first line makes a big_continuation variable. Then, the next line sets it to the continuation from that point, but for now returns 0. So a is 0 for now. Presumably, we asked for the square root of some reasonably big number, so 0**2 < n, and we call out continuation with the argument 1. This returns from the cont block, again. That's right, we're returning from that block twice. And this time around, a is 1. We go around again and now a is 2; eventually, we'll work our way up to the square root of n and we'll exit.

I'll pause a while to let you digest.

Note

There's an Python-to-Haskell compiler, "Berp". It implements all looping constructions (while, for), as well as exceptions, using continuations. It actually leads to a very powerful Python implementation that was nonetheless very easy to code.

So it turns out you can do while with continuations. So what? I'll tell you why this matters: if you can duplicate while, you can duplicate not only the other built-in looping constructs, but also all manner of varied and strange looping constructs that the designers of Python might never have imagined. For example, consider:

def print_leaves(tree, cc=None):
   if is_leaf(tree):
       print tree
       return
   else:
       cont cc:
           print_leaves(tree.left, cc)
       cont cc:
           print_leaves(tree.right, cc)

This code prints all the leaves of some binary tree (in order). Now, this might look like the standard recursive way of doing this. It is. But it is a lot more flexible, for suppose we wanted to take all of the even leaves and ask the user whether he really wants them printed. If the user tells us to, we'll print them, but the user can squelch them if they want. Now, we can do this recursively:

def print_leaves(tree):
   if is_leaf(tree):
       if is_odd(tree) or raw_input("Print? (y/n) ") == "y":
           print tree
       return
   else:
       print_leaves(tree.left)
       print_leaves(tree.right)

The problem with this is that we have to mix the logic that queried the user with the code that walked the tree. With continuations, we can separate those:

def print_leaves(tree, if_even=None, cc=None):
   if is_leaf(tree):
       if is_odd(tree) or if_even(tree, cc):
           print tree
       return
   else:
       cont cc2:
           if not print_leaves(tree.left, cc2):
               continue(cc2, False)
       cont cc2:
           if not print_leaves(tree.right, cc2):
               continue(cc2, False)
       return True


def if_even(tree, cont):
    return raw_input("Print? (y/n)") == "y"

Note that we use those continuations to allow us to exit without going down the right branch of a tree. Now say we want to let the user print, not print, or exit immediately. We can do that easily:

def if_even(tree, cont):
    response = raw_input("Print? (y/n/e) ")
    if response == "e":
       cont(False)
    elif response == "y":
       return True
    else:
       return False

And, of course, when we replace the textual prompt with a dialog, we don't have to think about how the recursive tree-walking operation is done.

Continuation Puzzles

What follows are two puzzles involving continuations. You're highly encouraged to try to solve each yourself.

Puzzle 1: Problem

Our first continuation puzzle is one I invented myself, and it asks you to explain what the following does (and how it does it):

callCC(callCC)(callCC(callCC))

In Scheme, this puzzle looks a bit prettier

((call/cc call/cc) (call/cc call/cc))

What's this callCC? It's just a function defined as such:

def callCC(f):
    cont cc:
        return f(cc)

This lets us specify the body of our cont block as a function somewhere and then use it later. It can be thought of as calling the function f with an argument that will replace the original callCC(f) call with any argument passed to it, and rerun the original.

Puzzle 1: Solution

So the first thing the function does is pass a continuation to callCC, and the continuation allows you to continue from the point after the continuation:

   callCC(callCC)(callCC(callCC))
   \------+-----/
          |
=> callCC(cc)(callCC(callCC))

The arrow goes from the continuation itself to the expression its return value will replace; the first line is the original code and the second is the first step in evaluating it.

Onward!

   callCC(callCC)(callCC(callCC))
   \------+-----/
          |
=> callCC(cc)(callCC(callCC))
   \--+-----/
      |
=> cc(k)(callCC(callCC))

=> k(callCC(callCC))

How'd we get that last line? Well, we replaced the expression underlined in the original expression with k, since that's the expression cc replaces with its argument.

Alright, now we replace the callCC(cc) that k is linked to with its argument, yielding…

callCC(callCC)(callCC(callCC))

What?! We get back the original expression. In fact, this expression is an infinite loop, which we created by cleverly using the time-traveling powers of continuations!

Puzzle 2: Problem

The second puzzle is called the yin-yang puzzle, and it's traditionally stated in Scheme, but I've taken the liberty of transcribing it to our pseudo-Python for you. It looks like this:

yin  = (lambda cc: output(1) or cc)(cont cc: cc)
yang = (lambda cc: output(2) or cc)(cont cc: cc)
yin(yang)

Note that Python is a somewhat clunkier language than Scheme, and we have to resort to output(1) or cc if we want to output 1 and then return the continuation.

This ends up outputting 121221222122221222221222222…, going on forever, and the puzzle is to explain how.

Puzzle 2: Solution

Hang on, it's a rough ride.

Well, the first time we output 1 is when we first assing yin. But the continuation, cc associated with yin has a future of passing through the (lambda cc: output(1) or cc) call; that is, next time we call it, we will output 1 and then continue on our business. In this case, our business is to rebind yang. But when we rebind it, its continuation remembers that it was going to print 2. Finally, we have a value of yin and yang. And now the fun begins.

We call yin with yang; keep in mind that yin is now a continuation. yin thus pretends to have returned yang from its (cont cc: cc) block, so it outputs 1 and binds yin to the old yang continuation. Still executing that continuation, it also prints the 2 that it was going to. That continuation finishes, and now we continue again after the setting of yin, and print another 2.

We now call yin(yang) again, but we call the same yin and yang we did the first time. Except now we know that we were going to print 122, so we do that and then print another 2. Looping again, we print 1222, and then another. Thus continues the pattern.

If you fully understood this (I just barely do), you understand continuations fully.

More on Continuations

You got to here and your head doesn't hurt? Dayumn. Well, my job here is done, but hopefully you're interested in continuations. What was covered here is but a small part of the power of continuations, so let's go over where else you can learn more.

The Wikipedia page is good for a refresher course on continuations, and has a some interesting referenced links. Continuations are an important part of the language Scheme, and I invite you to learn it — it is a very powerful, very elegant language. A good implementation is Racket.

An important distinction that can be made in Scheme is the distinction between lexical bindings and mutable binding. This concept is very hard to describe in Python, so I've skipped it above. But anyway, this allows a powerful changing the future of your program, somewhat like going back in time and remembering what you already know in the future. This gives you enormous expressive power (though strangely enough, it is theoretically unnecessary). There's a great comp.lang.lisp post describing this. Where this post talks about setf-binding versus let-binding, they are making this particular distinction.

One of the powerful things continuations can be used to implement is nondeterministic programming. This is a style of programming that further separates the generation of data and its consumption, somewhat like the coroutines example above. For example, suppose we want to write a quadratic equation solver. This is great, but quadratic equations have, at times, two solutions — which to return? We could always return the greater, but that would be wrong for those programs that require the lesser. Ah, you might say, I'll make it a parameter. This, too, is a poor choice, because what if the caller of your quadratic equation solver doesn't know which root it wants — say, for example, that this quadratic solver is just a small part of a very large computation that can return valid values for both the larger and smaller root.

The nondeterministic programming solution is to return one, but store away a continuation which instead returns the second. This way, we can do whatever calculations as if we had gotten the root we want, and later if it was not that one, "complain", triggering the continuation. You can read about nondeterministic programming in SICP, a book about computation, that is available online.

An interesting notion is the notion of a delimited continuation — this allows the same "jumping back in time" idea, but it is limited to a small cage, so that the continuation doesn't so much take you back in time as replay parts of its. It's a far more complex and powerful thing than I can explain here, but you can certainly read about in on Wikipedia.

There's even a group of linguists who claim that continuations have something to do with language. I have no idea, and couldn't make heads or tails of their paper, you might want to check out Chris Barker's Continuations in Natural Language; maybe you'll have better luck.

Lastly, if you're into implementing interpreters for programming languages, a common way to implement continuations is through Continuation-Passing Style. In this style, we write

(* 2 (+ 4 (/ 81 3)))

as

(/ 81 3 (lambda (result)
  (+ 4 result (lambda (result)
    (* 2 result cont)))))

Of course, this isn't something you ask the programmer to do by hand; instead, it's a mechanical transformation the interpreter does for you. The benefit of this representation is that it makes the continuations apparent — they are the last argument to every function. This is actually surprisingly efficient if your compiler is smart enough to do basic optimizations (nearly all Schemes fit this criteria, as do Haskell and ML-family languages). As always, Wikipedia has more.