Scheme Programming/Continuations

Introduction to call-with-current-continuation

call-with-current-continuation is a procedure that takes as an argument another procedure, that itself takes one argument. That argument is a continuation, which in the words of Scheme inventors Gerald Sussman and Guy Steel, is "just about to return from" call-with-current-continuation. A continuation is a procedure that represents "the rest of the computation." When you call a continuation as a procedure, control jumps to where call-with-current-continuation was originally called and whatever arguments you provide to the continuation become the return values of that call to call-with-current-continuation.

Save the following program:

cont-test.scm:

(define continuations '())

(define (push arg)
  (set! continuations
	(cons arg continuations)))

(define (capture-from-map arg)
  (call-with-current-continuation
   (lambda (cc)
     (push cc)
     arg)))

Then, try this from the REPL:

(load "cont-test.scm")
;  loading cont-test.scm
;  done loading cont-test.scm
#<unspecified>
> (define numbers (map capture-from-map '(1 2 3 4 5 6)))
#<unspecified>
> numbers
(1 2 3 4 5 6)
> continuations
(#<continuation 186 @ 891c400> #<continuation 186 @ 891c800> #<continuation 186 @ 891cc00> #<continuation 186 @ 891c000> #<continuation 186 @ 891b400> #<continuation 186 @ 891b800>)
> ((car (reverse continuations)) 76)
#<unspecified>
> numbers
(76 2 3 4 5 6)

What's going on here? After evaluating (define numbers (map capture-from-map '(1 2 3 4 5 6))), the continuations variable contains the continuation from each time map called capture-from-map, in reverse order. So when we evaluate ((car (reverse continuations) 76), execution control jumps back to where capture-from-map originally returned 1 to the map function, and the entire program stack as it existed at that time is restored. The "rest of the computation" from that point is map mapping capture-from-map across the rest of the list, which is (2 3 4 5 6), and then the resulting list being defined as the variable numbers. But this time around, we changed the result of the part of the computation which took place inside the call-with-current-continuation lambda.

(Note: the result stored in numbers after calling the continuation is implementation dependent, since the standard doesn't specify the order in which map calls the procedure passed as argument.)

The continuations variable is outside the scope of all this, and did not get reverted to '() when control jumped back. As a result, five new continuations were added to continuations:

> continuations
(#<continuation 186 @ 8923c00> #<continuation 186 @ 8923000> #<continuation 186 @ 8922400> #<continuation 186 @ 8922800> #<continuation 186 @ 8922c00> #<continuation 186 @ 8922000> #<continuation 186 @ 8921400> #<continuation 186 @ 8921800> #<continuation 186 @ 8921c00> #<continuation 186 @ 8921000> #<continuation 186 @ 891f400>)
> (length continuations)
11
>

In some Scheme implementations, call-with-current-continuation is also defined as call/cc. However, SCM doesn't define the shorter form. If you want it, you can define it yourself:

(define call/cc call-with-current-continuation)

C++-like Exceptions with Continuations

Some Scheme implementations have their own error-handling syntax, but SCM does not. We can define an exception system using a combination of continuations and macros. C++ exceptions are dynamic: When you throw one, control jumps to the next catch block up the call stack. To make that happen in our implementation, we'll keep a list of continuations that represent the catch blocks. Every time a try block is entered, it'll add a continuation to this stack, and every time a try block exits, a continuation will be removed from the stack. The easy part is implementing the continuation stack:

(define *cont-stack* '())

(define (push-catch cont)
  (set! *cont-stack* (cons cont *cont-stack*)))

(define (pop-catch)
  (let ((retval (car *cont-stack*)))
    (set! *cont-stack* (cdr *cont-stack*))
    retval))

Every time we call push-catch, a new continuation is added to the stack. When we call pop-catch, we get the last continuation that was added (and then the last one before that, etc), and that continuation is also removed from the stack.

dynamic-wind

The hard part is making sure that we detect every time that the block exits or is re-entered (which can happen because of continuations), so that we can maintain the continuation stack in the correct state. Fortunately, Scheme provides dynamic-wind, which take three procedures as arguments and has the same return value(s) as the middle lambda. The first and last procedures are guard procedures that can perform initialization and cleanup before entering and after exiting the middle procedure:

(dynamic-wind
   (lambda ()
      (let ((exception
	     (call-with-current-continuation
	      (lambda (cc)
		(push-catch cc)
		#f))))
	(if exception
	    (begin catch-body ... (escape)))))
    (lambda ()
      (begin body ...))
    (lambda () (pop-catch)))

The only thing left to do is define the escape continuation, which allows execution to leave the try block after the catch executes (otherwise the body would be executed again), and wrap it all in a macro. The entire program looks like this:

exception.scm

(require 'macro) ; Required to use this with SCM. Other Scheme implementations
                 ; may not require this, or it may even be an error.
(define *cont-stack* '())

(define (push-catch cont)
  (set! *cont-stack* (cons cont *cont-stack*)))

(define (pop-catch)
  (let ((retval (car *cont-stack*)))
    (set! *cont-stack* (cdr *cont-stack*))
    retval))

(define (throw exn)
  (if (null? *cont-stack*)
      (error "Can't use throw outside of a try form")
      ((car *cont-stack*) exn)))

(define-syntax try
  (syntax-rules (catch)
    ((try (body ...)
	  catch exception (catch-body ...))
     (call-with-current-continuation
      (lambda (escape)
	(dynamic-wind
	    (lambda ()
	      (let ((exception
		     (call-with-current-continuation
		      (lambda (cc)
			(push-catch cc)
			#f))))
		(if exception
		    (begin catch-body ... (escape)))))
	    (lambda ()
	      (begin body ...))
	    (lambda () (pop-catch))))))))

With the above program loaded into Scheme, you now have the ability to put error-handling code in one place, and you can jump to that place by calling the throw procedure, whose argument can be any value but #f. Use the argument to send information about what went wrong to the error-handling code.

(define (my-/ numerator denominator)
  (if (not (and (number? numerator)
                (number? denominator)))
      (throw "my-/ is for numbers")
      (/ numerator denominator)))

(try ((display (my-/ "two" "one"))
      (newline))
 catch message ((display message)
                (newline)))