Explaining Continuations

:: programming, scheme, racket, continuations

The other day I was reading through /r/scheme and found an interesting post about continuations. The post did a pretty good job of showing some examples of how to use continuations, but seemed to miss the mark explaining how they work and how to add them into your design. So I thought why not take a crack at it.

“A Continuation is an abstract representation of the control state of a computer program.” Thats how Wikipedia explains it. So it is a snapshot of the current state of your application at some given point in time. But how can that be useful?

Magic String

When using Continuations I like to think about what they can do for me. Image that you had a spool of string, string that can traverse space and time. You can tie one end of this string to a specific location in Space-Time and as you go on your way the spool unwinds. Throughout your day you move further and further from where you tied off that string but you always have a connection to that moment in time.

There is another special property to this string. If you pull on this string you magically get whisked back to that point in Space-Time where you first tied it off. You also are able to retain the information you learned over the day.

Imagine you decide to go for a long hike and wind up getting attacked by a bear, you can pull on your string and get sent back to the moment you first set off on your adventure. If you decide to go out for the walk again you remember where the bear was hiding and can take a completely new path. This time without worrying about running into that bear.

A simple example

Lets think about a function, one that takes in a list of numbers and returns back a list of reciprocals. Sounds easy enough.

(define (map-/ lst)
  (map (lambda (x)
          (/ 1 x))
        lst))

The only problem is when one of the numbers is Zero. We could test for a zero denominator and cons in a false, but our result would no longer be a list of reciprocals.

(define (map-/ lst)
  (map (lambda (x)
          (if (zero? x)
            #f
            (/ 1 x)))
        lst))

