Why is the Reactive Behavior tutorial taking so long? splitB

Writing the event tutorial brought out the need for several basic functions in Reactive, especially switchE. The behavior tutorial is also bringing with it a slew of necessary functions. The most surprisingly difficult to implement has been splitB.

-- |At every event occurrence, produce a behavior that is a combination of the
-- first and second where it acts like the first up to the event occurrence
-- and then acts like the second.
splitB :: Behavior a ->
          Behavior a ->
          Event b    -> 
          Event (b,Behavior a)

This post describes how this function was implemented. In doing so, we’ll explore internals of the Reactive library and come into contact with the tricky laziness issues that often come up when working with Reactive.

Some of this code will be using (fmap.fmap) style. If that’s unfamiliar, see Peter Verswyvelen’s great mini tutorial on it.

Motivation

The following graph shows a mouse’s x axis position information over a period of time with time 0 representing when the program starts. The y axis represents the x position and the x axis represents time. If you look close, you’ll notice that the graph consists of dots representing samples of the mouse position. The position of the mouse between these samples is unknown by the computer.

In Reactive, we like to think of such things as continuous. In reactive-glut, for example, the mouse’s x position is represented as a continuous line, as in the following graph. At times before the program begins, all the way to , the position is .

Several useful reactive programs involve dynamic collections where a responsive entity comes to life at a certain time. In this case, we would like the entity’s knowledge of the universe to begin only after it’s creation. Aside from modeling the domain well, it sidesteps the possibility of a memory leak.

In the following graph we show what an entity might see of the x mouse position after its creation at time t.

splitB

Our solution to the above issues is a general function called splitB:

-- |At every event occurrence, produce a behavior that is a combination of the
-- first and second where it acts like the first up to the event occurrence
-- and then acts like the second.
splitB :: Behavior a ->
          Behavior a ->
          Event b    -> 
          Event (b,Behavior a)

To do the splitting as mentioned in the mouse example, we can specialize splitB to:

splitBBot :: Behavior a -> Event b -> Event (b, Behavior a)
splitBBot = splitB (pure (error "splitBBot: no data"))

A naive implementation

Lets start with a naive implementation:

splitB :: Behavior a -> Behavior a -> Event b -> Event (b, Behavior a)
splitB bLeft bRight e = fmap f (withTimeE e)
  where
    f (b,ot) = (b, iffB (fmap (ot >=) time) bLeft bRight)
 
iffB :: Behavior Bool -> Behavior a -> Behavior a -> Behavior a
iffB = liftA3 iff
 
iff a b c = if a then b else c

Semantically, the above splitB implementation is correct. Unfortunately, there is a rather large operational issue: whenever the resultant events are evaluated, a traversal of the entire bRight behavior occurs. This CPU and memory leak amounts to a reactive head explosion.

Something Better

What we need is a decent forgetter mechanism. For our first try we’ll reduce the behavior problem into a reactive problem.

unb :: BehaviorG tr tf a -> ReactiveG tr (Fun tf a)
beh :: ReactiveG tr (Fun tf a) -> BehaviorG tr tf a

The above functions convert a behavior into a reactive of time functions and vice-versa. It’s important to note that unb doesn’t have a semantic meaning and wouldn’t be used in normal code. The G’s in these signatures represent “General” in the aspect that the time types (tr and tf) are not fixed to any specific data type. The typical Event and Behavior types have tr and tf set to Double.

Now we can reduce our splitB implementation into an equivalent splitR implementation.

splitB l r e = fmap (second beh) (splitR (unb l) (unb r) e)
 
splitR :: Ord t => ReactiveG t a -> -- left
                   ReactiveG t a -> -- right
                   EventG t b -> -- Split locations
                   EventG t (b, ReactiveG t a) -- results

Lets assume we have a glueR for reactive that chops the right side of its first argument at time t, chops the left side of its second argument at time t, and glues the two pieces together:

glueR :: Ord t => ReactiveG t a ->  -- left
                  ReactiveG t a ->  -- right
                  Time t ->
                  ReactiveG t a -- combination of left and right with time t in the middle

We may now implement splitR:

splitR :: Ord t => ReactiveG t a -> -- left
                   ReactiveG t a -> -- right
                   EventG t b -> -- Split locations
                   EventG t (b, ReactiveG t a) -- results
splitR l r s = fmap snd (scanlE f (r,error "splitR, shouldn't see it") (withTimeGE s))
  where
    f (r,_) (b,t) = (c, (b,c))
      where
        c = glueR l r t

