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
switcherleads to time leaks.
switcheris an acceptable loss of expressivity,
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
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
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.
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.
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
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
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 e1 <- accumE 0 e e2 <- accumE "" (((++) . show . ($ 0)) <$> e)
ensures that the events
e2 always accumulate the same portion of the input event
e. (In a sense,
Context is just a glorified
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.
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
Event with an additional type parameter, aptly called
type Behavior era a = Time -> a type Event era a = [(Time,a)]
era as a type-level time interval. By using universal quantification over
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
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
switcher will throw away old history before making an event or behavior available.
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