Call With Current Continuation
Call With Current ContinuationThe SchemeLanguage as defined by R5RS [RevisedReportOnAlgorithmicLanguageScheme] provides a function named CALL-WITH-CURRENT-CONTINUATION (or CALL/CC for short) that captures the current continuation as a first-class object (see ContinuationExplanation). Several other languages provide equivalent or similar functionality. In Scheme, the captured continuation has unlimited extent: it can be stored in a variable and can be called/activated as many times as desired. If and whenever the continuation is called, the then-current continuation will be abandoned, and the program flow will continue at the point at which the continuation was captured.
CALL/CC is almost equivalent to CeeLanguage's setjmp. The procedure given to call/cc is called with the current continuation, whatever would happen next if call/cc returned normally, as its one argument. So by invoking that procedure the procedure given to call/cc can return to the context where call/cc was invoked, just like longjmp. It, or another procedure that gets hold of the passed continuation somehow, can do this at any later time, and more than once. Scheme implementations vary in what happens to any stacks, exception handlers, etc. etc. when this happens.
Using CALL/CC one can very easily implement CoRoutines, lightweight multi-threading, back-tracking, exception handling, and something like collaborative multitasking, all safely and in-process. The full power of call/cc is not needed to do all of this, and some languages/implementations only provide restricted continuations that can be activated at most once and only if the captured execution context is still valid (single-shot upward-only continuations, see SingleUseContinuation).
If your program evaluator/interpreter is implemented using ContinuationPassingStyle you get call-with-current-continuation for free. CALL/CC is then a very natural operation since every function is called with the current continuation anyway. This is explained in the book EssentialsOfProgrammingLanguages.
Here is the corresponding implementation of call-cc using CPS:
(define (cps-call/cc k consumer)
(let ((reified-current-continuation (lambda (k1 v) (k v))))
(consumer k reified-current-continuation)))
If you're a C programmer, you might find this explanation easier: in C, you can take a pointer to a function. In C, you also have a return statement. Suppose the return statement were a function (which never returned, of course). It would take a parameter of the same type as the return type of the function it was returning from. Now suppose you could take its address. You could store that address in a variable or pass it as a parameter, and allow functions to return on your behalf. That's what call/cc allows you to do. You can use it as a replacement for throw and catch, or you can set up coroutines with it (see ContinuationsAndCoroutines). -- EdwardKiser
I am not sure that I understand this. Am I on the right tracks if I think of it like the Unix setjmp and longjmp? -- ChrisBrooking?
That's certainly the right track, except that with setjmp/longjmp it is illegal to do a longjmp after the function calling setjmp has returned. With call/cc, there is no such limitation: you can invoke the continuation whenever you like, as often as you like. -- StephanHouben
I used this sort of thing once with some machine code added into a C function so that the return address was faked to return somewhere else. This was used to do cooperative task switching. --JohnFletcher
I HaveThisPattern (I used it a similar trick (all in assembler, though) of faking the stack pointer - hence faking the return address and much more . A long time ago now (about 1985, I think)) -- PaulHudson
See ContinuationsInCee.
A very simple example:
(call-with-current-continuation
(lambda (return)
(begin
(display "One ")
(return #t)
(display "Two ")
#f)))
The lambda-expression evaluates to an anonymous function of one parameter. This anonymous function gets invoked by call-with-current-continuation and the parameter - here called return - gets bound to an escape procedure, i.e. a procedure value that encapsulates the current continuation. The function prints "One " and then returns #t without ever printing "Two " because the second display-expression is part of the abandoned continuation. Note that the activation of the captured continuation appears syntactically as a function call since Scheme conflates continuations with the escape procedures that encapsulate them.
Historically, the language construct to capture the current continuation in Scheme wasn't always a function; a special operator called CATCH or LET-CC was used instead. In R5RS Scheme this can be implemented using DefineSyntax and CALL/CC:
(define-syntax let-cc
(syntax-rules ()
((let-cc variable . body)
(call-with-current-continuation
(lambda (variable) . body)))))
Using this operator the example would read:
(let-cc return
(display "One ")
(return #t)
(display "Two ")
#f)
In this example the continuation was used in an upward-only way, which doesn't demonstrate the full power of continuations.
Another example:
(call-with-current-continuation
(lambda (exit)
(for-each (lambda (x)
(if (eq? x 'nuclear)
(exit x)
(symbol->string x)))
'(this is a nuclear bomb in your garage))))
This uses a captured continuation to escape from the middle of the "for-each" function. Again, the continuation is used in an upward-only way. However, the poor author of the "for-each" function has to be prepared for the possibility that the (lambda (x) ...) function never returns.
Now, the thing that makes Standard Scheme's continuations unique is that the continuation has unlimited extent. What I mean is, you can return it like this:
(call-with-current-continuation (lambda (return) return))...and it is still valid. This allows you to use it to set up co-routines.
See also SchemeCoroutineExample, ContinuationsAndCoroutines, ContinuationPassingStyle.
Isn't this a disguise for goto's and JMP instructions?
Isn't every high-level (i.e. higher that goto or JMP) flow-of-control structure? Isn't that the point?
CallWithCurrentContinuation is a disguise for JMP in the same way that writing down the directions for how you got somewhere and what you had with you when you got there is a disguise for teleportation.
CallWithCurrentContinuation is a universal control structure - you can implement any control structure on top of it. Unlike gotos and JMP it is structured - continuations are values not textual labels in a program. Call/CC is best used for blowing students' minds, or providing elegant solutions to difficult problems. For example web transactions can be viewed as suspension and resumption of continuations, which makes handling state on the web a lot easier. The folks at PLT have done some work on this I recommend their papers. See DrScheme for URLs. See also the SmalltalkLanguage framework SeasideFramework and WebTransactionsWithContinuations.
Actually I would dispute the notion that CallWithCurrentContinuation is a universal control structure. I don't think it is meant to replace if/then/else, or iteration. What it does replace is stuff like throw/catch, coroutines, and backtracking.
Those are two different issues. It is not meant to be used as a replacement of anything, because it is well known that continuations are pretty confusing. But CallWithCurrentContinuation is universal, and can be used to implement if/else, iteration, etc. That implementation ideally is then hidden behind a facade of some sort, e.g. a macro in Lisp.
Indeed. Why do people say they would dispute something and then dispute some other claim entirely?
Can you show an example of using CallWithCurrentContinuation to implement if/else?
Actually, you don't need call/cc to implement if/then/else; first-class functions are enough. In Scheme:
;;;
;;; TRUE is a procedure that takes two procedures and invokes the
;;; first one.
;;;
(define (true true-k false-k)
(true-k))
;;;
;;; FALSE is a procedure that takes two procedures and invokes the
;;; second one.
;;;
(define (false true-k false-k)
(false-k))
;;;
;;; IF-THEN-ELSE takes a boolean and two procedures, and invokes the
;;; first one for true, the second one for false.
;;;
(define (if-then-else bool true-k false-k)
(bool true-k false-k))
;;;
;;; Yeah, this definition is cheating. Pretend KZERO? was a primitive.
;;;
(define (kzero? n)
(if (zero? n)
true
false))
(define (factorial n)
(if-then-else (kzero? n)
(lambda () 1)
(lambda () (* n (factorial (- n 1))))))
Note that while this doesn't use CallWithCurrentContinuation, it does use a form of ContinuationPassingStyle. Looking at it this way, booleans are functions that choose between two continuations; truth just means "take the first path" while false means "take the second path."
A true call/cc method in Smalltalk might look like this:
callCc: aBlock ^aBlock value: [:arg | ^arg]I tried this in SqueakSmalltalk (put the method on Object), and it works, except that continuations cannot escape outside their dynamic extent: trying to do so raises a BlockCannotReturn exception.
In principle, this is more an implementation restriction than a language restriction: if this restriction was to be lifted, then we would have full call/cc in Smalltalk. Now that would be cool...
No, it's not an "implementation restriction", it's restriction of the language semantics. Saying "if this restriction was (sic) to be lifted" is the same as saying "if full call/cc were added to Smalltalk", resulting in tautology.
Stephan, Wilf LaLonde? and Mark VanGulik? describe how to build call/cc in Smalltalk in their paper, "Building a Backtracking Facility in Smalltalk Without Kernel Support" in the 1988 (!) OOPSLA proceedings. You can reproduce it quite easily in VisualWorks or Squeak. --AnthonyLander
I'll check it out! Thanks! -- sh
[From SchemeLanguage]
The coolest feature in Scheme is CallWithCurrentContinuation. -- EdwardKiser
Be aware that many view CallWithCurrentContinuation not as a cool feature, but as a fatal flaw. It's like having a nuclear bomb in your garage. Cool, sure, but do you really want one? Specially when the neighbor's kids might drop in? Call-cc is the ultimate minimalism; sure, it replaces goto, block, throw, catch, etc, but not in a controlled way. It makes it impossible to, by inspection, determine how often a piece of code might be executed. An example of OnceAndOnlyOnce at the language design level?
Actually, no one, not even you, considers call/cc to be "a fatal flaw", and you've contradicted yourself by saying its not cool and then saying nuclear bombs are cool.
Is it really important to know how many times a piece of code is going to be executed? How many times has the computer game DOOM been executed?
It is important for some compilers. Lisp compilers can sometimes avoid putting a variable inside a heap-allocated frame where Scheme compilers cannot, since a procedure call might return twice. Consider code such as:
(let ((x 1))
(do-some-call-that-might-return-twice)
(display x)
(set! x 2))
Now, if the call that might return twice, does indeed return twice, then the second time call to display will have x = 2. This typically means that the location in which x is stored must be heap allocated.
However, a Scheme programmer who wouldn't explicitly want to use this particular effect of call/cc, would rebind the second x with let and not use set!.
Another reason you would care how many times a bit of code is executed is it's hard to do this bit of code in the presence of call/cc:
(let ((file (open ...)))
(unwind-protect
...
(close file)))
(that is, close the file after you finish using it, regardless of whether you left the code due to an error or anything else) What is this supposed to do if you save a continuation in the middle here? You can leave the code and then at any later time, completely unpredictable by the compiler, you can come right back in and use file again. (Note: dynamic-wind doesn't solve this, because either you'll close the file multiple times or you'll open and close it repeatedly, both of which aren't the right thing)
Why doesn't dynamic-wind solve this? Because you can call/cc back in and break it? And the "solution" would be to forbid general call/cc, as in CommonLisp? Sorry, but the cure seems worse than the problem.
Of course Scheme doesn't solve the problem of immediately releasing resources in full generality, since it is equivalent to the HaltingProblem.
Anyway, if you really really don't want full call/cc to take place, wrap the call in something like this:
(define (upward-only continuation)
(let ((first-time #t))
(dynamic-wind
(lambda () (if (not first-time)
(error "Sorry, I can't let you do that, Dave")))
continuation
(lambda () (set! first-time #f)))))
(define cc
(upward-only (lambda () (call-with-current-continuation (lambda (cc) cc)))))
(display "So far so good")(newline)
(cc 'dummy)
Someone above compared call/cc with a nuke in the garage. Should it be ConsideredHarmful? The argument for it is that it is a powerful tool with which one can implement lots of cool stuff (coroutines, cooperatively-scheduled threads, most traditional control structures including goto, etc....) That sounds to me to be similar to the old arguments in favor of goto (who needs if/then or loops when goto does 'em all?)
Perhaps you can only hear strawmen. No one says "who needs if/then or loops" -- neither advocates of goto nor advocates of call/cc. Rather, it is you who are saying "who needs call/cc when something else can do that?
To ask the question another way--is there anything that can be done with call/cc that cannot be done with a suitable set of higher-level structures? The death knell for goto was when it was proven that one could indeed transform an arbitrary goto-based program into one using higher-level control structures. Might a similar argument exist with regard to call/cc--that if a language wants coroutines, etc...it should provide these instead of call/cc?
You're asking it there's anything that can be done with call/cc that cannot be done by adding that very thing to the core language, which is point-missingly absurd in the extreme. Also, your claim about the death knell for goto is a myth -- it was already well known that an arbitrary goto nest could be transformed into a single loop and a state variable -- it's called an interpreter loop. It was Dijkstra's "goto considered harmful" paper that was most instrumental in the shift to structured programming.
I don't know the answer, which is why I'm asking the question.
You have actually asked three totally different questions. Should it be considered harmful, is it necessary, should languages provide features such as coroutines -- are quite different. Not knowing the answer is just the beginning of your lacks.
-- ScottJohnson
The comparison to goto is interesting, in that it points us to a feature of Lisp/Scheme culture. Yes, you can implement various higher level structures with call/cc. Indeed, if your Scheme implementation offers those features (as extensions beyond R^5RS), then they will almost certainly be implemented that way, but hidden behind macros.
Here is where the analogy with goto falls down: in every language I can think of where you might be going to implement a higher level control structure with goto you would have no means of hiding or reusing that technique, you'd have to explicitly put it in each time. Oh, I suppose you could jump through a few hoops with the C pre-processor or m4 or something to tidy up a bit. But in Scheme, these new control structures would be defined once, and thereafter would be indistinguishable from the built-in control structures (many of which are macros, in any practical Scheme implementation, anyway).
come on, that's silly; if/then, while, etc. can all be implemented via macros using generated labels and gotos. People have done this numerous times in assembly languages.
It should be noted that the developers of the Scheme language themselves claimed that a function call was equivalent to "goto with parameters." This was because of Scheme's ability to recognize tail calls. Since call/cc is a function call, it would also amount to "goto with parameters."
Using macros to build higher-level stuff over goto and/or continuations is best way in my opinion. For example, you can see how it is done in some Forth systems; you can just define IF or THEN or whatever to run at compile-time and put stuff into the stack and generate branch instructions and so on.
Call/cc is important for other things besides coroutines. Call/cc allows a callback-oriented API to be converted back to direct style. Examples of this include externalizing an InternalIterator, and reconciling traditional "straight-line" code with the event-driven structure of GUI's and callbacks. Every construct that is capable of this can be shown to be at least as powerful as call/cc (i.e. call/cc can be implemented in terms of it). I would argue that call/cc allows the programmer to abstract away from the style of interface, and should therefore be considered a vital language feature.
Type/Program Safety and Call/CC
I've been thinking about safety verification in the context of CallWithCurrentContinuation and ContinuationPassingStyle in general, especially in the context of imperative programs. A safe program is one that only performs well-defined operations; in the context of evaluation, 'type'-safety is only performing evaluations for which every evaluation-step is understood, whilst in the context of execution, safety is performing communications only within established protocols. The most common examples of protocol violations involve the most common communications resources. E.g, for the memory subsystem, safety failures include failure to eventually release memory once requested, attempting to release it twice, attempting to use memory without first requesting it. For the filesystem, one must close files once opened, and cannot write to unopened files. For mutexes, one must eventually unlock the mutex. These are simple protocols, but protocols can be arbitrarily complex (e.g. TCP, HTTP, FTP, Bittorrent). A 'finalization' or 'goodbye' step is common to a great many protocols, be they complex or simple.
While Call/CC makes it very easy to violate these protocols (to finalize twice, to never finalize, to use after finalizing a resource, to jump back into the middle of code where you're expected to be holding a mutex that was released earlier, etc.), that isn't such a big deal. After all, any programmer can go about violating protocols... it's quite easy even without Call/CC. Of greater question, however, is whether CallWithCurrentContinuation makes safety-verification too difficult... especially considering that people can put those continuations generated by 'call/cc' just about anywhere (drop them into a list, for example).
And I speak not just of automated safety verification, but also of the sort where a human dives into the code and tries to figure out what the heck is going on. It's easy enough to get by without Call/CC, but you lose the ability to define entirely new mechanisms to control computation. But to hear your opinions (especially those of you who enjoy the benefits of automated type checking): would it be worth using Call/CC even if it means giving up static verification of a program? Or would it be better to favor the creation of new language primitives for program flow control that have well-understood properties and are, thus, much easier to verify?
I do understand that there are those who would argue: He who gives up freedom for safety deserves neither (though the proper Franklin quote involves 'temporary' safety). I'm not particularly interested in such an argument. I direct this query more to those who already prefer static type-safety.
Continuations with Formally Limited Extent
Program safety analysis would benefit from knowing the extent of continuations in a formal manner. At the same time, human programmers need the mechanism to be intuitive enough that it is easy to grasp and utilize. So here's a possibility: Add a procedural concept fini, such that in any procedural block of code, you can specify (at any spot in that block) fini <X>. This is similar in concept to Java's "finally", and the same could be used (though I disapprove of the syntax common to Java/C++ for this purpose). The fini specifies a contract that the specified operation will be executed exactly once (at least once, at most once) at the end of the block but before all prior 'fini' specifications, regardless of which forward continuation is ultimately taken (return, throw, continue, break, abort, retry, ignore, anything passed by call/cc, etc. etc. etc.). Continuation Passing code can then, formally, be considered to possess a procedural-type-error if it can be proven that this constraint is violated (executed twice or never executed), and can be considered unsafe if it cannot be proven that the constraint isn't violated. Execution-paths that do not possess risk crossing 'fini'-code twice are considered safe.
// Pseudocode in MyFavoriteLanguage procedure { let x = open-file("whatever.mp3") fini { close-file x; } let retry = call/cc return-continuation let r = attach-resource("sound-system") catch(e) { throw exception-with-retry:(e,retry); } fini { detach-resource(r); } ... do loops and stuff involving file and audio using ContinuationPassingStyle ... // implicitly detaches resource here // implicitly closes file }Note that fini itself doesn't execute anything and has no risk of throwing an exception. The procedural operation specified after each fini is contractually guaranteed to execute at some point, and to execute -exactly once-. The compiler might use 'fini' like the Java/C++ stacked-based 'finally', shifting it towards the end of the block. Indeed, this might be the usual implementation when the semantics are clear unless some more optimal solution is found.
However, to provide a more interesting example, I added 'retry', which holds the current continuation at that point (much like a goto label). Further, 'retry' can be tossed in as part of an exception (neat for when you want something like an abort/retry/ignore exception on a 'foreach' operation). Supposing the caller catches this exception, the caller might or might not choose to execute the 'retry' continuation, and might even store it in a variable and execute it twice. Executing it once is a valid operation, as is aborting... and on all the acceptable paths, there must exist a guarantee that the 'finally' (close-file) operation is executed exactly once. Attempting to execute twice, however, would generally be unsafe because the continuation might execute the 'fini' code twice).
...
The ability to guarantee a 'close-file' even if the caller chooses to abort or throw rather than 'retry' implies that not ONLY is 'retry' passed back with the 'throws' operation... so is every other possible continuation upon receipt of the exception (implicitly, 'throw' and 'return'). True CPS doesn't have a stack... it just has continuations being passed around both implicitly and explicitly, which might happen to involve a stack where it is useful as an optimization.
This is nothing new. It's called 'delimited continuations'. Please have a look at e.g.
http://lambda-the-ultimate.org/search/node/delimited+continuationThanks for the link. I'm checking it out, though I now have a strong impression that the lambda-the-ultimate search engine is worse than even this Wiki's search engine...
I can't disagree with that :) The link was not meant as a useful search result, but rather as a mix of site, key word and some results that could steer your further search.
Worth noting that RubyLanguage has CallWithCurrentContinuation too, but it just named #callcc. Ths usage is actually identical to SchemeLanguage:
callcc do |cc| . .. end(blocks are lambdas in ruby)
unfortunately, Ruby's callcc is currently incredibly slow, implemented via stack copying
Also of interest: AmbInRuby
Of course, not having actually sat down and hacked at this in a good Scheme implementation, I am struggling with this whole idea. I understand what a continuation is, I think, but not entirely why. But to address the what for a moment, it seems to me that continuations seem to imply a MetaObjectProtocol-like system-- I'd call it a MetaObjectProtocol personally, but others may have their own definitions. Anyway, it seems that they imply that in that they formalize the stack into objects that you deal with-- continuations-- rather than leaving the stack as an implementation detail that you aren't supposed to rely on, but that sufficiently-complex C programs will tend to take advantage of anyway. Is this a more or less apt comparison?
Not really, although it isn't completely confused. The MetaObjectProtocol is not particularly related. The comments about stacks is an implementation issue through and through, and hence that is far too concrete, but probably captures some of the idea. Continuations are an abstraction of control flow, and can be used to implement any kind of control flow at all.
Objects in Simula 67 were somewhat like continuations (each was a thread) but not as general, most language objects are not much like continuations (since in general they do not have autonomous control; their methods are called synchronously and those methods run to completion; and they do not and cannot represent the existing control state, and if they did, would not be able to modify it).
Ponder "engines" in Scheme.
continuations don't formalize stacks -- that's already done by the semantic model that establishes what happens when you return from a function. And on the contrary, continuations /prevent/ you from relying on a stack implementation, by violating the stack discipline.
CALL/CC can also be seen as Peirce's law, which is a rule added in intuitionistic logic to make classical logic. But you can also make a "law of excluded middle" operator with continuation, which makes a function, that when called, goes back to where the function was made and becomes the value it was called with. (You can also define CALL/CC in terms of this operator, or vice-versa; just like you can in logic.)
CategoryFunctionalProgramming CategoryScheme CategoryLanguageFeature CategoryContinuation
EditText of this page
(last edited June 18, 2014)
or FindPage with title or text search