Semantics of a Signal

[Jack Waugh]

In an abstract sense, what does a signal signify?  I read that it is a mapping from time to (Maybe something) where the something is an underlying type of value such as could be expressed in Haskell (e. g. mouse coordinates), but I also read that there is information related to latency as well.  What is that information?  Is the time, for the mapping of time to value, measured in the partition containing or directly connected to the original input device (resource) where the signal arose or where the first of a chain of transformed signals arose?  For Reactive Demand Programming, do all the communicating partitions have to have clocks that are within some known tolerance of being synchronized?  What happens to a signal when it crosses from one partition to another?  Does the semantics of the crossing operator include some transform on what we must understand as the semantic content of the signal?  In answering, please leave implementation out and only talk about semantics in the abstract for the signals.  From reading your answer, I would like to be able to judge whether a given purported implementation does in fact implement Reactive Demand Programming.  Thanks.

[David Barbour]

Much like the answer to 'what does a value signify?', the answer to 'what does a signal signify?' depends on context. So perhaps I should answer your question by describing an example context.

A signal involved in a data query might represent a question like "where is the ping pong ball?". There is some point in time when you start asking this question, and there is likely some point in time at which you'll stop asking it - e.g. based on the duration of a ping pong game. The signal is called "active" for this duration in which the question is continuously posed.

To acquire an answer to your question may require some side effects, such as powering up a video camera or Kinect device in the ping-pong room, acquiring images, running expensive and power-consuming algorithms. Obviously, we want to shut all these behaviors down when you're no longer interested in the answer. Hence, tracking the active duration of the query is useful. 

The camera takes some time to acquire frames. Computations take time. There are network delays. These little latencies add up. Hence, there will typically be some latency between your query and the response signal. 

In RDP, we track these latencies and model them logically and statically (though we can model dynamic latencies with a staged program). Modeled latencies tend to be conservative or empirical in nature. Naturally, the real-world latencies have some variance - network hiccups and the like. But RDP is very robust to occasional hiccups, and even to slighly underestimating latencies. (Snapshot consistency, eventual consistency, and anticipation provide three more layers of defense.) We'll pretend latencies are static, and we'll get away with doing so. Or, if our latency numbers are too far off, we'll simply halt the program in error.

Modulo a little latency, you'll get a response to your query. This response might indicate the location of the ping pong ball, or it might report an error like "network is down, sorry" or "there is no ping pong ball" or "wtf? which ping pong ball?" or "camera is still warming up, please wait". But in any case, you do get a response. (Error reporting qualifies as an *active* signal.) RDP has a nice invariant called 'duration coupling', which guarantees you'll receive an active response for the same duration you maintain an active query.

Supposing you get the location of the ping pong ball, that location should be kept continuously up-to-date. That is, it's a time-varying value, a signal. If the network goes down in the middle of the game, you might switch to a 'network is down' response. But you should also resiliently recover when the network is back up.

Now that you have your ping-pong query response, you might use this in other ways. For example, you could send the signal to a database to record the game for posterity. Or you could transform the signal into a scene-graph and push it to a local display service. RDP differs from FRP significantly in that signals can be pushed (to influence other services) just as easily as they're pulled (e.g. as response to a query).  

... Anyhow, in this example I've mentioned different signals signifying different things: queries, error status, time-varying locations, scene-graphs intended for display, etc. I've also described latencies and duration coupling.

I hope the above example provides a useful context for comprehension. Onwards to your other questions:

Re: "Is the time, for the mapping of time to value, measured in the partition containing or directly connected to the original input device (resource) where the signal arose or where the first of a chain of transformed signals arose? do all the communicating partitions have to have clocks that are within some known tolerance of being synchronized?"

Every partition is free to measure time. In the ping pong example, the mapping between location of the ping pong ball and time would, I imagine, be performed as near to the sensor as feasible (perhaps leveraging a clock in the camera). Clocks are allowed to drift. And RDP can pretty well tolerate a small drift, relative to latency. But distributed RDP systems are expected to either synchronize clocks (via ntp, GPS, or similar) or to maintain estimates of remote clocks and translate time values as needed. 

Re: "What happens to a signal when it crosses from one partition to another?  Does the semantics of the crossing operator include some transform on what we must understand as the semantic content of the signal?"

