Deterministic Hierarchical Finite State Machine

This article is about Deterministic Hierarchical Finite State Machines (DHFSM) and how we use them to build applications - especially web applications.

Finite State Machines - FSMs - is a very old and well known formalism used to describe the behavior of dynamic systems as a set of states and transitions between them, triggered by events.

The main idea is the following:

1. The system can be in one and only one possible state at the time
2. For finite state machines the number of states is limited and known in advance.
3. The system can change its state - perform a transition - when an event occurs. In deterministic state machines the result of such a transition is solely defined by the previous state and by the type of event.
   

Note: A very important consequence of the second rule is: given a state and a sequence of events, the system will always arrive exactly in the same target state. We can deterministically “replay” a specific process by defining the initial system state and a sequence of events with associated data.

As an example let’s describe a very simple behavior of an electrical device using the following schema:

Now we need to describe with more details what happens when this device is switched on:

We see that initially this system enters in the “Waiting” state and when it receives a call it starts ringing. After that we can start to talk or to record a message. And finally it goes back to the waiting state. This statechart describes the behaviour of a telephone or a voice messaging application. All mentioned above states - “Waiting”, “Ringing”, “Talk”, “Recording” - are sub-states of the “On” state. So we are talking about an Hierarchical Deterministic Finite State Machine.

Hierarchical FSMs allow us to describe behaviour and logic of much more complex systems than simple “flat” FSMs.

Application Development Without FSMs

In existing systems very often - almost always - the application logic is spread over the code in various modules asynchronously sending data, receiving data and exchanging messages between them. Part of the logic is hidden behind UI components, part is implemented on the server and partially in client libraries managing the internal application state.

The complexity of such applications grows exponentially with the number of implemented features. As a result the complexity of bug fixing, maintenance and evolution of these applications also grows exponentially.

Using HFSMs as the main backbone allows to reduce the growth of application complexity from exponential to linear:

FSM as the Application Backbone

A FSM statechart defining the application logic can be seen as a skeleton - it defines in advance what the application can or can not do. It defines all possibilities and application constraints in a minimalistic and explorable way. By the structure of the skeleton specialists immediately can say a lot about the whole organism and its potential behaviour.

By analyzing states and events triggering transitions, the FSM engine can check the logical validity of statecharts and detect many errors even before starting the application process.

With this approach our applications can be compared with PowerPoint presentations. The PowerPoint itself can be considered as a simple Finite State Machine Engine showing "executing" sequentially individual presentation slides. We can view many presentations without changing the engine. In our case the HFSM engine works in a similar way - it loads the application description and starts the show. The difference with the PowerPoint is that instead of visualizing slides the FSM engine changes the application states and notifies all registered handlers about state activations / deactivations. These handlers can process, load or store data, show information on the screen, receive and validate user’s input etc.

Very important feature of this architecture is that the same logical process can have various numbers of registered handlers organized in “layers”:

In early stages of the application development the FSM engine can visualize textual descriptions and low-fidelity UI prototypes for each process state. It can be something very simple, like scanned jots on a piece of paper. At the next stage designers will add to the same process detailed screen visualizations. The next layer will bring HTML components for each state. And, finally, developers will add their code dealing with real data.

Every stage in the application development adds a new layer of handlers without removing or duplicating efforts of all other stakeholders implied in the development process and all the time - starting from the very first hand-drawings - we have an operational application.

At the final stage the resulting application uses only layers required in production. Everything else - like design sketches, docs, low-end UIs - can be used for documentation purposes during the whole application lifecycle. These layers can be visualized at any moment in parallel with the real application to describe and explain how the system works.

All changes in the application logic - in statecharts - are immediately visible for all implied participants. If developers add or remove some states it becomes immediately clear if some modifications in UIs should be introduced by designers. And vice versa. So the FSM is not only the skeleton for the application, it also becomes the central communication backbone for all specialists involved in the application development, greatly facilitating exchanges between teams of different skills

Conclusion

FSM-based approach for application building has the following advantages:

• FSM allows explicitly define and show the application logic
• Many logical application problems can be detected even before the application is launched which reduces significantly the number of possible bugs at run-time.
• Users can dispose of an up and running application at all development stages - from initial jots on papers until the released application
• The same statecharts can be used to launch multiple versions of the same application: it is very easy to have a demo and full version of the same application
• It enables tight collaboration between all implied participants - designers, integrators, developers since communication is greatly facilitated using FSM

The architecture of the applications developed by Georito is based on these principles