Thursday, June 03, 2004

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.


(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)))
(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.


Anonymous Anonymous said...

Very nice!

Really helped me understanding the very basics.


10:14 AM  
Blogger sekat said...

thank you

6:41 AM  

Post a Comment

Subscribe to Post Comments [Atom]

<< Home