Q&A RDP from LtU

From a recent discussion on LtU:

Q: How would you implement stateful behaviors, like the tuple space?

Reactive Demand Programming (RDP) is designed to orchestrate stateful behaviors (and sensors, actuators, foreign services), not to implement them. So access to state is treated like a foreign service or FFI, but with a few standard models provided by the language runtime.

Tuple spaces would either be a standard service, or modeled atop some other standard. A candidate primitive for implementing a tuple-space is a term-rewrite model where ‘demands’ describe a set of rewrite rules and the state is a term. The term would effectively be rewritten every instant.

I haven’t written the blog article on state spaces yet, but I discuss elements of how access to a state service would be provided in an article on demand monitors, and I discuss several candidate state models in an article on stability.

Q: What are your primitive language constructs?

RDP is a programming model, not a language. But for the model primitives:

Signals with clear activity cycles (i.e. explicit starting and stopping times) serve as the values of RDP. Signals describe values that vary over time. Some signals may describe continuous values (as in: continuous function, like ((T - (2011 Sep 9)(*sine(T*pi)), while other signals may be piecewise discrete (i.e. 0 for T<(2011 Sep 9), 1 after). Activity cycles are critical for modeling disruption or non-existence of signals.

Note: you cannot model ‘instantaneous’ events with RDP signals. Every signal must have an activity cycle with positive duration, even if only for a picosecond. An instantaneous signal simply didn’t happen, as far as the optimizers and RDP behaviors are concerned.

RDP requires a global time model. My current implementation uses a simplified UTC with picosecond precision.

RDP can support many pure-functional operations on signals – e.g. you can add two real-valued signals together to generate a new real-valued signal. The set of available functions depends more on the programming language. I can imagine languages that enforce real-time properties, i.e. by avoiding recursive functions.

RDP is structured and constrained in such a way that you are guaranteed two signals being added will have the same activity cycle. Thus, the question never arises how we should add a real-value to an inactive signal. This is achieved by a ‘duration coupling’ property (duration of response equals duration of demand) and required use of a synchronization primitive (synch :: (Signal s) => (s x) :& (s y) ~!> (s (x,y))) before we can operate on the (x,y) pair using a function.

A consequence of duration coupling is that time cannot be squished or stretched in the model, though shifting (delay) is allowed, as is anticipation.

RDP’s main primitives are its composition operators, which are based on Arrows. My model of arrows is a variation to support asynchronous signals and enforce correct use of ‘synch’, based on Adam Megacz’s generalized arrows.

A good RDP programming language should not need to expose the arrows model to users, who should be able to treat behaviors much like functions.

Access to sensors, state, actuators, and foreign services is not primitive to RDP any more than OpenGL is primitive to Procedural. However, a programming system must ultimately provide such access in order for an RDP program to actually do something useful.

Signals in RDP must generally be updated over time. E.g. a sensor must provide updates even if the demand doesn’t change. The simplest update model is a switching signal – at time T, switch to new signal S’. However, more advanced update models are feasible, e.g. it is feasible to ‘patch’ a large database.

Q: What exactly is a demand? A piece of arbitrary data inserted into some set of demands of a behavior?

A demand is a signal. I call a signal a ‘demand’ when it is the input to a behavior. A response is also a signal, which happens to be the output from a behavior.

Q: Can you model each behavior as an actor that receives messages placeDemand(x) and removeDemand(x)?

No. This approach misses a few concerns such as security, concurrency, consistency, and provision of the response. For example, it would be a problem if Alice can placeDemand(x) then Bob can remove it!

For modeling RDP atop message-passing, I favor a more connection-oriented approach. In an imperative model, this looks something like:

updLnk <- mkLink behavior responseHandler;
updLnk (t0,s0)
 // ... later ...
updLnk (tk,sk)
 // ... disconnect ...
updLnk (tf,never)

Each link is good for one demand. To make multiple demands, you would build multiple links. The ‘removeDemand(x)’ is subsumed by simply setting the demand to a permanently inactive signal (never). Consistency is achieved because we indicate precisely when each update occurs in logical time. (By idiomatic use of ‘delay’, we can ensure these times are far enough the future that we do not experience glitches.)

A single ‘updLnk’ operation carries a full signal update. Thus, it can carry a lot of information about the future. For example, we could model the path of a baseball as a signal, and we’d only need one update (or perhaps a couple more to refine the prediction) rather than a bunch of periodic updates.

The ‘mkLink’ operation is composable, in the sense that the ‘updLnk’ value could be a response handler to another ‘mkLink’ operation. It helps that the initial demand is inactive, such that we can build a complex behavior by use of ‘mkLink’ then activate it all at once.

However, this ‘implementation-layer’ composition is tedious, difficult to optimize, and strongly discouraged. The most likely place where developers would need to muck with signals in this fashion is adapting those external sensors, state, actuators, and foriegn service models.

Developers of an RDP application are expected, instead, to compose a single RDP behavior that describes the entire application. The application is then activated as a whole.

Q: Are behaviors first class? That is, can you place a behavior as a demand on another behavior?

Dynamic behaviors are supported by RDP, and essential to many RDP design patterns (including service discovery, brokering, staged programming). The whole RDP application is also considered a dynamic behavior.

There are some usage constraints. You cannot store a dynamic behavior in state (logically, dynamic behaviors are continuously revoked) and there are limits on delay if you need the response from the behavior.

Q: How does pulling a response work? Can you model it in a kind of continuation passing style? I.e. can you instead of pulling on X, place a demand on X that contains another behavior Y, and then X puts the demand containing the result on Y?

For the implementation, I provide a response handler when building the link. This might be considered a sort of staged continuation passing style.

In general, use of dynamic behaviors to model responses in RDP would be a bad idea. First, RDP’s safety properties require a response to every demand with a statically computed latency, so we would need a variation of linear typing to enforce the requisite discipline. Second, optimizations based on RDP’s spatial idempotence, such as multi-cast and proxy caching, are undermined when every behavior comes with a unique explicit callback. Third, keeping response implicit and universal better supports functional composition.

As is, I prefer to keep response a primitive aspect of RDP behaviors. However, this is something I thought a lot about after first conceiving of RDP.

This entry was posted in Language Design, Reactive Demand Programming. Bookmark the permalink.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s