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]

About these ads
This entry was posted in Concurrency, Language Design, Reactive Demand Programming. Bookmark the permalink.

8 Responses to Comparing FRP to RDP

  1. Ah, so… Is “spatial commutativity” the buzzword I was looking for in our email conversations to describe why I thought Model-View-Controller had an inherent advantage over FRP that academics ignore?

    • dmbarbour says:

      No, ‘spatial commutativity’ is not the buzzword you were looking for. (Also, I doubt any MVC implementations exhibit it.)

      Your concern with FRP regarded the effort of propagating effects, and combining effects, and especially how these efforts scale with system size. Since FRP is pure and closed, a software agent becomes responsible for executing any prescribed effects (“hey, look, this FRP expression says our camera should be turned off, so let’s actually turn it off!”). Any interesting FRP expression will control many resources (camera, network connections, video display, etc.). Unfortunately, bringing these effects together to the aforementioned software agent will involve synchronizing so that the effects can be observed and executed. Worse, we synchronize on all potential effects, not just the actual ones. In a sense, the cost of each effect in FRP is the cost of ALL the effects in FRP… and that’s a terrible scaling property, and you’re right to be concerned about it. (Even Elliott’s Push-Pull FRP has this fallacy.)

      For RDP, I’ve developed a model of asynchronous arrows (I’ll eventually finish that blog post), developed starting from Adam Megacz’s Generalized Arrows. These allow me to separate the responsibilities for ‘behavior composition’ (which doesn’t require synchronization) from ‘signal or value composition’ (which requires I bring multiple values to a location in space-time for observation). Developers must be explicit when they synchronize, which minimizes ‘accidental’ synchronization. Effects are divided among multiple software agents without synchronizing them.

      Such principles could also be applied to FRP, allowing us to avoid its synchronization bottlenecks. The trick is applying it in such a way that the result should still be called ‘functional’ reactive programming.

      Anyhow, if you’re looking for a buzzword, try: “synchronization bottleneck”

      • Methodologically, FRP confuses me the more I gaze into its navel. I do not understand why anyone would want to sell something for animating computer graphics based on a denotational semantics. Maybe my mind has been poisoned by Newman and Sproull’s classical texts from the 1970s on computer graphics, where they explain the trade-off in various rasterization techniques and how different algorithms fair differently, quantitiatively (space/performance cost) and qualitatively (image quality). Maybe my knowledge of denotational-fu is lacking, but I would think you want a semantics that supports *classes of* storage. For example, I don’t see how FRP can guarantee synchronicity down to the hardware level. A mathematical formalism should be able to solve those sorts of timing edge cases. I have never, ever seen FRP researchers address this sort of “Laws of Programming”-style refinement.

        My head spins when I read papers about “Real-time FRP” and “Event-driven FRP.”. These both seem like a total and utter contradiction in terms. When I read those specific papers, I feel like I am completely missed something… especially when they resort to operational semantics to explain how things actually work.

      • dmbarbour says:

        > trade-off in rasterization techniques and how different algorithms fair differently, quantitatively and qualitatively

        You can certainly model different image definitions and rendering targets (raster and otherwise) in FRP or RDP.

        > I don’t see how FRP can guarantee synchronicity down to the hardware level.

        FRP doesn’t guarantee anything by itself. Achieving tight tolerances for temporal precision and accuracy would require cooperation from the compiler, OS, and ultimately the hardware. But, assuming this cooperation, FRP conveniently provides enough information to model and implement highly synchronous behaviors. To achieve this, developers explicitly model a small delay between sensor inputs and actuator outputs. That delay must be wide enough to get time on the CPU, read sensor data, calculate and update actuator commands. Hardware devices, especially those requiring synchronization, will support buffered IO (preferably a timed schedule of operations). So the problem really reduces to ensuring that the actuator buffers hold the correct operations data at least slightly before it becomes necessary. It is useful to model delays somewhat conservatively (e.g. 10 ms when bare minimum is 1 ms). This affords us larger buffers, greater flexibility to accommodate new behaviors without risk to existing behaviors, and mitigates external risks (e.g. from the OS or variable network latencies).

      • With regards to MVC, I noted that imperative data binding is a generalization of the Observer pattern where the Subject is decoupled from the Observer by a Registrar. In this regard, the Registrar is a lot like a “vat” in the E programming language.

        With MVC, this style is possible, although most GUI toolkits purporting to be MVC discourage this style, such as QT with its baroque “Slots and Signals” and .NET with its “Events and Delegates”. Moreover, general developer education is unaware of this style of programming with MVC, and instead tend to hardwire dependencies and create weird cyclic relationships between Observer and Subject without actually thinking through requirements.

  2. dmbarbour says:

    I am developing, in my spare time, a soft real-time Haskell library for RDP, plus a distributed protocol called ‘avon’. I have also hashed out how to achieve a reasonable facsimile of RDP atop HTTP (albeit, without much security and rather poor performance).

    Haskell has helped me formalize the model into type-classes without sacrificing concerns for performance or FFI integration, but I’ll admit my efforts at formalization have me generalizing the model far beyond anything I immediately need. I’m only implementing the model once, supporting two signal models (piecewise discrete and piecewise discrete-or-continuous).

    I do not believe there are any other implementations in development. (RDP is still very young.) If you are interested in building one for your favorite language, I can provide some good advice and blog a bit more about the model and my implementation of it.

  3. I’m thinking through how the eventless approach would suit some use-cases I run into frequently:

    For example, consider a module that is responsible for interpreting gestures, like an operating system’s double-click event detector. It’s desirable that the notion of “double-click” is separated from the actual down-up-down-up continuous signal from the mouse, as this interpretation should be customizable at a single point by the user and be identical across various user space programs.

    The obvious way of modelling this is in terms of converting continuous signals into events, for which clients can listen.

    Would I be right in guessing the RDP way of doing this would be to maintain a continuous set of “the last x seconds of double-clicks” where each double-click is stored, perhaps, with a unique id? Then, clients would be expected to subscribe to this collection as it evolves over time?

    I wouldn’t be happy, I don’t think, with this model because it seems to be erasing the logical events, only to force client code to recover the logical events (by detecting additions to the tuple space and keeping a list of “already serviced” double-clicks etc). If this isn’t the RDP way I’d be interested in hearing how you might model this scenario.

    • dmbarbour says:

      It seems your concern is that the OS and an RDP application might perform some redundant computation in a subtly incompatible manner – i.e. `the OS` (or perhaps the windows `shell`) has its own notion of double-clicks.

      Well, there’s nothing preventing an RDP signals from carrying some information about OS events. You can provide a dedicated signal for OS-provided double-clicks, abstracting the mouse as if it had an additional button, e.g. “left” “right” and “dblclick”. Lacking other information, you could assume dblclicks are each 1ms long.

      For gesture recognition in RDP, in general, using intermediate state as a user model is a reasonable approach. For short gestures (at most a few milliseconds) you could alternatively use delay and anticipation (compare present to future to detect events). But state will generalize to a broader class of user modeling.

      Regarding “the RDP way of doing it”: I have my own ideas about UI. RDP was developed under pressures to model scalable, composable, zoomable, cooperative UIs. I didn’t create RDP just so I can repeat the errors of imperative UI. I would emphasize declarative and RESTful UI idioms, models that persist easily, subject to shared views, undo, and direct manipulation. Activation checkboxes instead of buttons. A hand or bar of active tasks instead of double-clicking icons.

      The notion of ‘double clicks’ strikes me as awkward even in traditional UI.

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