ebopp.de

Carboxyl 0.1 released

24 May 2015

With this post I would like to announce the release of Carboxyl 0.1 and highlight some of the most recent changes I made to the crate. Carboxyl is a library for functional reactive programming in Rust. In case you are not familiar with it, have a look at the docs.

For the past few months I have been experimenting with its API. By now I feel fairly confident that the current state can be maintained without major breaking changes. This is the reason why I have decided to release the current state of the crate as version 0.1.

Over the last releases I made one very fundamental change and a couple of smaller additions. The fundamental change was, of course, the switch from pure push-based semantics to hybrid push-pull semantics. Furthermore, there was some renaming, slight API changes and a mechanism to allow for in-place state updates using mutable references.

Hybrid push-pull semantics

In an earlier post I mentioned that I had been looking into implementing push-pull FRP, as outlined in Conal Elliott's paper on the topic. Now I did not quite follow the recipe Elliott explains in great detail in that paper, but it definitely served as a great source of inspiration.

Let me begin by explaining the semantic difference between push and pull semantics when dealing with event handling in general.

In a push-based approach, each event directly triggers a chain of computations that need to be performed in order to reflect its occurence. For instance, when a mouse button is pressed on a send button in a mail client, this will eventually lead to sending the mail. Typically this is implemented via some mechanism to register callbacks, which are executed on each event. In other words the event is pushed through a network of callback handlers. This is also how Carboxyl worked internally before the change (version 0.0.9 and earlier).

In contrast, in pull-based event handling an event does not cause any immediate effects. Instead, whenever a consumer needs some concrete data it pulls that data from the source, which could be a stream of events or a function or a composition of these.

Both approaches have their advantages and disadvantages. The push-based approach is commonly used for event handling, as it avoids polling for events all the time. However, it does not work particularly well in the context of values that change continuously in time, e.g. smooth animations, transitions, etc. For this purpose, one typically has to sample the state of a value at a fixed rate.

While the pull-based approach does not really apply to discrete series of events, it works much better in the context of such time-dependent quantities, as it can simply model them as functions of time. Then the consumer can sample at an arbitrary, potentially varying rate. The execution of computations is then driven by demand. When a time-varying quantity is not sampled, it won't be computed at all.

Now, how does all this map to functional reactive programming with Carboxyl?

As you might guess, streams are simply a series of discrete events and thus can be dealt nicely using push-based semantics. Each event directly causes a chain of dependent events and state updates.

This is how streams currently work in Carboxyl:

// Create a sink to push events
let sink = Sink::new();
let stream = sink.stream();

// A blocking iterator over the events in the stream
let mut events = stream.events();

// Push an event and the iterator will receive it
sink.send(3);
assert_eq!(iter.next(), Some(3));

The interesting part are signals. Previously, this was called a Cell in Carboxyl. I deemed this change in terminology necessary, as the standard library contains Cell and RefCell, which slightly confuses matters. Furthermore, I think that signal conveys the semantics better than cell (or behaviour, which is more common in FRP).

Semantically a signal is a time-varying value. In Carboxyl this is represented as a generic type that can be sampled at any time. This can be implemented by a call to some function. The current system time, for instance, can be implemented using some system function. The sampling behaviour of a signal at a given point in time is fully defined by that function.

In practice, you can get a signal like that from a function by using the lift! macro with only one argument:

fn system_time() -> Time { /* ... */ }
let time: Signal<Time> = lift!(system_time);

Note: there is work in progress to provide something like this and other time-related functionality as a separate crate carboxyl_time.

However, there are also signals that change between different behaviours in response to discrete events. If the last event firing in a stream is held as a signal, for example, the signal's behaviour between events can be seen as a constant function that returns the value of the last event. But this constant function changes with each event.

let sink = Sink::new();
let last: Signal<i32> = sink.stream().hold(0);

assert_eq!(last.sample(), 0); // behaves like || 0
sink.send(2);
assert_eq!(last.sample(), 2); // not it behaves like || 2

In summary, the signal can be seen as function that can be sampled at any time, but may change entirely in response to discrete events. Changing the function itself is dealt with by pushing the event that generates the new function, while sampling that function at some time is done by pulling. These two kinds of signals are only special cases of the general type that combines push- and pull-based aspects. They can be easily composed with each other and with streams using lift!, hold, snapshot and switch.

A fundamental difference to Elliott's work is that time is not explicit in Carboxyl. Instead, the ordering of events is ensured by a (somewhat primitive) transaction system.

The downside of not having explicit time is, that streams do not form a monad, as far as I can tell. However, both streams and signals exhibit some algebraic structure as functors, applicatives and monoids. This has been tested to some extent using Quickcheck.

As a side note: initially I tried to follow Elliott's purely functional implementation strategy (which was done in Haskell) but it turns out, that Haskell's implicit laziness does not translate particularly well to a strict language like Rust. So I refactored my previous implementation, a network of callbacks, handlers, RW-locks and mutices, and added some sampling functions.

Efficient in-place updates

Using FRP as an event handling mechanism in a systems language like Rust has a certain cost: every event is dynamically dispatched and you also should not use any mutable state. While the former issue can't be avoided without breaking abstraction and modularity, the latter issue can be addressed.

In issue #62 this has been implemented. The essence is to provide a primitive in-place variant of the Stream::scan method used to accumulate events as a signal considering the signal's previous state.

The interface is fairly similar (leaving out most trait bounds for simplicity):

fn scan<B, F: Fn(B, A) -> B>(&self, initial: B, f: F) -> Signal<B>;
fn scan_mut<B, F: Fn(&mut B, A)>(&self, initial: B, f: F) -> SignalMut<B>;

Instead of mapping the previous state with some update event to the new state, the update function passed to scan_mut operates on a mutable reference to the current state. In contrast to the normal Signal, the new SignalMut type never clones its content, but only allows new signals to be created by working with references to it.

Its API is obviously somewhat less flexible, but generally tries to provide similar functionality to Signal. The most prominent limitation is that you cannot directly sample a SignalMut, as that would require moving the content out. Possibly a future extension to the API could provide a read-only guard that dereferences to the content instead.

This new type is mostly an escape hatch from the purely functional world to allow some effectful performance optimization, as it allows in-place operations avoiding frequent costly cloning of values. It should also improve Carboxyl's compatibility with other libraries, as there are many Rust crates that cannot reasonably expose a purely functional API, e.g. nphysics.

Other changes

Apart from these major changes, there were some minor additions. Most notably it is now possible to switch between streams of streams, which before only worked for signals of signals.

Another addition was coalesce. This stream method allows to reduce multiple event firings occuring within the same transaction into a single event using an (ideally) commutative operator.

Outlook

Now that the core has nice semantics and appears to be reasonably stable, I am going to focus on applying it to reactive 2D and 3D applications. Naturally, new users and their feedback about Carboxyl's current API are always very welcome.

There are some current developments related to Carboxyl that may be of interest: