FRP — API redesign for reactive-banana 1.0

After having released version 0.9 of my reactive-banana library, I now want to discuss the significant API changes that I have planned for the next release of the library, version number 1.0. These changes will not be backward compatible.

Since its early iterations (version 0.2), the goal of reactive-banana has been to provide an efficient push-based implementation of functional reactive programming (FRP) that uses (a variation of) the continuous-time semantics as pioneered by Conal Elliott and Paul Hudak. Don’t worry, this will stay that way. The planned API changes may be radical, but they are not meant to change the direction of the library.

I intend to make two major changes:

The API for dynamic event switching will be changed to use a monadic approach, and will become more similar to that of the sodium FRP library. Feedback that I have received indicates that the current approach using phantom types is just too unwieldy.
The type Event a will be changed to only allow a single event occurrence per moment, rather than multiple simultaneous occurrences. In other words, the types in the module Reactive.Banana.Experimental.Calm will become the new default.

These changes are not entirely cast in stone yet, they are still open for discussion. If you have an opinion on these matters, please do not hesitate to write a comment here, send me an email or to join the discussion on github on the monadic API!

The new API is not without precedent: I have already implemented a similar design in my threepenny-gui library. It works pretty well there and nobody complained, so I have good reason to believe that everything will be fine.

Still, for completeness, I want to summarize the rationale for these changes in the following sections.

Dynamic Event Switching

One major impediment for early implementations of FRP was the problem of so-called time leaks. The key insight to solving this problem was to realize that the problem was inherent to the FRP API itself and can only be solved by restricting certain types. The first solution with first-class events (i.e. not arrowized FRP) that I know is from an article by Gergeley Patai [pdf].

In particular, the essential insight is that any FRP API which includes the functions

accumB  :: a -> Event (a -> a) -> Behavior a
switchB :: Behavior a -> Event (Behavior a) -> Behavior a

with exactly these types is always leaky. The first combinator accumulates a value similar to scanl, whereas the second combinator switches between different behaviors – that’s why it’s called “dynamic event switching”. A more detailed explanation of the switchB combinator can be found in a previous blog post.

One solution the problem is to put the result of accumB into a monad which indicates that the result of the accumulation depends on the “starting time” of the event. The combinators now have the types

accumB  :: a -> Event (a -> a) -> Moment (Behavior a)
switchB :: Behavior a -> Event (Behavior a) -> Behavior a

This was the aforementioned proposal by Gergely and has been implemented for some time in the sodium FRP library.

A second solution, which was inspired by an article by Wolfgang Jeltsch [pdf], is to introduce a phantom type to keep track of the starting time. This idea can be expanded to be equally expressive as the monadic approach. The combinators become

accumB  :: a -> Event t (a -> a) -> Behavior t a
switchB :: Behavior t a
        -> Event t (forall s. Moment s (Behavior s a)
        -> Behavior t a

Note that the accumB combinator keeps its simple, non-monadic form, but the type of switchB now uses an impredicative type. Moreover, there is a new type Moment t a, which tags a value of type a with a time t. This is the approach that I had chosen to implement in reactive-banana.

There is also a more recent proposal by Atze van der Ploeg and Koen Claessen [pdf], which dissects the accumB function into other, more primitive combinators and attributes the time leak to one of the parts. But it essentially ends up with a monadic API as well, i.e. the first of the two mentioned alternatives for restricting the API.

When implementing reactive-banana, I intentionally decided to try out the second alternative, simply in order to explore a region of the design space that sodium did not. With the feedback that people have sent me over the years, I feel that now is a good time to assess whether this region is worth staying in or whether it’s better to leave.

The main disadvantage of the phantom type approach is that it relies not just on rank-n types, but also on impredicative polymorphism, for which GHC has only poor support. To make it work, we need to wrap the quantified type in a new data type, like this

newtype AnyMoment f a = AnyMoment (forall t. Moment t (f t a))

Note that we also have to parametrize over a type constructor f, so that we are able to write the type of switchB as

switchB :: forall t a.
    Behavior t a
    -> Event t (AnyMoment Behavior a)
    -> Behavior t a

Unfortunately, wrapping and unwrapping the AnyMoment constructor and getting the “forall”s right can be fairly tricky, rather tedious, outright confusing, or all three of it. As Oliver Charles puts it in an email to me:

Right now you’re required to provide an AnyMoment, which in turn means you have to trim, and then you need a FrameworksMoment, and then an execute, and then you’ve forgotten what you were donig! :-)

