Animated Reactive State Transition

In my recent article on Reactive State Transition, I concluded that a transducer variation won’t work cleanly due to potential for cyclic operations, and the interaction between continuous and discrete time.

I must amend this argument.

Augmenting RST transitions with delay would allow developers to ensure a finite number of discrete transitions between any two instants in continuous time, and would make those transitions directly observable (no need for anticipation). This in turn would allow associating transitions with imperative effects – i.e. to model a transducer. Assuming an RDP context, one can easily observe the state to decide a continuous RDP behavior for the duration of the state, which can still be useful to model events (e.g. by applying a bunch of rules to other RST machines for a duration of one millisecond).

A static set of transition rules, with delay, effectively defines a discrete animation which is either cyclic or has a clear endpoint. This internal animation is mostly orthogonal to the external animation of all RST models, which is achieved by reactively adjusting the transition rules. If the design is well chosen, there should be no difficulty

There are some semantic concerns, however, regarding how the two animation models should interact – e.g. can internal animations be interrupted by changes in external conditions? The rest of this article addresses these concerns.

First Class Transitions

An interesting question for this model is whether transitions are first-class states. This is an important design option:

  • If transitions are identified as edges in a graph – e.g. (3,4) – then the state transition rules do not identify the edges, and the model is ‘committed’ to each transition.
  • If transitions are labeled and treated as first-class states, then it becomes feasible to model interrupts at any time as an extra edge from a transition state.

I am strongly inclined to offer precedence to external reactivity and support for interrupts based on changes in transition rules. This is better for many use cases, and seems to offer many simplicity and elegance advantages: To the observer and persistence systems, state is uniformly structured. To the developer, the notion of `transition` and `primary state` become conceptually interchangeable (e.g. think of transition as the instantaneous step, and the delay as being part of the state). For external RST machines, `reset` can be represented entirely within the model (disable other transition rules, apply *->0) as opposed to a special feature that bypasses active commitments.

Delay as Logical Timeout

Directly assigning delay to transitions seems problematic, unless the decision is committed in the first instant it becomes available – and I’ve already decided against that sort of commitment. The problem is that the rules might change a bit, adjusting the delays between two nodes. Conceptually, the history of the rules should not be part of the current state (I want bounded state per RST machine) so there is no way to say: “hey, I’ve been in this state for X milliseconds, time to switch based on a rule that has been consistently available for X milliseconds!” There would also be funky issues with rules changing over time – e.g. the exact same rule, except for a shorter delay.

A viable alternative is to model the RST machine as providing a simple timer and timeout mechanism. Consider the following:

  • The abstract animated RST machine has three abstract registers (Current,Next,Timeout) and a Clock.
  • When Clock=Timeout, and Clock is about to increase, Current is assigned the value in Next.
  • Transition rules consist of four values: (S,T,F,D). Value S describes a starting state (or range thereof). Values T,F identify specific states. D is a delay which must be zero or positive.
  • A transition is chosen based on matching S against Current. When a transition is selected, this affects both the current and future states for the machine:
    1. Current := T
    2. Next := F
    3. Timeout := Clock+D
  • Rules for the non-animated RST from the prior article are modeled as (S,T,T,0).
  • Observers of the RST can only see Current state at any given instant in time. Next and Timeout are effectively write-only as part of choosing a transition rule.

A very trivial animated RST to perform some action for 1 millisecond after every 999 millseconds:

enum { START, ACTIVE, STOP, PERIOD_WAIT }
p = 1.0s
d = 0.001s
m = {(START,ACTIVE,STOP,d), (STOP,PERIOD_WAIT,START,p - d)}

All four states are necessary since delay can only be assigned at a transition. Two states effectively represent labeled `edges` in the graph.

Resolving Ambiguity

In the prior article I described how it is important to resolve ambiguity – even if in an arbitrary manner – to achieve deterministic, consistent, cheaply fault-tolerant via redundancy, easily verified and validated behavior. Of course, it’s better to avoid ambiguity than to resolve it, but for a collaborative and reactive system like RDP it can be difficult to prevent ambiguity.

The simple heuristic from the earlier article can still apply with a minor tweak: first filter all the (S,T,F,D) transition rules that can apply to a given state (by S), then choose the transition rules that lead to the lowest T state. If there is more than one, choose a transition rule that leads to the lowest F state. If there is more than one, choose the transition rule with the lowest delay D. There can be only one.