In general, we can model types as having location information, e.g. distinguishing between Integer@David'sMachine vs. Integer@Jack'sMachine. These types are especially valuable for working with crossing operations.

Similarly, first-class functions might be specific to a machine - i.e. if I have a function of type (String@David'sMachine→Integer@David'sMachine)@David'sMachine, and I send it to you, you now have (String@David'sMachine→Integer@David'sMachine)@Jack'sMachine. Obviously, you can't do much with such a function except send it back to me at a later date. But that isn't useless!  Supposing the function represents some authority, this allows a very clean separation between acquiring authority an and applying it (cf. object capability security).

Pure functions or behaviors are usually generic with respect to location, e.g. (String@p→Integer@p) or ((x@p→y@p)*w@p → z@p). So if I send you one of these, you could use it wherever. The exception to this is heterogeneous computation, e.g. we might wish to distinguish functions that can run on GPUs or FPGAs from those that require the full power of a CPU, so we could have different 'kinds' of places even for pure functions.

Other than location information, the 'semantic content' of a signal is not usually changed. 

We might wish to directly model disruption in the crossing behavior, i.e. the possibility that a network is down. But we can often model that separately, i.e. by allowing acquisition of the 'crossing behavior' to fail if the network is down, then assume the crossing behavior itself, once acquired, never fails. (This is a nice separation of failure concerns.)

... If you're interested in details, look into "Type theory for mobility and locality" by Jonathon Moody, or the slides for Tom Murphy VII's thesis defense, or his actual thesis "Modal types for mobile code". 

There is some nice interaction with substructural types, e.g. I can give you "use once" functions, or add expirations so the (String@David'sMachine→Integer@David'sMachine) function is use-it-or-lose-it within 3 seconds (latency). Some patterns, like separating acquisition of a crossing behavior from applying it, rely on expirations.

I'm still getting a handle on explaining RDP. Please let me know where this answer helped you, and where you need clarification.

Best,

Dave

[Jack Waugh]

"I want to know where the ping pong ball is" and "It's at (x, y, z)" would be distinct signals in your model, right?  So if you were using an RDP language to simulate the execution of a program having lazy evaluation as a ubiquitous built-in feature, such as Haskell, you'd need two signals in the language of the simulation to model one flow in the language being simulated -- one signal for the demand for a result, and a distinct signal for the response, right?

Let's say the agent that wants to know "where is the ping pong ball" is in one partition, call it Socrates, and the agent that can calculate the answer from camera data, etc., is in another partition, call it Xenophon.  So say Xenophon calculates that at time t, the ball was flying through (x, y, z).  But communication from Xenophon to Socrates takes time dt.  Does the response signal in Socrates say the ball was at (x, y, z) at time t, or that it was at (x, y, z) at time t + dt?

Say that if a keyboardist holds down the shift key and hits the A key, I want to insert A in some text body that I'm building up, but if they hit A without the shift key, I want to interpret that event as "a" in lowercase.  Assuming that the logical device linking the physical keyboard to the network of flows and operators programmed in RDP, presents a distinct signal for "the shift key is being held down" and another one for "the A key is being held down", please show pseudocode in RDP terms for determining an interpretation that capital "A" is to be inserted in the text.

