call-with-current-continuation

In Scheme programming, the function call-with-current-continuation, abbreviated call/cc, is a control operator. It has been adopted by several other programming languages.

Taking a function f as its only argument, call/cc takes the current continuation (i.e., a "snapshot" of the current control context or control state of the program) as an object and applies f to it. The continuation object is a first-class value and is represented as a function, with function application as its only operation. When a continuation object is applied to an argument, 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 and the argument of the continuation then becomes the "return value" of the call/cc invocation. Continuations created with call/cc may be called more than once, and even from outside the dynamic extent of the call/cc application.

Making this type of implicit program state visible as an object is known in computer science as reification. (Note that Scheme does not syntactically distinguish continuation application from function 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 or even the obscure COMEFROM.

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))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

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)

  ;; 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-with-current-continuation
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))
  
  ;; (-> X u 'you-fell-off-the-end)
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

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.

Call-with-current-continuation can also express other sophisticated primitives. For example, the following code performs cooperative multitasking using continuations:

;; Cooperative multitasking using call-with-current-continuation
;; in 25 lines of scheme

;; The list of threads waiting to run. This is a list of one
;; argument non-returning functions (continuations, mostly)
;; A continuation is a non-returning function, just like (exit),
;; in that it never gives up control to whoever called it.

(define readyList '())

;; A non-returning function. If there is any other thread
;; waiting to be run, it causes the next thread to run if there
;; is any left to run, otherwise it calls the original exit
;; which exits the whole environment.
(define exit
  ;; The original exit which we override.
  (let ((exit exit))
    ;; The overriding function.
    (lambda ()
      (if (not (null? readyList))
	  ;; There is another thread waiting to be run.
	  ;; So we run it.
          (let ((cont (car readyList)))
            (set! readyList (cdr readyList))
	    ;; Since the readyList is only non-returning
	    ;; functions, this will not return.
            (cont '()))
	  ;; Nothing left to run.
	  ;; The original (exit) is a non returning function,
	  ;; so this is a non-returning function.
          (exit)))))

;; Takes a one argument function with a given
;; argument and forks it off.  The forked function's new
;; thread will exit if/when the function ever exits.
(define (fork fn arg)
  (set! readyList
        (append readyList
		;; This function added to the 
		;; readyList is non-returning,
		;; since exit is non returning.
		(cons
		 (lambda (x)
		   (fn arg)
		   (exit)) '()))))

;; Gives up control for the next thread waiting to be run.
;; Although it will eventually return, it gives up control
;; and will only regain it when the continuation is called.
(define (yield)
  (call-with-current-continuation
   ;; Capture the continuation representing THIS call to yield
   (lambda (thisCont)
     ;; Stick it on the ready list
     (set! readyList
           (append readyList
                   (cons thisCont '())))
     ;; Get the next thread, and start it running.
     (let ((cont (car readyList)))
       (set! readyList (cdr readyList))
       ;; Run it.
       (cont '())))))

In 1999, David Madore (the inventor of Unlambda programming language) found a 12 characters term in Unlambda that have the same effect (write all integers in unary form) of an over 600 characters term with an operation equivalent to call/cc.^[1] When converting this term into Scheme he obtained a scheme program that known as the yin-yang puzzle. It was then being customary ^[2] to show while discussing call/cc:

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

An illustration of the puzzle: Every statements between brackets are the states of yin and yang immediately before (yin yang); The number means whether the 1st continuation or the 2nd to jump. The statement after the number represents the context.

;@*
[(yin 1 ()) 
(yang 2 (yin 1 ()))]
;@*
[(yin 2 (yin 1 ()))
(yang 2 (yin 2 (yin 1 ())))]
;*
[(yin 1 ())
(yang 2 (yin 2 (yin 1 ())))]
;@*
[(yin 2 (yin 2 (yin 1 ())))
(yang 2 (yin 2 (yin 2 (yin 1 ()))))]
;*
[(yin 2 (yin 1 ()))
(yang 2 (yin 2 (yin 2 (yin 1 ()))))]
;*
[(yin 1 ())
(yang 2 (yin 2 (yin 2 (yin 1 ()))))]
;@*
[(yin 2 (yin 2 (yin 2 (yin 1 ()))))
(yang 2 (yin 2 (yin 2 (yin 2 (yin 1 ())))))]
;...
;...

Criticism

Oleg Kiselyov, author of a delimited continuation implementation for OCaml and designer of an API for delimited stack manipulation for the implementation of control operators, advocates the use of delimited continuations instead of the full-stack continuations that call/cc manipulates: "Offering call/cc as a core control feature in terms of which all other control facilities should be implemented turns out a bad idea. Performance, memory and resource leaks, ease of implementation, ease of use, ease of reasoning all argue against call/cc"^[3]

Relation to non-constructive logic

The Curry-Howard correspondence between proofs and programs relates call/cc to Peirce's law, which extends intuitionistic logic to non-constructive, classical logic: ((α → β) → α) → α. Here, ((α → β) → α) is the type of the function f, which can either return a value of type α directly or apply an argument to the continuation of type (α → β). Since the existing context is deleted when the continuation is applied, the type β is never used and may be taken to be ⊥.

The principle of double negative elimination ((α → ⊥) → ⊥) → α is comparable to a variant of call-cc which expects its argument f to always evaluate the current continuation without normally returning a value. Embeddings of classical logic into intuitionistic logic are related to continuation passing style translation.^[4]

Languages that implement call/cc

• Scheme
• Racket
• Standard ML ^[5]
• Haskell in the continuation Monad
• Ruby ^[6]
• Unlambda

See also

• GOTO
• Continuation passing style

References

External links

• A short introduction to call-with-current-continuation
• Definition of call-with-current-continuation in the Scheme spec
• Humorous explanation of call-with-current-continuation from Rob Warnock in Usenet's comp.lang.lisp
• Cooperative multitasking in Scheme using Call-CC

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.