| Modelize your interface | Encode the graph | Run the generated machine! |
|---|---|---|
 |  |  |
This library enables you to write user interfaces as state machines. You specify the machine as a graph. The library computes a function which implements that machine. You use that to drive your interface. It integrates easily with any or no framework. Tests can be automatically generated.
Salient features :
| Code playground | Demo | State Machine |
|---|---|---|
| password meter component |  | |
| movie database search interface |  |  |
| wizard forms |  |  |
This library fundamentally implements computations which can be modelized by a type of state machines called hierarchical extended state transducer. This library offers a way to define, and use such transducers.
Now, the whole thing can sound very abstract but the major motivation for this library has been the specification and implementation of user interfaces. As a matter of fact, to every user interface can be associated a computation relating inputs to the user interface to an action to be performed on the interfaced systems. That computation often has a logic organized around a limited set of control states, and can be advantageously modelized by a state machine.
This library is born from :
This is a work in progress, however the main API for the v1.0 should be relatively stable.
It works nicely and have already been used succesfully for user-interfaces as well as in other contexts:
In such cases, we were able to modelize our computation with an Extended Hierarchical State Transducer in a way that :
In short :
f such that actions = f(state, event). We call here f the reactive function for the user interface.g such that (actions_n, state_{n+1} = g (state_n, event_n). That is, we explicitly include the modification of the state triggered by
events. Depending on the choice that is made for state_n, there is an infinite number of ways
to specify the user interface.Let's take a very simple example to illustrate these equations. The user interface to specify is a password selector. Visually, the user interface consists of a password input field and a submit password button. Its behaviour is the following :
set password button is ignored, otherwise
the password is set to the value of the password inputA f partial formulation :
| State | Event | Actions |
|---|---|---|
{input: ""} | typed a | display input in red |
{input: "a"} | typed 2 | display input in green |
{input: "a2"} | clicked submit | submit a2 password |
{input: "a"} | typed b | display input in red |
{input: "ab"} | clicked submit | --- |
A g partial formulation :
| state_n | event | actions_n | state_{n+1} |
|---|---|---|---|
{input: ""} | typed a | display input in red | {input: "a"} |
{input: "a"} | typed 2 | display input in green | {input: "a2"} |
{input: "a2"} | clicked submit | submit a2 password | {input: "a2"} |
{input: "a"} | typed b | display input in red | {input: "ab"} |
{input: "ab"} | clicked submit | --- | {input: "ab"} |
A state machine partial formulation :
| Control state | Extended state | Event | Actions | New control state | New extended state |
|---|---|---|---|---|---|
| Weak | input: "" | typed a | display input in red | Weak | input: "a" |
| Weak | input: "a" | typed 2 | display input in green | Strong | input: "a2" |
| Strong | input: "a2" | clicked submit | submit a2 password | Done | input: "a2" |
| Weak | input: "a" | typed b | display input in red | Weak | input: "ab" |
| Weak | input: "ab" | clicked submit | - | Weak | input: "ab" |
The corresponding implementation is by a function fsm with an encapsulated initial internal state
of {control state : weak, extended state: {input : ''}} such that, if the user types 'a2' and
clicks submit :
fsm(typed 'a') = nothing
fsm(typed '2') = nothing
fsm(clicked submit) = submit `a2` password
The corresponding visualization (actions are not represented) :
Note that we wrote only partial formulations in our table, as the sequence of inputs by the user
is potentially infinite (while this article is not). Our tables do not for instance give a
mapping for the following sequence of events : [typed 'a', typed '2', typed <backspace>]. Conversely, our state machine concisely represents the fact that whatever input
we receive in the Weak control state, it will only go to the Strong control state if some
pre-configured condition are fulfilled (both numbers and letters in the password). It will
only submit the password if the clicked submit event is received while it is in the Strong
state.
The starting state and these two assertions can be combined into a theorem : the machine will only submit a password if the password is strong. In short, we are able to reason formally about the machine and extract properties from its definition. This is just one of the many attractive properties of state machines which makes it a tool of choice for robust and testable user interface's implementation.
For the modelization of a much more complex user interface, and more details on the benefits of state machine, I'll refer the reader to a detailed article on the subject.
npm install state-transducer --save
To run the current automated tests : npm run test
The machine implementation is just a function. As such it is pretty easy to integrate in any framework. In fact, we have implemented the same interface behaviour over React, Vue, Svelte, Inferno, Nerv, Ivi, and Dojo with the exact same fsm. By isolating your component behaviour in a fsm, you can delay the UI library choice to the last moment.
As of April 2019, we officially provide the following integrations :
makeWebComponentFromFsmThe key objectives for the API was :
As a result of this, the following choices were made :
immutable.js)inputs is a stream of
well-formatted machine inputs, and f is the fsm, then the stream of outputs will be inputs.map (f). It is so simple that we do not even surface it at the API level.Concretely, our state transducer will be created by the factory function createStateMachine,
which returns a state transducer which :
Let us insist again on the fact that the state transducer is not, in general, a pure function of its inputs. However, a given output of the transducer 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 transducer another function which 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.
There are a few things to be acquainted with :
To familiarize the reader with these, we will be leveraging two examples. The first example is the aforementioned password selector. This pretty simple example will serve to showcase the API of the library, and standard state machine terminology. The second example modelizes the behaviour of a CD player. It is more complex, and will feature 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. We will not indigate into the implementation however. For a very advanced example, I invite the reader to refer to the wizard form demo.
We then present into more details the semantics of a state transducer and how it relates to its configuration. Finally we present our API whose documentation relies on all previously introduced concepts.
We will be using as our base example the password selector we discussed previously. As a reminder, its behaviour was described by the following state machine :
To specify our machine, we need :
The first three are clear from the graph. The initial control state can also be deduced from the graph. The initial exxtended state can be derived from the mapping table above describing the behaviour of the password selector.
The fsm ends up being defined by:
const initialExtendedState = {
input: ""
};
const states = {
[INIT]: "",
[STRONG]: "",
[WEAK]: "",
[DONE]: ""
};
const initialControlState = INIT;
const events = [TYPED_CHAR, CLICKED_SUBMIT, START];
const transitions = [
{ from: INIT, event: START, to: WEAK, action: displayInitScreen },
{ from: WEAK, event: CLICKED_SUBMIT, to: WEAK, action: NO_ACTIONS },
{
from: WEAK,
event: TYPED_CHAR,
guards: [
{ predicate: isPasswordWeak, to: WEAK, action: displayInputInRed },
{ predicate: isPasswordStrong, to: STRONG, action: displayInputInGreen }
]
},
{
from: STRONG,
event: TYPED_CHAR,
guards: [
{ predicate: isPasswordWeak, to: WEAK, action: displayInputInRed },
{ predicate: isPasswordStrong, to: STRONG, action: displayInputInGreen }
]
},
{
from: STRONG,
event: CLICKED_SUBMIT,
to: DONE,
action: displaySubmittedPassword
}
];
const pwdFsmDef = {
initialControlState,
initialExtendedState,
states,
events,
transitions
};
where action factories mapped to a transition compute two things :
For instance :
function displayInitScreen() {
return {
updates: NO_STATE_UPDATE,
outputs: [
{ command: RENDER, params: { screen: INIT_SCREEN, props: void 0 } }
]
};
}
The full runnable code is available here.
This example is taken from Ian Horrock's seminal book on statecharts and is the specification of a CD player. The behaviour of the CD player is pretty straight forward and understandable immediately from the visualization. From a didactical point of view, the example serves to feature 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 on control states.H is a pseudo-control state called shallow history stateCD_Paused has the sixth control state as entry point, and the transition from CD_Paused into
that control state is called an automatic transition. Entering the CD_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 transitionsTo illustrate the previously described transducer semantics, let's run the CD player example.
| Control state | Internal event | External event |
|---|---|---|
| INIT_STATE | INIT_EVENT | |
| 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 | -- |
Note :
No Cd Loaded leads to enter CD Drawer ClosedClosing CD Drawer to CD LoadedForward down event transitions the state machines to Stepping forwards, as it applies to all atomic states nested in the CD Loaded subgroup control stateCD Playing the
last atomic state for compound state CD Loaded subgroup.We give here a quick summary of the behaviour of the state transducer :
Preconditions
{{[event_label]: event_data}}Event processing
INIT_EVENT event which advances the state machine out of the reserved internal
initial control state towards the relevant user-configured initial control state
INIT_EVENT event carries the initial extended state as dataINIT_STATE initial control state,
triggered by the reserved initial event INIT_EVENTNO_OUTPUT if none), extended state and control state do not change.
Break away from the loopA few interesting points :
The aforedescribed behaviour is loosely summarized here :
History states semantics
An history state relates to the past configuration 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]:
OUTER control state will have been [OUTER.A, INNER, INNER.S, INNER.T]OUTER control state will correspond to the INNER control
state (the last direct substate of OUTER), leading to an automatic transition to INNER_SOUTER control state will correspond to the INNER.T control
state (the last substate of OUTER before exiting it)In short the history state allows to short-circuit the default entry behaviour for a compound state, which is to follow the transition triggered by the INIT event. When transitioning to the history state, transition is towards the last seen state for the entered compound state.
fsmDef.states) must be unique and be JavaScript stringsfsmDef.events) must be unique and be JavaScript stringsINIT_STATE) cannot be used when defining transitionsfsmDef.statestransitions data structure must be defined in the states data
structureNO_OUTPUT)updates and outputs property (no syntax sugar) (NOT
ENFORCED)
fsmDef.transitionsfsmDef.settings must include a updateState function covering the state machine's extended
state update concern.By initial transition, we mean the transition with origin the machine's default initial state.
guards for the initial transitionAdditionally the following applies :
NO_OUTPUT)fsmDef.initialControlState) must be a state declared in fsmDef. statesINIT_EVENT) are only allowed for transitions involving
compound states
fsmDef.states must be used as target or origin of transitions in
fsmDef.transitionsfsmDef.events must be used as triggering events of transitions in
fsmDef.transitions(from, event, predicate) - sameness defined for
predicate by referential equality (NOT ENFORCED)transitions array of the
state machine (but there can be several guards in that row)
A -eventless-> B, there cannot be a competing
A -ev-> Xev. Such transitions would unduely complicate the input testing generation, and decrease
the readability of the machine so we forbid such transitions1INIT_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 stateupdateState :: 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)Those contracts ensure a good behaviour of the state machine. and we recommend that they all be observed. However, some of them are not easily enforcable :
Contracts enforcement can be parameterized with settings.debug.checkContracts.
We have included two helpers for visualization of the state transducer :
toPlantUml :: FSM_Def -> PlantUml.
toDagreVisualizerFormat :: FSM_Def -> JSON
Automated visualization works well with simple graphs, but seems to encounter trouble to generate
optimally satisfying complex graphs. The Dagre layout seems to be a least worse option. I
believe the best option for visualization is to use professional specialized tooling such as
yed. In a future version, we will provide a conversion to yed graph format to facilitate
such workflow. The yed orthogonal and flowchart layout
seem to give pretty good results.
store.pickOne can be used to select the next transition
The use of state machines is not unusual for safety-critical software for embedded systems. Nearly all safety-critical code on the Airbus A380 is implemented with a suite of tools which produces state machines both as specification and implementation target. The driver here is two-fold. On the one hand is productivity : writing highly reliable code by hand can be done but it is painstakingly slow, while state machines allow to generate the code automatically. On the other hand is reliability. Quoting Gerard Berry, founder of Esterel technologies, << low-level programming techniques will not remain acceptable for large safety-critical programs, since they make behavior understanding and analysis almost impracticable >>, in a harsh regulatory context which may require that every single system requirement be traced to the code that implements it (!). Requirements modeled by state-machines are amenable to formal verification and validation.
State machines have also been used extensively in games of reasonable complexity, and tutorials abound on the subject. Fu and Houlette, in AI Game Programming Wisdom 2 summarized the rationale : "Behavior modeling techniques based on state-machines are very popular in the gaming industry because they are easy to implement, computationally efficient, an intuitive representation of behavior, accessible to subject matter experts in addition to programmers, relatively easy to maintain, and can be developed in a number of commercial integrated development environments".
More prosaically, did you know that ES6 generators compile down to ES5 state machines where no
native option is available? Facebook's regenerator
is a good example of such.
So state machines are nothing like a new, experimental tool, but rather one with a fairly extended and proven track in both industrial and consumer applications.
This library is old and went through several redesigns and a large refactoring as I grew as a programmer and accumulated experience using it. I actually started after toiling with the cyclejs framework and complex state orchestration. I was not an expert in functional programming, and the original design was quite tangled (streams, asynchrony, etc.) and hardly reusable out of cyclejs. The current design resulting from my increased understanding and awareness of architecture, and functional design.
The key influences I want to quote thus are:
Not like it matters so much but anyways. Feel free to skip that section if you have little interest in computer science.
Alright, let's build the concept progressively.
An automaton is a construct made of states designed to determine if a sequence of inputs should be accepted or rejected. It looks a lot like a basic board game where each space on the board represents a state. Each state has information about what to do when an input is received by the machine (again, rather like what to do when you land on the Jail spot in a popular board game). As the machine receives a new input, it looks at the state and picks a new spot based on the information on what to do when it receives that input at that state. When there are no more inputs, the automaton stops and the space it is on when it completes determines whether the automaton accepts or rejects that particular set of inputs.
State machines and automata are essentially interchangeable terms. Automata is the favored term when connoting automata theory, while state machines is more often used in the context of the actual or practical usage of automata.
An extended state machine is a state machine endowed with a set of variables, predicates (guards) and instructions governing the update of the mentioned set of variables. To any extended state machines it corresponds a standard state machine (albeit often one with a far greater number of states) with the same semantics.
A hierarchical state machine is a state machine whose states can be themselves state machines. Thus instead of having a set of states as in standard state machines, we have a hierarchy (tree) of states describing the system under study.
A state transducer is a state machine, which in addition to accepting inputs, and modifying its state accordingly, may also generate outputs.
We propose here a library dealing with extended hierarchical state transducers, i.e. a state machine whose states can be other state machines (hierarchical part), which (may) associate an output to an input (transducer part), and whose input/output relation follows a logic guided by predefined control states (state machine part), and an encapsulated memory which can be modified through actions guarded by predicates (extended part).
Note that if we add concurrency and messaging to extended hierarchical state transducers, we get a statechart. We made the design decision to remain at the present level, and not to incorporate any concurrency mechanism.2
There are however semantics which allow such transitions, thus possibilitating event bubbling. ↩
Our rationale is as follows : ↩
David Harel, Statecharts.History.CACM : Speaking in the strict mathematical sense of power of expression, hierarchy and orthogonality are but helpful abbreviations and can be eliminated ↩
David Harel, Statecharts.History.CACM : <<I definitely do not recommend having a single statechart for an entire system. (...) concurrency occurs on a higher level.)>> ↩
FAQs
State machine library (Extended Hierarchical State Transducer)
The npm package kingly receives a total of 79 weekly downloads. As such, kingly popularity was classified as not popular.
We found that kingly demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Newly introduced telemetry in devenv 1.4 sparked a backlash over privacy concerns, leading to the removal of its AI-powered feature after strong community pushback.
Security News
TC39 met in Seattle and advanced 9 JavaScript proposals, including three to Stage 4, introducing new features and enhancements for a future ECMAScript release.
Security News
Deno 2.2 enhances Node.js compatibility, improves dependency management, adds OpenTelemetry support, and expands linting and task automation for developers.