(let ([results (map-/ lst)])
  (if (member #f results)
    #f
    results))

This works but we are running through the list twice: map-/ and member. If only we could do both tasks at the same time. If only we could undo the generation of our reciprocal list if we ran into a zero.

Using the magic string

Looking at our latest version of map-/ if we hit the (zero? (car lst)) case it would be great if we could just undo everything. Using continuations we can.

(call/cc) takes in a function with a single parameter, our magic string. Really its a call to restore our state to where call/cc is.

(define (odd-test x)
  (call/cc
    (lambda (k)
      (when (odd? x) (k)) ; If Odd, pull string
      (displayln "Only evens get here"))))

If we call this function with an odd number we hit our test case and pull out of what we were doing. Better yet, if we passed a parameter to (k) then call/cc would return that value. Otherwise, as typical functional programming, the last value on the last line contained in the lambda will be returned when the execution of the body in call/cc completes.

So how can this help our map-/ function? If we wrapped it up inside a call/cc we could go through our normal operation and if we hit the Zero test case pull out.

(define (map-/ lst)
  (call/cc
    (lambda (k)
      (map (lambda (x)
              (if (zero? x)
                (k #f)      ; Divide by zero, return #f
                (/ 1 x)))
            lst))))

If we run map-/ with a list of positive numbers call/cc will return the result of map. If the list contains a Zero, it will return the value passed to k#f.

(map-/ '(1 3 2)) ; -> '(1 1/3 1/2)
(map-/ '(1 0 2)) ; -> #f

Changing history

Unlike real time travel, what you do prior to going back has affect. How can this knowledge help up? We can do work and then go back keeping the current changes. If we do this over and over we can get very interesting results.

Daniel Martins’ Post that started this all off gave an example of an iterator that uses continuations.

(define (iterate lst)
  (define (state return)
    (for-each
      (lambda (item)
        (let/cc state-cc
          (set! state state-cc)
          (return item)))
      lst)
    (return 'done))

  (define (generator)
    (call/cc state))
  generator)

Lets start by looking at the state function. As we noticed in the previous example, this function fits the Continuation Passing format (a function that takes a single argument…a continuation argument). Inside it runs for-each on a list applying a lambda function. Notice the last call in the lambda is (return item). This is the call that pulls us back to the original context where the continuation was created.

(define lst '(1 2 3 4))
(define (state return)
  (for-each
    (lambda (item)
      (return item))
    lst))

(call/cc state) ; -> 1
(call/cc state) ; -> 1

It looks as if our code works. for-each iterates over the list and when the first item is run we call our continuation function and return the item. But this doesn’t really help us as we never can get past the first item.

What if we could change our state function so that the next time it is called we have moved on to the next item in the list. By using let/cc we get the current continuation. Since Scheme functions are really just variables you call, we could change the value of state to the current iteration in the loop.

(let/cc state-cc          ; Takes our current stack
  (set! state state-cc))  ; and stores it in state

What does this do? We are using our magic string and tying it off inside our loop. When we pull on it we get yanked back inside the iteration of our loop. Essentially we are able to track our run through the for-each, return out of it with the current item and then later jump back in to pull the next item.

(define lst '(1 2 3 4))
(define (state return)
  (for-each
    (lambda (item)
      (let/cc state-cc
        (set! state state-cc)
        (return item)))
    lst))

(call/cc state) ; -> 1
(call/cc state) ; -> 2

To top it off Daniel packages it all up returning a function you can call that does the (call/cc) for us. This is a nice simple design using Continuations. In the spirit of this post we’ll go one step further and make this into a real generator, not just an iterator.

Stream Generator

A stream generator is a pattern that where you take an iterator function and an initial value to create an infinite list of results, each being the input for it’s successor.

F(init) -> x1
F(x1) -> x2
F(x2) -> x3
...
F(xM) -> xN

Obviously we cannot actually create an infinite list as we would never be able to return it after generation as it would go on forever. What if we could create one of the items in our infinite list and return it using our continuation functionality. We could then come back and create the next item and return that.

Lets start by creating an infinite loop that runs our function.

(define f add1)
(define (state)
  (let loop ([value 0])
    (let ([x (f value)])
      (loop x))))

Probably a bad idea to run this as it runs forever. So the next step is to add in our continuation passing

(define f add1)
(define (state return)
  (let loop ([value 0])
    (let ([x (f value)])
      (return value)
      (loop x))))

(call/cc state) ; -> 0
(call/cc state) ; -> 0

Again, we never get past that first call of return. If we could change state at each iteration we can get the result we are looking for. Since our loop is infinite we can do this forever.

(define f add1)
(define (state return)
  (let loop ([value 0])
    (let ([x (f value)])
      (let/cc state-cc
        (set! state state-cc)
        (return x))
      (loop x))))

(call/cc state) ; -> 0
(call/cc state) ; -> 1
(call/cc state) ; -> 2

Lets wrap this up so we can call (generate f) and get a nice object to iterate over. While we’re at it we can add an option initial value to start our list.

(define (generate f [init 0])
  (define (state return)
    (let loop ([value init])
      (let ([x (f value)])
        (let/cc state-cc
          (set! state stat-cc)
          (return x))
        (loop x))))

  (define (generator)
    (call/cc state))
  generator)

(define numbers (generate add1))
(numbers) ; -> 0
(numbers) ; -> 1
(numbers) ; -> 2

(define twos (generate (lambda (x) (* 2 x)) 1))
(twos) ; -> 1
(twos) ; -> 2
(twos) ; -> 4
(twos) ; -> 8

Update

It was pointed out to me by jrapdx that my (generate) example was very Racket specific. So here is an update that will make it work for pretty much any Scheme with call/cc support.

let/cc is a macro in Racket that generates the following code:

(let/cc k body ...+)

(call/cc (lambda (k) body ...))

So we can replace the let/cc call with call/cc and a few extra lines and our generator turns into:

(define (generate f [init 0])
  (define (state return)
    (let loop ([value init])
      (let ([x (f value)])
        (call/cc (lambda (state-cc)
                  (set! state stat-cc)
                  (return x)))
        (loop x))))

  (define (generator)
    (call/cc state))
  generator)

Thanks jrapdx for the update.

Conclusion

There are tons of other situations to use continuations. Creating coroutines, exception handling, maintaining state in web-servers. But they all use the basic concept of exiting the current execution. Once you understand the basic concept all the other examples make a lot more sense.