(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'll 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 save this "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. but in fact, 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:
        cc = continuation()
        eat()
        continue(cc)
    play(FLASH_GAME)

This code isn't quite right, but the basic concept is that 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:
        cc = continuation()
        eat()
        continue(cc)
    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)

These cont blocks represent what parts of the code are "interrupting" the normal flow of the program, with the actual continutation representing that normal flow.

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):
    return 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 "interrupting" that to execute the function normally. The continuation, then, is a kind of "bookmark" pointing to the return statement, and continuing that continuation acts as a premature exit from the function, "jumping forward" to the interrupted return statement. That's what continue(ec, -1) does: it continues from the cont statement with the value -1, it is as if the body of the function was just return -1. This 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):
    return 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 exits not to its own cont block, but to the cont block inside elements_until_first_positive. In this way it acts a like an exception. Exceptions are really just a very limited form of continuations, and in Scheme exceptions are implemented exactly this way (though usually with an optimized and limited kind of "escape continuation").

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). 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, but the fact that we are mixing the perfect-square generation code with the code that selects 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 and I don't expect you to 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, 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 and features. 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. (The real thing just blocks your program. 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 is 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 avoids the problem of the function marching off to the right edge of the screen. Here each cont block pauses execution until the callback returns.

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

big_continuation = None

def ceiling_sqrt(n):
    a = (cont cc:
        global 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 our 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):
   if is_leaf(tree):
       print(tree)
   print_leaves(tree.left)
   print_leaves(tree.right)

This code just traverses a binary tree and prints all the leaf nodes. We can, of course, generalize this code by passing in a callback to let the caller decide which nodes we print:

def print_nodes(tree, should_print):
   if should_print(tree):
       print(tree)
   print_leaves(tree.left, should_print)
   print_leaves(tree.right, should_print)

Now the user can print just the even nodes, say, with:

def is_even(node):
    return node.value % 2 == 0

print_nodes(tree, is_even)

But what if we want to skip all nodes below an even node? We could of course use this callback, which walks up from the given node, checking that none of its ancestor nodes are even:

def is_below_even(node):
    while node:
        if node.value % 2 == 0: return False
        node = node.parent
    return True

But this is totally unnecessarily slow: not only is there an extra "walking" step, but we need to test every skipped node, even though as soon as we see an even node we can instead skip the whole subtree. Continuations let us do something different, by modifying our print_nodes function:

def print_nodes(tree, should_print, cc):
   if should_print(tree, cc):
       print(tree)
   cont cc:
       print_leaves(tree.left, should_print, cc)
   cont cc:
       print_leaves(tree.right, should_print, cc)

This code surrounds each recursive tree traversal in a continuation, allowing us to abort that subtree traversal in the callback:

def is_below_even(node, cc):
    if node.value % 2 == 0: continue(cc)
    return True

Or we can have a "search" function that searches for a node with a given value:

node = cont abort:
  print_nodes(tree, lambda node, cc:
              continue(abort, node) if node.value == value else False)

Here the callback returns False for every node (so nothing is printed) but it also aborts straight to the outermost continuation (named abort) as soon as it finds the node. In fact, a lot of tree-traversal and data-structure traversal code can use continuations to make one kind of traversal function serve many purposes: search, mutation, filtering, early exit, and so on.

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.