Archive for January, 2012

Reinversion of control with continuations

January 18, 2012

In my last post I mentioned how it is possible to achieve a form of "reinversion of control" by using (green) threads. Some commenters noted how this is effectively a solved problem, as demonstrated for example by Erlang, as well as the numerous variations on CSP currently gaining a lot of popularity.

I don’t disagree with that, but it’s just not the point of this series of posts. This is about understanding the computational structure of event-driven code, and see how it’s possible to transform it into a less awkward form without introducing concurrency (or at least not in the traditional sense of the term).

Using threads to solve what is essentially a control flow problem is cheating. And you pay in terms of increased complexity, and code which is harder to reason about, since you introduced a whole lot of interleaving opportunities and possible race conditions. Using a non-preemptive concurrency abstraction with manual yield directives (like my Python gist does) will solve that, but then you’d have to think of how to schedule your coroutines, so that is also not a complete solution.

Programmable semicolons

To find an alternative to the multitask-based approach, let’s focus on two particular lines of the last example:

    reply = start_request();
    get_data(reply)

where I added an explicit semicolon at the end of the first line. A semicolon is an important component of an imperative program, even though, syntactically, it is often omitted in languages like Python. It corresponds to the sequencing operator: execute the instruction on the left side, then pass the result to the right side and execute that.

If the instruction on the left side corresponds to an asynchronous operation, we want to alter the meaning of sequencing. Given a sequence of statements of the form

    x = A(); B(x)

we want to interpret that as: call A, then return control back to the main loop; when A is finished, bind its result to x, then run B.

So what we want is to be able to override the sequencing operator: we want programmable semicolons.

The continuation monad

Since it is often really useful to look at the types of functions to understand how exactly they fit together, we’ll leave Python and start focusing on Haskell for our running example.

We can make a very important observation immediately by looking at the type of the callback registration function that our framework offers, and try to interpret it in the context of controlled side effects (i.e. the IO monad). For Qt, it could look something like:

1
    connect :: Object -> String -> (a -> IO ()) -> IO ()

to be used, for example, like this:

1
2
    connect httpReply "finished()" $ \_ -> do
        putStrLn "request finished"

so the first argument is the object, the second is the C++ signature of the signal, and the third is a callback that will be invoked by the framework whenever the specified signal is emitted. Now, we can get rid of all the noise of actually connecting to a signal, and define a type representing just the act of registering a callback.

1
    newtype Event a = Event { on :: (a -> IO ()) -> IO () }

Doesn’t that look familiar? It is exactly the continuation monad transformer applied to the IO monad! The usual monad instance for ContT perfectly captures the semantics we are looking for:

1
2
3
4
5
    instance Monad Event where
      return x = Event $ \k -> k x
      e >>= f = Event $ \k ->
        on e $ \x ->
          on (f x) k

The return function simply calls the callback immediately with the provided value, no actual connection is performed. The bind operator represents our custom semicolon: we connect to the first event, and when that fires, we take the value it yielded, apply it to f, and connect to the resulting event.

Now we can actually translate the Python code of the previous example to Haskell:

1
2
3
4
5
6
7
8
9
10
    ex :: Event ()
    ex = forever $ do
      result <- untilRight . replicate 2 $ do
        reply <- startRequest
        either (return . Left) (liftM Right . getData) reply
      either handleError displayData result

    untilRight :: Monad m => [m (Either a b)] -> m (Either a b)
    untilRight [m] = m
    untilRight (m : ms) = m >>= either (const (untilRight ms)) (return . Right)

Again, this could be cleaned up by adding some error reporting functionality into the monad stack.

Implementing the missing functions in terms of connect is straightforward. For example, startRequest will look something like this:

1
2
3
4
5
    startRequest :: Event (Either String Reply)
    startRequest = Event $ \k -> do
      reply <- AccessManager.get "http://example.net"
      connect reply "finished()" $ \_ -> k (Right reply)
      connect reply "error(QString)" $ \e -> k (Left e)

where I took the liberty of glossing over some irrelevant API details.

How do we run such a monad? Well, the standard runContT does the job:

1
2
    runEvent :: Event () -> IO ()
    runEvent e = on $ \k -> return ()

so

1
    runEvent ex

will run until the first connection, return control to the main loop, resume when an event occurs, and so on.