(For those readers for who receive this message by e-mail instead of seeing it in the context of the discussion of which it is part, the context starts at at https://groups.google.com/forum/#!topic/reactive-demand/1hGn7s_aTuE ).

[David Barbour]

On Sat, Aug 16, 2014 at 2:38 AM, Jack Waugh <jv2a...@gmail.com> wrote:

"I want to know where the ping pong ball is" and "It's at (x, y, z)" would be distinct signals in your model, right?

Right. And the stuff in between asking and receiving would be called a 'behavior' in RDP parlance. 

 

communication from Xenophon to Socrates takes time dt.  Does the response signal in Socrates say the ball was at (x, y, z) at time t, or that it was at (x, y, z) at time t + dt?

The latter. 

However, there are various patterns Xenophon could apply to preserve the exact timing. The most obvious perhaps is to report (t, x, y, z) at time t, such that Socrates later receives (t, x, y, z) at time t+dt. More interesting approaches include providing not just a position, but an estimated arc, such that Socrates can maintain a precise view of the ping pong ball at every intermediate moment, and we only need to update the signal for each change in the arc (with error tolerances).

The use of two different times - i.e. one intrinsic to the content, one intrinsic to the view of the content - is similar to bitemporal database concepts [1]. That said, it isn't essential for most problems.

 

[1] http://en.wikipedia.org/wiki/Bitemporal_data 

Say that if a keyboardist holds down the shift key and hits the A key, I want to insert A in some text body that I'm building up, but if they hit A without the shift key, I want to interpret that event as "a" in lowercase [..] please show pseudocode in RDP terms for determining an interpretation that capital "A" is to be inserted in the text.

Using John Hughes arrows [2] to represent RDP behaviors, it might look something like:

insertExample :: unit ➟ unit

insertExample = (keyState 'A' &&& keyState 'shift') >>> zip >>> arr mkInsertCmd >>> applyCmd >>> ignore

ignore :: a ➟ unit

keyState :: KeyIdent → (unit ➟ Bool) 

type Insert a = Insert a | Delete | Done

mkInsertCmd :: (Bool,Bool) → Insert Char

mkInsertCmd (True,True) = Insert 'A'

mkInsertCmd (True,False) = Insert 'a'

mkInsertCmd (False,_) = Done

legend:

  ➟ U+279F    RDP arrow

  → U+2192    pure functional arrow

The behavior `applyCmd` deserves more explanation since it's dealing with a stateful resource. Conventional imperative state manipulations (get and set) are difficult to express using continuous RDP signals. But there are state models appropriate for generic manipulation by continuous signals [3][4]. In this case, we might require a frame with 'Done' to shift to a state where we'll accept the next character.

[2] http://hackage.haskell.org/package/base-4.7.0.1/docs/Control-Arrow.html

[3] http://awelonblue.wordpress.com/2011/12/02/animated-reactive-term-rewriting/

[4] http://awelonblue.wordpress.com/2013/03/27/declarative-state-machines/

[David Barbour]

On Sat, Aug 16, 2014 at 11:07 AM, David Barbour <dmba...@gmail.com> wrote:

On Sat, Aug 16, 2014 at 2:38 AM, Jack Waugh <jv2a...@gmail.com> wrote:

"I want to know where the ping pong ball is" and "It's at (x, y, z)" would be distinct signals in your model, right?

Right. And the stuff in between asking and receiving would be called a 'behavior' in RDP parlance. 

For pedantic precision, I should clarify: the actual string "I want to know where the ping pong ball is" or "It's at (x,y,z)" would be the result of sampling the signal at a particular instant in time. The signal would represent the whole time-varying sequence of "It's at (x,y,z)" strings, and even "I want to know where the ping pong ball is" has some time-varying nature (since you start asking it at some point in time, and stop asking at another). 

But I expect you already understood this. :)

[David Barbour]

On Sat, Aug 16, 2014 at 11:07 AM, David Barbour <dmba...@gmail.com> wrote:

insertExample :: unit ➟ unit

insertExample = (keyState 'A' &&& keyState 'shift') >>> zip >>> arr mkInsertCmd >>> applyCmd >>> ignore

This example maintains a continuous signal to 'applyCmd'. We could actually break it down, so we have separate behaviors for inserting 'A' vs. 'a' vs. doing nothing. I haven't touched much on complex/composite signals so far, since I didn't want to distract from your main question. 

But there is a difference between (Signal of (a+b)) vs. (Signal of a + Signal of b). Similarly, there is a difference between (Signal of (a*b)) vs. (Signal of a * Signal of b). In each case, the meaning is similar, but the latter can potentially have different latencies and locations. The 'zip' behavior, used above, would take type  (Signal of a * Signal of b) at the same location, and return (Signal of (a*b)) which is suitable input for a pure function, implicitly synchronizing latencies as needed. 

An 'ideal' RDP language might not require this distinction, i.e. always using the composite signal instead of the signal of composite values (perhaps allowing the compiler to make the decision). But it is rather difficult to represent recursive data structures (lists, trees, etc.) as simple signals... and an implementation is often better off to treat as a single value elements that will change together.

[Jack Waugh]

I would be interested in reactions to the following hypotheses:

H1: RDP is semantically consistent with a description that says that if a Signal is a result of some communication or of some calculation, the Signal denotes a mapping from time to values, in which the time that is the key to the mapping is the time that the value is available from the communication or calculation.

