| 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.
createStateMachine :: FSM_Def -> FSMThis FSM factory function takes the parameters defining the behaviour of the state transducer,
and returns the created state transducer. The created state transducer is a regular function called
with inputs which are passed to the encapsulated state machine, which computes the function's
output. The syntax for an input is {{[eventLabel] : eventData}}, i.e. an input is an object
with exactly one key, which is the event identifier, and the value matching the key is the event data.
The machine additionnally may carry over environment variables, which are accessible in guards, and action factories. This helps maintaining such functions pure and testable. Environment variables can also be used to parameterize the state machine's behaviour.
History pseudo states are generated by a helper function historyState :: HistoryType -> ControlState -> HistoryPseudoState. An history state is coupled to a
compound control state, and has a type (deep or shallow). Passing this information to the factory
produdces the sought history state.
The settings.updateState property is mandatory, and specify how to update a model from the .updates produced by an action factory. We used successfully JSON patch operations for model updates, but you can choose to use the inmutable library of your choice or a simple reducer. The
important point is that the extended state should not be modified in place, i.e. updateState is
a pure function.
The settings.debug.checkContracts, when set, represent contracts that the state machine must
fulfill. The state-transducer library comes by default with a set of contracts enforcing most
of the syntax and semantics of the state machine format chosen.
The settings.debug.console, when set, represent a console object through which tracing and
debug info will flow. This is useful in development and can be turned off in production.
settings.updateState property is mandatory!settings property should not be modified after being passed as parameter (i.e. should
be a constant): it is not cloned and is passed to all relevant functions (guards, etc.)We are going to show the definition for the following hierrchical state machine :
The definition is as follows :
const states = { [OUTER]: { [INNER]: { [INNER_S]: '', [INNER_T]: '' }, [OUTER_A]: '', [OUTER_B]: '' }, [Z]: '' };
const fsmDef = {
states,
events: [EVENT1, EVENT2, EVENT3, EVENT4],
initialExtendedState: { history: SHALLOW, counter: 0 },
transitions: [
{ from: INIT_STATE, event: INIT_EVENT, to: OUTER, action: ACTION_IDENTITY },
{ from: OUTER, event: INIT_EVENT, to: OUTER_A, action: ACTION_IDENTITY },
{ from: OUTER_A, event: EVENT1, to: INNER, action: ACTION_IDENTITY },
{ from: INNER, event: INIT_EVENT, to: INNER_S, action: ACTION_IDENTITY },
{ from: INNER_S, event: EVENT3, to: INNER_T, action: ACTION_IDENTITY },
{ from: INNER_T, event: EVENT3, to: INNER_S, action: ACTION_IDENTITY },
{ from: INNER, event: EVENT2, to: OUTER_B, action: ACTION_IDENTITY },
{ from: OUTER, event: EVENT1, to: Z, action: ACTION_IDENTITY },
{
from: Z, event: EVENT4, guards: [
{
predicate: function isDeep(x, e) {return x.history === DEEP},
to: historyState(DEEP, OUTER),
action: incCounter
},
{
predicate: function isShallow(x, e) {return x.history !== DEEP},
to: historyState(SHALLOW, OUTER),
action: incCounter
}
]
},
],
settings : { updateState : applyJSONpatch }
};
Note in particular :
statesACTION_IDENTITY when there is no action to be applied
NO_OUTPUThistoryStateThere are plenty of additional examples in the test directory.
traceFSM :: Env -> FSM_Def -> FSM_DefThis function converts a state machine A into a traced state machine T(A). The traced state
machine, on receiving an input I outputs an object with the following information :
outputs : the outputs A(I)updates : the update of the extended state of A to be performed as a consequence of receiving the input IextendedState : the extended state of A prior to receiving the input InewExtendedState : the extended state of A after receiving the input I and computing
the outputscontrolState : the control state in which the machine is when receiving the input Ievent::{eventLabel, eventData} : the event label and event data corresponding to Isettings : settings passed at construction time to AtargetControlState : the target control state the machine has transitioned to as a consequence of receiving the input Ipredicate : the predicate (guard) corresponding to the transition that was taken to
targetControlState, as a consequence of receiving the input IactionFactory : the action factory which was executed as a consequence of receiving the
input IguardIndex : the index for the guard in the .guards array of a transition away from a
control state, triggered by an eventtransitionIndex : the index for the transition in the .transitions array which contain the
specification for the machine's transitionNote that the trace functionality is obtained by decorating the action factories in A. As
such, all action factories will see their output wrapped. This means :
null.Note also that env is not used for now, and will be used to parameterize the tracing in future
versions of the library.
Cf. tests
makeWebComponentFromFsm :: ComponentDef -> FSMThis factory function creates a web component which takes no observed attributes or properties. The behaviour or logic of the component is parameterized by the machine passed as parameter. The communication capability of the component is parameterized by subjects generated from a subject factory passed as parameter. The command handling capability are provided by command handlers and effect handlers passed as parameters. An initial event, terminal event (unused for now), and a moniker indicating absence of actions to perform can be passed as options.
The web component receives input through its input subject, passes to the encapsulated machine which computes outputs and the component subsequently process those outputs via the command handlers. The web component may or may not use the output subject to emit events. At the moment, we do not have any example or test covering this use case.
Component whose behaviour is defined by a machine can be seamlessly integrated into any framework by converting to web component. Note however that the portion of the web component specification used, custom elements v1, is only supported in modern browsers. In the web component scenario, communication betwween the web component and other framework's component occurs through the input and output subject or DOM events. It is not possible to use any facility provided by the framework.
We have implemented a movie search app with Nerv, a lightweight React clone which works with browsers down to IE8. The entry file can be found here.
const fsm = createStateMachine(movieSearchFsmDef, {
updateState: applyJSONpatch,
debug: { console }
});
function subjectFromEventEmitterFactory() {
const eventEmitter = emitonoff();
const DUMMY_NAME_SPACE = "_";
const _ = DUMMY_NAME_SPACE;
const subscribers = [];
return {
next: x => eventEmitter.emit(_, x),
complete: () => subscribers.forEach(f => eventEmitter.off(_, f)),
subscribe: f => (subscribers.push(f), eventEmitter.on(_, f))
};
}
const nervRenderCommandHandler = {
[COMMAND_RENDER]: (next, params, effectHandlers, el) => {
const { screen, query, results, title, details, cast } = params;
const props = params;
render(screens(next)[screen](props), el);
}
};
const commandHandlersWithRender = Object.assign(
{},
commandHandlers,
nervRenderCommandHandler
);
const options = { initialEvent: { [events.USER_NAVIGATED_TO_APP]: void 0 } };
makeWebComponentFromFsm({
name: "movie-search",
eventSubjectFactory: subjectFromEventEmitterFactory,
fsm,
commandHandlers: commandHandlersWithRender,
effectHandlers,
options
});
render(h("movie-search"), document.getElementById("root"));
Because of the API design choices, it is possible to realize the possible extensions without modifying the state chart library (open/closed principle):
INIT transition (by contract there is exactly one such
transition) and the initial_extended_state; and leaving everything else intactNote that some extensions may perform effects (logs, ...), meaning that the order of evaluation and application of operations would then become significant in general. Extension performing effects should only be used in development.
Equipped with a history of inputs and the corresponding history of outputs, it is also possible to do property-based testing (for instance checking that a pattern in a sequence of outputs occurs only when a pattern occurs in the matching sequence of inputs).
Some extensions may be useful to check/test the design of the automata, i.e. checking that the automata which acts as modelization of requirements indeed satisfies the requirements. When sufficient confidence is acquired, those extensions can be safely removed or deactivated.
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.
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
In this section, we seek to define quickly the meaning of the key terms which will be commonly used when referring to state machines.
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.