Conclusion

I love the simplicity and elegance of this approach, but unfortunately, it is far from a complete solution. So far we have only dealt with "one-shot" events, but what happens when an event fires multiple times? Also, as this is still very imperative in nature, can we do better? Is it possible to employ a more functional style, with emphasis on composability?

I’ll leave the (necessarily partial) answers to those questions for a future post.

Advertisements

From event-driven programming to FRP

January 10, 2012

The problem

Most of modern programming is based on events. Event-driven frameworks are the proven and true abstraction to express any kind of asynchronous and interactive behavior, like in GUIs or client-server architectures.

The core idea is inversion of control: the main loop is run by the framework, users only have to register some form of “callbacks”, and the framework will take care of calling them at the appropriate times.

This solves many issues that a straightforward imperative/procedural approach would present, eliminates the need for any kind of polling, and creates all sorts of opportunities for general-purpose optimizations inside the framework, with no impact on the complexity of user code. All of this without introducing any concurrency.

There are drawbacks, however. Event-driven code is hideous to write in most languages, especially those lacking support for first class closures. More importantly, event-driven code is extremely hard to reason about. The very nature of this callback-based approach makes it impossible to use a functional style, and even the simplest of interactions requires some form of mutable state which has to be maintained across callback calls.

As a very simple example, suppose we want to perform a GET request and retrieve some data, handling any HTTP error that might occur. In a generic event-driven frameworkm, we would need to implement a simple state machine whose graph will look somewhat like this:

A simple state machine

Each state (except the initial one) corresponds to a callback. The transitions are determined by the framework. To avoid starting more than one request at a time, we will need to explicitly keep track of the current state.

Now let’s try to make a simple change to our program: suppose we want to retry requests when they fail, but not more than once. Now the state machine becomes more complicated, since we need to add extra nodes for the non-fatal error condition.

A slightly more complicated state machine

In our hypotetical event-driven code, we need to keep track of whether we already encountered an error, check this flag at each callback to perform the right action, and update it appropriately. Moreover, this time the code isn’t even shaped exactly like the state machine, because we reuse the same callback for multiple nodes. To test our code exhaustively, we need to trace every possible path through the graph and reproduce it.

Now assume we want to allow simultaneous requests… you get the idea. The code gets unwieldy pretty fast. Small changes in requirements have devastating consequences in terms of the state graph. In practice, what happens most of the times is that the state graph is kept implicit, which makes the code impossible to test reliably, and consequently impossible to modify.

Towards a solution

A very simple but effective solution can be found by observing that state graphs like those of the previous examples have a very clear operational interpretation in the context of the equivalent synchronous code.

A single forward transition from A to B can be simply modelled as the sequence A;B, i.e. execute A, then execute B. Extra outward transitions from a single node can be mapped to exceptions, while backward arrows can be thought of as looping constructs.

Our second state machine can then be translated to the following pseudopython:

while True:
    for i in xrange(2):
        error = None
        try:
            reply = start_request()
            data = get_data(reply)
            break
        except Exception as e:
            error = get_error(e)
    if error:
        handle_error(error)
    else:
        display_data(data)

This code is straightforward. It could be made cleaner by splitting it up in a couple of extra functions and removing local state, but that’s beside the point. Note how easy it is now to generalize to an arbitrary number of retries.

So the key observation is that we can transform asynchronous code into synchronous-looking code, provided that we attach the correct semantics to sequencing of operations, exceptions and loops.

Now the question becomes: is it possible to do so?

We could turn functions like start_request and get_data into blocking operations that can throw. This will work locally, but it will break asynchronicity, so it’s not an option.

One way to salvage this transformation is to run the code in its own thread. Asynchronous operations will block, but won’t hang the main loop, and the rest of the program will continue execution.

However, we need to be careful with the kind of threads that we use. Since we don’t need (and don’t want!) to run multiple threads simultaneously, but we need to spawn a thread for each asynchronous operation, we have to make sure that the overhead is minimal, context switching is fast, and we’re not paying the cost of scheduling and synchronization.

Here you can find a sketched solution along these lines that I wrote in python. It’s based on the greenlet library, which provides cooperative multithreading.

In the next post I will talk about alternative solutions, as well as how to extend the idea further, and make event-driven code more declarative and less procedural.