H2: If a software library provided a way to make and use two-way channels in which demand flowed in one direction and results in the opposite direction, that would benefit programmers at least as much as if the library implemented the Signal concept of RDP.

H3:  To implement RDP on top of an actor language would not take away from the usefulness of RDP.  Messages in  the actor language could be used to communicate value updates to implement the Signal concept.  (For continuous-valued signals, instead of just signal value updates, the update would also update values to substitute for the parameters in a formula to estimate the future path of the signal).  The kind of "implement on top of" I mean here, is the kind where the programmer can see and use the underlying language as well as the high-level paradigm.  For example, in David Barbour's Simply Reactive library, the programmer can use all the facilities of Haskell (and indeed must use some of them in order to speak to the library).

[David Barbour]

On Mon, Sep 1, 2014 at 9:56 AM, Jack Waugh <jv2a...@gmail.com> wrote:

I would be interested in reactions to the following hypotheses:

H1: RDP is semantically consistent with a description that says that if a Signal is a result of some communication or of some calculation, the Signal denotes a mapping from time to values, in which the time that is the key to the mapping is the time that the value is available from the communication or calculation.

Seems okay.

 

H2: If a software library provided a way to make and use two-way channels in which demand flowed in one direction and results in the opposite direction, that would benefit programmers at least as much as if the library implemented the Signal concept of RDP.

I would deny this hypothesis. It is true that RDP can be modeled over two-way channels. But the contents of each 'demand' and 'response' message should still represent a signal, or an idempotent patch on a signal. 

For example, rather than repeatedly saying "the value is now ...", we say "the value starting at time T is v1, and at time T+3 we expect it to change to v2, and at time T+9, we expect it to change to v3, and at time T+11, we expect the signal to halt, and at time T+21, we expect the signal to resume with value v4, and at time T+29 assume it will halt until further communications arrive". Then later, we might adjust this, perhaps affirming the value at time T+3 and tweaking our future at T+11 and beyond.

Making the signal concept explicit results in a more robust, composable, and efficient system: precise logical timings, reasonable estimates for future values in case of communication hiccups, limited support for retroactive correction and retraction (which results in very nice atomic concurrency properties, an alternative to transactions), better warm-up times because schedulers can anticipate when which resources are needed, better integration with planning systems in general, and more efficient use of computation resources (via batching and composition of updates, and avoiding some update messages when they'd match anticipated values, and optimistic concurrency). 

 

H3:  To implement RDP on top of an actor language would not take away from the usefulness of RDP.  Messages in  the actor language could be used to communicate value updates to implement the Signal concept.  (For continuous-valued signals, instead of just signal value updates, the update would also update values to substitute for the parameters in a formula to estimate the future path of the signal).  The kind of "implement on top of" I mean here, is the kind where the programmer can see and use the underlying language as well as the high-level paradigm.  For example, in David Barbour's Simply Reactive library, the programmer can use all the facilities of Haskell (and indeed must use some of them in order to speak to the library).

In Sirea, I used a 'vat' concept [1], and I'll probably use it for most future implementations. A vat might be understood as a process that batches incoming update messages for efficiency, has some special handling to limit frequency when computing feedback cycles, and integrates with the scheduler to prevent any vat from running too far ahead of other vats on the same host machine (i.e. so no process falls too far behind). A nice feature of vats is that they're little islands of consistency, and we can easily reason about snapshot consistency properties even between vats (since all updates from a vat will also be batched). Vats also served as an initial simulation for distributed computation, i.e. typed locations.

While RDP could be implemented on an actors language - and, indeed, that was an approach I considered a deeply in 2010, as I had been working with actors when I conceived of RDP - I had some difficulty reasoning about consistency when combining multiple signals, and it seems difficult to achieve similar performance properties. Of course, you could probably implement the vats concept within an actors system with a little performance overhead (complete with incoming and outgoing mail carriers), but I think it would take a fair amount of discipline to use. 

Access to underlying actors language would be useful for integration with resources exposed to the actors language. But, as with integrating IO resources in Sirea, it would take a fair amount of discipline to safely integrate *new* resources while preserving RDP's nice features (like anticipation and ability to update the live program) and without violating RDP's properties (causal commutativity, spatial idempotence).

[1] http://awelonblue.wordpress.com/2011/10/06/vat-model-for-rdp/