Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
Call-with-current-continuation
View on WikipediaIn the Scheme computer programming language, the procedure call-with-current-continuation, abbreviated call/cc, is used as a control flow operator. It has also been adopted by several other programming languages.
Taking a function f as its only argument, (call/cc f) within an expression is applied to the current continuation of the expression.
For example ((call/cc f) e2) is equivalent to applying f to the current continuation of the expression. The current continuation is given by replacing (call/cc f) by a variable c bound by a lambda abstraction, so the current continuation is (lambda (c) (c e2)). Applying the function f to it gives the final result (f (lambda (c) (c e2))).
As a complementary example, in an expression (e1 (call/cc f)), the continuation for the sub-expression (call/cc f) is (lambda (c) (e1 c)), so the whole expression is equivalent to (f (lambda (c) (e1 c))).
In other words it takes 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.
In computer science, making this type of implicit program state visible as an object is termed reification. (Scheme does not syntactically distinguish between applying continuations or functions.)
With call/cc a variety of complex control operators can be implemented from other languages via a few lines of code, e.g., McCarthy's amb operator for nondeterministic choice, Prolog-style backtracking, Simula 67-style coroutines and generalizations thereof, Icon-style generators, or engines and threads or even the obscure COMEFROM[citation needed].
Examples
[edit]As shown by the next example, call/cc can be used to emulate the function of the return statement known from C-style languages, which is missing from Scheme:
(define (f return)
(return 2)
3)
(f (lambda (x) x))
=> 3
(call-with-current-continuation f)
=> 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 next 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)
;; Both internal functions are closures over lst
;; Internal variable/Function which passes the current element in a list
;; to its return argument (which is a continuation), or passes an end-of-list marker
;; if no more elements are left. On each step the function name is
;; rebound to a continuation which points back into the function body,
;; while return is rebound to whatever continuation the caller specifies.
(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))))) ;; (return element) evaluates to next return
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 next sample 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 whatever called it.
(define ready-list '())
;; 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? ready-list))
;; There is another thread waiting to be run.
;; So we run it.
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
;; Since the ready-list is only non-returning
;; functions, this will not return.
(cont #f))
;; 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! ready-list
(append ready-list
;; This function added to the
;; ready-list is non-returning,
;; since exit is non returning.
(list
(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 (cont)
;; Stick it on the ready list
(set! ready-list
(append ready-list
(list cont)))
;; Get the next thread, and start it running.
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
;; Run it.
(cont #f)))))
In 1999, David Madore (inventor of the Unlambda programming language) accidentally discovered a 12-character Unlambda term, making use of call/cc, that printed all natural numbers sequentially in unary representation: ``r`ci`.*`ci.[1] This program and the apparent mystery surrounding its effect have attracted some attention, and are commonly known as the yin-yang puzzle.[2] A Scheme translation, provided by Madore, is as follows:
(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))
Criticism
[edit]Oleg Kiselyov, author of a delimited continuation implementation for OCaml, and designer of an application programming interface (API) for delimited stack manipulation to implement 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
[edit]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 empty type.
The principle of double negation 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 implementing call/cc
[edit]See also
[edit]References
[edit]- ^ David Madore, "call/cc mind-boggler"
- ^ Yin Wang, "Understanding the Yin-Yang Puzzle"
- ^ "An argument against call/cc".
- ^ Sørensen, Morten Heine; Urzyczyn, Paweł (2007). "Classical Logic and Control Operators". Lectures on the Curry-Howard isomorphism (1st ed.). Boston, MA: Elsevier. ISBN 978-0444520777.
- ^ "The CONT signature". Standard ML of New Jersey. Bell Labs, Lucent Technologies. 1997-10-28. Retrieved 2019-05-15.
- ^ "class Continuation - Documentation for Ruby 3.5".
- ^ Kowalke, Oliver (2014). "Context switching with call/cc". Boost.org. Retrieved 2019-05-15.
- ^ "R: Call with Current Continuation".
External links
[edit]- A short introduction to
call-with-current-continuation - Definition of
call-with-current-continuationin the Scheme spec - Humorous explanation of
call-with-current-continuationfrom Rob Warnock in Usenet'scomp.lang.lisp - Cooperative multitasking in Scheme using Call-CC
Call-with-current-continuation
View on Grokipedia(call-with-current-continuation
(lambda (exit)
(for-each (lambda (x)
(if (negative? x) (exit x)))
'(54 0 37 -3 245 19))))
; => -3
(call-with-current-continuation
(lambda (exit)
(for-each (lambda (x)
(if (negative? x) (exit x)))
'(54 0 37 -3 245 19))))
; => -3
(define list-length
(lambda (obj)
(call-with-current-continuation
(lambda (return)
(letrec ((r (lambda (obj)
(cond ((null? obj) 0)
((pair? obj) (+ (r (cdr obj)) 1))
(else (return #f))))))
(r obj))))))
(define list-length
(lambda (obj)
(call-with-current-continuation
(lambda (return)
(letrec ((r (lambda (obj)
(cond ((null? obj) 0)
((pair? obj) (+ (r (cdr obj)) 1))
(else (return #f))))))
(r obj))))))
'(1 2 3 4) but #f for '(a b . c).[1] Beyond Scheme, the idea has influenced languages like C++ proposals for stackful coroutines and functional programming paradigms emphasizing delimited continuations.[5]
Overview
Definition and Purpose
call-with-current-continuation, commonly abbreviated as call/cc, is a higher-order function in the Scheme programming language that captures the current continuation and passes it as an argument to a provided procedure. Its signature is(call/cc proc), where proc is a procedure accepting one argument—the captured continuation.[7] When invoked, call/cc calls proc with this continuation, which is packaged as an escape procedure; if proc returns normally, that value becomes the result of the call/cc invocation, but if the escape procedure is called instead, it restores the captured continuation and supplies the given value as the result.[1]
The primary purpose of call/cc is to enable explicit capture and manipulation of the current continuation, facilitating non-local control flow in functional programming paradigms where such mechanisms are not natively provided.[7] This allows programmers to implement advanced control structures, such as coroutines for cooperative multitasking, exception-like handling for error propagation, and backtracking for search algorithms, by treating the program's execution context as manipulable data rather than implicit stack management.[1]
At its core, call/cc reifies the continuation—the remaining computation to be performed after the current point—as a first-class value, specifically a procedure that can be stored, passed around, and invoked at any later time. This reification transforms abstract control flow into concrete, programmable entities, empowering developers to compose and redirect execution dynamically. The key benefit lies in its provision of fine-grained control over program dynamics, allowing explicit treatment of continuations as data to achieve behaviors that would otherwise require language extensions or lower-level interventions.[7]
Historical Development
The concept of continuations, foundational to call-with-current-continuation (call/cc), was first systematically explored by John C. Reynolds in his 1972 paper "Definitional Interpreters for Higher-Order Programming Languages," where he used them to define interpreters for higher-order languages, enabling the representation of control flow as data values.[8] This work built on earlier ideas, such as Peter Landin's J-operator from 1965, but Reynolds' formulation provided a practical mechanism for embedding continuations within program values, influencing subsequent language designs.[9] Scheme, developed by Guy L. Steele Jr. and Gerald J. Sussman, incorporated continuations early in its evolution through the Lambda Papers series published between 1975 and 1980 at MIT's Artificial Intelligence Laboratory. The initial 1975 description of Scheme as an interpreter for extended lambda calculus did not explicitly include call/cc, but subsequent papers, such as "Lambda: The Ultimate Imperative" (1976), modeled imperative constructs using continuation-passing style, demonstrating how continuations could simulate escapes and nonlocal control.[10] By the Revised Report on Scheme (RRS) in 1978, continuations were integrated as a core element for advanced control, evolving from the 1975 "catch" special form into a more procedural approach; call/cc itself emerged in later implementations around 1982, named by Scheme developers to capture the current continuation explicitly.[11] These developments in the Lambda Papers profoundly shaped functional programming by emphasizing continuations as first-class entities for expressing complex control flows without traditional stacks.[12] call/cc was first standardized in the Revised^3 Report on the Algorithmic Language Scheme (R3RS) in 1986, where it was defined as a primitive procedure packaging the current continuation as an escape procedure of unlimited extent.[13] This was followed by further refinements in the Revised^5 Report (R5RS) in 1998 and the Revised^7 Report (R7RS) in 2013, which retained call/cc unchanged while introducing library support and enhanced exception handling, ensuring compatibility with prior standards.[14] Early practical implementations, such as Chez Scheme developed by R. Kent Dybvig starting in 1984, demonstrated call/cc's utility in production interpreters, transitioning it from a theoretical tool in continuation-passing interpreters to a robust feature for tasks like coroutines and backtracking.[15] As of 2025, call/cc has seen continued adoption in modern Scheme variants without major syntactic alterations, as evidenced by its standard inclusion in GNU Guile 3.0 (released 2020), which added just-in-time compilation while preserving full continuation support for high-performance applications.[16] Discussions in language design communities have explored safer delimited continuations as alternatives, but call/cc remains a core, unaltered primitive in implementations like Guile 3.x, underscoring its enduring influence on Scheme's paradigm.[17]Core Concepts
Continuations
In computer science, a continuation represents the remainder of a computation following a given point in a program, encapsulating the future course of execution from that point onward. It is typically modeled as a function that takes a value as input and produces the final answer of the overall computation. This abstraction originated in early work on denotational semantics for handling control structures like jumps.[18] In the context of Scheme, continuations captured by call/cc are escape continuations, which are designed for non-local exits and can be invoked multiple times, each unwinding the current stack to the capture point and restoring the continuation from there by supplying the value as the result of the call/cc.[19] A key conceptual model for understanding continuations is continuation-passing style (CPS), a programming paradigm where every function accepts an additional argument representing its continuation, explicitly passing control to it upon completion. In this style, the overall computation is composed by chaining these continuation functions, transforming imperative or direct-style code into an equivalent functional form that makes control flow explicit. Thecall/cc operator facilitates this by implicitly converting direct-style code to CPS, allowing continuations to be captured and manipulated as first-class values.[18]
To illustrate, consider a simple expression in pseudocode, such as (+ 1 2), embedded within a larger program like (* (+ 1 2) 10). The continuation of the subexpression (+ 1 2) is the function that takes its result (3) and multiplies it by 10 to yield the final answer (30). This continuation effectively "delimits" the rest of the program, showing how the value produced flows into subsequent operations.
The significance of continuations lies in their ability to treat control flow as a first-class citizen, enabling advanced programming techniques such as coroutines, exception handling, and non-local control transfers. They form the foundation for more refined mechanisms like delimited continuations, which limit the scope of capture to avoid unintended full-program jumps.[20]
The call/cc Operator
Thecall/cc operator, shorthand for call-with-current-continuation, is a control operator in Scheme that captures the current continuation and passes it as an argument to a provided procedure.[19] When (call/cc f) is evaluated, where f is a procedure of one argument, the current continuation k—representing the remainder of the computation at that point—is explicitly reified as a first-class procedure and applied to f, yielding (f k).[21] If f returns a value v without invoking k, then k is applied to v, resuming the original computation.[19] This reification allows k to be stored, passed, or invoked later, effectively turning the implicit control flow into an explicit, manipulable object.[21]
In pseudocode terms, the captured continuation k can be represented as a lambda that applies the original continuation to its argument: k = λv. (apply-continuation original-k v), and the overall evaluation is (call/cc f) = (f k).[22] Invoking k with a value abandons the current computation entirely, discarding the ongoing evaluation context and jumping directly to the point where call/cc was invoked, supplying the value as the result of that original call.[21] This escape behavior enables non-local control transfers, where the captured continuation acts as an "escape procedure" that ignores any intervening continuations and restores the saved context.[19] Importantly, since continuations are first-class with unlimited extent, the same k can be invoked multiple times, each time re-executing from the capture point and potentially diverging the control flow repeatedly.[21]
Unlike lower-level control operators such as C's setjmp and longjmp, which provide only dynamic-extent continuations that cannot be stored or passed as values, call/cc fully reifies continuations as callable procedures, allowing arbitrary manipulation including multiple invocations without restriction to a single jump.[21] This first-class status enables more expressive control structures, though it contrasts with setjmp/longjmp's simpler, non-reifiable buffers that limit reuse and abstraction.[21]
Edge cases in call/cc behavior include its interaction with tail calls, where a call/cc in tail position ensures the invocation of the passed procedure is also a tail call, preserving proper tail recursion in Scheme implementations.[19] Continuations captured by call/cc have unlimited extent, persisting beyond the dynamic scope of the capturing call and avoiding garbage collection until no longer reachable, unlike dynamically scoped alternatives.[21] In practical evaluations, repeated or nested uses of call/cc can lead to stack growth in stack-based implementations if not optimized, as each capture may allocate continuation frames, though Scheme's tail-recursive nature mitigates this in non-escaping paths.[22]
Practical Usage
Basic Examples
One fundamental application ofcall-with-current-continuation, often abbreviated as call/cc, is to implement non-local exits, akin to throwing exceptions or performing early returns from nested computations in languages without built-in support for such control flow. This allows abandoning the current execution path and resuming at a higher level, effectively escaping from loops or recursive calls.[23]
Consider the following simple Scheme example that demonstrates an early exit:
(define foo
(lambda ()
(call/cc
(lambda (k)
(display "Processing... ")
(k 'early-exit)
(display "This won't execute")))))
(define foo
(lambda ()
(call/cc
(lambda (k)
(display "Processing... ")
(k 'early-exit)
(display "This won't execute")))))
(foo), this captures the continuation k at the point after the call/cc expression and immediately invokes it with 'early-exit, printing only "Processing... " and returning 'early-exit to the caller without executing the subsequent display. A step-by-step evaluation trace is as follows: (1) call/cc captures the continuation pointing to the dynamic environment after its own evaluation; (2) it applies the lambda to this continuation k; (3) inside the lambda, "Processing... " is printed; (4) k is invoked with 'early-exit, which restores the captured continuation and supplies 'early-exit as its result, bypassing the rest of the lambda body. This pattern is commonly used to emulate multi-return values or exceptions, such as in a nested loop search where a match is found and the search should terminate early. For instance, the standard member procedure can be rewritten using call/cc to return the tail of the list upon finding the element, avoiding further iteration:
(define member
(lambda (x ls)
(call/cc
(lambda (break)
(let loop ((ls ls))
(cond ((null? ls) #f)
((equal? x (car ls)) (break ls))
(else (loop (cdr ls)))))))))
(define member
(lambda (x ls)
(call/cc
(lambda (break)
(let loop ((ls ls))
(cond ((null? ls) #f)
((equal? x (car ls)) (break ls))
(else (loop (cdr ls)))))))))
(member 'b '(a b c)) returns (b c) by invoking break upon match, escaping the loop. The trace mirrors the simple case: capture at call/cc, iterate until match, invoke continuation to return the tail directly.[23]
Another basic use of call/cc is to enable simple backtracking in search problems, where the program tries alternative paths and retries previous choices upon failure, such as finding a value satisfying a condition from a set of options. This is often implemented via a non-deterministic choice operator like amb, which uses call/cc to capture points for retrying alternatives. A minimal amb for selecting from a list, combined with an assertion for validation, illustrates backtracking for finding a suitable value:
(define fail-stack '())
(define (amb choices)
(if (null? choices)
(fail)
(let ((choice (car choices))
(rest (cdr choices)))
(call/cc
(lambda (k)
(set! fail-stack (cons k fail-stack))
choice))
(amb rest))))
(define (fail)
(if (null? fail-stack)
(error "No more choices")
(let ((k (car fail-stack)))
(set! fail-stack (cdr fail-stack))
(k #f))))
(define (assert condition)
(if (not condition)
(fail)
#t))
;; Example: Find a number greater than 2 from {1,2,3}
(let ((x (amb '(1 2 3))))
(assert (> x 2))
x)
(define fail-stack '())
(define (amb choices)
(if (null? choices)
(fail)
(let ((choice (car choices))
(rest (cdr choices)))
(call/cc
(lambda (k)
(set! fail-stack (cons k fail-stack))
choice))
(amb rest))))
(define (fail)
(if (null? fail-stack)
(error "No more choices")
(let ((k (car fail-stack)))
(set! fail-stack (cdr fail-stack))
(k #f))))
(define (assert condition)
(if (not condition)
(fail)
#t))
;; Example: Find a number greater than 2 from {1,2,3}
(let ((x (amb '(1 2 3))))
(assert (> x 2))
x)
3. The step-by-step trace for the example (noting that this implementation tries choices in reverse order): (1) amb '(1 2 3) chains through choices to the end and initially fails, backtracking to try 3 first; (2) binds x=3, assert succeeds since 3 > 2; (3) the computation completes by returning 3. If no value satisfies the condition, it exhausts the stack and errors. This captures the continuation at the choice points and re-invokes to backtrack, enabling exploration of alternatives like finding a matching value in a list of candidates.[24]
A common pitfall when using call/cc arises from re-invoking captured continuations in ways that duplicate control flow or create recursive calls to the continuation itself, potentially leading to infinite loops or stack overflows. For example, storing a continuation k and invoking (k k) can result in endless re-capture and re-invocation if k includes the site of its own creation, as each invocation recreates an identical continuation that calls itself. Such issues stem from the full power of first-class continuations, where invocations can multiply execution paths unexpectedly, consuming resources without termination. Programmers must ensure continuations are invoked only once or in controlled contexts to avoid these loops.[25]
Advanced Applications
One advanced application of call-with-current-continuation (call/cc) is in implementing coroutines for cooperative multitasking within a single thread, allowing explicit control over task switching without relying on the underlying runtime's threading model. By capturing and invoking continuations, coroutines can suspend execution at yield points and resume later, enabling simulation of concurrent flows. This approach is particularly useful for lightweight concurrency in resource-constrained environments. For instance, a basic coroutine framework can use call/cc to create functions like spawn, yield, and quit, where yield captures the current continuation and passes control to a scheduler that resumes other coroutines in turn.[24] A representative example in Scheme demonstrates coroutine switching between two tasks: one printing even numbers and another odd numbers. The code might structure as follows, where continuations are stored in a queue for round-robin scheduling:(define *thread-queue* '())
(define (spawn thunk)
(set! *thread-queue* (cons thunk *thread-queue*)))
(define (yield)
(call/cc (lambda (here)
(let ((next-thread (car *thread-queue*)))
(set! *thread-queue* (cdr *thread-queue*))
(set! *thread-queue* (cons (lambda () (here #f)) *thread-queue*))
(next-thread)))))
(define (start-threads)
(call/cc (lambda (k)
(set! *thread-queue* (cons (lambda () (k #f)) *thread-queue*))
(let loop ((thunk (car *thread-queue*)))
(thunk)
(loop (car *thread-queue*))))))
;; Example usage
(spawn (lambda ()
(let loop ((n 0))
(display "Even: ")
(display n)
(newline)
(yield)
(loop (+ n 2)))))
(spawn (lambda ()
(let loop ((n 1))
(display "Odd: ")
(display n)
(newline)
(yield)
(loop (+ n 2)))))
(start-threads)
(define *thread-queue* '())
(define (spawn thunk)
(set! *thread-queue* (cons thunk *thread-queue*)))
(define (yield)
(call/cc (lambda (here)
(let ((next-thread (car *thread-queue*)))
(set! *thread-queue* (cdr *thread-queue*))
(set! *thread-queue* (cons (lambda () (here #f)) *thread-queue*))
(next-thread)))))
(define (start-threads)
(call/cc (lambda (k)
(set! *thread-queue* (cons (lambda () (k #f)) *thread-queue*))
(let loop ((thunk (car *thread-queue*)))
(thunk)
(loop (car *thread-queue*))))))
;; Example usage
(spawn (lambda ()
(let loop ((n 0))
(display "Even: ")
(display n)
(newline)
(yield)
(loop (+ n 2)))))
(spawn (lambda ()
(let loop ((n 1))
(display "Odd: ")
(display n)
(newline)
(yield)
(loop (+ n 2)))))
(start-threads)
start-threads initiates the queue with a halt continuation; the first spawn adds the even thunk; when run, it prints "Even: 0", yields, saving its continuation and running the next (odd), which prints "Odd: 1", yields back to even for "Even: 2", then odd "Odd: 3", and so on, alternating via the queue. This illustrates multiple jumps between continuations, achieving interleaved execution.[24]
Another sophisticated use is backtracking in search algorithms, where call/cc enables non-deterministic choice by stacking failure continuations, allowing automatic retry on dead ends, as in logic programming. The amb operator, for example, selects from alternatives and uses a fail continuation to backtrack upon assertion failure. This "time-traveling" search explores solution spaces efficiently without explicit recursion depth management. The yin-yang puzzle exemplifies this, demonstrating how intertwined continuations can create infinite backtracking loops that print escalating patterns, revealing the power of continuation reification in puzzles and parsers.[24]
In the yin-yang puzzle, the code is:
(let* ((yin ((lambda (foo)
(newline)
foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo)
(write-char #\*)
foo)
(call/cc (lambda (bar) bar)))))
(yin yang))
(let* ((yin ((lambda (foo)
(newline)
foo)
(call/cc (lambda (bar) bar))))
(yang ((lambda (foo)
(write-char #\*)
foo)
(call/cc (lambda (bar) bar)))))
(yin yang))
(define squared-ints
(lambda ()
(let* ((break #f)
(resume #f)
(yield
(lambda (value)
(call/cc
(lambda (r)
(set! resume r)
(break value))))))
(lambda ()
(call/cc
(lambda (cc)
(set! break cc)
(if resume
(resume '())
(let loop ((i 1))
(yield (* i i))
(loop (+ i 1)))))))))
(define g (squared-ints))
(g) ; => 1
(g) ; => 4
(g) ; => 9
(define squared-ints
(lambda ()
(let* ((break #f)
(resume #f)
(yield
(lambda (value)
(call/cc
(lambda (r)
(set! resume r)
(break value))))))
(lambda ()
(call/cc
(lambda (cc)
(set! break cc)
(if resume
(resume '())
(let loop ((i 1))
(yield (* i i))
(loop (+ i 1)))))))))
(define g (squared-ints))
(g) ; => 1
(g) ; => 4
(g) ; => 9
Implementations
In Scheme and Derivatives
call-with-current-continuation, often abbreviated as call/cc, was first standardized in the Revised^5 Report on the Algorithmic Language Scheme (R5RS) in 1998, where it is defined as a procedure that takes a single argument, a procedure of one argument, and calls that procedure with the current continuation as its argument. The dynamic extent of the continuation captured by call/cc is unspecified in R5RS. The Revised^7 Report on Scheme (R7RS), published in 2013, retains the core definition from R5RS with minor clarifications, maintaining call/cc as part of the base library while emphasizing its interaction with dynamic-wind for proper cleanup during continuation jumps. R7RS does not alter the unspecified dynamic extent. In Racket, a popular Scheme derivative, call/cc serves as an alias for call-with-current-continuation and captures the continuation up to the nearest enclosing continuation prompt, typically the default prompt tag, enabling delimited behavior by default. Racket extends this with dedicated support for delimited continuations via the racket/control library, where shift captures a delimited continuation up to the nearest reset, and reset delimits the scope, providing a more controlled alternative to undelimited jumps for composable control flow.[20] Chez Scheme implements call/cc through an optimized continuation-passing style (CPS) transformation during compilation, converting the source program into CPS form to handle control transfers uniformly and efficiently without runtime overhead for most calls. This approach represents continuations explicitly as stack frames in a garbage-collected heap, avoiding costly stack copying and allowing precise garbage collection by treating uncaptured frames as disposable while preserving captured ones as closures.[30][31] Guile, the GNU Scheme implementation, provides full support for undelimited continuations via call/cc up through its 3.0 series releases in 2023 and beyond, capturing the entire remaining computation as a procedure that can be invoked multiple times from the same thread. Guile's implementation relies on stack copying to represent continuations, which ensures compatibility with C interop but incurs performance costs for frequent captures, with continuations treated as first-class objects subject to the Boehm-Demers-Weiser garbage collector for tracing and reclamation.[17] Among Scheme derivatives, Chicken Scheme augments standard call/cc with the continuations egg, which introduces enhanced interfaces including Marc Feeley's continuation-capture and continuation-graft for explicit control, and Matt Might's escape procedures for lightweight, setjmp-like escapes, all built atop the core undelimited semantics. In Clojure, a Lisp dialect influenced by Scheme, undelimited continuations are emulated via the clj-continuations library, though practical usage often favors delimited variants like those in the delimc library for safer, composable effects without full program hijacking.[32][33] Scheme interpreters generally employ CPS as a core evaluation strategy, transforming expressions into continuation-expecting forms during interpretation or compilation to simulate control operators like call/cc without special runtime primitives, ensuring uniform handling of tail calls and exceptions. Continuations are typically represented as closures over the current stack or an explicit control stack, with garbage collection implications including the need to root stack frames in captured continuations to prevent premature reclamation, often using generational collectors that treat continuation frames as heap objects for efficient tracing.[30][34] As of 2025, call/cc has not been deprecated in any major Scheme standard or implementation, continuing to serve as the foundational undelimited control operator. However, there is a growing preference for delimited continuations in new Scheme code, driven by SRFIs like 226, which reframe call/cc within prompt-based delimiting for better modularity and reduced global state interference.[35]In Other Programming Languages
Call-with-current-continuation (call/cc) functionality has been adapted in various programming languages outside of Scheme, often through libraries or experimental features that emulate undelimited or delimited continuations using continuation-passing style (CPS) transformations or runtime mechanisms. These implementations typically address the challenges of integrating first-class continuations into non-functional or imperative paradigms, where direct support for capturing the entire execution stack is limited. While full undelimited continuations like call/cc are rare due to implementation complexities, partial analogs and delimited variants provide similar control flow primitives for tasks such as asynchronous programming and exception handling.[36] In Ruby, continuations are supported via thecallcc method in the Kernel module, introduced in Ruby 1.8 released in August 2003. This legacy feature requires loading the continuation library and generates a Continuation object that captures the current execution context, allowing nonlocal jumps similar to call/cc. Ruby's implementation uses a copy of the execution stack to represent the continuation, enabling applications like web session management in frameworks such as Wee, where continuations maintain state across HTTP requests without relying on traditional session storage. For instance, Wee leverages callcc to simulate a persistent computation environment, treating web interactions as cooperative multitasking. As of 2025, it remains available but is considered obsolete with proposals to remove it.[37][38][39]
Scala provides experimental support for unstable (undelimited) continuations through the scala-continuations compiler plugin and library, introduced in 2009. The @cps annotation transforms code into CPS, enabling delimited control operators like shift and reset for capturing partial continuations, which can approximate call/cc behavior in functional contexts. The plugin is unmaintained since 2020 and compatible only with Scala 2.12 and earlier; as of 2025, Scala 3 lacks native support, with delimited continuations available via third-party libraries and limited experimental work in Scala Native for stack-copying, but full undelimited continuations require custom plugin activation or are not standardized.[40][41][42]
In C#, the async/await keywords in .NET provide a partial analog to continuations by enabling asynchronous state machines that transform code into CPS internally, but they do not offer full call/cc semantics like capturing and reinvoking arbitrary stack frames. Complete call/cc-like functionality can be achieved through libraries implementing CPS, such as custom continuation monads that simulate undelimited control via delegates and exception handling, though these are not part of the core language and incur performance overhead due to the managed runtime's stack constraints.[43]
Other languages have incorporated continuation-like features in the 2010s and 2020s. Boost.Coroutine, added to the Boost C++ Libraries in version 1.53 (October 2011), supports asymmetric and symmetric coroutines that emulate stackful continuations for suspending and resuming execution, providing a foundation for call/cc-style control in systems programming. In Haskell, delimited continuations are available via the CC-delcont package, which implements multi-prompt control using a monadic framework based on selective CPS transforms, allowing partial captures without full undelimited jumps. Recent additions include the Nim cps library (developed in the early 2020s), a proc macro that performs compile-time CPS transformations to enable undelimited continuations for asynchronous and effectful programming. Similarly, Rust crates like switch-resume (updated through the 2020s) offer effect systems with continuation primitives, while experimental CPS implementations in crates such as continue support single-use continuations approximating call/cc for concurrency.[44][45][46][47]
Implementing call/cc in imperative languages presents significant challenges, particularly in representing continuations without native stack access. Common strategies include stack copying, which duplicates the runtime stack into a heap-allocated structure for portability across threads, as seen in Ruby and Scala Native implementations, versus trampolining, which avoids deep recursion by iteratively invoking thunks in a loop, reducing stack overflow risks but introducing overhead from repeated function calls. These approaches trade off efficiency and complexity; for example, stack copying enables full fidelity but requires careful garbage collection integration, while trampolining suits tail-recursive styles but complicates debugging in low-level languages like C++. Seminal work highlights that portable implementations often rely on exception handling to simulate continuation capture, ensuring compatibility with virtual machines like the JVM or CLR.[48][49][50]
Theoretical Implications
Connection to Logic
The Curry-Howard isomorphism establishes a correspondence between proofs in intuitionistic logic and programs in typed lambda calculi, where propositions are interpreted as types and proofs as terms inhabiting those types. In this framework, the call-with-current-continuation (call/cc) operator corresponds to Peirce's law, a principle of classical logic given by the formula , which is not provable in intuitionistic logic.[51] This equivalence allows call/cc to enable the encoding of classical proofs within intuitionistic systems by providing a term that realizes Peirce's law.[51] In typed lambda calculi, call/cc facilitates double negation elimination, the rule (where ), thereby bridging the gap between intuitionistic and classical logic. The type of call/cc can be formalized as , highlighting its non-intuitionistic character since this type is uninhabited in purely intuitionistic settings.[52] This typing reveals how call/cc captures the current computational context as a continuation, effectively simulating the escape from nested negations in logical proofs.[51] Historically, the connection between call/cc and logic was formalized in Timothy G. Griffin's 1990 work, which modeled control operators like call/cc using formulae-as-types interpretations, and builds on earlier efforts by Matthias Felleisen and others to abstract sequential control in lambda calculi.[51] Furthermore, call/cc plays a role in realizing Gödel's double negation translation, a method to embed classical logic into intuitionistic logic by prefixing formulas with double negations, where continuations provide the computational content for translated proofs.[53] These theoretical links have implications for proof assistants and theorem provers, such as Coq or Agda, where continuations via control operators can simulate classical axioms like Peirce's law or the axiom of choice within intuitionistic type theories, allowing users to reason classically while preserving computational interpretability for intuitionistic fragments.[54]Criticisms and Alternatives
One major criticism ofcall-with-current-continuation (call/cc) is its promotion of undisciplined control flow, which resembles unstructured jumps akin to goto statements and hinders code composability and local reasoning.[55] This generality often results in incomprehensible programs that resist modular analysis, as continuations can hijack the entire control stack without lexical scoping boundaries.[55]
Performance overhead is another significant drawback, stemming from the need to copy the full continuation stack upon capture, which imposes unavoidable costs even for simpler control needs like exceptions or generators.[55] Additionally, call/cc facilitates space leaks by retaining references to captured continuations that prevent garbage collection of unused stack portions, leading to excessive memory retention in practical applications such as stream generation.[55] Debugging is complicated by these non-local jumps, which obscure execution traces and make it challenging to trace control flow in complex programs.[55] In multi-threaded environments, call/cc's stack-capturing mechanism exacerbates issues, as continuations tied to thread-specific stacks can lead to synchronization problems and are generally unsuitable without extensive modifications.[56]
A prominent alternative to undelimited continuations like call/cc is delimited continuations, introduced by Olivier Danvy and Andrzej Filinski in their 1990 work on abstracting control via iterated continuation-passing style transformations.[57] These capture only a bounded "slice" of the continuation up to a specified delimiter, enabling reusable and composable control effects without full program hijacking. Common operators include shift and reset for static delimiting, or abort and reset for lighter, dynamic control abstractions that avoid the overhead of full stack manipulation.[57] Delimited continuations are implemented in languages such as Racket through its racket/control library and in Scala via libraries supporting shift/reset semantics.[20]
In comparison, delimited continuations provide scoped effects that compose modularly, contrasting with call/cc's undelimited nature, which can abruptly terminate or restart the entire computation and lacks inherent boundaries for safe reuse.[58]
As of 2025, effect handlers have emerged as a growing alternative, offering structured abstraction over effects like exceptions or asynchronous operations without relying on explicit continuations. Languages such as Koka and Effekt integrate effect handlers natively, allowing handlers to intercept and resume computations in a delimited manner, often compiling efficiently to avoid the pitfalls of full continuations while supporting similar expressiveness.[59] This approach reduces the need for call/cc by providing composable, effect-typed control that aligns better with modern functional programming paradigms.[60]