Anticipation in RDP Reduced

Some time ago, I described anticipation in RDP. In that article, I envisioned a behavior intially called `anticipate`, that I eventually shortened to `bpeek`. For discrete-varying signals, it might be specialized to `bpeekL`.

-- observe a specific distance into a signal's future
-- return Nothing when signal is inactive in said future
bpeek :: DT -> B (S p a) (S p (Maybe a))

-- observe all discrete signal values up to signal's future, with
-- its current value then future updates. 
bpeekL :: (Eq a) => DT -> B (S p a) (S p (a,[(T,Maybe a)]))

Unfortunately, it seems this form of anticipation interferes with an equivalence property, which I’ll call ‘merge equivalence’. Merge equivalence is the dual to spatial idempotence.

  • Merge Equivalence: forall foo . (foo +++ foo) >>> bmerge = bmerge >>> foo
  • Spatial Idempotence: forall foo . bdup >>> (foo *** foo) = foo >>> bdup

Sirea only supports merge equivalence if the input signals are already synchronized. In an ideal RDP language, latencies would be built right into the type system and any desired synchronization would therefore be explicit prior to merge, so this caveat would be unnecessary. Sirea supports spatial idempotence more generally, though developers must be careful when using a few unsafe behaviors (which are documented thus). Unfortunately, spatial idempotence is not leveraged for optimizations in Sirea.

(Aside: I use the phrase spatial idempotence to describe replicated concurrent operations. Temporal idempotence would describe behavior of sequential operations, i.e. values `f` for which (f . f) = f. RDP does not promise temporal idempotence of behaviors, though specific behaviors may have that property, and (under the hood) signal updates are temporally idempotent, which is useful for robust communication.)

Merge equivalence is a very valuable equivalence property. It allows developers to reason about conditional expressions, and case-decomposition of a problem domain. Further, merge equivalence is essential for dynamic behaviors. Whenever an evaluation behavior switches from one dynamic behavior to another, we want the transition to be seamless. If `foo` is equivalent to `bar`, then switching from foo to bar should not even be observable (and we can’t cheat by comparing for equivalence; behaviors are opaque).

The contradiction between bpeek and merge equivalence is obvious when presented as an example:

-- may observe periods of inactivity due to switching
(bpeek 0.1 +++ bpeek 0.1) >>> bmerge 

-- switching is no longer observable after merge
bmerge >>> bpeek 0.1

Consequently, I’ve decided to eliminate anticipation as a plain behavior in RDP. This is a blow to RDP’s expressiveness. But I believe this does not greatly undermine the utility of speculative evaluation and anticipation in RDP. Many use-cases for anticipation are isolated to resources anyway:

  • pre-load files (e.g. textures, configurations) that we’ll need in the near future
  • smooth motion of a robotic arm based on anticipated commands
  • anticipate future constraints to improve stability of planners or constraint systems
  • leverage anticipated updates to improve predictions on a stateful world model

Resources can freely leverage anticipated demand without hurting merge equivalence. And developers can leverage anticipation through resources. Some resources, especially world models, may allow direct queries about anticipated future states.

This entry was posted in Reactive Demand Programming, State. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s