The above implementation uses scanlE to pass along the previous occurrence’s result to serve as a condensed version of the “right” reactive. We’ll deconstruct the Reactive data type to implement glueR in terms of glueE:

glueR :: Ord t => ReactiveG t a ->  ReactiveG t a -> Time t -> ReactiveG t a
glueR _ r (Max MinBound) = r
glueR l r (Max MaxBound) = l
glueR (Stepper al el) (Stepper ar er) t = Stepper al (glueE t el er)

In the above function, we see that a Reactive internally consists of an initial value and an event who’s occurrences represent possible changes.

Implementation of glueE is straightforward:

glueE :: Ord t => Time t -> EventG t a -> EventG t a -> EventG t a
glueE k = (fmap.fmap) (join . fmap (f k) . withTimeGE) eitherE
  where
    f k (e,t) | t < k     = either pure (pure mempty) e
              | otherwise = either (pure mempty) pure e

Thoughts

Our implementation of splitB certainly helps with our naive implementation’s memory and CPU leak. Unfortunately, when an occurrence is evaluated, all the behavior’s steps since the previous occurrence must still be traversed.

Much Better, but Very Tricky

Ideally, we would like each our occurrences to do no traversal when evaluated. If the prior event’s evaluation of the behavior caused concurrent evaluation of the current behavior, before it occurred, we can get this.

Lets look at a different implementation (note the different type signature) of glueE

glueE :: Ord t =>   Time t  ->
                 EventG t a ->  -- left
                 EventG t a ->  -- right
                 (EventG t a,   -- right event
                  EventG t a)   -- combination of left and right
glueE k l r = if k < min lt rt
               then (r,r)
               else if lt < rt
                      then second (mappend (once l)) (glueE k (restE l) r)
                      else first  (mappend (once r)) (glueE k l (restE r))
  where
    lt = firstETime l
    rt = firstETime r
 
-- If there is an occurrence, return the time of the first occurrence,
-- otherwise return +infty
firstETime :: Ord t => EventG t a -> Time t
firstETime = futTime . eFuture

glueE returns a copy of its right event and is completely identical semantically. However, the right event that is returned is now is written in terms of the combination. If one incrementally starts evaluating the returned right event, they are also evaluating the combination event at the same time. Think about it.

We can expand this to our glueR implementation:

glueR :: Ord t => ReactiveG t a ->  -- left
                  ReactiveG t a ->  -- right
                  Time t ->
                  ( ReactiveG t a   -- right
                  , ReactiveG t a ) -- combination of left and right
glueR _ r (Max MinBound) = (r, r)
glueR l r (Max MaxBound) = (r, l)
glueR (Stepper al el) (Stepper ar er) t = (Stepper ar *** Stepper al) (glueE t el er)

Finally, we put this together for our fully optimized splitR

splitR :: Ord t => ReactiveG t a -> -- left
                   ReactiveG t a -> -- right
                   EventG t b -> -- Split locations
                   EventG t (b, ReactiveG t a) -- results
splitR l r s = fmap g (withNextE (fmap snd (scanlE f (l,error "splitR, shouldn't see it") (withTimeGE s))))
  where
    f (cPrev,_) (b,t) = (c, (b,c,cPrev'))
      where
        (cPrev',c) = glueR l cPrev t
    g ((b,c,_), (_,_,c')) = (b,c')

The (fmap snd (scanlE f... part returns a triple (b,c,cPrev) where b is the value at the event splitter, c is the combination of the reactives at that event, and cPrev is the combination of the reactives at the previous event. cPrev is identical to c in the prior occurrence, however it has gone through that special transformation in glueR.

fmap g (withNextE... replaces the c in the triples with the cPrev in the subsequent event. The resulting 2-tuple is the answer.

Conclusion

If one has a widget of type UI -> Geometry3 we can now take a simple UI type:

data UI = UI {
  mousePosition      :: Behavior (Double,Double),
  leftButtonPressed  :: Event (),
  rightButtonPressed :: Event (),
  keyPressed         :: Event Key,
  framePass          :: Event ()
}

And define a function that will allow for new widgets to be created on command without worry of memory leak.

splitUiBot :: Ui -> Event b -> Event (b,Ui)

Hint: We’ll also need the use of a more general version of splitE.

Alright, now I can get back to writing that Behavior tutorial!