In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, 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 takes the current continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
(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
Function application
In mathematics, function application is the act of applying a function to an argument from its domain so as to obtain the corresponding value from its range.-Representation:...
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 will become 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
Reification (computer science)
Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object — a resource — is created in a system as a proxy for a non computable/addressable object...
. (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
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
s and generalizations thereof, Icon-style generator
Generator (computer science)
In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values...
An engine is a continuation-based construct that provides timed preemption. Engines which can contain other engines are sometimes called nesters and engines which don't have this ability are then called flat engines or "solo engines" . To implement timed preemption there needs to be a clock. This...
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process...
s.
Relation to non-constructive logic
The Curry-Howard correspondence between proofs and programs relates call/cc to Peirce's law
Peirce's law
In logic, Peirce's law is named after the philosopher and logician Charles Sanders Peirce. It was taken as an axiom in his first axiomatisation of propositional logic. It can be thought of as the law of excluded middle written in a form that involves only one sort of connective, namely...
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...
: ((α → β) → α) → α. 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 ⊥.
In propositional logic, the inference rules double negative elimination allow deriving the double negative equivalent by adding or removing a pair of negation signs...
((α → ⊥) → ⊥) → α 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.
Examples
As shown by the following example, call/cc can be used to emulate the functionality of the return statement
Return statement
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after where the subroutine was called, known as its return address. The return address is saved, usually on the process's call stack, as part of the operation...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
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))
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-continuatio
in 25 lines of schem
The list of threads waiting to run. This is a list of on
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 threa
waiting to be run, it causes the next thread to run if ther
is any left to run, otherwise it calls the original exi
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 give
argument and forks it off. The forked function's ne
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 contro
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 ')))))
It is customary to show the yin-yang puzzle 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))
