4 ms·

Agreed, I found this page hopelessly meandering and confused. The way continuations were explained to me is that they are "the rest of the program," which isn't

Agreed, I found this page hopelessly meandering and confused. The way continuations were explained to me is that they are "the rest of the program," which isn't much better, and it took me a while to wrap my head around them. But in the end they really are simple. As you said it's just the stack and the PC register. Calling a continuation jumps back to where the continuation was created, and execution resumes as though the program had been running there all along. One neat thing you can do with continuations is use them to implement multitasking—see "Concurrent Programming in ML."

jcrites 11y ago
It's fun to try to explain concepts, and a nice way to refresh memory, so let me take a shot. 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) What is the function that represents calling print(___ + 2) and substituting a value for ___? In a language with lambda functions, we can represent the expression with the hole in it as a lambda: lambda n: print(n + 2) The lambda function is a precise concept with a definite representation, as opposed to the vague idea of the blank. 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) Now I want to design a callback so that I can invoke f() in this way, with behavior that was equivalent to print(f(x) + 2)) The question is, what callback can I pass to f() that will have the same overall result as 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 kind of callback where we pass an expression representing what to do next is called a continuation. Thus we say that the lambda function we described is the "continuation" from within f(x) given the expression print(f(x) + 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) This style does not require a control operator quite like 'return', since invoking the callback explicitly has the same effect. 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.
- sago 11y ago
  > You can think of each point in the code as having a continuation which is what to do next immediately after it. 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.

jcrites 11y ago

It's fun to try to explain concepts, and a nice way to refresh memory, so let me take a shot. 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) What is the function that represents calling print(___ + 2) and substituting a value for ___? In a language with lambda functions, we can represent the expression with the hole in it as a lambda: lambda n: print(n + 2) The lambda function is a precise concept with a definite representation, as opposed to the vague idea of the blank. 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) Now I want to design a callback so that I can invoke f() in this way, with behavior that was equivalent to print(f(x) + 2)) The question is, what callback can I pass to f() that will have the same overall result as 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 kind of callback where we pass an expression representing what to do next is called a continuation. Thus we say that the lambda function we described is the "continuation" from within f(x) given the expression print(f(x) + 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) This style does not require a control operator quite like 'return', since invoking the callback explicitly has the same effect. 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.

sago 11y ago
> You can think of each point in the code as having a continuation which is what to do next immediately after it. 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.