Signals in RDP

Reactive Demand Programming (RDP) describes behavior as signal transformers, in continuous time, with side-effects. For example, I might push a control signal to a camera (to influence pan, zoom, tilt, and focus), and the camera will provide a response signal in return (perhaps containing video image or control state). As mentioned in an earlier article, a signal in RDP varies over time in both its value and its activity (present or absent). Naively, one might model a signal as type Signal a = T -> Maybe a, where T is continuous time and the ‘Nothing’ value indicates the signal was absent at the queried time. However, various concerns prevent me from using this as a representation for signals:

  • discrete update: I call a signal discrete if its value is constant between updates and it experiences a finite count of updates in every finite continuous time period. For dynamic behavior, it is important that the choice of which agents to use updates discretely. Similarly, many foreign service or FFI adapters are more feasible if I guarantee discrete updates.
  • constant optimization: for processing signals that may vary continuously over time, I can achieve significant performance advantages if I am able to identify contiguous periods in which the value is constant.
  • garbage collection: while absent, a signal has no influence on an RDP system. If I know that a signal’s absence is a permanent condition, then I can forget it. Developers are thus able to reason about space cost in terms of active links, update rates, and delay rather than program history.
  • algebraic signals: in physical modeling (including games or animations), I can express many signals as piecewise algebraic functions of time. This could allow precise, efficient computation of integrals, derivatives, collisions and intersections (a < b) in continuous time, especially when compared to the brute-force alternatives necessary for opaque functions. (Note: integration can only be performed by an agent, not a behavior. However, it is a useful technique for modeling state.)
  • serialization: RDP is designed to support distributed behaviors. Doing so requires that at least some signals (those crossing the boundary between hosts) be serializable. I can tolerate piece-wise serializability, but for continuous signals or efficient lazy signals, it is necessary to send functions of time.
  • differential: when a signal carries a sufficiently large value, such as the current state of a document or a relational database query, it becomes profitable to describe signal updates in terms of ‘patches’ to the value. MPEG4 vs. MJPEG demonstrates how delivering patches can save an order of magnitude in bandwidth and space costs. The idea here is ‘temporal’ compression: don’t repeat what has been said before – inherently stateful, but this is regenerable state (we can always get a fresh snapshot) so doesn’t cause any resilience issues. In some carefully constrained cases, the benefits are composable – i.e. we can operate directly on patches, without building the full value.

Aside: differential update is orthogonal to asynchronous update, though both techniques help RDP developers work efficiently with processing large structures. I’ll be writing a separate article on RDP’s support for asynchronous behavior, and will clarify the difference there.

The critical revelation is that RDP benefits from having many ‘types’ of signals: discrete, continuous, differential (with many specializations), serializable, algebraic. I do not wish to tackle the above list all at once. So my goal is to model signals in such a way that I do not paint myself into any corners.

The Model

I have developed a preliminary model:

class Signal s where
  type SigTime s -- time type for signal 
  type SigUp s :: * -> * -- update type for this signal
  s_never :: s () -- always absent
  s_invert :: s () -> s () -- flip activity profile
  s_drop :: s a -> s () -- capture activity profile
  s_mask :: s a -> s () -> s a -- mask activity profile
  s_zip :: s a -> s b -> s (a,b) -- signals in parallel
  s_merge :: s a -> s a -> s a -- combine activity (favor right)
  s_update :: s a -> SigUp s a -> s a -- apply update
  s_future :: SigTime s -> s a -> SigUp s a -- update constructor
  s_sample :: s a -> SigTime s -> (Maybe a, s a)
  s_final :: s a -> SigTime s -> Bool -- semi-decision
  s_final _ _ = False
s_always = s_invert s_never

Note that all the constructors use ‘()’ as the data type – developers cannot just offer an arbitrary value. A signal must, in general, control which values it accepts. This is important for both differential and algebraic signals.

Each signal instance provides its own update type. This is useful to allow ad-hoc ‘patching’ models. At least one patch is supported for every signal instance (s_future), since that is the only one RDP really needs. In the implementations I’ve developed so far, type SigUp s a = (SigTime s, s a) and s_future = (,). I am not satisfied that this model of updates would be sufficient in the general case. For example, it makes sense that a patch could ‘fail’, having been tailored to the original value. However, in the context of RDP, there is never a risk of such errors, and patch errors could always be captured in the ‘s’ type if necessary.

