«
»

Blending continuity into reactive values

25th January 2008, 03:13 pm

This post continues from “Reactive values from the future” and “Reactive normal form”.

Fran/FRP reactive behaviors could change continuously, while reactive values change only discretely. The Reactive library keeps continuity orthogonal to reactivity. To combine continuity and reactivity, simply compose reactivity with a non-reactive type of functions of time.

One could literally use Reactive (Time -> a), but Reactive also includes a more optimizable version as the module Data.Fun. The denotation of Fun t a is simply t -> a, but it has a constructor (K) for constant-valued functions, which occur frequently.

data Fun t a = K a | Fun (t -> a)

As with the other types in Reactive, most of the operations on Fun values are in the form of instances of standard type classes, specifically Monoid, Functor, Applicative, Monad, and Arrow. As an example of optimization,

instance Functor (Fun t) where
  fmap f (K   a) = K   (f a)
  fmap f (Fun g) = Fun (f.g)

Data.Reactive defines reactive behaviors very simply as a type composition of Reactive and Fun Time:

type Time = Double

type ReactiveB = Reactive :. Fun Time

Wrapping the combination in a type composition (g :. f) gives Functor and Applicative instances for reactive behaviors that combine the corresponding instances for Reactive and Fun Time.

Combining reactive values and non-reactive functions in this way, we can create implementations that mix data-driven (push) and demand-driven (pull) evaluation. The reactive value part is data-driven, resulting in a time function. That time function can then be polled until a new time function is pushed for further polling. As an important optimization, only poll when the time function is really time-varying (made with the Fun constructor). If it’s constant (made with K), then output the value just once and wait until the next push.

I’m not sure whether this elegant composition of orthogonal notions is really a good idea in practice. A benefit is the extra static typing and ability to use of the two types independently. A drawback is that the operations on reactive values have to be rewrapped and perhaps tweaked for convenient use directly on reactive behaviors.

Tags: , , , , , ,  |  Comment (RSS)  |  Trackback

7 Comments

  1. falcon:

    Wow, you are on a roll with these FRP posts :) I am very excited about this and am trying to understand these articles, despite struggling with Haskell’s syntax and concepts. May I suggest that you show some examples of reading some simple streams of numbers off a network (rather than using GUIs as your examples). Perhaps a stock market feed (yes, we have discussed this before ;) )

    25 January 2008, 6:25 pm

  2. Vladimir Shabanov:

    Your new FRP imlpementation is very interesting. I like the idea of using standard type classes as a basis for the library. Also the usage of threads allows one to write more scalable applications. And I find this way of handling imperative event-driven computations very elegant.

    What I don’t understand yet is how synchronous compuations can be done with this model?

    Take the following computation for example (I use CSP-like notation for simplicity):

    A = 1 -> event -> 2
