Lambda the Ultimate

I thought that was really interesting too. Personally, I think that sequential user interactions are a terrible thing, and severely constrain the things you can do with the web. Imagine trying to write an IDE or a serious word-processor or spreadsheet with a non-AJAX webapp (I haven't used Writely, but I believe they're AJAX). However, the web made 3 features ubiquitous that users have now come to depend on:

1. Persistent, always available undo. No matter where you are on the web, the back button always gets you back to where you came from (well, unless an AJAX app just broke it).
2. The ability to jump directly into an interaction, bypassing intermediate pages. Also the ability to store your place in an interaction (bookmarks, history list, writing down a URL) and pass that information to a friend
3. A universal GUI focused on displaying information. Webpages are frequently more information-dense than desktop apps, and the good ones have less extraneous visual clutter

Interestingly, the first 2 of those features depend heavily upon continuations. I wonder if we'll see webapps evolve to be more like desktop apps, but those desktop apps will need continuations anyway.

I'm not convinced that "linear" apps are becoming more popular. Let's not forget that web applications are far outnumbered by simple websites that support true random access (via search engines).

I see quite a lot of influence on desktop applications from the web. An increasing number of apps generate their UI using HTML-ish rendering (XUL, Apple's desktop widgets, etc). Searching is becoming more important, though it has a way to go. Also, there's sometimes navigation via link-following with forward and back buttons (IntelliJ is pretty good at this).

I don't quite get the appeal of continuation frameworks. It seems like they introduce a coupling between what should be a long-lived, stable data representation (bookmarks) and something that a developer should be able to rewrite whenever they feel like it (a method's local variables). Just like Java serialization isn't so hot for a database format, framework-generated continuations seem like a really bad idea for long-lived bookmarks.

Last night I wrote (and junked) a long piece on why I wanted native first class continuations. It was so long, I broke it into two long pieces. But I favor a rule of thumb: something I can say well can be said quickly. The conclusion: what I wrote last night sucked. I'm unsure how to write something readably short.

But I really want to say something on this topic, so instead I'll just hint around my focus without really making definitive statements. (I'd rather say something about complex servers, but the number of words just explodes when I tackle that vein of thought.)

A couple plausible metaphors came mind: knots in strings and a classic brain teaser. This paragraph is about the brain teaser, which is stated as follows. You have three jugs holding 8, 5, and 3 gallons each. The 8 gallon jug is full of water and the other two jugs are empty. Divide the water into two equal parts (four gallons each in two different jugs), only by means of pouring water from one jug to another. [Hint: if you first get two gallons into the 3g jug, then filling it from a full 5g jug leaves four gallons in the 5g jug.]

What's the point of this brain teaser? Sometimes you can simulate the tool you want (a four gallon jug) to measure out your problem, but the simulation is not something obvious every time when coding, especially when performing many other simulations at the same time -- because none of your other tools are exact fits either. Your toolkit is a bunch if weirdly sized jugs rated to hold different fluids, and your system uses water, oil, gas, liquid nitrogen -- you name it -- that you don't want mixed.

This is where the knots-in-strings metaphor comes into play. Someone gives you a string with a single granny knot in it, and challenges you to remove the knot. Okay, no problem. The simpler the strawman, the easier it is to solve, right? How about something harder? Someone gives you a string with lots of knots in it all interlaced in one snarl -- a true Gordian knot -- and challenges you to remove the knot. Take your time, but the clock is ticking.

I've notice that folks like to present single granny knot problems when they argue first class continuations are unnecessary. (The demonstration of untangling looks so easy.) But it would take forever to present a Gordian knot problem, so in effect they don't seem to exist in blog venues, which filter for simplicity. But that's not realistic. Your typical professional coder sees Gordian knots in code all the time. You spend your first few days on a new job counting such knots, and listening to tales the old timers tell about folks lost at sea, tangled in nets during past storms. (Sorry, I'm having too much fun.)

Suddenly I'm liking this fishing boat metaphor that's come to mind, so I'll go with it. Okay, your typical programming language vendor is really making nets for fisherman. Net vendors want to sell nets pitched as cheap, strong, and reliable. (You can add weight and other factors to this metaphor, but it doesn't matter.) Really cheap and virtually indestructible would be nice. They want to make nets will simple knots in them -- cheap, easy to produce, and strong within easily measured parameters when looking at a net in isolation.

Fishing net vendors (programming language vendors) offer nets for sale to fisherman -- deck crew and ship captains alike -- based on scenarios that are simplified, and often don't resemble what happens at sea, with all that gear deployed, following the schedule invented, and using the new accouterments on the ship's deck. Once the crew starts landing incredible numbers of fish (and why are they doing this in a storm anyway?) and jury-rigging the equipment to solve problems on the spot, weird things start to happen. The nets almost always snarl and there's no time to fix every tangle under the pressure. Knots that tangle nets at sea are a different order problem than the simple knots in rope making the net work as a net.

