Hacker News Reader

Comment by pmoriarty | Hacker News Reader

Do any non-Lisp/Scheme languages have continuations?

Here's the obligatory "Haskell has a monad for that" comment

http://hackage.haskell.org/package/mtl-2.2.1/docs/Control-Mo...

Speaking of monads, one of the themes in Prof. Sussman's "Adventures in advanced symbolic programming" course was that many metacircular evaluator experiments can be set up by using mostly the same core evaluator but swapping out the underlying monad. I'm pretty sure I implemented the "ambivalent operator" that way, using the list monad (in Scheme), but when we lifted amb to the host Scheme, it needed call/cc to be able to use the built-in control flow.

One thing I like about Haskell is that it's designed so that adding new control flow is not a big deal -- just design a monad. In Scheme it seems to be more work to get it all right.

That kind of feels like cheating though. I mean, the complicated part of a continuation is that it restores the same context and state that the app had right before the plunge. But Haskell inherently doesn't have "floating" state, it's all self-contained within each parameter. So in Haskell it's more or less a fancy goto-statement.

The linked module defines a "monad transformer" that can wrap other monads with a continuation-capturing layer. This means, among other things (Haskell's solution is awesomely general) that you can indeed use it with state, if you compose it with the state monad, or even the IO monad.

(The bottom of the documentation page has a contrived example of this.)

There's lots of continuation styles & libraries, but most are delimited continuations.

In my opinion, delimited ones are far cleaner to implement and to work with than the more universal continuations of Scheme. call/cc, as a product of Scheme's efforts on simplicity[1], has to encompass a larger amount of low-level state than most real-world uses of it use (and it's used far less frequently in "real applications" than academically). Having a better suite of flow control forms and keeping continuations delimited has far less constraints on the design of the runtime and leads to more focused and explicit operation without a bunch of implicit unused implications hanging around.

[1 = simplicity as in fewer built-in operations]

Any recommendations for write-ups on how delimited continuations are implemented?

my reading is that by 'delimited continuations', white-flame is just referring to explicit closures and function calls. which lets you build up event-driven machines in any language that supports closures.

the distinction is that in scheme, where (at least in the standard implementation) each function call takes an implicit continuation and the code is everted using a bulk cps-transform before being interpreted or further compiled.

in this later case, its possible to use call/cc to create a continuation at any point in a 'normal' program, without having to construct the control flow explicitly. its this 'continuations everywhere' approach that can burden the runtime with a lot of consequences, possibly even precluding the use of a stack at all depending on the implementation.

in the former case you can basically do by-hand cps or event-handling in anything. asm, C, c++, python (3), go, js..

Check out Andy wingo's blog. He implemented delimited continuations for guile, and provides lots of sources for his implementation.

And ofcourse everything by Oleg Kiselyov

Also, delimited continuations are no less general than the regular ones. Regular continuations are also delimited, because they cannot capture control beyond the program's startup function.

If we place a prompt at the top of the main function of the program and use that for making delimited continuations, we basically get regular continuations: continuations that can potentially return all the way to the top, just as far as regular continuations.

(We can even set it up so that if any such a delimited continuation does actually get that far, the process will exit.)

Delimiting is actually an extra bit of expressive power, not a constraint.

We can compare the delimited continuation to a boomerang or yo-yo: we know that it will only go so far, and then return. That's why it can be used as a function. When resumed, it will get no farther than the delimiting prompt, and then whatever value pops out of that contour bounces back to us, who resumed the continuation.

The continuation won't keep going and then bail the program.

Regular continuations can simulate delimited ones: there is some jig put in place (with macros or whatever) which catches when the continuation has bubbled up to the faked-out prompt, and redirects the control---by invoking some other continuation that represents the boomerang return. Or something like that.

There are tricks for implementing the delimited ones, though, that don't involve such a thing. Like pushing the delimited continuation onto the stack, so that the return out of the prompt is just an actual return. I.e. entire "future computation" of the delimited continuation is just "installed" into the stack at the current top. The activation frames are hooked up, and then there is a new topmost frame: that of the restarted continuation, to which the procedure context is restored.

