Functional Reactive Programming

In 1997 Conal Elliot created a Functional Reactive Animation system (Fran) and defined Functional Reactive Programming. While Fran was used only for animation, the core building blocks (Events and Behavior) outlived Fran and are very relevant for Reactive Programming in general.

Building blocks

FRP defines two reactive data types, Events and Behaviors. Events represent a sequence of discrete timestamped values, for example mouse clicks. They represent all (past and future) occurrences of some event at a specific times. They are discrete: you can count them.

Event α = [(Time, α)]

This notation, directly from the Fran paper, means that Events are generic (in type α) and and represent a collection of pairs of time and value. In other words Event extends Collection<(Time,A)>.

Behaviors, on the contrary, are continuous and time-varying values. For example analog position, velocity or acceleration, the temperature, or time itself, are behaviors. At any given (valid) time a behavior has a value. You can measure velocity, but you can not count a velocity as it may have infinite amount of values over time. Behaviors can be represented as a function from time to a value:

Behavior α = Time → α

Translating this notation to for example Java: Function<Time,A>. Given a time, get a value A.

To get a visual idea of aboves definitions, consider this graph representing a (mouse-move) Event and one representing a (sinus) Behavior.

Signals

Behaviors are not so practical: in the digital world of computers we need to approximate behaviors and their continous values. We can only measure the values a finite amount of times, bounded by computer clock cycles. When Wan et al. created a FRP for realtime systems (RT-FRP) they needed a way to provide strict limits on the time and space required for computations. They observed the following isomorphism between Events and Behaviors:

Event α ≈ Behavior ( Option α )

This means that at each point in time there is either some event or there is no event. In their system they used signals which represent an optional value at each time. Continuous values, behaviors, when used in the computer are really discrete values or measurements and thus values at every timestep. Events only have values at some timesteps.

Often there is an actual maximum frequency at which the behavior measurements are needed, for at least two reasons:

• the input is received only at the sample speed of the sensors and
• the system can only display the results to the screen at a maximum of the refresh rate of the monitor or a given output rate to other outputs.

Depending on how the behavior is used, this even allows for some optimization: by not firing an event when the sampled value did not change, we can prevent unnecessary recomputations. When further computations count or average the values this can not be done of course, so in most languages this is an explicit operation, often called distinct.

Some restrictions on this isomorphism have to be regarded however, as one can express behaviors that are hard or impossible to convert to deterministic events. Sometimes these difficulties are solved by increasing the sampling rate, like with integrals. Languages like Fran allow for behaviors like integrate which apply mathematical integration to a function. These behaviors can be approximated with sampling rates going close to zero.

Examples of impossibly convertible behaviors are sharp (behavior with some different value at exactly and only time t), Zeno’s paradox (increasing frequency going to infinity), and unpredictable (non-determinism). These examples share the feature that frequency and sampling rate play an important role. This is hard to express semantically, Wan and Hudak describe them as non-terminating or erroring for their real time FRP.

Examples

The original Fran implementation became deprecated. However, other FRP libaries were created based on Fran, so just for fun, let’s look at some examples.

wiggle = sin (pi * time)

wiggle defines a Behavior which fluctuates over time between -1 and 1. If time would be just a constant value we would know how to apply pi * and the sin functions. However, time is a Behavior and Fran exploits implicit lifting of Haskell type classes and the appropriate type class instances to use familiar syntax for the reactive types. Let’s delve deeper.

colorCycle t0 =
  red    `untilB` leftButtonPress t0 *=> \t1 ->
  green  `untilB` leftButtonPress t1 *=> \t1 ->
  colorCycle t2

Events can be used in conjunction with Behaviors as shown in this colorCycle example. Here the leftButtonPress t0 are the mouse clicks starting from time t0. When this event occurs untilB switches from red to whatever the right side of that expression emitted: a new behavior which starts of as green. A next click will recursively switch to a new colorCycle, so the behavior becomes red again. You might wonder what the arrow *=> means. Recall that events are time and value pairs, so Elliot defined:

• +=> as a handler which takes both time and data of the event
• ==> as a handler which takes only the data of the event
• *=> as a handler which takes only time of the event
• -=> as a handler which receives none of the data

These different handlers are available as a convenience to not pollute the code with unused lambda-arguments or directly use expressions needing only those arguments.

Many operators are available, for which I am not going to provide individual examples, but instead here are some important ones here:

Semantics

The semantics of Events and Behaviors are well defined in Elliots paper Push-Pull Functional Reactive Programming. The original definitions and primitives are replaced by common Haskell classes and methods where possible, giving the semantics of the Event and Behavior instances of Functor, Applicative Functor, Monoid and Monad, when they exist.

For both Behavior and Event the Functor instance is trivial: a function is applied each value, leaving the time value intact. The Applicative Functor instances are less trivial. For a function-valued and one or more argument-valued Behaviors the Applicative Functor <*>-function samples functions and arguments at time t. The resulting Behavior consists of the application of those inputs.

instance Applicative Behavior where
  at (pure a)
      = pure a
      = const a
  at (bf <*> bx)
      = at bf <*> at bx
      = λt ⟶ (bf `at` t) (bx `at` t)

For Event the Applicative Functor needs to handle two Event’s which not necessarily have equal (amount of) values of t. Therefore all possible pairs constructed from values of the two Event’s, yielding m + n different time clusters of values, as we need to wait for both time values t₁ and t₂, effectively taking the maximum t.

For Event’s the Monoid and Monad instances are defined by Elliot. The Monoid instance can provide an empty Event (never occurs) and merge multiple Events, in a time-ordered fashion.

The Monad instance is useful when an Event generates Events, for which Elliot uses an astroid collision tracking example, where each spawned astroid generates an Event of collisions. The instance takes care of flattening this event-valued event, taking care that inner events cannot fire before they are created by the outer event.

Continue with Elm