Umm, I don't think I like this metaphor any more. But at least the last paragraph is lots shorter than what I wrote last night. Here's my main point: the cost of tools in isolation is different than the cost of tools when deployed in the field, especially if the scale and complexity of field deployment is a lot different from a numerics benchmark. Sometimes you want to use a different cost function, depending on the context. To lower the cost in a very complex end system, you might prefer to increase basic costs in the tools in isolation, because the cost function looks better when you deploy with more-versatile but more-expensive parts.

Continuations typically require an implementation which uses more heap memory, and appears to churn gc more than necessary when viewed in isolation. However, sometimes the use of first class continuations is like having jugs in every single size you want to measure, without awkward simulations. When push comes to shove in complex servers, sometimes developers give up and just start allocating more memory and copying things, because the whole nest of knots has gotten too much to untangle. When this happens, a little more allocation in stack frames might start to look like small potatoes. A slightly more expensive tool that eliminates some chaos is a gem, if it puts the developer back in control.

Okay, that was too long. But it didn't stink as much as my last effort.

In French we have a saying 'Ce que l'on conçoit bien s'énonce clairement et les mots pour le dire arrivent aisément': to summarize: if one understand clearly a problem, he can explain it easily.

If you don't manage to explain your point easily, think again about the point you're trying to make..

I think I agree with that most of the time. I might be able to make my point again more clearly.

Compared to other features in a programming language, first class continuations are relatively complex. For example, most of Scheme is nice and simple, except for continuations. :-)

Continuations also incur runtime costs, like heap based stack frames. So what good are they? I'll avoid "coroutines are really neat", which I think is valid; instead I'll make a point about cost.

A complex and expensive primitive in a language might only pay off when you can factor some large cost out of a complex and expensive high level use case. And the more complex and expensive the use case that gets reduced, the more sense it makes to save the cost this way.

So it makes sense that simple use cases won't make good examples of where an expensive primitive looks cost effective. A really good (terribly complex) use case might be hard to cite for many reasons.

For example, no one wants to admit they actually create (or just experience) certain kinds of messes that can be helped by a complex and expensive low level primitive. It's Emporer's new clothes social territory.

People in technical venues like this one use brevity, simplicity, and clarity as an indirect measure to assess idea quality and/or speaker competence. So if something requires complexity to describe correctly, then it can't be said and be graced with easy acceptance, using that metric.

Agreed about your point, that's why it's difficult to defend GC also for example.

Of course the irony is that once people get their hands on Java or C# (since they apparently did not get their hands on Scheme, Lisp or ML, etc.) or maybe even Perl or Python, they quickly appreciate GC.

How do you know when to de-allocate an instance? What if I open a web browser on your app then close the web browser (or my machine crashes) before completing the interaction? Now you leak server resources -> bad.

What if you add a timeout so that state objects are released after a while. You still use unnecessary resources, albiet for a limited time. So I am using your app, get distracted or go get lunch, and when I come back I find my session has expired and the data I input has vanished -> bad.

Ruby on Rails adopts a system whereby it serializes sessions to disk, but I don't know what its policy for freeing dead ones is. It's probably sensible though.

You have the same problem with any multi-page web interaction. What if the user has a single browser window open, gets halfway through an order form, then decides they don't really care and shuts down the computer? You have to decide when to free up the resources of that session. And you have no way of knowing whether they just got up for a cup of coffee or have given up entirely on their purchase.

That problem disappears if you track current session state entirely using cookies, hidden form fields or URL request parameters thereby keeping the server essentially stateless. It's definitely possible and common to write webapps with no server side resources allocate to track client state.

How do you know when to de-allocate an instance?

Using timeouts.

and when I come back I find my session has expired and the data I input has vanished

So? it is so bad? if you have a job to do, just do it. I can't wait for you forever ("I" as in the server).

Ruby on Rails adopts a system whereby it serializes sessions to disk, but I don't know what its policy for freeing dead ones is. It's probably sensible though.

1) what does this have to do with continuations?
2) what If I never come back? how does RoR deal with that?
3) what keeps me from implementing serialization state without having continuations?

You're still saving the continuation, you're just doing it manually. Your Java object is essentially a continuation where you have to set the state manually. True continuations save the state automatically based on what local variables are currently on the call stack.

The resource leak Mike mentions occurs because you're saving the continuation on the server and only storing a pointer to it on the client. Many continuation frameworks will serialize the continuation totally and send it back to the client as a hidden field. This preserves REST properties (easy caching, back-button aware, history list, multiple window-friendly) at the expense of bandwidth.

