Peeking into the future with RDP

One aspect of reactive demand programming that sets it apart from other reactive programming models is its support for optimistically working with the predicted future states of signals.

Think about a signal that carries the current time in seconds, that you want to display on screen as a clock. The screen should update close to the full second.

Let's say your clock display uses complicated drawing routines that take a while to display. So if you start drawing at the full second, your drawing will always lag behind the full second.

But why should this be? The clock signal already knows that it will change to the next full second at a particular time in the future, and can communicate this to the display code.

In RDP, we can view a value not as a point, but as an arrow in time, that may point into the future. Consider a mouse: during mouse moves it is often possible to give a good prediction of where the mouse will move in the next instant. With RDP it's possible for the mouse signal to communicate this information to its clients.

Given that the clock display code can peek into the clock signal's future, it can perform intensive processing at leisure before the actual switch to the next full second (e.g. by drawing into an offscreen buffer and copying it to the screen buffer at the full second).

Predictions are often wrong, so clients always need to have a fallback (e.g. throwing away the prepared drawing in the offscreen buffer and drawing from scratch, accepting a laggy display). But the fact that RDP signals can inform clients about future states enables a wider spectrum of behaviors that were previously impossible to achieve.

The worm is the spice

Just had a nice insight regarding systems that deal with reactively updating (potentially large, structured) values such as RDP:

The dynamic output of a process is indistinguishable from a static storage resource (file).

In batch systems like Unix, this symmetry is not so deep: the output stream of a process looks somewhat like a file, but the process can't make any changes to earlier, already emitted portions of the stream. This is unlike a file, which can be edited anywhere.

In a reactive system, a process output is truly indistinguishable from a file. The process may decide to update any part of the emitted value at any time, just like a user editing a storage resource.

Apart from being a nice symmetry in itself, I think this also offers new possibilities for user experience. Processes and files can be used interchangeably in the UI. A file can be viewed as a (rather boring) process, whose output gets edited by the user (similar to data in pi calculus).

RESTful RDP with big values

What if you want to use a big value, like a whole database table or weblog, as a Reactive Demand Programming signal value? This would make it possible to use RDP to orchestrate things like incremental MapReduce pipelines. Here's one weird trick to make it work.

In effect, each RDP signal becomes a RESTful server, speaking an HTTP-like protocol. Clients of a signal remember the ETag of the last version of the signal they've processed, and send it to the server on subsequent requests.

The protocol to retrieve the value of a signal may work like this:

• If a client hasn't seen a previous version of the signal, it sends no ETag. The server replies with the complete value. The value may be split up into multiple pages, using something like an Atom paged feed. (Other non-sequential kinds of splits are possible: for example, tree-like data like a filesystem can be fetched in parallel using hierarchical splits.)
• If a client has seen and processed a previous version of the signal it sends the stored ETag. There are three possibilities:
• The content hasn't changed (i.e. the server's ETag matches the client-sent ETag), so the server replies with a status code that indicates that there is no new content (HTTP's 304 Not Modified).
• The content has changed, so the server replies with a diff of the client's version versus the server's version.
• The content has changed, but the server is unable to provide a diff against the client's version. This can happen for servers that do not keep a complete history, or also if the server determines that it's more efficient to have the client retrieve the whole value again instead of sending a diff. The client has to re-fetch the whole signal value, as if it had seen no previous version of the value.

I haven't worked out all the details, but I think this scheme could be made to work.

A trivial implementation of Reactive Demand Programming

I wrote a trivial implementation of RDP in JavaScript to help me understand how it works.

It's called bucky-rdp (about 200 lines of heavily commented code).

It currently supports Sirea's bconst, bpipe, and bfmap.

Here's an example:

// Create some behaviors for transforming numbers.
var bDouble = rdp.bFMap(function(val) { return val * 2; });
var bMinusOne = rdp.bFMap(function(val) { return val - 1; });

// Create a pipeline behavior of the two behaviors
var myBehavior = rdp.bPipe(bDouble, bMinusOne);

// Apply an inactive input signal to the pipeline behavior
var sigIn = rdp.makeSignal();
var sigOut = rdp.apply(myBehavior, sigIn);

// Change the input signal value and watch the output signal change
sigIn.setValue(2);
console.log(sigOut.getValue()); // Prints 3
sigIn.setValue(4);
console.log(sigOut.getValue()); // Prints 7
sigIn.deactivate();

(This post refers to v1.0.1)

Grokking Reactive Demand Programming

TL;DR: RDP is an exciting declarative model of how computational processes (behaviors) are connected by continuously updating values (signals) to effect changes on storage and external state (resources).

I've come a bit closer to understanding David Barbour's Reactive Demand Programming model, and this has confirmed my previous hunch that RDP is one of the most interesting systems designs since Unix. If you're looking for new, better ways to structure dynamic, interactive applications, I strongly recommend checking out RDP.

I would call RDP an orchestration model, since it cares about how you connect and assemble components of your app, and gives you a lot of freedom in what these components do and how they interact. This also fits with David's description of an RDP application as "a complex symphony of signals and declarative effects orchestrated in space and time".

In terms of Unix, RDP's behaviors correspond to processes, signals correspond to pipes, and resources correspond to storage and other external, stateful things.

Signals (pipes, channels)

A signal continuously delivers a potentially changing value. The current implementation always updates the complete value, but RDP doesn't rule out diff/patch-based signal updates, to model e.g. a large set as a signal value.

In addition to these simple signals carrying a single value, there are also compound signals, such as (x :&: y) which represents the concurrent, asynchronous product of signals x and y, IOW a signal representing two independently updating signals. Analogously, (x :|: y) represents a disjoint sum of signals, with either x or y being active at any given point in time.

A signal is either active (carrying a value), or inactive (disrupted). Application-level errors have to be modelled as part of the value, there is no "stderr".

Behaviors (processes, computation)

A behavior won't do anything until you place a demand on it. You place a demand on a behavior by applying an input signal (the demand) to it; the behavior will produce an output signal for the duration of this application.

Multiple demands can be placed on a behavior at the same time. The behavior can either reply to each input signal with a different output signal, or with the same output signal, depending on the purpose of the behavior. For example, a "calculator" behavior may take N input signals with expressions like "1 + 2" and "3 * 5" and deliver a distinct output for each input; on the other hand, a "sum" behavior may take N input signals carrying a number and produce a total sum as the output signal, which would be the same for all inputs.

Behaviors can be composed into dataflow networks. A simple composition is the pipeline behavior, b1 >>> b2: the input signal of this pipeline behavior will be processed by the behavior b1; b1's output signal becomes the input signal for behavior b2; and finally, b2's output signal becomes the output of the whole pipeline behavior.

The Sirea Haskell implementation of RDP comes with other behaviors such as bdup, that copies a single signal into both branches of a :&: product, for creating more complex networks of signals and behaviors. There are also primitives like bfirst and bsecond for running different behaviors against the branches of product signals, and bfmap for applying ordinary Haskell functions to signals. (See Arrows.)

Resources (storage, external state)

RDP doesn't say anything about state, so it has to come from the outside. Access to stateful resources such as filesystems is abstracted through behaviors: to access a filesystem you use a behavior like readFile "foo.txt" that continuously delivers the contents of the file "foo.txt" as output signal.

Creating new resources in RDP is impossible, so resource discovery idioms are used: for example, to "create" a file, you use a UUID as its name, and it will be automatically created the first time you write to it.

I hope this has been helpful. For further reading, check out the extensive README of the Sirea RDP implementation, and David Barbour's blog.

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.