Home

Awesome

Modelize your interfaceEncode the graphRun the generated machine!
password submit fsmpassword selector fsm transitionspassword selector

npm version Contributions welcome

Table of Contents

Features

This library enables you to implement the behaviour of your user interfaces or components as state machines. The behaviour is the relation between the actions performed on the user interface (button clicks, etc.) and the actions (commands) to perform on the interfaced systems (fetch data, display screens, etc.). You specify the machine as a graph. The library computes a function which implements the state machine which specifies the behaviour. You drive your interface with that function, you display the UI with the UI framework of your choice.

Salient features:

Documentation

All documentation can be accessed in the dedicated web site.

Tooling

Kingly has been used to implement large applications such as Conduit, a simplified Medium's clone. On such a large machine, the process has been significantly smoothed by using the free professional graph editor yEd to produce the machine graphs.

In summary, Kingly has the following tools available:

devtool screenshot

Examples

You can review the following examples which have been implemented with the same state machine, across different UI frameworks, with links to the corresponding codesandboxes. Note that the examples may use older versions of Kingly.

Trivial counter application

State MachineDemoUI library
trivial counter fsmtrivial counter demoVanilla JS

Password meter

State MachineDemoUI library
password submit fsmpassword meter demoVanilla js<br>Nanomorph<br>Vue

Movie database search interface

State MachineDemoUI library
movie app machinemovie app demoVue<br>React<br>Ivi<br>Inferno<br>Nerv<br>Svelte

Wizard forms

State MachineDemoUI library
wizard form machinewizard form demoCycle JS

Motivation

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.

The major motivation for this library is 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.

Jump to the tutorials.

This library was born in early 2016 from:

In the four years of existence and use of this library, we reached an API which should be fairly stable. It has 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:

Install

npm install kingly --save

Cf documentation

Tests

To run the current automated tests: npm run test

Integration with UI libraries

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 with the exact same fsm. By isolating your component behaviour in a fsm, you can delay the UI library choice to the last moment.

API design

The key objectives for the API was:

As a result of this, the following choices were made:

Concretely, our state machine will be created by the factory function createStateMachine, which returns a state machine which:

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 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.

Visualization tools

We have included two helpers for visualization of the state machine:

visualization example

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. We provide a CLI for conversion to yed graph format to facilitate such workflow (cf. yed2Kingly). The yed's orthogonal and flowchart layout seem to give pretty good results.

Credits

Roadmap

Roadmap v1.0: complete core, set API in stone

Roadmap v1.X: consolidate

Roadmap v1.Y: testing

Who else uses state machines

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.

About the name

We call this library "Kingly" to express it allows developers to rule their UI -- like a king. Developers define rules in the machine, in the form of control states and guards, those rules define what is possible and what is not, and what should happen in response to events.

And also, the other names I wanted were already taken :-).

Acknowledgments

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:

Annex

So what is an Extended Hierarchical State Transducer ?

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.1

Footnotes

  1. Our rationale is as follows:

  2. 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

  3. David Harel, Statecharts.History.CACM: <<I definitely do not recommend having a single statechart for an entire system. (...) concurrency occurs on a higher level.)>>