Conal Elliott

I’ve gotten interested lately in revisiting functional reactive programming (FRP). I was never entirely satisfied with the semantics or implementation in my original Fran formulation or in its successors. Over the last year, I’ve enjoyed getting more interface and functionality from standard type classes, and I’ve realized that quite a lot of FRP could be both packaged and implemented by leveraging those classes. This post describes that packaging, and in particular shows how the Monad interface makes some operations very easy to define. I suspect that monadic functional reactivity is a very powerful structuring tool with lovely applications.

At ICFP 07, I had a conversation with Mike Sperber about FRP and about his FRP-based Lula system for stage lighting. Mike used blocking threads in Lula, which I had never considered for FRP. While playing with the idea, I realized that I could give a very elegant and efficient solution to caching, unlike my previous FRP implementations, including the recent DataDriven library. From there, I stumbled on the idea of reactive normal form and separating out an aspect of reactivity into the notion of future values. A third new (to me) idea is to factor out continuity from reactivity, so that reactive behaviors arise by composing orthogonal notions of reactive values and non-reactive functions of continuous time.

Two previous posts presented future values, first describing interface and semantics and then a multi-threaded implementation. This post builds a simple foundation for FRP on top of future values, as part of a library Reactive.

Functional events and reactive values

A functional event is (semantically) a stream of time-associated values, ordered with respect to time. For example, the stream of keystrokes you’ll type. While many systems have a primitive notion of events, functional events are compositional, i.e., they’re constructed by applying operations to one or more simpler events, e.g., the lower-case version of your keystroke stream, the substream of uppercase keys, or the temporally interleaved stream from your keystrokes and mine (data massaging, filtering, and merging). As usual, compositionality leads to reuse.

A reactive value is a functional notion for a value that changes discretely over time, based on the occurrences of one or more (possibly composite) events. Reactive values provide a a first class encapsulation of the infinite time-line of varying values. As such, they replace many of the uses of imperative programming, particularly concurrent imperative programming, which is notoriously difficult to work with and reason about.

The semantics of a reactive value can be simply a function of time. Since reactive values change discretely (though see below for continuous change), their meanings will be step functions (changing only at a discrete–but possibly infinite–set of domain values). Since a step function is fully defined by an initial value and a discrete set of time-associated values (the changes), we can represent reactive values as a value plus an event that yields more values over time.

data Reactive a = Stepper a (Event a)

How then might we define Event? It is a stream of a first occurrence and some more occurrences, just like Reactive. But the first occurrence and the remainder event are knowable only in the future. Therefore,

newtype Event a = Future (Reactive a)

using the Future type described in a previous post.

Composing reactivity

Standard classes

Many of the means of constructing events and reactive values are packaged as methods on the standard type classes Monoid, Functor, Applicative, and Monad. See the Reactive wiki page and documentation for descriptions of these instances. Here are a few examples:

• The event e `mappend` e' occurs whenever e or e' occurs.
• The event fmap f e (also called f <$> e) occurs with value f x whenever e occurs with value x.
• The reactive value rf <*> rx at time t is equal has value f x, where rf and rx have the values f and x respectively at time t. The (<*>) and pure functions (the methods of Applicative) are the basis of applying an n-ary function to n reactive values, to form a reactive value. Note the implicit and semantically simple concurrency.
• If ee is an event-valued event (ee :: Event (Event a)), then join ee is an event whose occurrences are all of the occurrences of all of the events in ee.

Switching

The main tools for introducing reactivity are stepper and switcher. (These combinators were added to Fran after the original paper, which had only single-shot events and therefore encouraged an explictly recursive programming style.) The stepper function exactly corresponds to the Stepper constructor in our our new representation of Reactive above.

stepper :: a -> Event a -> Reactive a
stepper = Stepper

For a more general reactive combinator, switcher takes an initial reactive value and an event that generates reactive values to switch to.

switcher :: Reactive a -> Event (Reactive a) -> Reactive a

Pleasantly, it is very easy to define this general form of switching in terms of the simpler stepper. To see how this definition works, note that the arguments of switcher are also suitable as arguments to stepper, but the result will be of type Reactive (Reactive a) instead of Reactive a. Fortunately, Reactive is a monad, so join turns reactive-reactive values into reactive values.

r `switcher` er = join (r `stepper` er)

Other building blocks

Many other event and reactive value combinators are described in the Reactive library docs. Here are just a few:

• Cumulative application of functions from a function-valued event.
• A scanl for events and one for values.
• Filtering of Maybe-valued events, and filtering of an event by a boolean reactive value.
• Sampling of a reactive value at each occurrence of an event.

Coming attractions

Future posts will (a) present the implementation of events and reactive values via a reactive normal form, and (b) say how to blend temporal continuity with our discrete notion of reactive values.

I see FRP as being a viable alternative to imperative programming, especially with concurrency. Like the imperative programming model, FRP is about change. Unlike concurrent imperative programming, FRP has formally tractable–even simple–semantics. Future blog posts will give examples of how to reduce dependence on side-effects, widening the pure, and hence semantically tractable and composable, core of programs.

---

Edit 2008-02-07: added missing type parameter in Event definition.

I’ve gotten interested lately in revisiting functional reactive programming (FRP). I was never entirely satisfied with the semantics or implementation in my original Fran formulation or in its successors. Over...