Overview
In this section, we explicit the Kingly’s API for standard state machines and hierarchical state machines; and cover in detail the API semantics. For those with interest in software architecture, we also detail the principles at the core of Kingly design.
To start defining a state machine with Kingly, it is necessary to get acquainted with:
- the basic state machine formalism;
- its extension, including hierarchy (compound states), and history states;
- the library’s API; and
- Kingly machine semantics.
While that may seem like a lot, it is actually fairly simple to get started and progressively build up skills. Readers may find a gradual step-by-step introduction to the concepts may refer to the tutorials. You may want to go back and forth between the present reference and the tutorials, as one complements the other. The reader can also refer to the examples section for full-fledged additional examples.
This section aim to serve as a reference documentation and should contain the entire description of the public Kingly API. We also provide a glossary of terms that you can refer to anytime you doubt the meaning of a word.
If there is anything you would like to add or any feedback on the current API, let us know! We love to hear from you.
General concepts
In this section, we will use the example of a reasonably complex CD player application, whose behavior is modeled by a hierarchical state machine. For this example, we will show a run of the machine, and by doing so, illustrate advanced concepts such as compound states, and history states. This example will be focused on the modeling rather than the implementation.
CD drawer modeling
This example is taken from Ian Horrock’s seminal book on statecharts and is the specification of a CD player. The behavior of the CD player should be understandable from the visualization, or if not, from your previous experience with a CD player. From a didactic point of view, the example features advanced characteristics of hierarchical state machines, including history states, composite states, transient states, automatic transitions, and entry points. For a deeper understanding of how the transitions work in the case of a hierarchical machine, you can have a look at the terminology and sample run for the CD player machine.
The salient facts are:
NO Cd loaded
,CD_Paused
are control states which are composite states: they are themselves state machines comprised of control states.- The control state
H
is a pseudo-control state called shallow history state. - All composite states feature an entry point and an automatic transition. For instance,
CD_Paused
has the sixth control state as an entry point, and the transition fromCD_Paused
into that control state is called an automatic transition. Entering theCD_Paused
control state automatically triggers that transition. Closing CD drawer
is a transient state. The machine will automatically transition away from it, picking a path according to the guards configured on the available exiting transitions.
Example run
To illustrate the previously described machine semantics, let’s run the CD player example. The machine processes internal and external events. External events comes from the user or external systems. Internal events are generated by the machine itself. For instance, the INIT
event is an internal event that the machine triggers to go to its initial control state (No Cd loaded
here), or every time it transitions to a compound state (for instance CD Loaded
) — in order to go to the initial control control state of the compound state.
Control state | Internal event | External event |
---|---|---|
INIT_STATE | INIT | |
No Cd Loaded | INIT | |
CD Drawer Closed | — | |
CD Drawer Closed | Eject | |
CD Drawer Open | Eject (put a CD) | |
Closing CD Drawer | (eventless) | |
CD Loaded | INIT | |
CD Loaded subgroup | INIT | |
CD Stopped | — | |
CD stopped | Play | |
CD playing | Forward down | |
Stepping forwards | Forward up | |
CD playing | — | . |
The previous table illustrates the semantics of the visualization. At start, the machine will transition to the No Cd Loaded
control state. As this is a compound state, it will transition again to the initial control state of that compound state and end up in the CD Drawer Closed
state. That compound state is not a compound state, so the machine will remain there. When the user triggers the Eject
event, the graph tells us that the machine will transition to the CD Drawer Open
control state. Triggering Eject
again will have the machine transition to the Closing CD Drawer
control state. That control state is eventless. That means that there are no events that causes it to change its control state. Instead the machine immediately takes any transition that is possible. We have two here, according to whether there is a CD in the drawer or not. You can try to do the run in your head by looking at the graph and compare your results with the previous table.
This is how a graph is used to model the behavior of an application. The control state (graph node) in which the machine is has transitions (graph edges) that define what events are reacted to, and what those reactions are (edge labels).
Note:
- the state entry semantics — entering
No Cd Loaded
leads to enterCD Drawer Closed
. - the guard — because we put a CD in the drawer, the machine transitions from
Closing CD Drawer
toCD Loaded
. - the eventless transition — the guards are automatically evaluated to select a transition to progress the state machine (by contract, there must be one).
- the hierarchy of states — the
Forward down
event transitions the state machines toStepping forwards
, as it applies to all atomic states nested in theCD Loaded subgroup
control state. - the history semantics — releasing the forward key on the CD player returns to
CD Playing
, the last atomic state for compound stateCD Loaded subgroup
.
The full syntax for the visual language used to model state machines with graphs can be found in the Graph editor section.
From here, you can go to explore the createStateMachine
API that allows you creating state machines. The parameters passed to the function will include a JavaScript encoding of graphs like the one we just presented.
Kingly machine semantics
The following is fairly technical. The objective is to provide you with a thorough understanding of how a Kingly machine processes inputs. You may not need to reach this level of details if you are just starting with the Kingly library. You may want to review the tutorials and additional examples.
We give here a quick summary of the behavior of a Kingly state machine:
Preconditions
- the machine is configured with a set of control states, an initial extended state, transitions, guards, action factories, and user settings
- the machine configuration is valid (cf. contracts)
- Input events have the shape
{[event_label]: event_data}
Event processing
- Calling the machine factory creates a machine according to specifications and triggers the reserved
INIT_EVENT
event which advances the state machine out of the reserved internal initial control state towards the relevant user-configured initial control state- the
INIT_EVENT
event carries the initial extended state as data - if there is no initial transition, API consumers must pass an initial control state
- if there is no initial control state, API consumers must configure an initial transition
- an initial transition is a transition from the reserved
INIT_STATE
initial control state, triggered by the reserved initial eventINIT_EVENT
- the
- Loop
- Search for a feasible transition in the configured transitions
- a feasible transition is a transition which is configured to deal with the received event, and for which there is a fulfilled guard
- If there are no feasible transitions:
- issue memorized output (
NO_OUTPUT
if none); extended state and control state do not change. - break away from the loop
- issue memorized output (
- If there is a feasible transition, select the first transition according to what follows:
- if there is an
INIT
transition, select that - if there is an eventless transition, select that
- otherwise, select the first transition whose guard is fulfilled (as ordered per array index)
- if there is an
- evaluate the selected transition
- if the target control state is a history state, replace it with the control state it references (i.e. the last seen nested state for that compound state)
- run the action factory defined in the selected transition to get extended state updates, and machine outputs
- update the extended state (with the updates produced by the action factory)
- aggregate and memorize the outputs
- update the control state to the target control state defined by the selected transition
- update the history for the control state (applies only if the control state is a compound state)
- iterate on Loop
- THE END
A few interesting points:
- a machine always transitions towards an atomic state at the end of event processing
- on that path towards an atomic target state, all intermediary extended state updates are performed. Guards and action factories on that path are thus receiving a possibly evolving extended state. The computed outputs will be aggregated in an array of outputs.
The aforedescribed behavior is loosely summarized here:
History states semantics
A history state relates to the past configuration of a compound state. There are two kinds of history states: shallow history states (H); and deep history states (H*). A picture being worth more than words, thereafter follows an illustration of both history states:
Assuming the corresponding machine has had the following run [INIT, EVENT1, EVENT3, EVENT5, EVENT4]
:
- the configurations for the
OUTER
control state will have been[OUTER.A, INNER, INNER.S, INNER.T]
- the shallow history state for the
OUTER
control state will correspond to theINNER
control state (the last direct substate ofOUTER
), leading to an automatic transition to INNER_S - the deep history state for the
OUTER
control state will correspond to theINNER.T
control state (the last substate ofOUTER
before exiting it)
- the shallow history state for the
In short, the history state allows short-circuiting the default fixed entry behavior for a compound state, which is to follow the transition triggered by the INIT
event. When transitioning to the history state, the transition has as a target the last seen state for the entered compound state.
Contracts
Format
- state names (from
fsmDef.states
) must be unique and be JavaScript strings - event names (from
fsmDef.events
) must be unique and be JavaScript strings - reserved states (like
INIT_STATE
) cannot be used when defining transitions - at least one control state must be declared in
fsmDef.states
- all transitions must be valid:
- the transition syntax must be followed (cf. types)
- all states referenced in the
transitions
data structure must be defined in thestates
data structure - all transitions must define an action (even if that action does not modify the extended state or returns
NO_OUTPUT
)
- all action factories must fill in the
updates
andoutputs
property (no syntax sugar)NO_OUTPUT
must be used to indicate the absence of outputs and only for that- the
outputs
property should always be set (behavior in case ofundefined
is unspecified).
- all transitions for a given origin control state and triggering event must be defined in one row of
fsmDef.transitions
fsmDef.settings
must include aupdateState
function covering the state machine’s extended state update concern.
Initial event and initial state
By initial transition, we mean the transition with origin the machine’s default initial state.
- An initial transition must be configured:
- by way of a starting control state defined at configuration time
- by way of an initial transition at configuration time
the init event has the initial extended state as event dataThe machine cannot stay blocked in the initial control state. This means that at least one
transition must be configured and be executed between the initial control state and another state
. This is turn means:at least one non-reserved control state must be configuredat least one transition out of the initial control state must be configuredof all guards for such transitions, if any, at least one must be fulfilled to enable a
transition away from the initial control state
- there is exactly one initial transition, whose only effect is to determine the starting control state for the machine
- the action on any such transitions is the identity action
- the control state resulting from the initial transition may be guarded by configuring
guards
for the initial transition
- there are no incoming transitions to the reserved initial state
Additionally the following applies:
- the initial event can only be sent internally (external initial events will be ignored, and the machine will return
NO_OUTPUT
) - the state machine starts in the reserved initial state
Coherence
- the initial control state (
fsmDef.initialControlState
) must be a state declared infsmDef.states
- transitions featuring the initial event (
INIT_EVENT
) are only allowed for transitions involving compound states- e.g.
A -INIT_EVENT-> B
iff A is a compound state or A is the initial state
- e.g.
- all states declared in
fsmDef.states
must be used as target or origin of transitions infsmDef.transitions
- all events declared in
fsmDef.events
must be used as triggering events of transitions infsmDef.transitions
- history pseudo-states must be target states and refer to a given declared compound state
- there cannot be two transitions with the same
(from, event, predicate)
- sameness defined for predicate by referential equality
Semantic contracts
- The machine behavior is as explicit as possible
- if a transition is taken and has guards configured, one of those guards must be fulfilled, i.e. guards must cover the entire state space when they exist
- A transition evaluation must end
- eventless transitions must progress the state machine
- at least one guard must be fulfilled, otherwise, we would remain forever in the same state
- eventless self-transitions are forbidden (while theoretically possible, the feature is of little practical value, though being a possible source of ambiguity or infinite loops)
eventless self-transitions must modify the extended statelest we loop forever (a real blocking infinite loop)note that there is not really a strong rationale for eventless self-transition, I recommend
just staying away from it
- eventless transitions must progress the state machine
- the machine is deterministic and unambiguous
- to a (from, event) couple, there can only correspond one row in the
transitions
array of the state machine (but there can be several guards in that row)- (particular case) eventless transitions must not be contradicted by event-ful transitions
- e.g. if there is an eventless transition
A -eventless-> B
, there cannot be a competingA -ev-> X
* There exists however semantics which allow such transitions, thus making event bubbling possible.
A -ev> B
andA < OUTER_A
withOUTER_A -ev> C
!!: there are two valid transitions triggered byev
. Such transitions would unduly complicate the input testing generation, and decrease the readability of the machine so we forbid such transitions*. Note that this does not apply for reserved events likeINIT_EVENT
or the empty event (corresponding to eventless transitions)
- to a (from, event) couple, there can only correspond one row in the
- no transitions from the history state (history state is only a target state)
- A transition evaluation must always end (!), and end in an atomic state
- Every compound state must have exactly one unconditional (unguarded)
INIT
transition, i.e. a transition whose triggering event isINIT_EVENT
. That transition must have a target state which is a substate of the compound state (no hierarchy crossing), and which is not a history pseudo-state - Compound states must not have eventless transitions defined on them (would introduce ambiguity with the
INIT
transition) - (the previous conditions ensure that there is always a way down the hierarchy for compound states, and that way is always taken when entering the compound state, and the descent process always terminate)
- Every compound state must have exactly one unconditional (unguarded)
- the machine does not perform any effects
- guards, action factories are pure functions
- as such, exceptions while running those functions are fatal, and will not be caught
updateState:: ExtendedState -> ExtendedStateUpdates -> ExtendedState
must be a pure function (this is important in particular for the tracing mechanism which triggers two execution of this function with the same parameters)
- guards, action factories are pure functions
Those contracts ensure the good behavior of the state machine. and we recommend that they all be observed. However, some of them are not easily enforceable:
- we can only check at runtime that transitions with guards fulfill at least one of those guards.
In these cases, we only issue a warning, as this is not a fatal error. This leaves some flexibility to have a shorter machine configuration. Note that we recommend explicitness and unambiguity vs. conciseness. - the purity of functions cannot be checked, even at runtime
Contracts enforcement can be parameterized with settings.debug.checkContracts
.
Design goals
The key objectives for the API were:
- generality, reusability, and simplicity
- there is no explicit provision made to accommodate specific use cases or frameworks
- it must be possible to add a concurrency and/or communication mechanism on top of the current design
- it must be possible to integrate smoothly into React, Angular, and your popular framework
- support for both interactive and reactive programming
- parallel and sequential composability of state machines
As a result of this, the following choices were made:
- functional interface: the state machine is just a function. As such, it is a black-box, and only its computed outputs can be observed
- complete encapsulation of the state of the machine
- no effects performed by the machine
- no exit and entry actions, or activities as in other state machine formalisms
- there is no loss of generality as both entry and exit actions can be implemented with our state machine. There is simply no syntactic support for it in the core API. This can however be provided through standard functional programming patterns (higher-order functions, etc.)
- every computation performed is synchronous (asynchrony is an effect)
- action factories return the updates to the extended state to avoid any unwanted direct modification of the extended state (API user must provide such update function, which in turn allows him to use any formalism to represent state - for instance
immutable.js
) - no restriction is made on the outputs of Kingly machines, but inputs must follow some conventions (if a machine’s output match those conventions, two such machines can be sequentially composed
- parallel composition naturally occurs by feeding two state machines the same input(s))
- as a result, reactive programming is naturally enabled. If
inputs
is a stream of well-formatted machine inputs, andf
is the fsm, then the stream of outputs will beinputs.map(f)
. It is so simple that we do not even surface it at the API level.
- as a result, reactive programming is naturally enabled. If
Concretely, our state machine will be created by the factory function createStateMachine
, which returns a state machine which:
- immediately positions itself in its configured initial state (as defined by its initial control state and initial extended state)
- will compute an output for any input that is sent to it since that
Let us insist again on the fact that the state machine is not, in general, a pure function of its inputs. However, a given output of the machine depends exclusively on the sequence of inputs it has received so far (causality property). This means that it is possible to associate to a state machine another function that takes a sequence of inputs into a sequence of outputs, in a way that that function is pure. This is what enables simple and automated testing.