Wednesday, September 5, 2012

Reactive Demand Programming

David Barbour has created a very promising and exciting paradigm for writing interactive, networked applications: Reactive Demand Programming (RDP).

RDP is very sophisticated and I can't really do it justice here, but its salient points are:
  • An RDP application is a dynamically-changing set of semi-permanent, bidirectional data exchanges, called behaviors. What pipes are to Unix, behaviors are to RDP.
  • A signal is a monodirectional channel carrying a value, and varies discretely over time.
  • A behavior is made up of one or more input signals, called demands, and a single output signal.
  • RDP builds in the notion of anticipation - every signal update comes with the expected duration the new value is valid. This allows low latency through smart scheduling.
  • [Update: See David's corrections in the comments.]
An example for a behavior would be a camera receiving move and zoom commands (or rather demands) with discrete time intervals (e.g. as long as a user moves the camera joystick) from one or more users on input signals, interpolating these commands using some deterministic decision procedure (such as averaging all commands), and outputting camera frames on the output signal, with the anticipation measure telling clients something about the rate at which the camera refreshes, allowing them to smartly perform display reprocessing.

The best way to get started is the README of David's RDP implementation. David has also just posted a progress report on his blog, which contains many articles on RDP.

I think RDP is one of the most exciting developments in interactive application development and is worth checking out.


dmbarbour said...

I'm glad to have your interest, Manuel. As I've done a poor job communicating about RDP, I'll try to clarify a few things:

Rather than "many input signals, one output signal", a behavior may have a distinct output signal for each distinct input signal. Much like a function can have a distinct value for each input. A behavior corresponds closely to a function. RDP behaviors are not pure functions, but far more restricted in side-effects than a typical functional/imperative hybrid. The constraints on effects are such that behaviors can be treated very much like pure functions, e.g. with respect to commuting expressions or eliminating duplicate expressions. One thing you can do with pure functions that you cannot do with RDP behaviors is completely eliminate a behavior just because you drop the output.

The essential property of RDP is enforcing declarative effects while (unlike most logic and concurrent constraint paradigms) also supporting procedural abstraction and encapsulation. This puts RDP at a very sweet spot between logic and procedural. Dynamic behaviors allow RDP an OO-like aspect, staged binding of resources. (Staged is somewhere between early binding and late binding. I like to call it `punctual` binding. :)

Via declarative effects, multiple input signals to a behavior can interact. It is possible, for example, to combine a set of signals into signal of sets - a useful pattern that became the basis for demand monitors.

Signals for RDP don't need to vary discretely. But discrete-varying signals are a helluva lot easier to implement and reason about. Still, I plan to eventually support a limited subset of continuous-varying signals, e.g. via trigonometric polynomials. (Right now, I lean towards modeling continuous signals as a layer above the discrete-varying signals.)

I had not thought of signals as channels before. I guess that may be useful, since there is a tight correspondence in RDP (signal updates are necessarily communicated via some sort of data plumbing).

I agree that anticipation is a significant feature of RDP. It reduces latency and synchronization overheads. I can actually anticipate more than one future value at a time, which (assuming a system that is predictable for a few seconds at a time) can potentially save an order of magnitude in communication and processing costs - i.e. I can tell you about the next ten updates, then correct you if I later realize I was wrong about the seventh update, and thus benefit from reduced communication and batched computations. It's also valuable for chained composition of constraint, planning or prediction systems, and resource acquisition.



Manuel Simoni said...

Could you please explain how a programmer can make a behavior return different independent outputs for different inputs?

dmbarbour said...

An RDP programmer does not need to do anything special to make a behavior return distinct outputs for distinct inputs. Consider two cases:

1) A simple behavior `bfmap (+ 1)` takes the input signal and adds one to produce an output signal. Clearly, this behavior can be used in any number of locations, and every distinct input signal will generate a distinct output signal. (`bfmap` is one of many primitive constructors for behaviors provided by Sirea.)

2) A behavior representing access to a filesystem resource (perhaps a particular directory) may allow a developer to provide an input signal containing a filename, and respond with an an output signal containing that file's contents (which might change over time). Obviously, it is essential that each distinct filename produce the appropriate file contents (which may be distinct), even if there are many concurrent requests.

I wonder if we're speaking past one another. What is it you mean by `many input signals`? I suppose it could refer to a complex signal like (x :&: (y :|: z). But I think this is not the case.

For RDP, it hugely helps to distinguish behaviors from resources. Resources (including sensors, actuators, state, demand monitors, etc.) exist outside of RDP. Some behaviors may provide access to external resources. If you use a behavior that accesses a resource multiple times, you do not replicate the resource; you just end up accessing the same resource many times.

Resources like a filesystem can provide a distinct response to each input because, when setting up the signal connection for the demand, one also sets up a signal connection for the response. Demand and response are tightly coupled in RDP (modulo dead-code optimizations).

If we want to guarantee that every signal has the same response, we can use a unit signal. Since all active unit signals are the same, at least in the short term, it is very easy to reason that all the responses should be the same.

Manuel Simoni said...

"What is it you mean by `many input signals`?"

For example, the inputs from the camera operators' joysticks.

dmbarbour said...

Yes, that is what I understood. Did the prior explanation help?

Taking your camera example in particular: a camera can have more than one behavior associated with it - e.g. one behavior to control the actuation (pan, tilt, zoom) and another behavior to request the video stream.

Obviously, most simple cameras cannot return different video streams to different clients. Well, I suppose one could request variations like down-sampling the resolution or update frequency. But, assuming a simple camera model that only replies with one video signal to all active clients... makes a rather poor example if you want to see a different response for each client!

Even assuming all active clients effectively receive the same video signal from the camera, one must think of this as a duplicated signal - i.e. each client can (via distinct behaviors composed with the video acquisition) manipulate the signal through different post-processing filters and deliver the video to different monitors.

The control signals are a different story. As you mentioned earlier, one option is to `average` the requests to influence the camera. Another option is to respond to some control signals with "unable to comply". Note that the response to the control signal doesn't need to be a video stream.

(Note: "averaging" demands is not preferred in RDP. For idempotence, duplicate demands must not be counted twice. So if you want to average, you must ensure there are no duplicate demands - e.g. by including with each demand a unique URL identifying the client. Similar idioms apply to tallying votes.)