It is possible to express transitions of the form (S,T,F,0) where T is not equal to F. In this sense, the animated RST might be slightly more expressive than the original RST even for zero-latency transitions. However, the T->F state is treated as occurring only at the end of the instant, which means it has the lowest priority relative to other transitions from T. Effectively, after reaching T by an (S,T,F,0) rule, we can add a single-use rule of the form (T,infinity,F,0) for deciding priority.

Resolving Cycles

A cycle including T will prevent the T->F transition from ever firing, since the machine will keep choosing a path other than T->F. So cycles resolve the same way they do in the prior RST model. Effectively, one can understand a cycle as stabilizing as though an extra rule of the form (L,L,L,0) is introduced, where L is the lowest labeled state in the cycle.

Of course, since T represents a transitory state (an edge), there really shouldn’t be cycles including T. This is possible only if introducing interrupts in a malformed graph. In practice, it should be a non-issue. In the rare cases it is an issue, at least it will be so deterministically.

Weaknesses

As with RST, animated RST has a lot of arbitrariness, which always smells bad to me – but is not unexpected due the simplistic (overly simple) nature of RST and of state machines in general.

The real problem is fundamental: timeouts. Even when timeouts are deterministic and logical (like in an RDP system), there isn’t any natural relationship between timeouts and the state of the external systems. No matter what value is locally chosen for a timeout, it’s arbitrary and wrong! Systems with timeouts do not compose well; inner timeouts easily accumulate to larger values than outer timeouts.

Conclusions

Timer and timeout based state machines would support rapid development of simple frame-oriented animations (such as a GIF image) and various simulations. It can be useful for animating periodic activity (e.g. once per second, per minute, per hour, per day). Timeouts apply almost directly to integration and adaptation of event systems, whether to recognize complex events or to decide when to re-deliver a message.

The advantages of RST still apply: State is collaborative without exclusive control. Future RST state at any given instant can easily be anticipated to the extent one can anticipate future transition rules, accommodating even the internal animation. State cost is bounded (up to integer type) in any given instant. State is stable within each instant and often across fluctuations in transition rules. The RST machine can easily be modeled as external and eternal, and abstract infinite spaces of integer-labeled RST machines can be provided to model complex reactive memory systems (except now with animated memory!). There is a clean reset state (*->0).

Animated RST has potential to be a powerful tool in the toolbox. I’ll certainly try implementing it.

Fortunately for my personal brand of insanity, RDP pushes this arbitrariness to the edges of the system: access to an RST service must be provided as a foreign service, possibly by a language runtime or extension. This allows many arbitrary variations to coexist peacefully.

[Edited heavily 2011 October 19]

Advertisements
This entry was posted in Concurrency, Language Design, Reactive Demand Programming, State and tagged , . Bookmark the permalink.

2 Responses to Animated Reactive State Transition

  1. vaderr12 says:

    “(…)Effectively, after reaching T by an (S,T,F,0) rule, we can add a single-use rule of the form (T,infinity,F,0) for deciding priority.”

    Hi, I’m not sure if I understand fully, but I think that single-use rule should be something like (T,F,F,infinity). Am I right?

    • dmbarbour says:

      The idea here is that the (S,T,F,0) rule effectively goes from state S to state F, but only if there is no transition rule from T to anywhere else. (If we didn’t care about T, we would have used transition rule (S,F,F,0).) This behavior of being ‘derailed’ by any rule at T can be useful for modeling extensible systems, forcing detours. Anyhow, let’s assume the rule at T is: (T,(F+1),K,0.1). That is, we go to (F+1). Then, if there are no other transition rules available for a tenth of a second, we go to K.

      Anyhow, the ‘priority’ issue regards a resolution rule: when I have two paths before me, take the one with the lowest number. This offers simplicity and determinism, albeit at the cost of being completely arbitrary. Thus, if we used (T,F,F,infinity), and added that rule to the existing (T,(F+1),K,0.1), then we’d go from T to F instead of from T to F+1. OTOH, if we use (T,infinity,F,0) for the first rule, then we go from T to (F+1) because the latter rule is available and (F+1) is less than infinity.

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