Ryan Ingram (ryani) wrote,
Ryan Ingram

Functional Reactive Programming

Recently I was reading Conal Elliott's draft paper Simply Efficient Functional Reactivity.

It's a great paper and his blog has a lot more information and a good introduction to FRP and what makes it interesting; better than I can write. Many implementations of FRP pay a big performance penalty communicating "nothing happened" between parts of the code and then re-evaluating results that can't possibly change. Conal instead flips the problem around and does data-driven evaluation: when events happen, they trigger re-evaluation of all data that depends on those events (which may include other events). Ideally, only data that needs to be recalculated is.

But, one thing I don't like about Conal's implementation is that is uses what he terms "unambiguous races" to compare future events. The idea is to spawn two threads doing different computations, but for which you've proved that eventually both computations must give the same result. Then whichever one finishes first can be taken as the value of the result.

I think that spawning two threads in this way is pretty wasteful, and I was sure there was a better way. I had some ideas revolving around Transactional Memory which I was sure would lead to a way to solve this problem without spawning additional threads. And I was right, sort of!

In Conal's system, the two main types are these:
data Reactive a = Stepper a (Event a)
newtype Event a = Ev (Future (Reactive a))

That is, a "Reactive" object has a current value and an event which gives new values to switch to. And an "Event" is just a reactive object that might not be known until some point in the future. So all of the trickiness comes down to how Future is implemented. In Conal's implementation "improving values" are used; an improving value has a method which allows you to compare a partially unknown "improving value" to a totally known value, as well as a way to wait until the value is completely known. The unambiguous race is used to wait on two values and pick whichever one must come first.

Here's a simplification of my new basis for future values:
data Future a = Fut
  { waitFor :: Time -> STM ()
  , value :: STM (Time, a)

"STM x" is just a computation that uses the Haskell "Transactional Memory" library to return an object of type x. So a Future has two operations: "waitFor" that takes a time and returns nothing, and a value which returns the actual time and result.

The idea is that each future can live in its own universe, and each universe can have its own concept of time. Most of the interesting computation on futures uses "firstFuture" which takes two futures and returns a new future representing the "first" of those two. But how can we combine two futures in this way? Well, STM gives us two amazing tools: "retry" and "orElse". Any STM computation that executes "retry" says "I can't run right now, block until something that I looked at while running changes". And "orElse" lets you take two STM blocks and glue them together, trying to run the first, and if it fails, going back to before it ran at all and using the second instead.

Here's an example of how useful this is: lets say you have two STM computations that may fail or may give a result. Now, you want to write something that does something different in each case of the above. It turns out that you can build that easily out of a primitive I call "maybeSTM".

maybeSTM :: STM a -> STM (Maybe a)

maybeSTM runs its argument, and, if it succeeds with result x, gives you "Just x". If it fails, you get "Nothing", instead of the "retry & hang" behavior the computation would do. It turns out to be easy to implement:

maybeSTM m = justSTM m `orElse` return Nothing
justSTM m = do
  a <- m
  return (Just a)

or, to shrink it down to the code I actually wrote:
maybeSTM m = fmap Just m `orElse` return Nothing

Then you can use this to implement firstFuture:
firstFuture :: Future a -> Future a -> Future a
firstFuture a b = Fut waitab valueab where
  waitab t = do
    waitFor a t
    waitFor b t
  valueab = do
    aReady <- maybeSTM (value a)
    bReady <- maybeSTM (value b)
    case (aReady, bReady) of
      (Nothing, Nothing) -> retry -- neither is ready, no information
      (Just (ta, va), Just (tb, vb)) -> -- both are ready, pick first
        if (ta <= tb)
          then return (ta, va)
          else return (tb, vb)
      (Just (ta, va), Nothing) -> do -- first is ready
        -- wait in b's universe for ta to pass;
        -- start over if something changes in the meantime
        waitFor b ta
        return (ta, va)
      (Nothing, Just (tb, vb)) -> do -- second is ready
        -- wait in a's universe for tb to pass;
        -- start over if something changes in the meantime
        waitFor a tb
        return (tb, vb)

So the result future lives in a universe with a timeline that matches the later of the two timelines it is given; it just waits for both of them. If one of the input futures becomes ready, we just need to wait in the other universe for that time to pass; then we know that the other future couldn't become ready with a time "ahead" of the first.

The nice thing is that there's no multi-threading or nondeterminism involved in determining which future is first; all you have to do is make sure that your "waitFor" implementations actually wait for the correct time, and that you don't lie about the time when your future became valid, and everything else just works and reduces to the same pure interface Conal proposes.

Now, why would you want multiple universes anyways? Well, a really useful universe is the one where you know everything all the time; I call this the "pure" universe. You can use this universe to write a clock event that triggers every 60 ticks, for example:

exactly :: Time -> a -> Future a -- part of the Future library

clock :: Event ()
clock = stepClock 60

stepClock :: Time -> Event ()
stepClock t = Ev (exactly t react) where
  react = Stepper () (stepClock (t+60))

Now, you always know exactly when the next stepClock event is; there's one at time 60, one at time 120, and one at time 180, etc. But this universe is totally disconnected from reality; the "now" value for the pure universe is always at the end of time, where everything is in the past and therefore known.

But lets say you want to do something when the user clicks their mouse, or at time 60, whichever comes first:

mouseClicked :: Event () -- you'd write this as part of your GUI interface
firstEvent :: Event a -> Event a -- removes all occurrences of an event past the first
(<+>) :: Event a -> Event a -> Event a -- merges two event streams using firstFuture

clockOrClick :: Event ()
clockOrClick = firstEvent (clock <+> mouseClicked)

The "mouseClicked" event lives in the universe of your GUI; its time has to match up with the actual time of you clicking the mouse, and so it needs a little more work. But overall the interface makes doing this work pretty painless. I have some more examples; comment if you are interested or have any questions.
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded