Comparing FRP to RDP

Functional Reactive Programming (FRP) was pioneered by Conal Elliott and Paul Hudak around 1995 and published as Functional Reactive Animation in 1997. It has developed much since then. There are two common approaches to FRP: signal composition (Signal a), or composition of signal-transformers (Signal a -> Signal b). The latter version is sometimes called ‘arrowized’ FRP. A Signal is a time-varying value, but there is a lot of tension among developers between the choice of continuous time vs. discrete time. Naively, Signal might be: type Signal a = T -> a. It is common for ‘events’ – instantaneous behaviors – to be modeled specially, for mouse clicks, collisions, et cetera.

FRP semantics, at least as originally designed, are purely functional. There are no side-effects for computing a signal at a given point in time, and you can recompute the program and get the same results if you keep a record of the inputs. Developers may hook signals to real-time input sources (such as a mouse position or button state); one doesn’t compute a signal for real-time T until that instant has passed. FRP compositions are generally stateful; that is, a signal’s value at time T may have a dependency on its value at time T-dT. This makes FRP a general computation model, but causes a lot of headaches with regards to space leaks and modeling the ‘infinite histories’ of a signal. Output from an FRP program is achieved by mapping the output state or event stream onto a machine, typically via monadic interpreter.

Reactive Demand Programming (RDP) was invented by me (David Barbour) around April 2010 and has developed over the last year. RDP is effectively my vision of how FRP could be scaled to work with open, modular, distributed systems. It tackles issues of resource management, resource integration, system discovery, plugin extensibility, coordination, synchronization, security, scalability, consistency among distributed observers, resilience to network disruption, and partitioning tolerance. To achieve these properties, RDP allows some carefully constrained side-effects, and is more conservative than FRP about introducing state. It is also ‘eventless’.

In RDP, access to an external resource is represented as a an RDP behavior – a signal transformer with constrained effects. For example, access to a video-camera might be modeled as Signal Control ~> Signal VideoBuffer. Here, the Control signal might provide arguments such as pan, tilt, zoom, IR filter, and the output would be the camera’s video feed.

The input signal is called demand, and the output is called response, though the substance (signals) is the same. Sensors, actuators, foreign services, resources, and other ‘external’ systems are generally called agents. RDP behaviors will compose these agent capabilities in rich, ad-hoc manners based on an arrows model:

• Sequential composition (f >>> g) – this would feed output signal from f as input to g.
• Parallel composition (dup >>> f *** g) – this would copy a signal and send it to be processed synchronously by f and g.
• Choice composition (split >>> f +++ g) – this would take an ‘Either a b’ signal and use f for a-values and g for b-values. More powerful dynamic behaviors are also feasible.

And there is also effectful composition – two subsystems can communicate through shared state or demand monitor, if they have the capability.

Constraints on Demand-effects

• duration coupling: duration of response is equal to duration of demand
• spatial commutativity: the source of a demand (who provided it, which connection it arrives on, etc.) is irrelevant
• spatial idempotence: equivalent demands have no additional effect on an agent’s behavior, and receive equivalent responses
• resilient: RDP behaviors keep no state that they cannot regenerate from scratch. Eventual consistency.
• continuous: control signals describe demand over time; there are no instantaneous events

Activity Cycle and Duration

Unlike FRP signals, RDP signals universally and explicitly model their own activity cycle (start, stop, disruption). This corresponds roughly to Signal a = T->Maybe a with ‘Nothing’ representing an inactive signal.

This feature allows RDP to model ‘open’ systems (i.e. a ‘new’ signal is simply one with an infinite history of inactivity), and also allows RDP to model static conditional control of subsystems (Signal (Either a b) ~> (Signal a) :+: (Signal b)).

Activity cycles are very predictable across composition because RDP enforces a property called duration coupling: duration of active response equals duration of active demand. (These durations will overlap in a stable system.) Duration coupling ensures that any disruption of demand will propagate across behaviors to agents and controlled resources.

