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)
Future type described in a previous post.
Many of the means of constructing events and reactive values are packaged as methods on the standard type classes
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
- The event
fmap f e(also called
f <$> e) occurs with value
eoccurs with value
- The reactive value
rf <*> rxat time
tis equal has value
f x, where
rxhave the values
xrespectively at time
purefunctions (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.
eeis an event-valued event (
ee :: Event (Event a)), then
join eeis an event whose occurrences are all of the occurrences of all of the events in
The main tools for introducing reactivity are
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
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.
scanlfor 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.
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