How to use continuations for servers

This text will describe an asynchronous server that is based on continuations to allow the programmer to write normal sequential control flow code. The full code is available in the Sandbox.

Continuations are a powerfull way to build your own control flow. This can be used to build your own flow statements, but even nicer uses are with webservers. The problem with webservers are, you have a rather stateless application model: the user accesses some function and get's back some HTML code. Then he sits over the result and sends back another form. Of course you can use server-side session data to pass on values. But your applications control flow will highly reflect the event nature of the web application: it will be scattered all over the place.

But there are different ideas on how to do this. One of those ideas uses continuations.

Continuations are just a way to capture what comes after your current statement. You usually have some function named call/cc (in Scheme) or callcc or whatever. This function just calls another function and passes on the current continuation - the point in control flow that will be executed on return from the call/cc call. The called function now can store this continuation somewhere and later call it to transfer back to the original function.

A simple use of continuations could be like this:

def anton(a,b):

  for i in range(a,b):

    def thunk(cc):

      if i % 2 == 0:

        cc('even')

      else:

        cc('odd')

    print i, callcc(thunk)

In this example continuations aren't actually needed - it's just to show how it could look like and work. What happens is that the function anton get's passed in two integers. A loop over a corresponding range is run and for every element the loop prints wether it's even or odd. What is special is that the even/odd stuff isn't done by some normal function, but by using continuations. The callcc(thunk) just calls the thunk function with the current continuation as a parameter. The thunk function uses this current continuation as a callable itself and calls it with the result. This is rather weird, as it looks like there will never be a return. But it does return, as the cc('even') or cc('odd') call will just transfer the value back to the callcc call and provide it as the result for that call.

But we don't have continuations in Python. Luckily we can fake them. At least we can fake them in a limited way that is sufficient to show what to do with them.

To fake continuations we need the Greenlets module. Just fetch the sources and run the usual python setup.py install to install it. It's available for many architectures, most noteably Linux 86, Linux PPC, Mac OS X, Windows and some other unix systems should work.

After you installed the greenlets module, you can start faking continuations. We start by first defining a type for continuations:

class Continuation(object):

  def __init__(self):

    self.greenlet = greenlet.getcurrent()

  def __call__(self, value=None):

    return self.greenlet.switch(value)

This is a rather simple beast: on instantiation we just capture the current greenlet and store it away. On call we will just switch to the captured greenlet. Greenlets are something like micro threads or co-routines. They capture an execution state that is in parallel to the current main execution thread. That's what we use to fake continuations, as those too capture the state of execution.

Now we need to define our callcc function:

def callcc(thunk):

  return greenlet.greenlet(thunk).switch(Continuation())

This is even simpler: we just create a new greenlet from the passed in procedure (named thunk) and pass the current greenlet (created by Continuation()) to it. That's all there is to continuations.

If there were a way to deep copy greenlets, we could even get multi-shot continuations by not invoking the captured greenlet itself but a copy of it. Only the __call__ method of the Continuation class would have to be changed. As it is, we can't copy greenlets and so have to live with single-shot continuations.

Now we need some server framework. I won't write out all code, you can see the full source in the Sandbox.

def server(sessionfunc):

  sessions = {}

  events = [ # here are the events to be returned

             # look in the Sandbox_ for it's content

           ]

  def getevent():

    # returns events one by one, look in the Sandbox_

  def buildIO(ucc):

    return lambda out: callcc(lambda cc: ucc((cc, out)))

  while 1:

    (action, user) = getevent()

    if action == 'exit':

      for (user, session) in sessions.items():

        (ucc, out) = session((action, ''))

        print ">%s: %s" % (user, out)

        ucc()

    elif action = 'login':

      (ucc, out) = callcc(lambda cc:

                        sessionfunc(user, buildIO(cc)))

      sessions[user] = ucc

      print ">%s: %s" % (user, out)

    elif action == 'value':

      print "<%s: %s" % (user, value)

      (ucc, out) = sessions[user]((action, value))

      sessions[user] = ucc

      print ">%s: %s" % (user, out)

This is rather complex. But there are only three situations that are worth looking at:

action == 'exit' denotes the case that there are no more events available. The server passes this event on to the user sessions and gives the user sessions a chance to finish up (the ucc() call). A session continuation will allways get a tuple of a action and a value and bring back a new user continuation and an output string. The output is just printed (in all three cases).
action == 'login' denotes the login of a new user. Here a the session function is called with the current continuation as parameter so that it later on can transfer back to us. Actually it get's passed in a callable that will do all the continuation switching for the programmer.
action == 'value' is the input handling stuff - the value is passed on to the user session and the result is output to the user.

So far this is nothing special - it just sends out forms to the user and receives requests from the user that it passes on to something. That this something is a session function or a session continuation doesn't tell us much - the code behind this could be as complicated as with standard CGI or stuff like this (switching on the action etc.).

So how does the actual user session look like? How is the session handling done, how are informations passed from one request to the next, how do you handle the overall control flow? It's very easy:

def session(user, IO):

  count = 1

  (action, value) = IO('give value %d:' % count)

  while action == 'value':

    count += 1

    (action, value) = IO('got %d, give value %d:' % (value, count)

  if action == 'exit':

    IO('logging out')

  else:

    raise ValueError(action)

Wow. That looks funny: no access to some special session stuff. Not the inverted control flow you usually get with event driven applications. Ok, events are in there, but they are handled in a normal sequential loop. This is handled by the IO function: the IO function is where the application escapes the current control flow, stores the current state of execution away and transfers the output over to the server for sending to the user. Then the session is in a frozen state - nothing happens until the user sends in a new request with the data for the last output. This data will be transfered back into the function - but it won't start from the first line, but will be tranfered to where it last left off.

That way your web application can be written like normal sequential stuff. It's even easier than GUI programming - your code is back to the way you were able to write when using just terminal IO.

Of course real applications won't only consist of one large sequential code block - in reality your code will be a mix of event driven stuff that triggers short sequences of code. But when you need sequential code, it's there - just think about complex application wizards where the user has to run through a set of forms and the flow of those forms depends on the values in them. Something like this is much easier done with sequential control flow than with event driven control flow, especially if you take the statelessness of HTTP into account - you would have to store all pages of the wizard in the users session data, fetch them from there on every request, check values, decide the next point in the control flow, jump there, produce your output. That's much simpler with continuations.

One problem with our faked continuations is the already mentioned single-shotness. Due to this we have a big problem with the back-button in the browser: when the user uses the back button, he will get an older form. But the server state will be the most recent continuation. So his input won't find the right situation in our code.

With multi-shot continuations we would be able to store all intermediate continuations under some page key that is provided with every form and every link from generated pages. That way if the user uses the back-button, an older continuation will be referenced automatically and the input will trigger the right actions in the control flow. That's because multi-shot continuations not only store the point in execution, but store local variables and stack as well. Of course this doesn't take into account other side effects of your code outside your continuation - for example database changes or changes to global variables.

To get multi-shot continuations you would have to switch from standard Python to Stackless - there you get something called tasklets that is very similar to greenlets, only even more powerfull. A speciality of tasklets is that they can be pickled - so you can just pickle the session continuation in the server and store it under it's page key. If the user later on accesses this page key again, you can revive the old continuation and feed the input in.