That's a good idea, though serializing a whole stack sounds scary. What if the stack contains pointers to memory on the heap, is the whole object tree serialized too? I guess it must be. *boggle*

Yes, but in practice the stack of webapps (excluding the basic HTTP parsing/marshalling functions, which usually aren't captured in the continuation) is usually fairly small. Looking at Java stacktraces of webapps I've written, I rarely have more than 3-4 frames of application code on the stack.

In theory, the amount of information that's captured by the continuation is precisely the information that's been entered by the user, as long as the app is smart and performs all the processing only after all steps have been completed. Few users have the time or patience to enter more than a couple K of info, unless the form includes uploaded files, which can't practically be serialized and passed around as a hidden form field anyway.

All that is needed to "save" is the information the user has input so far, which means a different instance of the application object model for each different state the user is in. So the server has one session per user, and each session has many 'sub-sessions' which each one corresponds to a "work flow" of the user. Submitting the same form from two different windows ends up affecting two different objects, and thus there are no complications, and no need for continuations.

Yep, what the "a different instance of the application object model for each different state user is in" amounts to is manually transforming the UI code to CPS (and then defunctionalizing it). With continuations you can write your UI in direct style, without having to perform the transformations by hand. I recommend reading the article ("Escaping ...") I mentioned earlier.

As I have implemented it (maybe I am missing something here), the UI has nothing to do with keeping the states around. The states are simply data objects. The UI is a separate layer filled from the data. Continuations offer to me nothing that I do not already have.

The UI has plenty to do with keeping around UI-related state, no?

Have you read the article?

Well, continuations allow you to "escape the event loop" or, in other words, allow you to write your UI in direct style rather than in defuntionalized CPS. See, for example, Escaping the event loop: an alternative control structure for multi-threaded GUIs (probably mentioned here before).

As regards web programming I think the issue is essentially "Automatically Restructuring Programs For The Web" (search the archives). I don't think this must be related to support for continuation at the VM level.

VM support is helpful, on the other hand, when you want to use it as a platform for languages with first class continuations. You can, of course, do the hard work yourself (instead of relying on the VM), but that's cumbersome for a variety of reasons.

finally someone had the guts to admit it!

it doesn't seem very major from a commercial POV

Actually I am not so sure about this. If we are talking about a platform war, instead of a language war, things like this can be important and have butterfly effects.

But LtU isn't for marketing discussions, so I guess we should drop it.

Speaking of Business Process Management and continuations, BPMScript uses Rhino and it's continuation support in this area apparently.

There is also Dragos Monlescu's Workflow Enactment with Continuation and Future Objects.

But the alternative, keeping the state on the client, is much better. It's simpler, more RESTful and less computations and storage are needed on the server (i.e. more distributed).

Continuations make an excellent platform on which to build very lightweight threads, and it's been done very successfully in various Scheme implementations - hundreds of thousands of threads are no problem. If Java had continuations, you'd already have your lightweight threads.

But let's say you were given your lightweight threads as a built-in feature in Java. Can you suspend them, then clone them, serialize them, migrate them to another machine? If you can at least suspend and clone them, so that you can restart a thread at the same point more than once, then you've got continuations. If you can't do that, then you're missing out on quite a few use cases.

Really, first-class continuations are just a consequence of applying proper factoring to the concept of threads. Is there some reason that the design principles we apply to our programs shouldn't apply to our languages?

If Java were a language in which concurrency was implicit in the language, embedded somehow, and Threads weren't objects, then there might be a high-level design argument for saying that first-class continuations aren't appropriate. But as it is, Java's high-level design begs for first-class continuations.

And how can you migrate them without first supending them, then serializing them and finally recreating them in the target machine?

Also, Erlang excels at concurrency because there is no shared state and no synchronization on that shared state. Well, if you remove those, continuations have none of the issues you mention.

And how can you migrate them without first supending them, then serializing them and finally recreating them in the targuet machine?

The implementer needs those sub-operations, but it's perfectly reasonable to not offer those sub-operations to an end-user. By analogy, implementers have to worry about register mappings and stack layouts, but end-users only need to know about call semantics, and have no acesss to the implementation level. A distributed JVM could certainly support thread migration without allowing general continuation semantics.

Continuations in Java are secondary to me. I would like to have continuations and (even more so) tail-calls in the JVM, not necessarily in Java. So, to me, this is not about “end-users”, it's precisely about (language) implementers. Must implementers be shielded from all the complexity too?

OTOH, maybe the JVM is bound to be just that - a Java VM, and not this multi-language run-time I'd wish it could be. [rant] But then maybe Sun & Bracha should stop marketing it as such, and drop feable attempts like invokedynamic, which isn't of much use anyway. [/rant] Sorry.

Subject line to be read in the same tones as "you don't hate children, do you?"

I understand that continuations would be a useful implementation technique for light-weight threads in Java, but I really was serious that I don't see the value of exposing them to the end-user

Hence my point that this is really about tools and supporting tool developers. How do you expose language features to tool developers without exposing them to end users? Or should tool developers just be forced to live with whatever end users get? The latter is the traditional answer, for traditional languages, but the nature of the relationship between language developers and their communities has been changing, with open source languages being one of the driving factors.

Re the issues with continuations, such as locks on shared resources, those are all well understood, and have been dealt with in various ways in environments that support continuations. One way is just "don't do that", and for some kinds of tools or frameworks, the tool can help make sure that things work properly, e.g. via finalizers, automatic transaction boundaries, etc.

migrate them to another machine

That would indeed be wicked cool, but could be handled by the runtime without explicit programmer knowlege of continuations.

So you're saying that you want to rely on Sun to implement this stuff for you whenever they get around to it, instead of the much larger pool of smart tool developers who could have implemented it already. In fact, those tool developers have implemented migrateable continuations already, but only via interpreters on top of the JVM, afaik.

I guess my takeaway is that what I really want isn't Scheme-in-Java, but rather Erlang-in-Java. Scheme-in-Java seems like it would cause more problems than it fixes. Erlang-in-Java would fix a lot more problems than it caused.

Erlang-in-Java would certainly fix some problems, but would leave many others unaddressed, and would push a particular model of concurrency. Continuations-in-Java (since we're not talking about anything close to full Scheme) would allow a whole range of other problems to be addressed in whatever way is appropriate to the problem.

The idea that continuations-in-Java would cause problems is speculative - what's the real concern? That ordinary programmers will start wildly abusing continuations, resulting in flaky and impenetrable spaghetti code everywhere? That bad tools which overuse continuations in all the wrong ways will proliferate? There's no evidence that these outcomes are particularly likely. Bad coding practice and bad tools die, usually quite quickly.

I think plausible arguments could be constructed against continuations-in-Java from various purely technical, language implementation perspectives, or even the perspective that rejiggering the VM will be too costly. But I'm not seeing any real technical factors underlying the concerns about what continuations might unleash on an unsuspecting programming public.

This re-raises a very interesting cultural subpoint that I haven't really thought about much lately. I can't recall who first made the observation—probably Alan Kay—but someone once said that the major difference between the Lisp/Smalltalk communities and other language design communities was an almost religious insistence in the Lisp/Smalltalk communities that any capability that was available to the language designer should also be available to the language user. You saw this with InterLisp's structure editor, with which you could trivially edit yourself into a crashing system, and you see it today in Squeak, which will happily spit out its own kernel, which is written in a subset of Smalltalk and then translated to C for compilation.

Java lies at the other end of the spectrum. Yeah, it's got reflection and dynamic bytecode loading, and people have made heroic efforts to take advantage of them with BCEL and CGLIB and built amazing edifices around them such as Hibernate, but these happened in spite, rather than because, of Java's support for such efforts. I find the philosophical distinction quite telling.

Before anyone asks, yeah, O'Caml's kinda-sorta closed in a similar way. However, I would point out that it has an excellent syntax extension mechanism, and there's only one module in the entire system—Obj—that is undocumented. I think the existence of Flow Caml, Acute, HashCaml, and MetaOCaml demonstrate reasonably well how far you can go with O'Caml's balance of closed vs. open implementation.

Amen. From my perspective as a language consumer rather than creator, I think I want the proper theory that gets away from the "hard to get right" and then everybody can relax and get into more use cases.

Shared state concurrency is apparently so bad that either people avoid it, or just ship stuff that has lots of bugs in it. Get away from that and maybe the people who avoided it because it is scary evil would start making cool new things?

It goes like this...

  Moe: Welcome to our C++ project! Our customers are/will be dying 
       when we get started.
       Okay, let's strap our explosives on them and run them
       through traffic as a warmup, before we install our software

  Rys: Great.

  Moe: Huh uh, that's not nearly enthusiatic enough.  More Cowbell!

However, continuations could also be stored on the client, in effect passing them "by value" instead of "by reference", thus satisfying his desire that the client communicate all the relevant information to a stateless server to complete the transaction.

Which places additional restrictions on the server, namely, a) that the continuations are not too large to be serialized back and forth, b) that the state contains nothing sensitive (hard to ensure), and c) any client-provided state must be fully validated.

There are viable trade-offs here as to an appropriate balance of server/client state, but (b) seems particularly tricky. Given how much state continuations can capture, it just seems safer to leave them server-side.

Besides, continuations, and particularly delimited continuations as you point out, are so small why not just leave them server-side for some state? That way you don't have to mess about with encryption. It makes reasoning about the system's integrity simpler, though it does impose limits on scalability and robustness.