Continuations: Wistfully yearning

During the past week, there was a conference at Microsoft's campus in Redmond, Lang.NET. I didn't attend, but I did look over again at the videos from the previous speakers (one of which was by Danny Thorpe).

However, it wasn't Danny's talk that I found most interesting. Instead, it was Shriram Krishnamurthi's presentation on continuation-based web application programming. Ian Griffiths wrote a disparaging post on continuations describing how they can work in a web application, in case you're not aware of their nature. I strongly disagree with Ian, though, to the point that I'm not actually sure if he's willfully misrepresenting those who would advocate continuations.

In my previous job, we developed a web application framework, running on top of ASP.NET, for data-entry intensive applications in the finance industry. The product is now called Topoix. I contributed a bunch of things to the underlying architecture and implementation, but one of them is particularly relevant to continuations: the way Topoix implements modal dialog boxes that ask the user a question. Essentially, displaying a dialog caused execution of business code on the server to stop and resume correctly, based on the reply, when the dialog was dismissed. The stopping and resuming didn't tie up a thread on the server, and nor did it require stickiness to a particular server in the farm, but obviously it required some state - persisted to disk and perhaps cached in memory, depending on how you wanted to configure things.

Now, I want to address some of the (IMHO) mistaken criticisms in Ian's article.

This requires a certain amount of magic under the covers. Supporting continuations in special cases such as function calls or iterators is much easier than providing completely generalised support. Continuations do not fit all that well with the stack-oriented execution model offered by the JVM or CLR.

I agree to the point that code that hasn't been transformed into continuation-passing style doesn't fit well with a stack-oriented execution model. But, however, bear in mind that translation from stack-orientation to continuation-passing style is a safe and semantics-preserving operation. Things really only get hairy if one uses callbacks from non-managed code, and one expects to be able to pass around a continuation with the non-managed code on the stack.

Ian continues:

Continuations can look attractive on the web, because they offer a tool that lets you capture the shape of a sequential user journey in the structure of your code.

Continuations can do more than capture sequential user journeys; if you take care to capture values, rather than references, they can capture an arbitrary history tree of independent, concurrent user journeys. This is because the stack in CPS is essentially converted into a linked list of activation records in the heap, where each activation record points to its parent. It's trivial to see that continuing at an earlier point (equivalent to pressing the back button in your browser) simply creates a new activation record which points to some tail of the linked list, and doesn't disrupt the concurrent "main trunk" of interaction. Providing that you don't mutate variables from previous activation records (unless that's desirable - consider e.g. site preferences, or login status), you don't have a problem with non-sequential navigation.

However, I think this is a bad idea. Although the relationship between the code and the user navigation path is apparently simple, it hides subtle but significant details. This makes the same mistake as we did in the 1990s with distributed object models. We’d like to believe we’re hiding a lot of implementation details behind a simple abstraction. In practice we’re hiding important features behind an inappropriate abstraction. Our industry has more or less learned the lesson that procedure calls are an unworkably naive abstraction for request/response messaging over a network. I suspect that it’s equally naive to attempt to manage the complexities of user/web server interactions with simple sequential code.

Ian here is saying that bad abstractions are a bad idea. I fully concur; when building abstractions, it's important to abstract the correct things, and not encourage writing the wrong sorts of programs. There are a few things to say about this, though. The first is that the really egregious abstractions are those which enable writing programs that one would not actually *want* to write, if one fully understood the abstractions in hand. I'm thinking in particular here of cross-machine COM or CORBA: we should prefer REST or document-style SOAP for reasons that are beyond the scope of this post, but I'll just say that they relate to the nature of object orientation as used in the small, with shared memory, on local machines, and how that falls apart when distributed.

However, I think Ian will have to come up with something better than condemning continuations as only being capable of abstracting "simple sequential code", if for no other reason than it's a falsehood.

So, Ian tries to come up with other reasons to slay the continuation beast. However, it's worth bearing in mind, when considering his objections, what the alternative is, and then asking one's self if the alternative isn't actually a continuation written out the long way.

Let's see.

Abandoned Sessions. Sometimes the user just walks away.

Well, a continuation that one persists to a cookie, hidden form fields, encoded in the URL, or to server-side storage, as necessary / appropriate, puts this one to rest. And besides, how does one solve this issue in the average trivial shopping-cart site? One must save state in exactly the same locations, but you have to encode the resumption of logic yourself, rather than having it done for you. The abstraction doesn't look weak here.

Now, there are things Ian says that aren't related to continuations per se, but rather to coding a web application as if it had state.

Continuation-based web servers aren't a way of pretending that the server is stateful when it needs to be stateless. Rather, they're a way of easing the pain of getting back to where you left off. That's why, when Ian says:

The problem with this is that a lot of the techniques we have learned for resource management stop working. Resource cleanup code may never execute because the function is abandoned mid-flow.

