Trimming inputs in functional reactive programming

This post takes a close look at one awkward aspect of classic (non-arrow) FRP for interactive behavior, namely the need to trim (or “age”) old input. Failing to trim results in behavior that is incorrect and grossly inefficient.

Behavior trimming connects directly into the comonad interface mentioned in a few recent posts, and is what got me interested in comonads recently.

In absolute-time FRP, trimming has a purely operational significance. Switching to relative time, trimming is recast as a semantically familiar operation, namely the generalized drop function used in two recent posts.

In the rest of this post, I’ll adopt two abbreviations, for succinctness:

type B = Behavior
type E = Event

Trimming inputs

An awkward aspect of classic FRP has to do with switching phases of behavior. Each phase is a function of some static (momentary) input and some dynamic (time-varying) input, e.g.,

sleep :: B World -> B Cat
eat   :: Appetite   -> B World -> B Cat
prowl :: Friskiness -> B World -> B Cat

wake   :: B World -> E Friskiness
hunger :: B World -> E Appetite

As a first try, our cat prowls upon waking and eats when hungry, taking into account its surrounding world:

cat1 :: B World -> B Cat
cat1 world = sleep world `switcher`
               ((flip prowl world <$> wake   world) `mappend`
                (flip eat   world <$> hunger world))

The (<$>) here, from Control.Applicative, is a synonym for fmap. In this context,

(<$>) :: (a -> B Cat) -> E a -> E (B Cat)

The FRP switcher function switches to new behavior phases as they’re generated by an event, beginning with a given initial behavior:

switcher :: B a -> E (B a) -> B a

And the mappend here merges two events into one, combining their occurrences.

When switching phases, we generally want the new phase to start responding to input exactly where the old phase left off. If we’re not careful, however, the new phase will begin with an old input. I’ve made exactly this mistake in defining cat1 above. Consequently, each new phase will begin by responding to all of the old input and then carry on. This meaning is both unintended and is very expensive (the dreaded “space-time” leak).

This difficulty is not unique to FRP. In functional programming, we have to be careful how we hold onto our inputs, so that they can get accessed and freed incrementally. I don’t think the difficulty arises much in imperative programming, because input (like output) is destructively altered, and programs have access only to the current state.

I’ve done it wrong above, in defining cat. How can I do it right? The solution/hack I came up for Fran was to add a function that trims (“ages”) dynamic input while waiting for event occurrences.

trim :: B b -> E a -> E (a, B b)

trim b e follows b and e in parallel. At each occurrence of e, the remainder of b is paired up with the event data from e.

Now I can define the interactive, multi-phase behavior I intend:

cat2 :: B World -> B Cat
cat2 world = sleep world `switcher`
               ((uncurry prowl <$> trim world (wake   world)) `mappend`
                (uncurry eat   <$> trim world (hunger world)))

The event trim world (wake world) occurs whenever wake world does, and has as event data the cat’s friskiness on waking, plus the remainder of the cat’s world at the occurrence time. The “uncurry prowl <$>” applies prowl to each friskiness and remainder world on waking. Similarly for the other phase.

I think this version defines the behavior I want and that it can run efficiently, assuming that trim e b traverses e and b in parallel (so that laziness doesn’t cause a space-time leak). However, this definition is much trickier than what I’m looking for.

One small improvement is to abstract a trimming pattern:

trimf :: (B i -> E o) -> (B i -> E (o, B i))
trimf ef i = trim i (ef i)

cat3 :: B World -> B Cat
cat3 world = sleep world `switcher`
               ((uncurry prowl <$> trimf wake   world) `mappend`
                (uncurry eat   <$> trimf hunger world))

A comonad comes out of hiding

The trim functions above look a lot like snapshotting of behaviors:

snapshot  :: B b -> E a -> E (a,b)

snapshot_ :: B b -> E a -> E b

Indeed, the meanings of trimming and snapshotting are very alike. They both involving following an event and a behavior in parallel. At each event occurrence, snapshot takes the value of the behavior at the occurrence time, while trim takes the entire remainder from that time on.

Given this similarlity, can one be defined in terms of the other? If we had a function to “extract” the first defined value of a behavior, we could definesnapshot via trim.

b `snapshot` e = fmap (second extract) (b `trim` e)

extract :: B a -> a

We can also define trim via snapshot, if we have a way to get all trimmed versions of a behavior — to “duplicate” a one-level behavior into a two-level behavior:

b `trim` e = duplicate b `snapshot` e

duplicate :: B a -> B (B a)

If you’ve run into comonads, you may recognize extract and duplicate as the operations of Comonad, dual to Monad‘s return and join. It was this definition of trim that got me interested in comonads recently.

