Chapter 6
Continuations

Kurt N�rmark ©
Department of Computer Science, Aalborg University, Denmark

Abstract
Previous lecture Next lecture
Index References Contents		 In this lecture we will discuss the continuation concept, as it is available in Scheme. Please notice that this lecture is only a half lecture, compared to the size of the earlier lectures in this collection

Introduction and motivation
Introduction and motivation
Slide Note Contents Index
References 

There is a need to be able to escape from a deep expression, in exceptional cases, for instance

We are interested in a primitive which provides advanced control of the remaining part of a calculation - a so-called continuation - relative to some given point in it

  • Exit or exception mechanism:

    • The need to abandon some deep evaluation

    • Still within the functional context

  • Continuation

    • Capturing of continations

    • Exploring new control mechanisms by means of continuations

Scheme support first class continuations dressed as functions

'Jumping' with catch and throw
The catch and throw idea
Slide Note Contents Index
References 

Catch and throw provides for an intuitively simple escape mechanism on functional ground

Syntax: 

(catch 'id expr)

Syntax: 

(throw 'id return-expression)

Scheme does not support catch and throw

Rather Scheme supports a much more powerful mechanisms based on the capturing of continations

A catch and throw example
Slide Note Contents Index
References 

Exit from a list length function in case it discovers a non-empty tail of the list

Program: An example using catch and throw. Please notice that the example is not a proper Scheme program. Catch and throw are not defined in Scheme.
 
(define (list-length lst)
  (catch 'exit
    (letrec ((list-length1
               (lambda (lst) 
                 (cond ((null? lst) 0)
                   ((pair? lst) (+ 1 (list-length1 (cdr lst))))
                   (else (throw 'exit 'improper-list))))))
       (list-length1 lst))))

Catch and throw are not available in standard Scheme

The continuation idea
The intuition behind continuations
Slide Note Contents Index
References 

The concept continuation: A continuation of the evaluation of an expresion E in a surrounding context C represents the entire future of the computation, which waits for the value of E

Table. An intuitive understanding of continuations of an expression in some context.
Context C and expression E

 Inituitive continuation of E in C

 
(+ 5 (* 4 3))
 The adding of 5 to the value of E 
(cons 1 (cons 2 (cons 3 '())))
 The consing of 3, 2 and 1 to the value of E 
(define x 5)
(if (= 0 x)
    'undefined
    (remainder (* (+ x 1) (- x 1)) x))
 The multiplication of E by x - 1 followed by a division by x
 

Being more precise
Slide Note Contents Index
References 

We can form a lambda expression that represents a continuation

Table. A more precise notation of the continuations of E
Context C and expression E

 The continuation of E in C

 
(+ 5 (* 4 3))
 
(lambda (e) (+ 5 e))
 
(cons 1 (cons 2 (cons 3 '())))
 
(lambda (e) (cons 1 (cons 2 (cons 3 e))))
 
(define x 5)
(if (= 0 x)
    'undefined
    (remainder (* (+ x 1) (- x 1)) x))
 
(lambda (e) (remainder (* e (- x 1)) x))
 

The capturing of continuations
Slide Note Contents Index
References 

Scheme provides a primitive that caputures a continuation of an expression E in a context C

The primitive is called call-with-current-continuation, or call/cc as a short alias

call/cc takes a parameter, which is a function of one parameter.

The parameter of the function is bound to the continuation, and the body of the function is E

Table. Use of call/cc and capturing of continuations.
Context C and the capturing 

(+ 5 (call/cc (lambda (e) (* 4 3)) ))
 
(cons 1 (cons 2 (cons 3 (call/cc (lambda (e) '()) ))))
 
(define x 5)
(if (= 0 x)
    'undefined
    (remainder (* (call/cc (lambda (e) (+ x 1)) ) (- x 1)) x))
 

Capturing, storing, and applying continuations
Slide Note Contents Index
References 

We here show capturing, imperative assignment, and a subsequent application of a continuation

Table. Capturing and immediate application of the capture continuations. Notice that the vaues of the expressions E are ignored in these examples
Context C and expression E

 Value of C

 Application of continuation

 Value

 
(+ 5 
 (call/cc 
  (lambda (e) 
   (set! cont-remember e)
   (* 4 3))))
 
17
 
(cont-remember 3)
 
8
 
(cons 1 
 (cons 2 
  (cons 3 
   (call/cc 
    (lambda (e) 
     (set! cont-remember e)
     '())))))
 
(1 2 3)
 
(cont-remember '(7 8))
 
(1 2 3 7 8)
 
(define x 5)
(if (= 0 x)
    'undefined
    (remainder 
     (* (call/cc 
         (lambda (e) 
          (set! cont-remember e)
          (+ x 1) ))
        (- x 1))
     x))
 
4
 
(cont-remember 3)
 
2
 

Use of continuations for escaping purposes
Slide Note Contents Index
References 

We here illustrate applications of the continuations for escape purposes

Table. Capturing and use of a continuation for escaping purposes
Context C, capturing, and escape call

 Value

 
(+ 5 
 (call/cc (lambda (e) (* 4 (e 10)))) )
 
15
 
(cons 1 
 (call/cc (lambda (e) (cons 2 (cons 3 (e 'x))))) )
 
(1 . x)
 
(define x 5)

(if (= 0 x)
    'undefined
    (call/cc (lambda (e) (remainder (* (+ x 1) (- x (e 111))) x))) )
 
111
 

Practical examples
Practical example: Length of an improper list
Slide Note Contents Index
References 

The length of an improper list is undefined

We chose to return the symbol improper-list if list-length encounters an improper list

This example is similar to the catch and throw example shown earlier in this section

Program: The function list-length, which returns the symbol 'improper-list in case it encounters an improper list.
 
(define (list-length l)
  (call-with-current-continuation
   (lambda (do-exit) (letrec ((list-length1 (lambda (l) (cond ((null? l) 0) ((pair? l) (+ 1 (list-length1 (cdr l)))) (else (do-exit 'improper-list)))))) (list-length1 l))) ))

Practical example: Seaching a binary tree
Slide Note Contents Index
References 

Searching a binary tree involves a recursively defined tree traversal

If we find the node we are looking for it is convenient to throw the out of the tree traversal

Program: A tree search function which uses a countinuation found if we find what we search for. Notice that this examples requires the function subtree-list, in order to work. The function returns #f in case we do not find node we are looking for. Notice that it makes sense in this example to have both the if expression and the #f value in sequence!
 
(define (find-in-tree tree pred)
 (call-with-current-continuation
  (lambda (found) (letrec ((find-in-tree1 (lambda (tree pred) (if (pred tree) (found tree) (let ((subtrees (subtree-list tree))) (for-each (lambda (subtree) (find-in-tree1 subtree pred)) subtrees))) #f))) (find-in-tree1 tree pred))) ))

Practical example: Coroutines
Slide Note Contents Index
References 

The implementation of coroutines is easily facilitated by capturing of continuations

Discussed at the black board

Contination passing style
Continuation passing style
Slide Note Contents Index
References 

The concept continuation passing style: Continuation passing style is a programming technique which rely on an extra parameter to each function. The extra parameter represents the contination of the computation

Continuation passing style stands for a radical restructuring of a 'normal style' program

With contination passing style, the use of call-with-current-contination is not longer needed

Program: A determinant function programmed in direct style.
 
(define (determinant a b c)
  (sub (square b)
       (mult (mult 4 a) c)))

(define (square a)
  (mult a a))

(define (mult a b)
  (* a b))

(define (sub a b)
  (- a b))

Program: A determinant function programming in continuation passing style. In order to apply it, pass the identity function of one parameter, (lambda (x) x), as actual parameter.
 
(define (determinant a b c k0)
  (mult 4 a 
    (lambda (v1)
      (mult v1 c 
        (lambda(v2)
          (square b 
            (lambda(v3)
              (sub v3 v2 k0))))))))
                                 
(define (square a k1)
  (mult a a k1))

(define (mult a b k2)
  (k2 (* a b)))

(define (sub a b k3)
  (k3 (- a b)))

Source files in this lecture
Contents Index References		 includes/catch-throw-ex
includes/list-length.scm
includes/tree-search.scm
includes/determinant.scm
includes/determinant-cps.scm
 

Chapter 6: Continuations
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: November 6, 2001, 10:37:09