5 ms·

A page about call/cc (2002)

39 points by tomjakubowski 11y ago

peter_l_downs 11y ago
Oooh, continuations! Such an elegant tool. If you're interested in looking at some messy code, I used continuations to perform a DFS without ever explicitly constructing a search tree as part of an attempt to programmatically write poetry – see https://github.com/peterldowns/bard https://github.com/peterldowns/bard (`interpreter.scm` in particular.)
- Filligree 11y ago
  I don't know if your program works, but I see you've got some poetry.
agumonkey 11y ago
Funny I was just reading about Delimited Continuations today http://logic.cs.tsukuba.ac.jp/cw2011/ http://logic.cs.tsukuba.ac.jp/cw2011/ The tutorial is great, neither too simple nor too hard (subjectively of course).
sago 11y ago
When I came to implement call/cc in my Scheme interpreter, I realised that a continuation is just a data structure holding the current function pointer and call stack. 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.
- niccaluim 11y ago
  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.
myrryr 11y ago
Scala CAN have continuations, you can turn them on in the compiler.
MichaelGG 11y ago
Interesting to see the note about nested functions being returned. C# and F# both do this, and I'd guess Java will too, once it gets them. In fact, it seems downright wrong to not allow returning nested functions in a GC language that has closures.

39 points by tomjakubowski 11y ago

Oooh, continuations! Such an elegant tool. If you're interested in looking at some messy code, I used continuations to perform a DFS without ever explicitly constructing a search tree as part of an attempt to programmatically write poetry – see https://github.com/peterldowns/bard https://github.com/peterldowns/bard (`interpreter.scm` in particular.)

Filligree 11y ago
I don't know if your program works, but I see you've got some poetry.

agumonkey 11y ago

Funny I was just reading about Delimited Continuations today http://logic.cs.tsukuba.ac.jp/cw2011/ http://logic.cs.tsukuba.ac.jp/cw2011/ The tutorial is great, neither too simple nor too hard (subjectively of course).

sago 11y ago

When I came to implement call/cc in my Scheme interpreter, I realised that a continuation is just a data structure holding the current function pointer and call stack. 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.

niccaluim 11y ago
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.

myrryr 11y ago

Scala CAN have continuations, you can turn them on in the compiler.

MichaelGG 11y ago

Interesting to see the note about nested functions being returned. C# and F# both do this, and I'd guess Java will too, once it gets them. In fact, it seems downright wrong to not allow returning nested functions in a GC language that has closures.