Information AboutCall-with-current-continuation |
| CATEGORIES ABOUT CALL-WITH-CURRENT-CONTINUATION | |
| programming language topics | |
|
Taking a Function ''f'' as its only argument, it 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 one operation: application. Thus, "f" may return the object, store it in a variable, place it a structure or a list, pass it to another function, or apply it. When a continuation object is applied (also called thrown), the existing continuation is eliminated and the applied continuation is restored its place. A programmer can use call/cc to emulate the functionality of ''return'' from C-style languages, which is missing from Scheme: (define (f return) (return 2) 3) (display (call-with-current-continuation (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. The power of call/cc lies in the ability for the continuation to be called more than once, and even from outside the dynamic extent of the call/cc application. 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: ;; 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 X , the code generalizes to ''any'' collection that can be traversed. With call/cc a programmer can implement a variety of complex control operators from other languages via a few lines of code: McCarthy's amb operator for non-deterministic choice; Prolog -style backtracking; Simula 67 -style coroutines and generalizations thereof; Icon-style generators (now available in Python); engines and threads; and a variety of lesser-known constructs. Lisp users have criticized the "call/cc" function as unnecessarily complicated and difficult-to-implement means. 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. Specifically, each call to the function copies the control stack and places it 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. SEE ALSO EXTERNAL LINKS
|
|
|