5.5. Continuations

Continuations in Scheme are procedures that represent the remainder of a computation from a given point in the continuation. They may be obtained with call-with-current-continuation, which can be abbreviated call/cc in many Scheme implementations.

`(call-with-current-continuation` procedure`)`	procedure
returns: the result of applying procedure to the current continuation

call-with-current-continuation is often abbreviated call/cc for the obvious reason that it requires fewer keystrokes to type. If the implementation you use does not have a binding for call/cc, you can define it or use the longer name in your code.

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

call/cc obtains its continuation and passes it to procedure, which must accept one argument. The continuation itself is represented by a procedure of one argument. (In the context of multiple values, a continuation may actually accept zero or more than one argument; see Section 5.7.) Each time this procedure is applied to a value, it returns the value to the continuation of the call/cc application. That is, when the continuation procedure is given a value, it returns the value as the result of the application of call/cc.

If procedure returns normally when passed the continuation procedure, the value returned by call/cc is the value returned by procedure.

Continuations allow the implementation of nonlocal exits, backtracking [9, 21], coroutines [11], and multitasking [6, 24].

The example below illustrates the use of a continuation to perform a nonlocal exit from a loop.

 (define member   (lambda (x ls)     (call/cc       (lambda (break)         (do ((ls ls (cdr ls)))             ((null? ls) #f)             (if (equal? x (car ls))                 (break ls))))))) (member 'd '(a b c)) ⇒ #f (member 'b '(a b c)) ⇒ (b c)

Additional examples are given in Sections 3.3 and 9.11.

The current continuation is typically represented internally as a stack of procedure activation records, and obtaining the continuation involves encapsulating the stack within a procedural object. Since an encapsulated stack has indefinite extent, some mechanism must be used to preserve the stack contents indefinitely. This can be done with surprising ease and efficiency and with no impact on programs that do not use continuations [12].

`(dynamic-wind` in body out`)`	procedure
returns: result of applying body

dynamic-wind offers "protection" from continuation invocation. It is useful for performing tasks that must be performed whenever control enters or leaves body, either normally or by continuation application.

The three arguments in, body, and out must be procedures of no arguments, i.e., thunks. Before applying body, and each time body is entered subsequently by the application of a continuation created within body, the in thunk is applied. Upon normal exit from body and each time body is exited by the application of a continuation created outside body, the out thunk is applied.

Thus, it is guaranteed that in is invoked at least once. In addition, if body ever returns, out is invoked at least once.

dynamic-wind appears in the Revised⁵ Report but not in the ANSI/IEEE standard.

The following example demonstrates the use of dynamic-wind to be sure that an input port is closed after processing, regardless of whether the processing completes normally.

 (let ((p (open-input-file "input-file")))   (dynamic-wind     (lambda () #f)     (lambda () (process p))     (lambda () (close-input-port p))))

Common Lisp provides a similar facility (unwind-protect) for protection from nonlocal exits. This is often sufficient. unwind-protect provides only the equivalent to out, however, since Common Lisp does not support fully general continuations. Here is how unwind-protect might be specified with dynamic-wind.

 (define-syntax unwind-protect   (syntax-rules ()     (( body cleanup ...)      (dynamic-wind        (lambda () #f)        (lambda () body)        (lambda () cleanup ...))))) ((call/cc    (let ((x 'a))      (lambda (k)        (unwind-protect          (k (lambda () x))          (set! x 'b)))))) ⇒ b

Some Scheme implementations support a controlled form of assignment known as uid binding, in which a variable takes on a temporary value during a given computation and reverts to the old value after the computation has completed. The syntactic form fluid-let defined below in terms of dynamic-wind permits the uid binding of a single variable x to a value v within a sequence of expressions e1 e2 ….

 (define-syntax fluid-let   (syntax-rules ()     (( ((x v)) e1 e2 ...)      (let ((y v))        (let ((swap (lambda () (let ((t x)) (set! x y) (set! y t)))))          (dynamic-wind swap (lambda () e1 e2 ...) swap))))))

(Implementations that support fluid-let generally extend it to allow an indefinite number of (x v) pairs, as with let.)

If no continuations are invoked within the body of a fluid-let, the behavior is the same as if the variable were simply assigned the new value on entry and assigned the old value on return.

 (let ((x 3))   (+ (fluid-let ((x 5))        x)      x)) ⇒ 8

A uid-bound variable also reverts to the old value if a continuation created outside of the fluid-let is invoked.

 (let ((x 'a))   (let ((f (lambda () x)))     (cons (call/cc             (lambda (k)               (fluid-let ((x 'b))                 (f))))           (f)))) ⇒ (b . a)

If control has left a fluid-let body, either normally or by the invocation of a continuation, and control reenters the body by the invocation of a continuation, the temporary value of the uid-bound variable is reinstated. Furthermore, any changes to the temporary value are maintained and reected upon reentry.

 (define reenter #f) (define x 0) (fluid-let ((x 1))   (call/cc (lambda (k) (set! reenter k)))   (set! x (+ x 1))   x) ⇒ 2 x ⇒ 0 (reenter '*) ⇒ 3 (reenter '*) ⇒ 4 x ⇒ 0

An implementation of dynamic-wind is given below. In addition to defining dynamic-wind, the code redefines call/cc (call-with-current-continuation).

 (define dynamic-wind #f) (let ((winders '()))   (define common-tail     (lambda (x y)       (let ((lx (length x)) (ly (length y)))         (do ((x (if (> lx ly) (list-tail x (- lx ly)) x) (cdr x))              (y (if (> ly lx) (list-tail y (- ly lx)) y) (cdr y)))             ((eq? x y) x)))))   (define do-wind     (lambda (new)       (let ((tail (common-tail new winders)))         (let f ((l winders))           (if (not (eq? l tail))               (begin                 (set! winders (cdr l))                 ((cdar l))                 (f (cdr l)))))       (let f ((l new))         (if (not (eq? l tail))             (begin               (f (cdr l))               ((caar l))               (set! winders l)))))))   (set! call/cc     (let ((c call/cc))       (lambda (f)         (c (lambda (k)              (f (let ((save winders))                   (lambda (x)                     (if (not (eq? save winders)) (do-wind save))                     (k x)))))))))   (set! call-with-current-continuation call/cc)     (set! dynamic-wind       (lambda (in body out)         (in)         (set! winders (cons (cons in out) winders))         (let ((ans (body)))           (set! winders (cdr winders))           (out)           ans))))

Together, dynamic-wind and call/cc manage a list of winders. A winder is a pair of in and out thunks established by a call to dynamic-wind. Whenever dynamic-wind is invoked, the in thunk is invoked, a new winder containing the in and out thunks is placed on the winders list, the body thunk is invoked, the winder is removed from the winders list, and the out thunk is invoked. This ordering ensures that the winder is on the winders list only when control has passed through in and not yet entered out. Whenever a continuation is obtained, the winders list is saved, and whenever the continuation is invoked, the saved winders list is reinstated. During reinstatement, the out thunk of each winder on the current winders list that is not also on the saved winders list is invoked, followed by the in thunk of each winder on the saved winders list that is not also on the current winders list. The winders list is updated incrementally, again to ensure that a winder is on the current winders list only if control has passed through its in thunk and not entered its out thunk.

The test (not (eq? save winders)) performed in call/cc is not strictly necessary but makes invoking a continuation less costly whenever the saved winders list is the same as the current winders list.