Skip to main content

Mobile Continuations for the Web

A continuation is basically the state of a program at the time the continuation was captured. For a common example, consider a blocking system call for any operating system. If the system call blocks the process, the continuation of that process is placed on a blocked queue until the system call completes. When the operation completes, the continuation is removed from the queue and resumed with the result of the system call.

There has been plenty of well-deserved hoopla around continuations for web interaction. Navigating a website is a great deal like operating on a program's continuations. A page generated from a server-side program contains references to a number of program continuations in its links and forms. Clicking a link or submitting a form invokes the captured continuation which the server then executes. The result is yet another set of continuations on the resulting page, ad infinitum.

Unfortunately, most continuation frameworks are designed around server-side continuations, where the continuations are saved on the server, and the client receives only a secure token naming the continuation. The Waterken server is a particularly beautiful example of this for Java. Awhile ago I ported an older version of the Waterken server to ASP.NET. Here is a public continuation for the comments page, and embedded in the comments page is the editing authority, which is an unguessable capability URL for the continuation to edit the comments page.

The Waterken "web-calculus" is actually a full blown persistent, distributed object system with a binding for the web.

However, maintaining persistent server-side state significantly complicates many aspects of web systems. It makes load balancing servers difficult, and persistent continuations are single threaded so only one invocation can proceed at a time which hurts scalability. Furthermore, if the continuations are persistent, as they are in Waterken which provides orthogonal persistence, then we must also contend with schema upgrade.

Two recent articles prompted me to re-examine these issues and devise a solution. First, Tommy McGuire posted a link to his "Infernal Device" paper on LtU. His paper describes a set of structures which can be used to develop an application by reifying the application's states as transitions in a finite state machine. The Transition objects are essentially application-specific partial continuations. The paper also details all of the different storage available in a browser, and how it can be exploited by a server to save state on the client.

For page-local state, the browser URL can hold up to 2kB on IE (other browsers can store more), and we have embedded form fields for POST requests. For site-local state, we have cookies which can be in the multi-kB size.

Then I came across this blog post about scaling Seaside by reducing the need to capture server-side state. The best way to optimize expensive operations is by avoiding them completely!

However, much program state does not need to reside on the server. We can capture a limited set of program state in the browser itself. In essence, we serialize the program continuation in the browser's URL or in its form fields. We also encrypt the serialized form to maintain integrity.

And so our program continuations have become mobile objects that migrate between client and server and can survive server restarts as long as any server state the continuations access also survives restart. A set of load balanced machines need only share the encryption keys, and user requests seamlessly migrate between them.

I've created a small library for mobile continuations written in C#. I also provide an IHttpHandler for use with ASP.NET. A web application using this library doesn't need to use any web controls or .aspx pages. An application is structured as a set of continuations which implement two operations: Show, and Apply. Show outputs the continuation via display-independent set of interfaces. Apply is invoked when a continuation receives a POST request. It takes a NameValueCollection containing all of the form's fields. This takes the place of a continuation's named arguments. I could implement a more elaborate system as found in the Waterken server where the fields are implicitly typed and named, but I felt a more limited scope is preferable for the time being.

By convention, continuations in the research literature are generally named "k", so the continuation interface is named K. This simple HelloWorld class implements the K interface and it embeds a continuation to an Adder object in its display:
    public struct HelloWorld : K
{
public void Show(IWindow v)
{
v.Title("Hello world!");
v.Body(this);
}

public void Show(IBody v)
{
v.Const("Hello", "Hello world!");
v.Promise("Adder", new Adder());
}

public void Show(IInput v)
{
}

public K Apply(NameValueCollection args)
{
return this;
}
}

The Adder class is equally simple, consisting of a text input and a submit button. This continuation builds a form which submits to itself. When applying the continuation, it adds its currently stored value to the value specified in the form and returns a new instance of Adder with the stored value.
    public struct Adder : K
{
int n;
string e;
public Adder(int n)
{
this.n = n;
this.e = "";
}

public void Show(IWindow v)
{
v.Title("Adder!");
v.Body(this);
}

public void Show(IBody v)
{
if (!string.IsNullOrEmpty(e))
{
v.Const("error", "Error: " + e);
}
v.Literal(n);
v.Literal(" + ");
v.K("y", "add", this);
}

public void Show(IInput v)
{
v.Text("x", "", "");
}

public K Apply(NameValueCollection args)
{
try
{
return new Adder(this.n + int.Parse(args["x"]));
}
catch
{
this.e = "Invalid number specified.";
return this;
}
}
}
The library also provides a compact object serializer. HelloWorld serializes to 48 bytes. Adding some simple fields barely increases the size at all. You probably won't be entering any of these URLs by hand of course. There are a few more optimizations that can be made to the serializer as well. CrystalTech hosts ASP.NET in a medium trust environment, so the library also works for shared hosts. Some contortions were necessary, and fully general object serialization is not yet available (for instance, serializing delegates will fail).

By default, the library assumes all continuation objects can be migrated to clients. This encourages more scalable program structures. If some object needs to remain server-side, simply implement the ILocal interface. There are no operations, but the interface marks the class as non-mobile. The default behaviour in this case is to generate a random 64-bit token, and migrate this token instead. When the token migrates back to the server, it re-connects to the original object. If the server restarts, this state is lost, but a state server as found in ASP.NET can be built which will allow the state to survive restarts and be shared between machines.

Schema upgrade can still pose a problem unfortunately, and unlike with server-side state where the continuations are stored centrally, you can't use a tool to upgrade them. Altering method implementations does not pose an upgrade problem. Adding and removing fields is problematic however.

Fortunately, applications using the library are already structured for easy upgrade and permit a configurable policy for deprecation. Basically, don't touch existing classes, and only create new classes. Replace the use of old classes in the program with the new classes, then whenever you judge it appropriate, remove the old class entirely. On any serialization errors, the library will invoke an application-specific handler which returns a continuation. I think any conceivable upgrade policy is feasible given these primitives.

The current source for the library is available here. I plan to improve the mechanism for displaying continuations in a medium-independent fashion. Ideally, I'd like to be able to create a binding for Windows.Forms, and for JSON requests, so that the same continuation-structured application can be reused unmodified in different environments.

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu