ebopp.de

Functional reactive event handling

26 Jan 2015

Event handling is a fairly complex and sometimes messy aspect of programming. Functional Reactive Programming (FRP) is a paradigm for handling events that promises to get rid of all problems of the classical observer pattern. When I first heard about the concept in a talk by Stephen Blackheath, I was pretty intrigued. It turns out event handling does not have to be as hard as I thought it was.

Sodium (a library implemented by him and collaborators) attempts to provide a cross-language implementation of the concept with a consistent API. I wanted to apply what I had learnt in Rust and thus started to implement FRP primitives myself.

The library resulting from this effort is called Carboxyl and is available on GitHub, crates.io and Rust CI. You can think of it as a port of Sodium to Rust for the most part, although it is not as polished yet. I published it two weeks ago, when it was still in a bit of a rough shape (concurrency issues mostly). By now the essentials work correctly, as far as I can tell. It does lack a couple of convenient functions though, which I am adding one by one. Eventually it may become the Rust implementation of Sodium, but I am not completely sure about that yet.

The documentation has seen some extension in the past, so it should be pretty self-explanatory for people familiar with FRP. This post is intended to be orthogonal to it (may end up in the docs at some point though). I will wrap up, what I have learned so far about the basic concepts behind FRP using the library to illustrate their practical application in Rust. This is mostly to ease the learning curve for people interested in using FRP in their own Rust projects.

The basics

The idea is pretty simple. Reactive programming on its own is essentially like a spreadsheet: you have cells containing values that may change over time in response to changes in other cells. Or, more generally, they change in response to events. An event may, for example, be a mouse click or a key being pressed or released.

FRP now throws in some functional programming to abstract these concepts. You can think of the event handling as a flow graph, where an event at one point has ripple effects on a variety of dependent quantities (like the cells in a spreadsheet).

While the FRP library takes care of managing the propagation of events through that graph, the job of the programmer is to design the flow graph using the primitives provided by the library. Or they can take components from other libraries, since the primitives compose very well.

To make this a bit more concrete: in both Sodium and Carboxyl there are two fundamental types: a stream is a discrete series of events and a cell is a value that changes over time. They have a number of methods to compose them with functions and other streams and cells.

(Sodium used to call these types event and behaviour until very recently. You may come across these terms and others in literature on FRP. I have adopted the new terminology for Carboxyl.)

Creating a stream

To get started we somehow have to feed the library with events. This is where the Sink comes in:

use carboxyl::Sink;
let sink = Sink::new();

Now that we have created a sink, we can start deriving streams from it:

let stream = sink.stream();

This stream will contain all events sent into the sink. So when we say sink.send(4), an event will be passed "downstream". You can observe this event by iterating over the events in a stream like this:

let mut iter = stream.iter();
stream.send(12);
assert_eq!(iter.next(), Some(12));

Note that the iterator will only contain events sent into the stream after its creation, this is why we do not observe the 4. The iterator blocks if there is currently no event that has been sent into the stream.

In subsequent examples, we will assume that some sinks and corresponding streams have been created, with which we can work.

Manipulating streams

There are three primitives that exclusively work on streams: map, filter and merge. The first two will be familiar to you, if you have worked with the iterator adaptors in the Rust standard library.

map creates a stream that takes upstream events, applies a function to them and propagates the result:

let squares = stream.map(|x| x * x);
let mut iter = squares.iter();
sink.send(3);
assert_eq!(squares_iter.next(), Some(9));

filter works on streams of Option<T> and propagates only the Some(…) events with their inner value.

let filtered = stream.filter();
let mut iter = filtered.iter();
sink.send(None); // ignored
sink.send(Some(3)); // converted to 3
assert_eq!(iter.next(), Some(3));

filter differs from the iterator method of the same name. For convenience, there is also a filter_with method that filters based on a predicate.

We can also merge two streams of the same type.

let merged = stream1.merge(&stream2);
let mut iter = merged.iter();
sink1.send(2);
assert_eq!(iter.next(), Some(2));
sink2.send(4);
assert_eq!(iter.next(), Some(4));

With these primitives you can already do quite a bit of event processing.

Holding values in a cell

A stream does not hold on to the events that pass through it. This is were cells come in handy. A cell knows its current value. We can easily create a cell by holding on to the last event of the stream:

let cell = stream.hold(3);

The argument is the initial value of the cell, when the stream has not yet received any event. The current value of the cell can be sampled at any time.