B = 1 -> event -> 3
C = A + B

    In continuation-based polling FRP implementation (data SF a b = SF { sfTF :: Time → a → (SF a b, b) }) A and B will switch simultaneously (C = 2 -> event -> 5). But in your pushing (event-driven) implementation C will become 2+1 after handling A and then 2+3 after handling B.

    I.e. computations in your implementation are not synchronous. With this loss of synchronism we can get too much recalculations if several values depend from one event and there is a value which in turn depends on them. Plus we get some non-determinism in this case (at least with current implementation of mappend on Futures).

    So what’s interesting to me — can the synchronous computations be implemented in Data.Reactive in some simple way?

    Also I’m interested in some examples of using time-dependent Data.Fun reactive values. Are there any of them? (I didn’t find them in Examples.hs)

    28 January 2008, 7:28 am

  3. conal:

    Thanks for the comments & questions, Vladimir. Also, for struggling with formatting without hints. Now I’ve added comment previewing and a remark about using markdown in reader comments.

    While my push implementation looks like it performs unnecessary recomputation, it needn’t, thanks to laziness. A single event occurrence may trigger thunks for multiple values may be generated for an output, but only the last one need get displayed and hence actually evaluated. The usage context must be a bit clever, as is the case in Phooey. (See idler. I haven’t explained this point clearly in the docs, and I don’t really expect anyone to figure it out on their own.

    By the way, even if the push implementation were recomputing unnecessarily, it would probably do so much less than a polling implementation, which recomputes even when no event or irrelevant events occur. Still, I like having no redundant computation at all.

    The above remarks all apply to the implementation. Semantically, erroneous/inconsistent values (e.g., 2+1) do appear but with a time duration of zero, so if you integrate the error function, you’ll get zero total error.

    Many uses of interaction use discrete approximations to continuous behavior, such as considering only finitely many mouse position samples or generating only finitely many display frames. In those cases, the intermediate, inconsistent-state values like 2+1 may well be be as accurate as either of the two consistent-state values (fully before and fully after the event). (Any discrete implementation will have nonzero total error, but at least I won’t add any unnecessary error.)

    I don’t have continuous (time-dependent) examples for Reactive yet. Until I do, you can see my old Fran tutorial to get the feel of what I have in mind.

    28 January 2008, 12:00 pm

  4. Vladimir Shabanov:

    Wow. Lazy evaluation rocks! Am I right that if we set all external sources first (e.g. set mouse & keyboard state at the begining of the frame) and will evaluate the scene after (i.e. render the frame) then we get synchronous evaluation for free thanks to lazyness?

    Or more simply, if we set “event” from the example above first (not evaluating C yet) and then start evaluating C then all intermediate values (2+1) will be just skipped by mappend without calculating?

    And if I understand correctly skipped thunks with lazy values will be created only on top-level value calculation, not at event setting phase (i.e. thunks generation is demand driven, which is very nice for GC). Or there is exists some eager (push) thunk generation in mkEvent internals (some threads are unpaused and MVars+threads are recreated bottom-up)?

    As for examples of continuous values I’m most interested in the implementation of integral function (all other examples are just combinations on top of it). I feel that some switching plus start time keeping is needed here, but I don’t clearly see the possible implementation.

    28 January 2008, 2:32 pm

  5. conal:

    Vladimir:

    I don’t know how to characterize clearly the current Reactive implementation with regard to push vs pull. In a sense, it’s all push, and in another sense, it’s all pull. At each output, there’s a thread that repeatedly pulls individual values out of a reactive value (essentially a stream). Each pull blocks until a new value is ready. In this implementation, reactive values are built compositionally, each having its own thread, blocked most of the time. Each input simply provides a value, resulting in a cascading network of brief unblocking of other threads.

    Thus the sequence of actions is very push-like, while the direction of pointers and code style is more like pull. I think it happens to find a happy combination of push-driven efficiency with the GC-friendliness of pull (because GC favors demand-driven computation).

    Wow. Lazy evaluation rocks! Am I right that if we set all external sources first (e.g. set mouse & keyboard state at the begining of the frame) and will evaluate the scene after (i.e. render the frame) then we get synchronous evaluation for free thanks to lazyness?

    I don’t think it’s quite that simple and automatic. The output end has to be a bit clever so that it doesn’t actually display (and thereby evaluate) every value that arrives. I don’t know how to wrap up that cleverness in a general and transparent way. In Phooey, I used an “idle” event per output. Every output (including intermediate values) gets stuffed into an IORef but not displayed. On idle, the latest one since the previous display is pulled out and displayed. (The IORef is Maybe-valued and is cleared to Nothing after each display.) If there is no new value since the previous display (the usual case), nothing happens. The display step is what actually forces evaluation. When previously stored but undisplayed values get overwritten, as with intermediate values or semantically valid rapidly changing values, the undisplayed values never get evaluated. I guess it’s a bit wasteful to repeatedly check that there’s still no new value to display.

    Or more simply, if we set “event” from the example above first (not evaluating C yet) and then start evaluating C then all intermediate values (2+1) will be just skipped by mappend without calculating?

    Not quite. mappend passes along the intermediate and final values, and the cleverness to ignore them is in the display end.

    Note that the implementation is not smart enough to know that it’s skipping values for different reasons (intermediate vs too frequent to evaluate and display). Maybe it could get smarter.

    And if I understand correctly skipped thunks with lazy values will be created only on top-level value calculation, not at event setting phase (i.e. thunks generation is demand driven, which is very nice for GC). Or there is exists some eager (push) thunk generation in mkEvent internals (some threads are unpaused and MVars+threads are recreated bottom-up)?

    I think I’ve answered this question above, as clearly as I understand.

    As for examples of continuous values I’m most interested in the implementation of integral function (all other examples are just combinations on top of it). I feel that some switching plus start time keeping is needed here, but I don’t clearly see the possible implementation.

    I haven’t thought about how to do integration in this setting, though it’s very important to me as well. Here’s are some thoughts, off the top of my head:

    • Integrate piecewise, i.e., integrate each non-reactive time function, and keep a running sum of the results. As you noted, we have to know when the switch happens.
    • Exploit the Fun representation to integrate exactly in the special case of constant functions. Extend the representation so additional cases can be integrated exactly. Perhaps univariate polynomials.
    • Choose a numeric integration method to use.
    • Adapt the step size to available computation cycles. For instance, give each integral a thread that repeatedly takes a step and then yields. Each time delta would be measured as the wake-up time minus the time of the previous step.
    • I wonder how integration threads would interact with my idle trick. Currently, my threads are all blocked most of the time, but the new integration threads yield while still runnable. Would the new active threads over-compete with the single GUI thread handling all of the outputs?
    29 January 2008, 4:19 pm

  6. Conal Elliott » Blog Archive » Invasion of the composable Mutant-Bots:

    […] a few recent posts, I’ve been writing about a new basis for functional reactive programming (FRP), embodied in […]

    6 February 2008, 9:15 am

  7. Conal Elliott » Blog Archive » Reactive values from the future:

    […] the implementation of events and reactive values via a reactive normal form, and (b) say how to blend temporal continuity with our discrete notion of reactive […]

    7 February 2008, 6:56 pm

Leave a comment