This aids greatly with robust resource management and job control: There is no risk of forgetting or losing a ‘terminate’ message. There is no incref/decref or list management hassle when multiple clients share a service. There are no issues of message arrival order.

Spatially Commutative, Spatially Idempotent

At any given instant, an agent is generally able to observe the set of active demands upon it, and provide a response for each distinct demand. However, ordering of demands and duplicates must not affect agent behavior. This describes two properties: spatial idempotence and spatial commutativity.

These properties make RDP very declarative. For example, if I have three behaviors of the form F(X), F(Y), F(Z), then I know I can rearrange them in code (so long as they still occur at the same time). If I can prove that X=Y, I can eliminate one of the two. And sometimes it is easier to refactor code by duplicating some expressions and letting the optimizer handle it.

Together, these properties also support powerful multi-cast optimizations similar to content distribution networks.

Some protocols, such as voting, require that each demand be unique. This would be achieved by adding, for example, a GUID to the demand value.

RDP is not ‘temporally’ commutative or idempotent. The same demand at a different time can have a different meaning.

Resilient, Stateless Behaviors

FRP expressions can capture history and state via integration or loop with delay.

RDP behaviors are less powerful than FRP in this respect, unable to locally express ‘non-regenerable’ state such as history. There is no loopback or differential-delay behavior that allows a behavior’s past to affect its own future. This isn’t to say RDP behaviors are truly stateless (there is a lot of implicit state in buffers and caches)… but, if that information is ever lost, it can be rebuilt from scratch.

RDP behaviors are, consequently, very resilient: after disruption, the RDP behavior itself (not counting the state it orchestrates) will recover to a condition as though disruption never occurred, and the whole system will be ‘eventually consistent’. Also, RDP supports several idioms that avoid state in common scenarios where other programming models would require it. These idioms help push RDP’ resilience properties as far as they can go. This frees developers to think about the few remaining pieces of state should be modeled in order to achieve desirable properties.

When developers do need state, they can obtain it from the environment.

Eventless Reactivity

Events in FRP are commonly used to describe ‘instantaneous’ behaviors such as mouse clicks and collisions. In RDP, you would represent a button’s state as being in the up or down position for some non-zero duration, and allow observers to keep their own state and make their own conclusions.

Events are rejected from RDP for many reasons: First, mutable state is necessary to compose events, but is something I’m trying to marginalize in RDP’s design. Second, events are neither very resilient to disruption or partitioning; we cannot just keep infinite histories of events for a late-arriving observer, so consistency tends to be a problem in event models. Third, programming errors with events are common and rarely obvious – e.g. forgetting to close a resource, or events arriving out of the tested order due to a new network configuration.

For the roles where developers do need events, I would favor they utilizing a more explicit state model, something similar to tuple spaces or mailboxes where ‘events’ are removed explicitly when they are no longer relevant. This way, the burden of reliable vs. unreliable events, and event ordering, and priority inversions, and so on is more explicitly left to developers.

Declarative

Commutative, idempotent, stateless, set-based effects give RDP a very declarative feel – i.e. developers can easily rearrange or refactor expressions, or even change them in a live system. FRP is pure but relatively stateful. Most local-reasoning benefits we might from ‘purity’ are achievable by the object capability model for security. Both FRP and RDP are highly composable, with high levels of declarative concurrency. But RDP further supports declarative composition and management of external resources (and management of them) whereas FRP requires propagating events to manage external connections and resource state (e.g. powering cameras on and off).

All things considered, I feel that RDP supports a far more declarative programming style than FRP. Since RDP doesn’t need to propagate control events to the outermost (input and output) signals in a behavior, it should also be vastly more scalable.

Delay

Both FRP and RDP allow developers to model delay, and achieve similar benefits from it. In RDP, delays are important for modeling real-time communication latencies and computation overheads. By modeling and stabilizing delays logically, we gain a high level of control over them. Further, if we model delays ‘conservatively’, then we don’t need to worry about straggling updates and can achieve both consistency and high levels of wait-free parallelism.