// Initial value
assert_eq!(cell.sample(), 3);
// Send in a new value
sink.send(-6);
assert_eq!(cell.sample(), -6);

Notably you can work with cells much in the same way as normal values by making use of the lift! macro. It effectively lifts a function operating on normal values to a function operating on cells:

let product = lift!(|a, b| a * b, cell_a, cell_b);
assert_eq!(product.sample(), cell_a.sample() * cell_b.sample())

Currently this works only for functions with up to four arguments, which should be enough for most practical purposes. (It can be increased though.)

Snapshot and switch

There are two further primitives operating on cells and streams. You can make discrete snapshots of the value of a cell using a stream. The result is a stream that joins events from the input stream with the value of the cell at the time they were fired.

Consider this example from the documentation:

let snapshot = cell1.snapshot(&stream2);
let mut iter = snapshot.iter();

// Updating its cell does not cause the snapshot stream to fire
sink1.send(4);

// However sending an event down the stream does
sink2.send(3.0);
assert_eq!(iter.next(), Some((4, 3.0)));

Up until now, everything that I have shown you leads to a static flow graph that produces some results that change over time. There is one more primitive we need to cover, that allows you to dynamically change the structure.

This primitive is called switch and it operates on a cell that contains another cell. A useful example to picture what this means is switching channels on a TV (to give credit, this is from the talk mentioned earlier). You can picture the video broadcast by any channel as a cell of images, or in other words a video is an image that changes over time. Let's include some input, say, a stream of button events from a remote control.

Using the primitives discussed before we can create a cell that contains the cell of images corresponding to the last channel switched to. This is done by mapping each button to the image cell associated with its channel and holding the resulting stream in a cell:

// news_channel:  Cell<Image>
// movie_channel: Cell<Image>
// button:        Stream<Button>
let active_channel: Cell<Cell<Image>> =
    button.map(move |b| match b {
            Button::A => news_channel.clone(),
            Button::B => movie_channel.clone(),
        })
        .hold(default_channel);

The switch primitive maps our active channel to the actual video shown on the screen in response to all that zapping:

let screen: Cell<Image> = active_channel.switch();

Setting up the example is a bit lengthy, so this is just an illustrative excerpt from a self-contained example in the docs.

In principle, you should be able to switch between streams, too. I simply have not implemented that yet.

Loops

More often than not mutable program state depends on its previous value. There is no way to directly express that with the functionality I have shown you so far. Essentially, you need to define a cell in terms of itself, which is not possible in Rust. (Lazy functional programming languages apparently do not have a problem with that.)

Therefore we need some workaround. Carboxyl currently provides this feature by providing a special constructor for cells. Let's see how you would implement a cell that counts event occurences in an input stream:

let counter: Cell<i32> = Cell::cyclic(0, |counter|
    counter.snapshot(&stream)
           .map(|(count, _)| count + 1)
);

You provide an initial value and a closure that maps the looped-over cell to a stream. That stream will be held in the cell using the initial value and then fed back into the closure. The closure will "see" the old value of the cell, which only gets updated, once everything else has been processed.

I have to note that I am not entirely happy with the API here yet. It would be nicer to leave out the initial value and provide a closure that would conceptually map the looped-over cell to itself. However, there are some implementation issues here. So consider this as work in progress, when using it.

Final notes

Internally Carboxyl makes heavy use of atomic reference counting, locking and trait objects for its callback mechanism. Thread-safety is currently accomplished by having only one transaction run at the same time using a global lock.

This is far from optimal, but it is a working implementation of FRP. Based on this faster and more concurrent internals could be developed without breaking the API. Software transactional memory appears to be a good way forward to address this issue, thus I may look into this at some point.

Conceptually, functional reactive programming is quite a leap coming from traditional event dispatch mechanisms. It is a very functional concept at its core. Naturally you should try not to use mutable state that is not abstracted in FRP primitives. However, that may not be possible under all circumstances and it is possible to introduce it into a project step by step.

Personally, I do not have a lot of practical experience with it yet, and am looking forward to using FRP for video games. I will most likely write some follow-up posts in the future about game loops, interfacing with I/O, writing functional simulations, etc.

I would love to see a fully functional reactive game framework written in Rust in the future. That likely requires some degree of cooperation, as there are many issues to address. I do not know whether Piston could still head in that direction. But thanks to the modular nature of most Rust libraries there are now plenty of good low-level components. On top of that functional reactive abstractions can be developed.