A few implementation concerns leak into the signals model with s_sample and s_final:

  • In addition to the signal state, s_sample returns a signal for further sampling in the future. This supports incremental computation, allowing the history to be garbage collected as I operate on it.
  • s_final allows us to conservatively ask whether a given signal has reached its final state (whether that is active or inactive) as of a given instant. The answer to s_final is ‘False’ if I cannot decide, or if deciding would risk divergence. I use s_final to drop dead links in the RDP implementation, since Haskell’s GC would not recognize a dead link.

More modeling of signals:

class SigFun ~> s where
  s_fmap :: (a ~> b) -> (s a -> s b)

class (Signal s) => SigSplit s where
  s_split :: s (Either a b) -> (s a, s b)

class (Signal s) => SigSelect s where
  s_select :: [s a] -> s [a]

class (Signal s, Signal s’) => SigShadow s s’ where
  s_shadow :: s () -> s’ ()
  su_shadow :: SigUp s () -> SigUp s’ ()

class (SigShadow s s’) => SigLift s s’ where
  s_lift :: s a -> s’ a
  su_lift :: SigUp s a -> SigUp s’ a

The use of SigFun is how I map signals. I can constrain the function types, for example, to be algebraic and trigonometric expressions. If developers do provide ‘SigFun (->) s’, they get Functor, Applicative, and Alternative for free. SigShadow and SigLift translate more broadly between signal types. We can lift a discrete signal to a continuous one, and might be able to shadow a continuous signal back into a discrete one.

SigSplit is important for asynchronous choice in the RDP model. SigSelect is used to generate demand monitors. I’m not entirely satisfied with SigSelect (I don’t like the hard-coded choice of lists) but I’ve not found a better option yet – I can get back to this one, I think.

Finally, I have two time-related signal transformers, which correspond quite directly to the use of delay and anticipate in RDP.

type SigDiffTime s = DTime (SigTime s)
class (AffineTime (SigTime s)) => SigDelay s where
  s_delay :: (SigDiffTime s) -> s a -> s a

class (AffineTime (SigTime s)) => SigPeek s where
  s_peek :: (SigDiffTime s) -> s a -> (s a, s ())

SigDelay simply time-shifts the signal by the given difference in time.

SigPeek is a bit more complex, since it actually maintains the activity profile of the input signal. In s_peek dt signal, the second output is active at time T whenever the input signal is active at time T but inactive at time T+dt.

The Implementation

At the moment, I am implementing only two signal types for my Haskell model of RDP – one discrete, the other continuous. These allow the full expressiveness of Haskell functions and values, comparable to Haskell’s many FRP libraries. They will provide a very nice baseline for comparing optimizations.

My initial attempt at this used lazy lists:

type SL t a = (Maybe a, [(t,Maybe a)]) -- DO NOT USE
newtype SigD t a = SigD (SL t a) -- discrete signal
newtype SigC t a = SigC (SL t (Either a (t-> a))) -- continuous signal

The ‘Either’ type in SigC allows me to perform the desired constant-optimization, and I could just check for the empty list to decide ‘s_final’.

I was about 90% finished with implementing the typeclasses for these models when I realized there a severe problem: I had been introducing simple filters, for example to combine adjacent Nothing values in the s_drop function. But, once we start filtering lazy lists, we cannot bound the amount of computation needed to progress. We might even search an infinite, lazy list for a value that simply doesn’t exist. Divergence is a severe risk and RDP’s potential real-time computation benefits are also lost.

I had two options: to eliminate filters – which has its own performance overheads when we start processing the same value repeatedly – or to find a solution that allows filters but constrains how far we look ahead. I chose option two.

My current implementation of signals uses temporal sequences:

