Call-with-current-continuation

From Wikipedia, the free encyclopedia

In computer science, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages.

Taking a function f as its only argument, call/cc reifies the current continuation (i.e. control context or control state of the program) as an object and applies f to it. The continuation object is a first-class value with application as the only operation. Scheme does not syntactically distinguish continuation application from function application. When a continuation object is applied, the existing continuation is eliminated and the applied continuation is restored in its place so that the program flow will continue at the point at which the continuation was captured. Continuations created with call/cc may be called more than once, and even from outside the dynamic extent of the call/cc application.

With call/cc a programmer can implement a variety of complex control operators from other languages via a few lines of code, e.g. McCarthy's amb operator for non-deterministic choice, Prolog-style backtracking, Simula 67-style coroutines and generalizations thereof, Icon-style generators, or engines and threads.

Lisp users have criticized the "call/cc" function as an unnecessarily complicated and difficult-to-implement means.^{[citation needed]} They hold that each one of those tasks can and should be implemented without call/cc, and that doing so will provide faster and more efficient constructs. Indeed, in many implementations of Scheme, the implementation of call/cc comes with a large speed and space overhead as with each call to call/cc the control stack is copied and placed in the heap as a continuation object; a call to a continuation replaces the existing control stack with the encapsulated one. Kent Dybvig, the implementor of the Scheme implementation Chez Scheme, and his collaborators have shown, however, that this overhead can be reduced to a few bits over a programming language implementation that allows arbitrarily deep recursions. The technique employs a form of lazy stack copying, i.e. call/cc becomes a constant-time allocation operation, and returns to captured continuations copy the existing stack only as far as needed.

[edit] Examples

As shown by the following example, call/cc can be used to emulate the functionality of the return statement known from C-style languages, which is missing from Scheme:

(define (f return)
  (return 2)
  3)
 
(display (f (lambda (x) x)))
 
(display (call-with-current-continuation f))

Calling f with a regular function argument first applies this function to the value 2, then returns 3. However, when f is passed to call/cc (as in the last line of the example), applying the parameter (the continuation) to 2 forces execution of the program to jump to the point where call/cc was called, and causes call/cc to return the value 2. This is then printed by the display function.

In the following example, call/cc is used twice: once to generate a "return" continuation as in the first example and once to suspend an iteration through a list of items:

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)
  ;; (-> X u 'you-fell-off-the-end)
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call/cc control-state)) 
 
  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each 
     (lambda (element)
       (set! return
             (call/cc
              (lambda (resume-here)
                ;; Grab the current continuation
                (set! control-state resume-here)
                (return element)))))
     lst)
    (return 'you-fell-off-the-end))
 
  ;; Return the generator 
  generator)
 
(define generate-digit
  (generate-one-element-at-a-time '(0 1 2 3 4 5 6 7 8 9)))
 
(generate-digit)
(generate-digit)

Every time the loop is about to process another item from the list, the function grabs the current continuation, and assigns it to the variable 'control-state'. This variable initially is the closure that iterates through all elements of the list. As the computation progresses, it becomes a closure that iterates through a suffix of the given list. While the use of "call/cc" is unnecessary for a linear collection, such as [LISTOF X], the code generalizes to any collection that can be traversed.