There are cases where large computations (e.g. ray-tracing) can’t be ‘hidden’ in a real-time delay. I believe developers should model those incrementally (explicitly using state) instead. Doing so is better for job control and partial results, anyway.

Anticipation

In FRP, peeking into the future is difficult because real-time data might not be fully available until a given instant is reached, and signals are treated as immutable values – i.e. to peek into the future, you must generally wait for it.

RDP benefits from its ‘open system’ implementation: signals are never known up front, so we must process them as a series of incremental updates. We can peek at the likely future of a signal, accepting that it may change further via reactive updates. We cannot look far into the future, but even looking just a little bit into the future can help us detect and classify events in real-time (such as a transition from button-up to button-down), compute ‘derivatives’, smooth and interpolate animations and robotic motion, coordinate plans to achieve a desired outcome, even keep ‘buffered’ state (noting that buffers carry information about the future, not the past). Anticipation is a very powerful tool, and fulfills many roles that would otherwise be achieved statefully. Anticipation can greatly augment use of state when we have it; for example, future predictions about state of a ‘world-model’ will tend to propagate to agents that are unaware of the world model.

Use of ‘delay’ can guarantee the quality of our anticipation buffer. For example, we can delay 30 milliseconds, then anticipate 30 milliseconds.

Ad-hoc Coordination

One of the major problems in RDP’s target domain is ad-hoc coordination and cooperation of independently developed software systems and agents. ‘Anticipation’ serves us very well in this role. Behaviors that peek into the future can attempt to influence it, by changing their own demand-effects in the present. Hopefully, the future will stabilize on an acceptable fixpoint rather diverge. (The stability problem is domain-specific, so is left to developers.)

In a sense, we can treat agents and RDP behaviors as providing a secure, distributed constraint model. Concurrent demands rarely conflict – i.e. if Alice and Bob each demand some widgets be added to a display, we can usually accommodate both demands. (Concurrent constraint programming was another major influence on RDP’s design.) Anticipation allows us to effectively resolve constraints in both time and space.

FRP doesn’t effectively support coordination of open systems.

What about Conflict?

One issue developers in an open system face is how to handle conflicting commands or demands. For example, Alice is demanding that the camera pan left, and Bob is demanding the same camera pan right.

Recognition and resolution of conflict is system specific and not directly supported by RDP. I have developed a small library of patterns, though. Bob and Alice could each have different ‘priorities’ securely added to their demand via intermediate capability. Or there could be a side-channel to tell Alice and Bob why their behavior is conflicting, so they can more effectively cooperate. We could favor inertia, keep doing whatever we’re already doing.

However, RDP does help a lot: confer existing models with fire-and-forget effects and stateful concurrency control (mutexes or transactions) make anything other than a last/first update wins policy rather difficult to achieve. RDP supports continuous, declarative, resilient, and predictable conflict resolutions since it is always resolving conflict from first principles (the set of active demands, current state). The ability to ‘anticipate’ can further augment conflict management, since if we can ‘anticipate’ a conflict, we can potentially act to prevent it before it happens. An ounce of conflict prevention might be worth a pound of conflict resolution.

FRP doesn’t effectively support conflict management in open systems.

Overall

1. FRP is purely functional. RDP allows carefully constrained side-effects (and tames them with object capability security principles).
2. FRP expressions keep state internally (integral, loop with delay). RDP behaviors allow access to ‘external’ state, but RDP behaviors cannot keep non-regenerable state internally.
3. In FRP, Signal () -> Signal () is useless. In RDP, Signal () ~> Signal () can describe a behavior of arbitrary complexity that, while active, may orchestrate many resources and systems.
4. FRP traditionally supports events. RDP rejects them.
5. In FRP, causal relationships introduce state. In RDP, we peek into the future to reduce need for state.
6. RDP provides effective and scalable support for open systems, where FRP requires obtuse adapters and lugging around an ever growing blob of control state and events.

[Edit: 2011 June 21 – reorganization and clarifications]
[Edit: 2011 August 26 – forward references to recent work, organization]