Late in 2017, I surveyed my fellow developers. The survey had only two questions: do you know what state machines are and do you use them. The staggering 95% had no idea on the subject. One of the developers said: "I know what state machines are but I don't need to worry about them because I develop software, not hardware." It's like saying "I write C#, so I don't need the internet. It's the Java programmers who surf the internet."
State machines are not limited to electronics. State machines are a universal tool for modeling behavior. Every piece of software that runs longer than a fraction of a second has behavior. Therefore, almost all programs could benefit from state machines.
The demo
Press the buttons below to play with the lift.
A hierarchy of machines
This demo uses several state machines to control a virtual lift. Having more than one machine is a typical situation.
Most practical applications are too complex to be modeled with just one automaton.
The state machines in the demo form a tree-like structure, a hierarchy.
It is essential to have a hierarchy. An unrestricted net of machines, where all can connect to all, is hard to test and support.
In an event-driven environment, a master machine talks to a slave machine by calling methods, as if the slave machine was a regular class.
The slave machine, however, can only communicate with its master by sending messages through the event loop.
The requirement to arrange machines in a tree is sometimes too strict. For practical purposes, it is okay to add some additional links between the machines.
The important thing is that the graph of machines must not have cycles.
A machine that sits lower in the graph must never directly call methods of the machine above it.
DRAKON makes automata-based programming practical
Even though state machines are a solid concept, it is hard to use them.
The mainstream programming languages do not have first-class support for state machines.
If a programmer wants to make a machine, he has to follow some informal patterns in code.
Such hand-made machines are better than just classes, but they are not easy to comprehend.
Visualization might help. But how to draw a state machine?
The traditional state machine diagrams are confusing and inconsistent.
They do not give quick answers to questions like "which signals does this machine accept in this specific state?"
or "which states can the machine switch to from this state?"
Another problem is that the programmer often needs to manually write part of the machine in a separate file.
These difficulties seem to be the reason why the software industry does not widely accept state machines.
The DRAKON visual language could be a solution to these problems.
A state machine can be represented with a DRAKON chart of type "silhouette".
Silhouette combines state machines with decision trees.
A silhouette diagram shows the states, the transitions, and the machine's decision logic in the same visual scene.
As a result, working with machines becomes easier.
Another benefit of using DRAKON for state machines is that DRAKON is an ergonomically optimized visual language. DRAKON diagrams are clean, predictable and consistent.
How to build a state machine with DRAKON
This demo shows a way to represent state machines with DRAKON silhouette diagrams. This is how to turn a DRAKON chart into a state machine:
Add the "state machine" keyphrase to the Parameters icon (the rectangle at the left top corner).
Each silhouette branch becomes a state.
Every branch must have a Switch icon with the "receive" keyword. The Case icons define the signals that the machine will accept and hence the methods that the generated class will have.
The Address icons at the bottom control state switching.
This way, DRAKON Editor generates one state machine class from one silhouette diagram.
The machines from the demo
The Door controls the inner and outer lift doors as one. There are one internal door and several external doors, one per floor. motor.connect() method connects the inner door to one of the outer doors.
The Door translates the logical "opened" and "closed" positions into coordinates and sends them to the motor.
The Door can have the following states: Closed, Opening, Open, and Closing.
When the door is in the Closed state, it accepts only the "open" message. Having gotten this message,
the door sends a command to the motor to open the physical door and enters the Opening state.
While in the Opening state, it is possible to send the "close" message to the Door and it will start closing.
When the motor has fully opened the physical door, it sends the "done" message to the Door.
The Door reports that it is now officially open.
When the Door is in the Open state, it accepts only the "close" message. The Closing state is similar to Opening. While Closing, the Door is waiting for the "done" message from the motor to switch to the Closed state.
The Cabin translates floor numbers into coordinates and controls the motor that moves the lift cabin.
A cabin can be either moving or standing still. These two possibilities make up the states of the Cabin machine: Moving and Still.
Having gotten the "move" command, the Cabin sets the new target for the motor. "move" is accepted in both Moving and Still states. While the cabin is moving, it waits for the "done" message from the motor. "done" means the motor has transferred the cabin to the target floor.
The job of the Scheduler is to choose the next floor.
The Scheduler makes this choice based on three pieces of information: which buttons are pressed, the direction of movement—up or down, and the current floor.
The direction of movement is stored as the state: Up or Down.
The current floor comes to the Scheduler in the "chooseNext" message.
The knowledge about pressed buttons is kept in the slave machine "buttons". Since "buttons" is a slave machine, the Cabin can call the methods of the "buttons" machine directly.
If the lift is moving up towards the fourth floor and button 3 inside the cabin is pressed, the Scheduler will decide that the lift should stop on the third floor first.
But if button 3 inside the cabin is not pressed and the "Down" button on the third floor is pressed instead, the lift should skip the third floor and proceed to the fourth.
LiftMain is the king of the hierarchy in this example. LiftMain makes the decisions what to do next based on user input and events from the lift machinery.
LiftMain is effectively a class because it has only one state: Ready.
Here are the rules that LiftMain implements:
"When the cabin stands on a floor and a button corresponding to that floor is pressed, open the door."
A signal that a button is pressed comes to LiftMain in the form of a "go" message.
Note that this message comes from the outside, but does not hit LiftMain directly.
First, the button press event is handled by the Buttons machine. Then, it goes up to the Scheduler and then the Scheduler forwards the message to the LiftMain.
Remember, that the topmost machine is responsible only for strategic decisions. Not all incoming messages should bother the boss.
"When a button is pressed and that button does not point to the current floor and the door is closed, go to the respective floor."
This combination of conditions is handled by the same decision tree for the "go" message.
"When the door opens, close the door after 2 seconds." LiftMain finds out that the door is open after getting an "opened" message from the Cabin.
"After the door closes, move the lift to the next scheduled floor." The Door machine notifies LiftMain that the door is closed by sending a "closed" message.
"When the lift arrives at a floor, open the door." When the Cabin comes to a floor, it sends an "arrived" message to LiftMain.
What exactly is awesome here?
DRAKON shows both the state machine and the decision trees for transition logic on the same diagram.
Other types of state machine diagrams are not as useful as DRAKON in representing transition logic.
On a UML statechart, for example, it is possible to specify which combination of conditions triggers a specific state transition of the machine.
However, these combinations of conditions are encoded in textual logical formulas like this one: X1 and X2 and not X3 or X4.
Textual logical formulas are hard to read. DRAKON offers visual decision trees which are a significant improvement over textual formulas.
Instead of deciphering the formula, the developer follows the paths that go through the decision tree.
Decision trees make automata easier to comprehend, and that increases the developer's productivity and reduces the number of errors.
Another benefit is the ability to alternate between questions and actions in a decision tree. Let's take the Scheduler machine as an example.
In the handler of the "chooseNext" message in the "Up" state, the Scheduler tries to find if there is a pressed button that wants the lift to go above the current position. The scheduler queries a slave machine to get this information. If no such button is pressed, the scheduler asks the slave if there are any requests to send the lift down from its current position.
This sequence of interactions with the slave machine goes down a continuous path through the decision tree. There is no need for "technical" states that interrupt the flow, like "waiting for a response from the slave machine."
As a result, the machine states in the system are concrete observable modes of operation.
A lift cabin can be either moving or standing still.
Such concrete states are intuitive; they are easy to find during the design stage.
Testing
Behavior is notoriously difficult to test. The number of possible paths that a typical interactive program has is combinatorial.
Besides, the previous actions affect the program's state,
and thus its future responses.
State machines drastically reduce the number of combinations that need to be tested. However, to be useful, state machines must be organized in a strict hierarchy.
A well-chosen hierarchy removes irrelevant combinations of states.
DRAKON helps create test scenarios. Here is how: for each state we go over each message that the machine accepts in that state.
We take each silhouette branch one-by-one and then iterate over the Case icons under the "receive" keyword. For each Case icon, we write short tests. We make one test for every path that starts with that Case icon.
Every test runs one real state machine surrounded by mocks. Since a machine can talk only to its master and immediate slaves, mocking is easy. All tests have a similar structure. First, we build the machine tree and assign input values to the properties of the mocks and the machine under test. Then, we send a message to the machine and finally, check the expected values.
Run the tests now
Conclusion
State machines are an efficient technique for modeling behavior.
Since behavior permeates most types of the modern software, state machines can be of great help to many developers.
Unfortunately, software developers rarely use state machines because it is hard to work with them.
DRAKON changes the way how we build and test state machines.
Thanks to DRAKON, automata-based programming becomes as practical and affordable as object-oriented programming.
