Executable finite state machines
state resources
Executable machines

Harel statecharts were always intended to be executable; reading the UML Superstructure specification, there are hints to their state machine execution behaviour. State.js and state.cs are a high performance implementation of executable state machines that support a subset of UML state machines that are relatively close to Harel’s statecharts. They are high performance in that all operations required to effect a state transition, including user specified behaviour, and regardless of model complexity, are pre-computed and cached for faster run-time execution.

To better explain state machine execution, we need to define three main areas of responsibility:

  • The state machine model definition.
  • The active state configuration of a state machine instance at runtime.
  • The runtime engine that evaluates events, causing transitions.
State machine model

The state machine model is purely a representation of the structure of a state machine coded in objects representing regions, states, pseudo states and transitions. User defined behaviour for state entry, state exit and transitions are also defined within the model; each can have multiple callbacks defined. A set of classes and enumerations are provided in state.js and state.cs to build models. The state machine model implements a visitor pattern to allow visitors to walk the tree structure of a state machine.

Vertex NamedElement Region Dynamic connector.7 State Dynamic connector.9 PseudoState Dynamic connector.11 StateMachine FinalState Dynamic connector.15 regions vertices Transition from to

Fig.1: Meta-model implemented by state.

It should in theory be possible to generate much of the code for state machine models from XMI or other such model languages.

There is nothing sophisticated in these classes and enumerations, they are solely used to describe the state machine model and broadly follow the UML Superstructure Specification for State Machines.

Active state configuration

A state machine’s active state configuration maintains the last known child state of all regions within a state machine model that have been entered; this definition is written very deliberately, as the need to implement history semantics requires us to maintain the last known active state of a region after the region’s parent has been exited (and therefore made the region and its parent state inactive).

Within state.js and state.cs, it is possible to have many active state configurations for a given state machine model. These are referred to as state machine instances. Many examples of state machines model physical devices, such as digital watches or vending machines, in these circumstances there is usually one instance for the model, however in many software applications we may have many instances of a given model.

State machine instances vary depending on the language; in C# it is defined as an interface that must be implemented, whereas in JavaScript the interface is more implicit, if an object contains the correct methods, it can be used as a state machine instance.

The callbacks defined within the state machine model can take as a parameter the specific state machine instance that is being operated on, thereby allowing you to build complex domain classes that combine you domain specifics with active state configuration.

Runtime

The runtime engine is further split into two halves:

  • A just in time pre-compiler that evaluates all transitions to compute the behaviour require to traverse it.
  • An engine that evaluates messages and effect state transitions accordingly.
Pre-compiler

The pre-compiler is the true heart of state.js and state.cs, it evaluates the state machine model in a number of passes to determine all the actions to perform during traversal.

The first pass uses a visitor to walk the state machine structure, building up the set of actions for the entry and exit of each element within the state machine hierarchy. The actions for state entry are split into two types as there are various ways to enter a state, simple entry and cascaded entry; simple entry consists of the user defined entry behaviour and updating the active state configuration, whereas cascaded entry enters the all the child hierarchy of the state as necessary. The exit actions do both, user defined behaviour and cascade of the exit operation to any child hierarchy as needed.

The second pass deals with the transitions; is where the interesting logic lies. Transitions have three kinds according to the UML specification, internal, external and local. Internal transitions do not effect a local transition, they just executes the user defined behaviour; external transitions perform a state transitions that exit the source, performs user defined transition behaviour and enters the target. Exiting the source is a complex operation: firstly, the exit operation is cascaded to any and all child active state in a depth first manner; the state is exited, including any user defined exit behaviour; finally, if the source and target states are in different regions, all active states between the source and the least common ancestor are also exited. State entry is largely a mirror of state exit. Local transitions are a small variant on external transitions where the target is a part of the source’s child hierarchy; in this case there is no exiting of the source as it remains active.

Given the confluence of the wide semantics of state machines, it is not alway possible to know the exact behaviour during this compilation phase, some of the actions just defer small decision making to runtime; this is especially relevant for the implementation of history.

The state machine model is compiled when the model is initialised; model initialisation is triggered implicitly on the first call to initialise a state machine instance using the model.

Each time the state machine model changes it is marked as dirty; the next call to the engine will trigger recompilation unless explicitly directed otherwise. This enables the state machine model to be dynamically extended during the programs runtime execution. As a state machine instance references particular states as part of its active state configuration, only additive changes are permitted (though removal of transitions and pseudo states is feasible this is not currently implemented in state.js or state.cs).

Engine

The engine is realised by a single function call evaluate; this takes message, state machine model and state machine instance, and performs state transitions as required.

It does this by a depth first traversal of the state machine instance’s active state configuration, finding transitions whose guard conditions evaluate positively. One found, the transition is traversed by executing all the actions that the pre-compiler determined.

Once a transition has fired for a state, parent states are not evaluated. It is possible for multiple state transitions to occur within orthogonal regions of a state machine model.