State machine notes

State machine

AKA finite state machine (FSM)

A machine that

1. can be in exactly one of a finite number of states at any given time

• one of these is the initial state

A state has

1. has a set of transitions defining what other states it may lead to.

• each of a state's transitions may be defined by a condition, usually regarding receiving external events. It could also be the condition of a specified amount of time passing.
• a definition of actions (usually side-effects) that occur when the state is entered, and when the state is exited. (but sometimes, transitions also cause actions).

A state is thus a description of the status of a system that is waiting to execute a transition. Often a transition is named for the event that causes it.

Statecharts (Hierarchical State Machines)

Statecharts are hierarchical state machines, in that one high-level state may contain an entire state machine within it.

• When enterering the high-level state, the sub-statemachine is initialized;
• when leaving the high-level state, the sub-statemachine is terminated (including firing its exit actions).
• the order of execution of entry actions must always proceed from the outermost state to the innermost state
• order of exit actions proceeds in the exact reverse order, starting from the innermost state

A sub-statemachine can contain sub-sub-statemachines and so on.

A super-statemachine could contain more than one sub-statemachine (parallel regions).

Statecharts also introduce the concept of 'history' transitions, which return to the previous state before the current (akin to a 'return' in a function call).

Also the concept of a "guard", which really just seems like adding detail to a condition; a guard can bail an event's transition if other conditions are not met.

Often the majority of a statechart (sometimes all of it) can be defined as a declarative data structure (e.g. see xstate.js)

See

• https://statecharts.github.io
• https://barrgroup.com/embedded-systems/how-to/introduction-hierarchical-state-machines
• https://xstate.js.org/docs/

Rationale

• easier to understand
• reduces bugs, scales well with complexity
• behaviour decoupled from components (e.g. can be declarative), supports agile/exploratory dev

Making the abstract state machine fully declarative data structure:

• an initial state (string)
• a dictionary of named finite states, each having
  • named actions (with arguments?) generated on entry & exit of the state
  • a list of sub-state machines, defined in the same way as the top-level state machine
  • a dictionary of named events it can handle (with arguments?), each with
    • optional conditions

Here events come in to the system, in series, as string names and perhaps additional context data to be used in conditions; and actions come out of the system in a similar way (e.g. they can be accumulated into a FIFO list, or invoke handlers immediately)