(call/cc this-class)

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.