FRP - Dynamic Event Switching

In their seminal paper Functional Reactive Animation, Conal Elliott and Paul Hudak introduced a function

untilB :: Behavior a -> Event (Behavior a) -> Behavior a

that can switch between different behaviors dynamically. In a more recent paper, Conal has renamed the function to switcher. Semantically, it can be defined as

switcher b eb = join (stepper b eb)
    where
    join bb = \time -> (bb time) time
    stepper x ex = \time ->
        last $ x:[x' | (time',x') <- ex, time' < time]

My first design decision for the reactive-banana library was to remove this function from the set of combinators. In this post

I’m going to explain that the original switcher leads to time leaks.
I will argue that removing switcher is an acceptable loss of expressivity,
but nonetheless also summarize two leak-free solutions for dynamic event switching. These are relevant for future versions of reactive-banana, even though I have no immediate plans to incorporate them.

By the way, it’s not just the switcher function that is affected, the same reasoning applies to the join function, i.e. the monad instance for Behavior.

Time leaks

My main reason for removing the switcher function is that it is prone to time leaks. Consider the example

e :: Event Int
e = ... -- some external event

f :: Int -> Behavior Int
f v  = accumB v ((+1) <$ e)

bbad :: Behavior Int
bbad = switcher (const 0) $ fmap (\v -> f v) e

The behavior bbad is a series of behaviors f v whose starting value v depends on the event e. However, these behaviors also accumulate the event e, which means that they depend on the history of the event e. But since the behaviors are generated dynamically, we can’t update them in advance, we have to store the history of the event e to be able to replay it on demand.

In general, any situation where we have to store the whole history of an event is called a time leak. Of course, an efficient implementation would never need to to do that; only the values at the immediately previous moment should matter. I am convinced that this should be a basic requirement on every FRP implementation.

Living without dynamic event switching

To avoid the time leak problem, I simply decided to not implement dynamic event switching in reactive-banana. But what do we lose in terms of expressivity?

It turns out that it’s actually not so bad; many cases that seem to require dynamic event switching can actually be described in terms of the Applicative instance and the apply function. The point is that one can often determine a static set of behaviors in advance and then switch between them. Here an example:

eswitch :: Event (a -> a -> a)

behavior1or2 =
    stepper (curry snd) eswitch <*> b1 <*> b2

Compare this to an implementation in terms of dynamic event switching

behavior1or2 =
    switcher b2 ((\f -> f b1 b2) <$> eswitch)

Of course, this doesn’t work for dynamic collections of behaviors. However, you can always consider a time-varying collection Behavior [a] instead of a collection of time-varying values [Behavior a]. That’s what I currently do in my BlackBoard program which stores a collection of slides.

Solution 1: Context dependence

I now want to summarize two approaches to dynamic event switching that avoid time leaks.

A first idea is to naively ignore the history of the event e and only accumulate from the time that the behavior is “created”. But this opens another can of worms, because any expression like accumB v ((+1) <$ e) is now context-dependent. In other words, it now denotes different behaviors depending on how much of the history of the event e is thrown away. For instance, the expression f 5 in

bbad2 = (+) <$> f 5 <*> bbad

denotes a different behavior than the expression f 5 that will occur inside bbad.

You can make sense of this phenomenon by declaring that f 5 actually denotes a behavior generator, i.e. that it can “generate” many different behaviors at different starting times. However, the main problem is that we still need a way to denote behaviors that are context-independent. Naively turning everything into a generator does not work.

Nonetheless, Gergely Patai has managed to create a solution along these lines. The key point is that the context is made explicit in the type system, via a monad Context (named StreamGen in his paper). The type of accumE will be

accumE :: a -> Event (a -> a) -> Context (Event a)

You can think of Context as being the reader monad

type Context a = Time -> a

The idea is that if you have a value x :: Context (Behavior a) and a time t :: Time, then the value x t denotes the behavior that “starts at time t”. For example, the behavior accumE 0 e t only accumulates occurrences of the event e that happen after t. (This is what avoids time leaks.)

The monad structure of Context allows you to enforce the same context. For instance, the do notation

do
    e1 <- accumE 0 e
    e2 <- accumE "" (((++) . show . ($ 0)) <$> e)

ensures that the events e1 and e2 always accumulate the same portion of the input event e. (In a sense, Context is just a glorified let statement.)

The type of the switcher function now becomes

switcher :: Behavior a -> Event (Context (Behavior a)) -> Behavior a

In other words, the event returns a context-dependent behavior. The point is that it is now impossible to generate a new behavior that depends on previous history: either the behavior depends on history, then it was already part of the network, or the behavior is newly generated with accumE, then it doesn’t depend on any history.

Solution 2: Parametricity

There is another solution, first described by Wolfgang Jeltsch.

Again, the idea is that the type of switcher should be changed so that it becomes impossible to access old history. This time, however, we don’t want to change the type of accumE. How to achieve that?

Consider the code

b1 = accumE 0 e
b2 = switcher (pure 0) (expression)

In order to avoid time leaks, we have to make sure that the variable b1 cannot be used inside the expression, we have to restrict its scope. This seems neigh impossible, but there is a precedent for that: the ST monad.

The idea is to augment the types Behavior and Event with an additional type parameter, aptly called era:

type Behavior era a = Time -> a
type Event era a    = [(Time,a)]

Think of era as a type-level time interval. By using universal quantification over era

switcher :: Behavior era a
         -> Event era ( ∀era'. Behavior era' a )
         -> Behavior era a

we can ensure that the behavior b1 from above cannot be used inside the second argument of switcher.

Unfortunately, this version of switcher is pretty useless, because now we can’t bring anything into scope. The solution is to give switcher the following type:

switcher :: Behavior era a
         -> Event era
              (∀era'. Behavior era' a -> ... -> Behavior era' a)
         -> Behavior era a  -> ... -> Behavior era a

This is to be understood in the sense that for each number of additional arguments, there exists a switcher function with this type. The idea is that switcher function itself brings variables into scope: if you want to use a variable inside the second argument, you first have to pass it through switcher, like this

b1 = accumE 0 e
b2 = switcher (pure 0) (\b1' -> expression) b1

In particular, switcher will throw away old history before making an event or behavior available.

Conclusion

Alright, I hope this survey was useful for setting the stage on time leaks and dynamic event switching.

Concerning reactive-banana, I don’t plan to include dynamic event switching in the immediate future. At the moment, I’m more interested in new abstractions for GUI programming. In particular, I’m thinking about introducing a third data type, a hybrid between Behavior and Event.