... it's not very relevant. One can't be holding any non-persistable resources when persisting a continuation, and with language and library support, this can be flagged at runtime or ideally at compile time (I can't help it, I'm a static guy, even though it's not fashionable in the web world). And since the continuation-persisting code needs to, you know, actually persist the objects on the linked-list stack, it can trivially flag the obvious problems when it discovers something it can't persist.

Thread Affinity. With an ordinary sequentially executing function, I can safely assume one thread will run the function from start to finish. But if I’m using continuations to provide the illusion that I’ve got sequential execution spanning multiple user interactions, then I might get a thread switch every time I generate a web page.

I see this as kind of a bogus problem. How often, when writing an ASP.NET application, does one work with objects or resources that have thread affinity, and expect them to be on the same thread when you next enter the server? I should think one doesn't expect this at all - one doesn't normally have the ability, much less the "problem", of handing an object from one request/response cycle to the next.

Web Farms. This is essentially the same problem as the thread affinity issue, but at the machine level: in a web farm, your sequential function might end up executing on a variety of machines over its lifetime. However, you’d probably avoid this problem in practice using sticky sessions. (And unless your continuations are serializable across machine boundaries you’ll have to do this.)

I don't see any point to using continuations if they can't be saved and resumed at will, across process boundaries, machine boundaries, server restarts, etc. If you limit the power of the continuations you consider, it's pretty easy to condemn them as not being powerful enough.

The Back Button and Branching

This one’s the killer.

Your web site may present linear user journeys, but that doesn’t mean your users necessarily follow them. I often don’t.

I habitually do two things that will confound any web site that expects the user to do things in a particular order. First, sometimes I use the back button. Second, sometimes I bifurcate my navigation - I’ll open a link in another tab. Both of these will confuse any web site that thinks it knows what my ‘current page’ is. The notion of a current page is not enshrined in either HTTP or HTML, and I enjoy the flexibility this offers me when browsing sites. Indeed, it’s one of the reasons I really like tabbed web browsers.

Here, I don't know what Ian is talking about. I mean, I understand exactly what he's saying, but it's a complete non-sequitur to jump from this behaviour to saying that it's incompatible with continuations. Continuation state forms a linked list on the heap. One can share the tail of a linked list among an arbitrary number of heads with zero problems.

This means I have to write my function in such a way that it can cope not only being rewound, but also to being split so that multiple threads execute the function simultaneously, each taking different paths. But of course because I’m using continuations, each of these threads gets to use the same set of local variables. The fact that I enabled users to inject gotos into my code at will is now looking like a walk in the park - now they can add arbitrary concurrency!

Here, when Ian says "use the same set of local variables", he's talking about mutating the tail of the list, which might be shared by other heads. And he's right in one sense: if you modify the tail, you better mean it, because you're modifying shared state, not local state.

However, I have a couple of more aces up my sleeve. If desired, the transformation that turns sequential code into CPS can also turn mutating assignments into single static assignments. Single static assignment is a form used in some compilers in the back end to ensure that a variable can only ever have a single definition. If one could annotate one's variables, indicating if they should be shared across multiple continuations (stored in the tail) or strictly local to every continuation that redefines it (essentially, hidden in a scoping sense by the redefining activation record), this problem goes away.

The deeper objection I have to Ian's criticism is that you have to deal with this problem anyway, and program transformation just makes your life easier. Consider what you'd have to do to handle Back Button and Branching without using the approach sketched above. You have all the same problems. You still need to make sure that wherever you stuff away your state, that it isn't inappropriately used by the branches. SSA transformation can do this automatically and declaratively.

Consequently, this approach requires you to write your code in such a way that it can tolerate sudden halts, thread switches, rewinding, and forking of execution.

Sudden halts, thread switching, rewinding, forking: what is it in the tear-down and re-setup of the ASP.NET page cycle that stops you from seeing these things, if you choose to describe them that way? Tearing down the page is surely a violent halt. Setting up again, possibly on another machine, is surely a wrenching thread switch away from your carefully constructed state. To support rewinding / forking (aka Back button / new tab / window), you still need need to juggle your state so that it's correctly stored, keyed and associated with its page which was originally displayed to the user. But continuations can do *all* of these things with easier to read code, and selective SSA transformation turns a fiddly choice (should this data be in the database, in memory, in a cookie, querystring, hidden field, client-side state sent back through AJAX) into a declarative form which your Web library should be abstracting for you.

Does your web development environment supporting continuations? If not, why not?

I will give Ian something, though. It's certainly not true (and shouldn't be true) that one simply writes a sequential application using continuations without thought for the network and then expect it to work fine across the web. That can't happen. However, I do believe that with the correct libraries, language, annotations and transformations, a far better language for web apps can be created. Whether it'll be along the lines of Volta, or one of the frameworks described herein, I don't know. However, I strongly suspect new language constructs, or at least flexible DSL support, is necessary. I can even think of implementing continuations using monads, so perhaps it'll be Haskell!