Understanding Scheme Continuations - Part I

Scheme is one of the languages that has built in support for continuations. Sometimes understanding them is a little difficult because of the way they have been explained. The best way to explain them is by example. In Scheme the call-with-current-continuation is one way to use them. This is also abbreviated as call/cc.

The call/cc procedure is passed a function of one argument and that argument is called the current continuation.

One common example used is

(+ 1 (call/cc

       (lambda (k)

         (+ 2 (k 3)))))

In this example there are a couple of things that are important to understand. Firstly the continuation can be explained as

(+ 1 something)

The call/cc part binds a continuation to k and the argument 3. The + 2 is completely ignored. As shown here. Any computation outside of k will be ignored.

 (equal? (call/cc (lambda(k) (+ 2 (k 3)))) 

         (call/cc (lambda (k) (* 10 (k 3))))) ==> #t 

Hence (+ 1 something) ==> (+ 1 3) ==> 4

This is a very simple example of an exiting or escaping continuation. It is useful to use when you want to exit a program in between a recursive loop because of some condition. An example is a list-product function. Written recursively, it gets each element from the list and multiplies it. A continuation could be used to exit when encountering a 0 element, since that automatically means the computation would be 0. Without the exit, the computation will continue unnecessarily.

Declaring a continuation globally can help one reuse it many times, which makes the 'rest of the computation' available for reuse. Taking the same example and modifying it a little.

(define r #f)



(+ 1 (call/cc

       (lambda (k)

         (set! r k)

         (k 3))))

This is when it becomes interesting. The continuation as usual will return 4 when executed the first time. But now it is stored in the global variable r and can be called from the top level with any value.

So

(r 3) ==> 4
(r 10) ==> 11
(r 0.1) ==> 1.1

The critical thing to understand here is that, this is not a function but a continuation. That can be illustrated by

(+ 3 (* 10 (r 5))) ==> 6

As shown above, it abandons the context that surrounds it.

Now we'll take a slightly more interesting example. A simple function that evaluates 2x^2 + 3y + 1. We will bind x and y to continuations.

(define r1 #f)

(define r2 #f)



(define (somefunc x y)

  (+ (* 2 (expt x 2)) (* 3 y) 1))



(somefunc (call/cc

           (lambda (c1)

             (set! r1 c1)

             (c1 1)))

          (call/cc

           (lambda (c2)

             (set! r2 c2)

             (c2 1))))

This example will show how the continuations remember the previous values. To start with it will call (somefunc 1 1) and set the values of x and y as 1 and 1. Everytime we call the continuations r1 and r2, it will record the previous value and use it to compute somefunc.

(r1 5) will compute (somefunc 5 1) and return 54. This will also record the value of x as 5. Now calling (r2 5) will compute (somefunc 5 5) and return 66. Now both x and y have been recorded as 5 and 5. This process will continue for as long as r1 and r2 are called.