Zero-cost state-machine library for robust, testable and portable user interfaces (most machines compile ~1-2KB)
|Modelize your interface | Encode the graph | Run the generated machine! | |---|---|---| | ||
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.
All documentation can be accessed in the dedicated web site.
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:
.graphmlfiles to Kingly state machines
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.
| State Machine | Demo |UI library |---|---|---| |||Vanilla JS
| State Machine | Demo |UI library |---|---|---| |||Cycle JS
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.
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:
npm install kingly --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 with the exact same fsm. By isolating your component behaviour in a fsm, you can delay the UI library choice to the last moment.
The key objectives for the API was:
As a result of this, the following choices were made:
inputsis a stream of well-formatted machine inputs, and
fis 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 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.
We have included two helpers for visualization of the state machine:
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. We provide a CLI for conversion to
yedgraph format to facilitate such workflow (cf. yed2Kingly). The
yed's orthogonal and flowchart layout seem to give pretty good results.
store.pickOnecan 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".
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.
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 :-).
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: - cyclejs, but of course, from which I started to understand the benefits of the separation of effects from logic - elm - who led me to the equational thinking behind Kingly - erlang - for forcing me to learn much more about concurrency.
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]
[^2]: Our rationale is as follows:
- statecharts include activities and actions which may produce effects, and concurrency. We are seeking an purely computational approach (i.e effect-less) to facilitate composition, reuse and testing. - In the absence of concurrency (i.e. absence of parallel regions), a statechart can be turned into a hierarchical state transducer. That is often enough! - there is no difference in terms of expressive power between statecharts and hierarchical transducers[^4], just as there is no difference in expressive power between extended state machines and regular state machines. The difference lies in naturalness and convenience: a 5-state extended state machine is easier to read and maintain than the equivalent 50-state regular state machine. - we argue that convenience here is on the side of being able to freely plug in any concurrent or communication model fitting the problem space. In highly concurrent systems, programmers may have it hard to elaborate a mental model of the statecharts solely from the visualization of concurrent statecharts. - some statecharts practitioners favor having separate state charts communicating[^5] in an ad-hoc way rather than an integrated statechart model where concurrent state charts are gathered in nested states of a single statechart. We agree.
[^3]: As a matter of fact, more than 20 different semantics have been proposed to define precisely the concurrency model for statecharts, e.g Rhapsody, Statemate, VisualMate, StateFlow, UML, etc. do not share a single concurrency model. [^4]: 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 [^5]: David Harel, Statecharts.History.CACM: <>