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 (e.g. a timeout).
• 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 (including firing its entry actions).
• 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 high-level transition can point to a specific state in a sub-statemachine

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

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

• History is a state that a transition can point to
• History may also keep track of states in sub-machines (marked H* in Harel)
• Q: is history cleared/reset when super-state exited, or retained?

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. Conditions may even include the states of other parellel regions.

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

• each region is named; and the state containing all the regions is named
• entry to super state initializes all sub-regions
• entry from a super-state to a sub-state in one region will initialize other regions with their default states
• a sub-region can transition to a super-state, which would force other sub-regions to exit
• an event can be handled by multiple sub-regions at once
• regions are mostly orthogonal: a transition in one has no effect on a sibling region (but transitions might be conditional on other regions' current states)
• Q: in what order do sub-regions process an event?
• Q: is the effect of an event in one sub-region processed to completion before considering the next, or do they advance more incrementally in parellel (cf. differences of depth-first/breadth-first traversal)

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/
• Harel, David. "Statecharts: A Visual Formalism for Complex Systems." Science of Computer Programming 8, North-Holland, 1987.

Rationale

• easier to understand; brain adapts well to discrete states and hierarchies
• can be designed as a diagram
• 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)