In the style of Semantic editor combinators,

snapshot = (result.result.fmap.second) extract trim

or

trim = argument remainders R.snapshot

The extract function is problematic for classic FRP, which uses absolute (global) time. We don’t know with which time to sample the behavior. With relative-time FRP, we’ll only ever sample at (local) time 0.

Relative time

So far, the necessary trimming has strong operational significance: it prevents obsolete reactions and the consequent space-time leaks.

If we switch from absolute time to relative time, then trimming becomes something with familiar semantics, namely drop, as generalized and used in two of my previous posts, Sequences, streams, and segments and Sequences, segments, and signals.

The semantic difference: trimming (absolute time) erases early content in an input; while dropping (relative time) shifts input backward in time, losing the early content in the same way as drop on sequences.

What’s next?

While input trimming can be managed systematically, doing so explicitly is tedious and error prone. A follow-up post will automatically apply the techniques from this post. Hiding and automating the mechanics of trimming allows interactive behavior to be expressed correctly and without distraction.

Another post will relate input trimming to the time transformation of interactive behaviors, as discussed in Why classic FRP does not fit interactive behavior.

3 Comments

  1. Chris King:

    So, the problem with cat1 seems to be more a problem of the semantics of switcher than of any need for extra FRP mechanisms. Your switcher, upon receipt at time T of an event carrying some behavior, starts behaving at time T as that behavior behaved at time 0… hence the space-time leak. OK, so why not define switcher to instead behave at time T as the switched-in behavior behaved at… time T? If someone really wants to look at a behavior’s past behavior, then they must explicitly delay it with some “delay” operator. This method worked well with my OCamlRT system.

  2. conal:

    @Chris:

    Your switcher, upon receipt at time T of an event carrying some behavior, starts behaving at time T as that behavior behaved at time 0 … hence the space-time leak. OK, so why not define switcher to instead behave at time T as the switched-in behavior behaved at … time T?

    The semantics of switcher is exactly what you are suggesting it be, rather than what you thought it is. The tricky part is that world contains information for times earlier than T, so there can be quite a lot of catching up to do.

    Is there a paper that defines the semantics of OCamlRT?

  3. Peter Verswyvelen:

    Some random thoughts:

    What Chris King describes is exactly what most imperative videogames do: everything happens in the “now”, and if you want to keep track of history, you need to use a “history” (aka delay or memory) function explicitly.

    As you mentioned before, imperative systems indeed don’t have the problem of past input being accumulated, since they use mutable variables. Since that gives plenty of side effects, the standard simulation approach is introducing two “world immutable state frames”, one for the current time and for the “earliest” future as determined by the time of the global earliest event occurrence. The two frames are “swapped”, so only one mutable reference cell actually exists. just as in Haskell, when combined parts of these frames don’t change, they can just be copied-by-reference to the next frame. I guess this basically is what Fruit and Yampa tried to mimic with Arrows: don’t make signals/behaviors/events first class values, so nobody can make a strong reference to the head of the stream; in a sense, signal functions only get to see the current “frame”. As you mentioned, systems like Yampa, Fruit and of course surely the imperative ones don’t give the same notational advantage as one usually gets with Haskell. I’m curious how Reactive will evolve to tackle this nasty dilemma.

    Also if I recall correctly in Yampa one had to mark all outputs as strict otherwise lazy evaluation will create a space/time leak again in case the outputs are not observed. This can be problematic when e.g. computing only bounding boxes of deformed geometry for doing visual surface elimination: ideally you don’t want to compute the deformed geometry if the bounding boxes are not visible, but in Yampa, this won’t work I guess since the non-strict deformed geometry would cause a space/time leak…

    Other systems like Autodesk’s Maya combine push/pull by having a push system that marks all intermediate and output values that depend on a changed input “dirty”, so that a “pull” of the dirty outputs only re-evaluates those intermediate values that need updating.

    Regarding push versus pull, I feel that in practice one must perform runtime profiling of a reactive application to figure out where in the dependency graph one needs to push or pull, as you can’t determine statically how often event sources will trigger.

    Other game developers (among I believe Tim Sweeney) have done interesting experiments with the software transactional memory to approach reactive behaviors (often called just AI in games ;): let every behavior “run” on its own thread, using STM variables to read/write the “current” state of other behaviors, retrying when read variables are overwritten by other behaviors during the atomic “update”. Since behaviors in general have few dependencies between them, this approach would scale massively, and when the CPU gets more cores, the system gets faster and faster without having to change the code at all :)

    I wonder what the reactive code using STM in Haskell would like like…

Leave a comment