Previous Table of Contents Next


If a 0 is detected, helper returns 0 directly without invoking next. The continuations that would have done the multiplications are never invoked:

   (list-mult ‘(2 3 0 4))
   (helper ‘(2 3 0 4) (lambda (x) x))
   (helper ‘(3 0 4) (lambda (result)
                      ((lambda (x) x) (* 2 result))))
   (helper ‘(0 4) (lambda (result)
                    ((lambda (result)
                       ((lambda (x) x) (* 2 result)))
                     (* 3 result))))
   0

CPS puts the burden of establishing and administering continuations on the programmer. But any computation, in any language, has an implicit continuation: What tasks are left to do after this computation finishes? For example, going back to the simple expression

   (+ (* 2 3) 4)

you can see that the implicit continuation of the multiplication is

   (lambda (result) (+ result 4))

If you imagine a compiler producing a machine language program for this expression, after the multiply instruction would come some instructions to add 4 to the result of the multiplication. (Actually, this is overly simplified. The real continuation of the multiplication, supposing that the expression was typed directly at the Scheme prompt, adds 4 to the result, prints the sum, and prompts the user for a new expression to evaluate. So the continuation isn’t really the same as the preceding lambda expression.)

Scheme allows the programmer to gain access to these implicit continuations. The Scheme primitive call-with-current-continuation (for which most Scheme implementations provide the abbreviation call/cc) takes one argument, a procedure that itself takes one argument. Scheme calls that argument procedure with the continuation of the call/cc as the argument. That is, in the expression

   (+ (call/cc (lambda (cont) (cont (* 2 3)))) 4)

the symbol cont represents the same continuation, now made explicit, as the continuation of (* 2 3) in the earlier expression:

   (define (list-mult nums)
     (call/cc (lambda (escape)
                (define (helper nums)
                  (if (null? nums)
                      1
                      (if (= (car nums) 0)
                          (escape 0)
                          (* (car nums) (helper (cdr nums))))))
                (helper nums))))

Here the helper procedure looks almost exactly like the conventional version without continuations; the only complication is that a call/cc is wrapped around it, and the resulting continuation is invoked if a 0 is seen. It may look as if the multiplications before the 0 must be carried out, as in the conventional version, but in fact, no multiplication is done at all until the recursion reaches the end of the list; the multiplications are done on the way out. Calling the escape continuation within helper avoids all of them.

The list-mult example uses continuations as a form of nonlocal exit, such as the setjmp and longjmp procedures in C or the catch and throw procedures in traditional versions of Lisp. call/cc corresponds to setjmp or catch, and invoking the continuation that it provides corresponds to longjmp or throw. Those other nonlocal exit mechanisms have the restriction that the exit (the longjmp or the throw) can be used only until the computation within the range of the corresponding setjmp or catch has completed. In Scheme, a continuation provided by call/cc is valid forever3:


3set! is Scheme’s notation for assigning a new value to a variable.
   > (define my-continuation ‘())    ; Make a global variable (value
                        ;irrelevant)

   > (+ (call/cc (lambda (cont)
                   (set! my-continuation cont)   ; Save this continuation
                   (cont (* 2 3)))) 4)         ; Finish the computation
   10
   
   > (my-continuation 20)            ; The saved continuation still works
   24

As a result, Scheme continuations can be used not only for nonlocal exit but to implement any desired control structure. For example, a multithreaded system can be implemented by using a continuation to remember the status of each thread that isn’t running right now.4


4The dot in the first line of the definition of together indicates that it accepts any number of arguments, whose values are presented to the procedure in a list. let creates a local variable and specifies its value. The variable exists only within the scope of the let; it’s not like set!, which affects a variable in a scope outside the let. The notation
   (let ((variable1 value1) (variable2 value2)) body)

is just an abbreviation for
   ((lambda (variable1 variable2) body) value1 value2)

That is, let is just a syntactic convenience for creating and invoking a procedure. for-each invokes a procedure, in this case fork, repeatedly with each element of a list, in this case tasks, as the argument.

   (define the-forks ‘())          ; list of all suspended forks

   (define finisher ‘())           ; will be continuation to end forking
   (call/cc (lambda (cont) (set! finisher cont)))

   (define (together . tasks)      ; run several tasks in parallel
     (for-each fork tasks)
     (waiter))

   (define (fork process)          ; create a new fork
     (call/cc (lambda (cont)
                (set! the-forks (append the-forks (list cont)))
                (process))))

   (define (wait)                  ; suspend this fork, resume another
     (call/cc (lambda (cont)
                (set! the-forks (append the-forks (list cont)))
                (let ((next-to-run (car the-forks)))
                  (set! the-forks (cdr the-forks))
                  (next-to-run ‘okay)))))

   (define (exit-fork)             ; finish this fork, resume another
     (if (not (null? the-forks))
         (let ((next-to-run (car the-forks)))
           (set! the-forks (cdr the-forks))
           (next-to-run ‘okay))
         (finisher ‘okay)))

   (define (waiter)                ; make sure all forks run to completion
     (if (not (null? the-forks))
         (begin (wait) (waiter))
         ‘finished))


Previous Table of Contents Next