Declarative State Machines

Lately, I’ve been wondering what state-machines would look like if specified for declarative systems.

Traditional state machines are specified to receive a stream of events as input. Each event may shift the machine into a new state. The transitions are programmed into the machine, and are commonly static in nature. Outputs from a state machine are typically based on the current state (a Moore machine) or on the transitions (a Mealy machine). These state machines are a good fit for imperative programming models. Serialization into an event stream fits imperative semantics due to the implicit passage of time across imperative actions. Such state models work best with a single writer, no concurrency. If there are multiple writers, it will be difficult to form a deterministic stream.

In 2011, I contemplated state machines for declarative systems and developed reactive state transition (RST). While RST can serve the same role as state machines, it is a very different programming experience, inverting many aspects of the traditional state machine. Instead of providing a stream of events, developers manipulate the RST program by adding and removing edges, and allow the state to flow through the program naturally. It’s essentially live coding applied to state machines.

RST was designed as an external state model, i.e. conceptually separate from the client application. There are many reasons to avoid local state, and it is necessary for use with my reactive demand programming model. In 2011, I was having some difficulty addressing external state models without making them generic. Fortunately, my recent designs towards ad-hoc external state will allow something much closer to a traditional state machine, having a static user-defined program (a fixed set of edges and potential states).

So I’m once again contemplating state machines for declarative systems.

The state machine will be influenced by declarations by agents external to it. Each declaration might apply inputs to the machine. There is no implicit passage of time between declarations, and multiple declarations easily overlap in time and influence concurrently. Thus, we might understand the state machine as being influenced by a sequence of frames where each frame is a set of inputs.

To keep the simplicity of traditional state machines, declared inputs should must from a simple input alphabet. For example, if the input alphabet is `a..f`, then a valid frame would be `acd`. The sequence of observations by the state machine is a series of frames, e.g. `acd, abd, cef, ce, cbd, bd, abd`. The input alphabet may represent observations, propositions, or control signals.

From there, we can almost directly apply the traditional state machine, simply using the powerset of the declarative input alphabet. I.e. we can draw edges and specify transitions such that frame `cef` is treated as a completely distinct event from `ce` or `cdef`.

The exception regards continuity. Frames represent continuous observations. Thus, we must not distinguish `acd, acd, acd, abd, abd, abd, abd, cef, cef` from `acd, abd, cef`. This exception can be addressed easily enough: if a state has an input with a given event, it must not have an output on the same event. Alternatively, we could analyze for loops globally, or settle loops deterministically. If developers need to distinguish a constant frames, they might consider adding a discrete clock signal, e.g. `acd, acdk, acd, acdk`.

That’s it! Nothing more is necessary to achieve declarative state machines. For output, both Mealy and Moore machines are useful in appropriate contexts (e.g. Mealy machines are useful for adapting imperative models, while Moore machines are better for composition).

Of course, a powerset can get impractically large, very quickly. We’ll want a shorthand to describe large sets of possible frames. We could use logical propositions: `a & c & ~b & ~e` includes the set of frames {ac, acd, acf, acdf}, and could easily be shorthanded to `ac-be`.

Interestingly, use of non-deterministic machines (NFAs) may prove more convenient and symmetric. An NFA essentially allows that we have a set of active states (usually understood to be possible states), just like we have a set of active inputs. This makes it easier to address signals individually. Potentially, we could address loops by simply activating every state reachable in the loop. This design also composes well in a declarative system with the Moore machine, since we could have a set of active output signals.

Advertisements
This entry was posted in Concurrency, Open Systems Programming, State. Bookmark the permalink.

One Response to Declarative State Machines

  1. Jimmy Hoffa says:

    As an example to a colleague I wrote a declarative state machine-like set of combinators in JavaScript when he showed me some eventful state machine in JavaScript that was getting a lot of play for use in Node.JS etc. Have a look for yourself; it’s very similar to the error monad from haskell but I took some liberties to keep it more compositional (I opted to stick with kleisli composition rather than bind so every composition results in a function, even in the case of alternate, so you declare the whole before you give it any values to start filtering through the gates) https://github.com/JimmyHoffa/Machinad

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