State Machines in DRAKON Editor

Home

By Stepan Mitkin

What is a state machine?

A state machine is an object that can alternate between different types of behaviour.

Another name for state machines is finite automata.

State machines are useful for a wide range of tasks. Solutions to many kinds of problems can be conveniently expressed as a state machine.

This abstraction is powerful and important. Unfortunately, one will rarely find it amongst the list of "patterns" that are taught to beginner programmers.

Which properties does a state machine have?

  • It is an object that by default is sitting and doing nothing.
  • It can respond to messages of certain types.
  • It is in a state. There can be several states that the machine can be in.
  • How exactly the machine will react to a message depends on:
    • the current state;
    • the type of the message.
  • After the machine has handled the message, it can shift to another state.

A class in object-oriented programming can be defined as a state machine with only one state. The term "state" here has a special meaning. It is not "the value of the fields and properties of an object". The state of a state machine refers to one of its mutually exclusive modes of operation. For example, a light switch can have two states, "on" and "off".

A state machine is an entity that operates in a stream of events. The actual reaction to each event depends on the type of the event and the previous events. This explicit reference to the past is what makes a state machine different from a class.

There are many uses of state machines. Let us mention a couple of them.

State machines can serve as workhorses in list and graph traversal. For example, they are pretty common in parsers and lexers.

A state machine that reads through a list can be seen as a simple robot that travels along that list. When traversing a graph, state machines can spawn child state machines at nodes with several outgoing edges. These child machines can independently follow different paths in the graph.

Another important application of state machines is control algorithms. Control algorithms are special. Normal, conventional algorithms must finish after a finite number of steps. Control algorithms, in contrast, execute forever. At least until stopped from outside. They implement behaviour of an object in a dynamic world. Those objects range from spacecrafts to GUI elements.

Many control algorithms are easily seen as a state machine. Often, as a hierarchy of state machines.

State machines and DRAKON

State machines can be represented using DRAKON. Here is how:

  1. Use the silhouette diagram type.
  2. The text in the "Formal parameters" icon should start with "state machine".
  3. The branches of the silhouette will define states.
  4. The leftmost branch becomes the initial state.
  5. The rightmost branch becomes the CleanUp method.
  6. The first icon in every branch (except the last) should be a "Select".
  7. The "Case" choices of the "Select" icon identify the message types.

Each state machine diagram will produce a class.

If "state machine" is the only text in the icon, the state machine will be weakly typed. A weakly typed machine will have a single method OnMessage for handling all message types. The actual message type will be determined by the Code field of the message parameter.

If there are parameters after the line with text "state machine", a strongly typed machine will be generated. A strongly typed machine will have one method per message type.

The implementation of state machines in DRAKON Editor

DRAKON Editor can generate source code from state machine diagrams in the DRAKON visual language.

Here is a real state machine in DRAKON-C#. It is a lexer that breaks text up into tokens.

Text that this lexer can handle may look like this:

var foo = bar.SomeMethod(n + 10/x);

What code comes out of the diagram above?

The result is a class that looks as follows:

class LexerMachine
{
    public void Whitespace(char c);
    public void Letter(char c);
    public void Digit(char c);
    public void Operator(char c);
}

The class name will be taken from the diagram name.

It has four methods that correspond to the accepted message types. This automaton accepts only these message types:

  • Whitespace
  • Letter
  • Digit
  • Operator

These methods run code that handles messages of a specific type. The actual code that is invoked in these methods depends on the current state. This automaton can be in one of the following states:

  • Idle
  • Identifier
  • Number
  • Operator

States and message types

Where do the states and message types come from?

The states are defined by the silhouette branches. All branches, except the last, determine:

  • the name of the state (comes from the branch name);
  • the behaviour of the automaton in this state (comes from the algorithmic content of the branch).

The last branch designates the final state. The automaton does not accept messages in the final state. Doing so generates an error. In this specific lexer state machine the last branch is not referenced.

The first icon in the branch must be a "select" icon with text receive.

The message types are defined by the "case" icons under the receive.

Message types

The signature

The signature (the list of accepted method arguments) is taken from the "formal parameters" icon.

The signature

An example of a strongly typed automaton:


state machine
int a
string b
SomeClass c

This will produce the following signature:

public void Foo(int a, string b, SomeClass c);

All methods that handle messages will have the same signature. Message handlers of different state machines can, of course, have different signatures.

An example of a weakly typed automaton:

Weakly typed

This will produce the following signature:

void OnMessage(IRuntime runtime, int myId, Message message);

See the working example in the example/automaton folder in the DRAKON Editor distributive.

Why is DRAKON so fit for state machines?

Using DRAKON to draw state machines has a clear benefit. Both the algorithmic part of the automaton and the state switching logic are placed on the same diagram.

The unique feature of DRAKON is that it shows a state diagram and decision trees on the same visual scene.


Updated on 29 December 2014

Contact: drakon.editor@gmail.com