Conal Elliott

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.

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