Another disadvantage is that the phantom type t “taints” every abstraction that a library user may want to build on top of Event and Behavior. For instance, image a GUI widget were some aspects are modeled by a Behavior. Then, the type of the widget will have to include a phantom parameter t that indicates the time at which the widget was created. Ugh.

On the other hand, the main advantage of the phantom type approach is that the accumB combinator can keep its simple non-monadic type. Library users who don’t care much about higher-order combinators like switchB are not required to learn about the Moment monad. This may be especially useful for beginners.

However, in my experience, when using FRP, even though the first-order API can carry you quite far, at some point you will invariably end up in a situation where the expressivitiy of dynamic event switching is absolutely necessary. For instance, this happens when you want to manage a dynamic collection of widgets, as demonstrated by the BarTab.hs example for the reactive-banana-wx library. The initial advantage for beginners evaporates quickly when faced with managing impredicative polymorphism.

In the end, to fully explore the potential of FRP, I think it is important to make dynamic event switching as painless as possible. That’s why I think that switching to the monadic approach is a good idea.

Simultaneous event occurences

The second change is probably less controversial, but also breaks backward compatibility.

The API includes a combinator for merging two event streams,

union :: Event a -> Event a -> Event a

If we think of Event as a list of values with timestamps, Event a = [(Time,a)], this combinator works like this:

union ((timex,x):xs) ((timey,y):ys)
    | timex <  timey = (timex,x) : union xs ((timey,y):ys)
    | timex >  timey = (timey,y) : union ((timex,x):xs) yss
    | timex == timey = ??

But what happens if the two streams have event occurrences that happen at the same time?

Before answering this question, one might try to argue that simultaneous event occurrences are very unlikely. This is true for external events like mouse movement or key presses, but not true at all for “internal” events, i.e. events derived from other events. For instance, the event e and the event fmap (+1) e certainly have simultaneous occurrences.

In fact, reasoning about the order in which simultaneous occurrences of “internal” events should be processed is one of the key difficulties of programming graphical user interfaces. In response to a timer event, should one first draw the interface and then update the internal state, or should one do it the other way round? The order in which state is updated can be very important, and the goal of FRP should be to highlight this difficulty whenever necessary.

In the old semantics (reactive-banana versions 0.2 to 0.9), using union to merge two event streams with simultaneous occurrences would result in an event stream where some occurrences may happen at the same time. They are still ordered, but carry the same timestamp. In other words, for a stream of events

e :: Event a
e = [(t1,a1), (t2,a2), …]

it was possible that some timestamps coincide, for example t1 == t2. The occurrences are still ordered from left to right, though.

In the new semantics, all event occurrences are required to have different timestamps. In order to ensure this, the union combinator will be removed entirely and substituted by a combinator

unionWith f :: (a -> a -> a) -> Event a -> Event a -> Event a
unionWith f ((timex,x):xs) ((timey,y):ys)
    | timex <  timey = (timex,x)     : union xs ((timey,y):ys)
    | timex >  timey = (timey,y)     : union ((timex,x):xs) yss
    | timex == timey = (timex,f x y) : union xs ys

where the first argument gives an explicit prescription for how simultaneous events are to be merged.

The main advantage of the new semantics is that it simplifies the API. For instance, with the old semantics, we also needed two combinators

collect :: Event a   -> Event [a]
spill   :: Event [a] -> Event a

to collect simultaneous occurrences within an event stream. This is no longer necessary with the new semantics.

Another example is the following: Imagine that we have an input event e :: Event Int whose values are numbers, and we want to create an event that sums all the numbers. In the old semantics with multiple simultaneous events, the event and behavior defined as

bsum :: Behavior Int
esum :: Event Int

esum = accumE  0 ((+) <@> e)
bsum = stepper 0 esum

are different from those defined by

bsum = accumB 0 ((+) <@> e)
esum = (+) <$> bsum <@ e

The reason is that accumE will take into account simultaneous occurrences, but the behavior bsum will not change until after the current moment in time. With the new semantics, both snippets are equal, and accumE can be expressed in terms of accumB.

The main disadvantage of the new semantics is that the programmer has to think more explicitly about the issue of simultaneity when merging event streams. But I have argued above that this is actually a good thing.

In the end, I think that removing simultaneous occurrences in a single event stream and emphasizing the unionWith combinator is a good idea. If required, s/he can always use an explicit list type Event [a] to handle these situations.

(It just occurred to me that maybe a type class instance

instance Monoid a => Monoid (Event a)

could give us the best of both worlds.)

This summarizes my rationale for these major and backward incompatible API changes. As always, I appreciate your comments!

FRP — API redesign for reactive-banana 1.0

Dynamic Event Switching

Simultaneous event occurences

Comments