> If we place a prompt at the top of the main function of the program and use that for making delimited continuations, we basically get regular continuations: continuations that can potentially return all the way to the top, just as far as regular continuations.

While this is certainly true in theory, in practice it doesn't seem that simple. When you start dealing with already-compiled code (can't apply a macro to it), first-class (built-into the language) continuations will work as you'd expect but delimited not at all. That can be a serious practical restriction.

I'm not used to Common Lisp but I assume you can customize how the "compile" command in ASDF works so maybe you can wrap your entire program, ASDF requirements at all, in that, and that's convenient. But consider Clojure which has equally powerful macros, but whose require forms won't customize like that. You could have your program's compilation phase go through and recompile the entire Clojure distribution of course, but there's some things you can only consume as bytecode (like anything Java related) and obviously you can't help that via CPS transformation. You'll need to get into bytecode manipulation like Quasar does. Not unlike those libraries in the C world that translate blocking system calls into nonblocking system calls for fiber / green-thread / whatever-you-want-to-call-it usage.

Coincidentally, this is exactly the reason I've found Clojure's async module to be such a pain to work with, compared to Quasar.

"Delimited" in continuations doesn't refer to a non-first-class hack. Delimited continuations are first-class, built-into-the-language objects (unless kludged otherwise, which is true of any continuations). They are just semantically nuanced relative to undelimited continuations in that they allow the program to clamp the future computation to within a specified dynamic contour. When the restarted continuation bubbles out to that boundary, it terminates and returns a value to whomever dispatched the continuation. And of course, it can be called again and again to do the same thing. That's why delimited continuations behave like functions and are composable.

Wikipedia provides a list of continuation implementations in a variety of languages:

https://en.wikipedia.org/wiki/Continuation#Programming_langu...

Some of these are first-class continuations; others support continuation passing style.

As an example, here's a simple proof-of-concept webapp I wrote in Ruby, based on continuations:

https://github.com/nathell/ruby-continuation-webapp

The Rhino javascript implementation has continuations. Chris Double once stuck it in Jetty, and I threw together a horrifying proof-of-concept Seaside-like continuation-based web programming library based on that: http://homepages.kcbbs.gen.nz/tonyg/lshift_archive/a-rhino-a...

As a proof-of-concept, it was fun, but that's as far as it went :-)

Rhino was a fun JS system. One of the continuation examples I did for a talk was migrating threads in Rhino: https://bluishcoder.co.nz/2006/06/11/migrating-javascript-th.... Start a thread on one machine, serialize the continuation and send it across the network and resume it on that machine.

Ruby has `#callcc` which produces first-class continuations AFAIK https://ruby-doc.org/core-2.2.0/Continuation.html

Yep. Relatedly, Ruby also has fibers.

Some Smalltalks have them and they are used by Seaside but made optional in Seaside 3.0 because of the platforms that don't have them.

I wonder how it could affect the performance of a interpreter if is build around (internal) continuations, so all the other cool things as exceptions are made on top of it.

I try a small demo, and the complexity of the interpreter get high fast.

Also, if not continuation, what else can be used?

C# has async/await and TPL, e.g. .ContinueWith(...)

Javscript has promises and async/await

If anyone can feedback on why my comment is wrong I'd appreciate it.

I know we're not meant to comment on downvoting but I want to uncover the error in my understanding of this subject because at least 3 people downvoted but there is no reply yet??

Async/await does not allow you to suspend a computation and then resume it, and it is not easy to chain.

Thanks.

I took continuation to include cases where you respond to asynchronous call backs while the program is still executing, in which case suspension isn't needed.

If you implement your own awaiter with INotifyCompletion [1], you get the continuation as an Action that you can invoke as you will. TBH I haven't done it, but I believe you could use that to implement something akin to call/cc.

[1] https://msdn.microsoft.com/en-us/library/system.runtime.comp...

Reply on news.ycombinator.com