data Step t a = Done | Wait (Seq t a) | Next t a (Seq t a)
newtype Seq t a = { step :: t -> Step t a }
type SL t a = (Maybe a, Seq t (Maybe a))
newtype SigD t a = SigD (SL t a)
newtype SigC t a = SigC (SL t (Either a (t -> a)

The code step seq tq will find Next step in seq that occurs at or before time tq. If no such element exists, we either return Done (the sequence has no more elements) or Wait (if there is a next element, it’s after the queried time). The ability to return Wait allows filtering without risk of divergence, i.e. the maximum amount of filtering is commensurate with the time queried. This also puts me back on track for my goals of a near real-time, predictable space implementation of RDP in Haskell.

The lazy lists implementation translated easily into the temporal sequence implementation. After I fully grokked what I had created, it only took a few hours to reach the same 90% implementation I started with.

Update 3 August 2011

On the signal patching issue, I’m thinking that I will provide a few extra functions:

  su_fmap :: Maybe ((a ~> b) -> (SigUp s a > SigUp s b))
  su_split :: Maybe (SigUp s (Either a b) -> (SigUp s a, SigUp s b))
  su_select :: Maybe ([Maybe (SigUp s a)] -> SigUp s [a])

The idea here is that the RDP model can flip between keeping an intermediate signal (cached) vs. straight signal transforms, based on what the underlying signal model supports. I’ll probably add su_delay and su_peek in a similar manner.

Advertisements
This entry was posted in Concurrency, Distributed Programming, Language Design, Reactive Demand Programming, Types. Bookmark the permalink.

2 Responses to Signals in RDP

  1. gasche says:

    There is something a bit fishy going on between partiality of your signals and structural congruences `s_split` and `s_select`. Imagine I use `s_split` to convert a `s (a + b)` to a `(s a, s b)`, then only interest myself in the `a` part of the signal. If I ask the `s a`, I may get an `a`, in which case I know that the original signal returned an `a`, but if I get an error, I don’t know if that means that the original signal returned a `b`, or was disabled. I have to look at the `s b` part simultaneously to know that, and this feels awkward. I would rather get a `s (a + 1)`, ie. `s (Maybe a)` from `s_split`, so that I get precise b-or-failure information directly. This can be encoded in your framework by observing `s_zip sa (s_invert (s_drop sb))`, so I can get both a value and availability information at the same time; but that means monitoring both `sa` and `sb` when I only want `a`-related information, and is probably less efficient for general signals.

    Similarly, I’m unsure what the semantics of `s_select` is wrt. failure. Will the resulting signal basically never fail? We may also wish a more structural conversion between (fixed-length) products of signals and signals of product, but again partiality makes things a bit complicated.

    I’m wondering if your model wouldn’t benefit from having an explicit, possibly separate representation of “permanent signals” that never fail — but that wouldn’t change anything in the `s_split` case.

    • dmbarbour says:

      Good to hear from you, gasche, and I thank you for your questions and concerns.

      In your comment, you use the words ‘error’ and ‘failure’. Inactivity is not error or failure. In RDP, there is no option to model error with inactivity – i.e. succeed or fail, duration of response will equal duration of demand, so developers must fill the response with something. Consequently, developers model errors in-band using `s (success + failure)`.

      In RDP, `s_split` is used to lift a to a conditional decision into the RDP layer. I.e. there is an RDP arrow of the form:`asplit :: (SigSplit s) => a (s (Either b c)) ((s b) :+: (s c))`. The primary uses of `asplit` are to (1) ‘turn off’ parts of the behavior graph that are not necessary, and (2) to process (s a) and (s b) on heterogeneous pipelines that can later be recombined with `amerge` (which uses `s_merge`). This is basically the static `if` expression of RDP, which is at least convenient (though less expressive than dynamic behavior).

      I agree that reducing `s (a+b)` to `s (a+1)` is sometimes useful. I’m sure you could achieve some equivalent of `fmap (either id (const ()))` in a transformation language for a signal that supports a sum-type.

      As you surmise, `s_select` is always active. The signal will hold the value `[]` if all the input signals are inactive. In context of RDP, access to the result of `s_select` is always masked by a query signal (using `s_mask`). The `s_select` feature is used to implement the demand-monitor concept, which I’ll describe in a later article.

      I almost did model ‘permanent signals’ that are always active. I decided against it because:

      • RDP never observes permanent signals, due to duration coupling. Even if the signal source is permanent, observation will always be masked by a query signal.
      • The discipline goal is targeted for composing RDP behaviors, not the RDP implementation and FFI/legacy adapters.
      • Haskell is not very effective at modeling what behaviors a type is not allowed to support (cannot say: “exclude this typeclass”)

      Signals are a stepping stone to describing the full (and more tightly constrained) RDP model. I will eventually finish the appropriate article, but I have a few more stepping stone articles lined up.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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