Continuation-Passing Style

re: Continuation-Passing Style

Tobias — Tue, 12 Aug 2008 12:16:02 GMT

God I love this sentence (I had to read it at least five times :)

"The continuation of the computation at the invocation of F is the remainder of the program execution beginning with incrementing x in the method M."

re: Continuation-Passing Style

Jigang Sun — Sat, 02 Feb 2008 10:51:22 GMT

To explain a complex concept in a simple and very understandable way is a contribution. I really do not understand why other mathematicians explain the simple word in a complicated way. If this page were available earlier, my thesis could have been finished better.

Continuation

Greg — Mon, 21 Jan 2008 18:58:23 GMT

We've been using this for more than 20 years to fake mutithreading on single CPU embedded machine in C. these environments typically do not have threading and usually have almost no Operating System.

The Marvels of Monads

Yet Another Language Geek — Fri, 11 Jan 2008 03:06:17 GMT

If the word "continuation" causes eyes to glaze over, then the word "monad" induces

re: Continuation-Passing Style

Sadek Drobi — Mon, 07 Jan 2008 03:23:02 GMT

Great post Wes! Do you mean by "M" the monadic one? Anyway, I hope to see some useful monads in C#, and maybe some syntax help for it from the language who knows...

re: Continuation-Passing Style

wesdyer — Sun, 23 Dec 2007 08:56:16 GMT

Derek & Peter:

Fantastic comments.

We use CPS to implement cooperative threading in JavaScript in Volta.

It is definitely true that a full CPS transform isn't very helpful in C# (to humans), but there are still many areas where it helps to convert portions of code to CPS.

As you have probably guessed, my next post will start to show another way (without CallCC) to take advantage of CPS without turning code inside-out.

re: Continuation-Passing Style

Derek Elkins — Sun, 23 Dec 2007 08:41:11 GMT

As a quick note adding to Peter Thatcher's comment: Indeed, continuations and/or continuation passing style (CPS) can be used to implement concurrency (i.e. implement very lightweight threads) with user-definable schedulers. By itself, it would be cooperative concurrency.

I'd like to expand the UI comment as well. As you say, the CPS transformation systematically takes "normal" code (called direct style) and turns it "inside-out." Why do you want your code inside-out? You don't. Unfortunately, some interfaces, specifically event-based ones, require it, e.g. many GUI frameworks and web applications. If the language has support for CallCC, you can write the direct style code and have it transparently work with an event-based GUI framework. When you first started programming, you might have written a program that reads two numbers from the console and displays the sum. With continuations, you could write code of that simplicity and have it work for GUIs or web applications (in fact, you could make it so that the exact same code will do all three depending on how you instantiate it.)

Continuation passing style is one way to support CallCC if your language doesn't, but unfortunately, continuation passing style is of very limited utility in C#. CPS transforming your code causes all functions in it to never return. Since, you can't rely on tail call optimization, this means that the stack will just build and build until it overflows. You can avoid this to some degree, but only by avoiding many of the sort of things that make CPS and continuations interesting. One of the things you can still do is the "uninversion" of control described above with regards to event-based systems. (You end up inadvertently implementing tail calls through trampolining.)

re: Continuation-Passing Style

Peter Thatcher — Sun, 23 Dec 2007 01:09:08 GMT

I'd like to add that CPS can also be used to simulate message-passing systems like Erlang or Scala have in a language without threads, including Javascript. In that case, you do something like the following Python:

receive(lambda msg : print msg)

Of course, that only receives one message. To loop, you need to either call more receives in the passed cotinuation or play trickery with specific language features like generators.

re: Continuation-Passing Style

Tanveer Badar — Sat, 22 Dec 2007 15:57:49 GMT

Excellent post. Really enjoyed it. And my head didn't explode :)