Vijay Mathew

Here is my humble attempt to demystify continuations! It is assumed that the reader is familiar with basic concepts like expressions and their evaluation, closures etc.

A continuation is a point in an expression being evaluated, frozen in time. Consider the following code:

This expression can be split into three points: +, 2 and 3. We can freeze the program at any of these points and store it away. This is accomplished with the procedure call-with-current-continuation or call/cc. The name itself gives a hint as to what it does. call/cc takes a procedure as argument and evaluates it. The evaluated procedure is passed a closure which contains the expression up to where call/cc was called. Let us see call/cc in action by freezing the point where the value 3 is supplied:

The current continuation is wrapped into the procedure object k. We store this in the global variable frozen and return the value 3 as required by the original expression. So, when it is evaluated the first time, the result will be 5. An easy way to understand continuations is to look at the expression as consisting of the procedure '+' and two holes:

The expression with the hole is stored in the continuation object. Anytime in the future, we can reuse this object like this:

What really happened when we evaluated frozen? The expression (+ 2 []) was resurrected and the hole was filled by the value returned by frozen. Thus the expression becomes (+ 2 10) and gets evaluated to 12. If you are a C programmer, continuations could be understood in the context of the setjmp and longjmp functions. While C allows you to jump back up the stack, call/cc allows moving in any direction. This is achieved by saving the entire stack at the point where call/cc was called. In our example, frozen is actually a closure that stores the stack up to the point where call/cc was evaluated. One common use of continuations is in emulating keywords that provide escape from a context. In the C family of languages these keywords are return, break and continue. Let us see how we can emulate one of them - return:

(define (find-element list-to-search is?)  
  (call/cc 
   (lambda (return)  
     (for element in list-to-search  
      (if (is? element)  
          (return element)))  
     #f)))  
   
;; Test  
   
(define (is-1900? e)  
  (= e 1900))  
  
(find-element (list 1890 2009 1900 2001) is-1900?) ;; => 1900  
(find-element (list 1890 2009 1901 2001) is-1900?) ;; => #f

When the searched element is found, it is passed as the argument of return, which actually represents the point where the evaluation of the body of find-element starts. Each time find-element is evaluated, the hole is filled with either #f or the argument passed to the inner call to return. This creates an illusion that find-element actually returns a value, while in effect the entire body of find-element (the hole) is getting replaced (or filled) by the value to which the continuation procedure evaluates. There is a built-in form that makes it easy to create escape continuations called let/ec. Here is the find-element procedure re-written using let/ec:

(define (find-element list-to-search is?)
  (let/ec return
          (for element in list-to-search
               (if (is? element)
                   (return element)))
          #f))

We can also use let/ec to emulate the break keyword, which can be used to terminate a loop prematurely:


;; This loop prints up to 5
;; and breaks.
;; Note: while is a special form in Spark-Scheme.

(define i 0)
(let/ec break
        (while (< i 10)
               (printf "~a~n" i)
               (if (= i 5)
                   (break #f))
               (set! i (add1 i))))

Continuations find use in implementing features like exception handling, green threads, co-routines etc. Most of these are already taken care of by abstractions built into Spark, so the programmer is saved from directly dealing with continuations. But understanding how continuations work is important because it can be used to provide intuitive solutions to certain kind of problems.

Aaron Lahman:
Hi, I am generally a fan of the box approach used in teaching continuations you use here, I think it's a great way to visualize them.

However, there is a small bug in your first example. Sure enough, if you invoke (frozen 10), the repl will print 12. But if you invoke (+ 1 (frozen 10)), it will _again_ print 12, not 13. 'frozen' doesn't represent (+ 2 []), but it represents _all_ of the program state up the call stack, including the fact that you entered it at the repl invoking 'frozen' could even lead to _undefining_ things you defined after setting 'frozen', because you invoked a continuation that captured the REPL at an earlier point in time. Here's the repro in SISC:

> (define call/cc call-with-current-continuation)
> (define frozen #f)
> (+ 2 (call/cc (lambda (k) (set! frozen k) 3)))
5
> (frozen 10)
12
> (+ 1 (frozen 10))
12
>

I covered this a bit here: http://bit.ly/jOPKU . I've since learned about delimited continuations in PLT Scheme, and they may also be an interesting read http://bit.ly/14kufm.

VIJAY MATHEW