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`

.

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.

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 `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.

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.

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`

.

Some HTML formatting is allowed in comments.

blog comments powered by Disqus