A page about call/cc (2002)
madore.org
madore.org
To create a continuation, scheme gives you call/cc which creates a continuation and passes it to a function.
To resume a continuation you call it like a function. Anything you pass in gets passed to whatever expression is at the FP on top of the call stack.
Scheme combines creating a continuation with a function call, just to make resuming a little more clean: by doing so, it guarantees that the FP on top of the call stack is a function call, so it knows it can pass the value you resume with to the top of the stack as if it were a returned value.
If you're creating continuations in your own language, you don't need to combine continuation creation with calling a function: there's nothing magic about call/cc, it just combines two separate steps to make the implementation a little simpler.
I never got the hang of 99% of explanations of call/cc. This 'a continuation represents the parts of the program expecting a value' seemed needlessly complicated.
One neat thing you can do with continuations is use them to implement multitasking—see "Concurrent Programming in ML."
Imagine a programming language where no function returns a value. Instead of returning a value, the function calls the callback and passes what would have been the return value as input. (JavaScript programmers should be familiar with this.)
If I had a regular program that calls a function and uses its return value, then can I transform that into an equivalent program that passes a callback? Consider an expression like print(f(x) + 2). Once f(x) returns a value, then the expression f(x)+2 can return a value, and so on. It's the call stack.
What would it mean to rewrite this program so that f(x) did not return a value, and instead took a callback saying what to do next? One way to think about this is to imagine removing the function and leaving a "hole" in the expression and call stack:
print(___ + 2)
lambda n: print(n + 2)
Now imagine that we overload f(x) so that it also takes a callback. When f() has produced its value, it calls the callback with that value:
f(x, callback)
print(f(x) + 2))
The callback I should pass to f() is a piece of code representing what we should do next, which is the lambda function we just wrote! So expressing the call to f() with a callback will look like this:
f(x, lambda n: print(n + 2) )
This also means that every time you're implementing a procedure f(x), you take the callback as input and invoke it when you have your return value. So imagine that f(x) just increments its value and returns it. Then, the callback form might be:
def f(x, callback)
callback(x+1)
You can think of each point in the code as having a continuation which is what to do next immediately after it. Continuation passing style makes this continuation explicit, but you can always speak about the continuation for a given point in the code, in the sense that you can work out what the function would be if you needed to pass it as a callback. Language runtimes that support continuations are essentially figuring this out for you -- you can simply ask them "give me the current continuation", and now you have what looks like a function to call to "keep going" from where you were before.
While it's not common to write code in continuation passing style, the understanding that every point in a program's execution has a "continuation" (callback that will be invoked with the return value) can allow for useful transformations or expressions of control flow. The insight behind continuation passing style is that regular and CPS styles are equivalent, in that you can transform one to the other automatically. In language runtimes that give you continuations, you can thus achieve the benefits of continuation passing style in limited contexts without writing the whole program that way.
You can think of it as anything you like. As a plate of burritos, even (to borrow the monads cliche). But why would you want to spend so many hundreds of words setting up an imaginary world like that?
When you're running a program, the computer keeps track of where in the program you are. A continuation is a data structure representing that point. You create a continuation by asking for the data structure representing the current point. Then you can resume it later, which replaces the current point with the point stored in that data structure.
I fail to see why you'd want to make this more complex.
My approach is not a 'how to explain it', it is what it actually is.
CPS definitely has its places, in functional languages and in compilers. But tying the idea of a continuation to it is needlessly complex, niche, and purely a historical quirk. It gives the impression that they're intrinsically related, but they're not. As you've demonstrated, you have to 'imagine' all kinds of stuff to make that view of continuations fit with regular code.
I tend to like the 'everything is a function' approach, it's clean and general, everything is explicit and can be decoupled or abstracted away.
ps: when introduced to the concept in college, I too left the class thinking that's just 'IP'. But somehow it didn't make me appreciate the possibilities. But maybe I'm just dumb :)
The advantage of the operational view is that it is true.
I wasn't sure what you are saying in your PS. That you think the functional description is obfuscatory? Or that you were taught the operational view in college and didn't understand why it would be useful?
I think it is unlikely to be you being dumb. Either way your lecturer should have worked through the 'possibilities' to demonstrate why it is useful (exceptions, multitasking, asynchronous code).
None is more true than the other. CPU didn't have "stack" before people wanted nice recursion I believe, and there are runtimes that don't use them.
With time I started to go away from low level and stay in logic land thinking it can be represented in many ways on the metal. But in school I was still thinking with hardware first. I don't think I could ever have envisioned coroutines or backtracking this way.
Interesting on the last point, that you'd find coroutines harder to explain with 'save the current place you're executing, go do something else, return to that place when you need to do more'.
I never got the hang of 99% of explanations of call/cc.
Simple explanation: continuations are goto/jumping where a value is passed from the place of jumping to the place being jumped goes to.
Explanation: continuations implement goto/jumping where a value is passed to wherever the jump goes to. The call/cc command does three things: (1) create and name a place to jump to, (2) hide this place from the outside, and (3) provide a function that accepts the value passed upon being jumped to. The throw command jumps to the state place and carries the value to be passed in jumping.
No offence, but I'll stick with my version, since it describes what is actually happening, and how to implement it.
If you don't save the calling environment, you are trashing the call-stack leading to undefined behaviour. So this is not really even goto, it's a desaster ... That's why the C/C++ equivalent of non-local goto, namely setjmp-longjmp, does indeed save the calling environment. You cannot have non-local goto in a language with a call-stack otherwise. In that sense, the callcc / throw combination is like goto, with the addition that the place you are jumping to (declared in callcc) is hidden from the outside.
Likewise exceptions in C++ are a form of non-local jump (albeit dynamically bound, unlike goto and call/cc) and they do clean up the stack.
In my drive to give a simple explanation of call/cc, I clearly oversimplified. I should have made it more clear that I'm talking about semantically meaningful non-local goto in a language with a call-stack. Thanks for pointing this out, sorry for the confusion.
goto on its own doesn't honor the call stack in C, which is what the setjmp.h is for, and non-local 'goto', so yeah, it is closer to that.
Continuations also don't have to use a call-stack (though I totally acknowledge we're outside mainstream programming now). The idea is very general, and very simple: a data structure that a) stores the current FP, and b) can restore that FP when required.
But in all cases what you do with a continuation is the same, you define a point in the computation (that's what callcc does) that you can go back to (by executing throw). That's why I like to explain callcc / throw by analogy with goto.
Once that behaviour is clear, the question of representation is natural and comprehensible.
Continuations can be used to explain a wide variety of program control such as calling/returning (procedures), raising/handling (exceptions), jumping/labeling (goto and labels), process switching (coroutines), backtracking (amb and fail), and capturing/invoking first-class continuations (callcc and throw).
An example of using the full power of continuations is the notorious argfc function [1]:
callcc lambda k.(throw k (lambda x.(throw k lambda y.x)))
(lambda x.(x 1);(x 2)) argfc = 1
(lambda x.lambda y.(x 1);(y 2)) argfc argfc = 2
If we use continuations linearly (i.e. exactly once) or affinely (at most once), such forms pathological behaviour cannot occur, so implementations might be easier. In particular, special cases of continuation use such as function call/return and exception throw/catch do not require such duplication of continuations, so can be implemented much more easily than general continuations. It is the completely unrestricted nature of full callcc/throw that requires the implementation to capture the whole call stack.
[1] H. Thielecke, Continuations, functions and jumps.
[2] J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.
(Then again, being on a team that wrote a cooperative task based callback centric run-time from the ground up really made it all sort of click together. In a very blatant "we should have used continuations sort of way!)
You have a dispatch loop that is in charge of "tasks". A task that wants to be continued later on uses a macro to copy the entire stack from the current point all the way down to the first function call that the dispatcher made for the task.
Copy off that stack and the current instruction pointer to a structure, tada, that is a continuation. Resuming is pretty easy in raw C land.
Compare that to a lovely CS description:
> In computer science and computer programming, a continuation is an abstract representation of the control state of a computer program.
I know that the world isn't all C, but "copy of the stack" is so much easier to grok at first.
Anyways, if at any point in my life I ever get to be part of another team that writes a from the ground up run-time for an embedded system (doubtful), then I'm copy off one of those C macros that does continuations. Our code base would be a fraction of the size!
The tutorial is great, neither too simple nor too hard (subjectively of course).