The Synthesis of SMACC

Introduction

As one begins a study into the history of state machines in computing, it’s important to understand that humans have been using concepts like procedures and states, long before academic applied the formalism that we use in computer science today.

See for example..

Mealy & Moore

The history of state machine formalism typically begins George Mealy’s 1955 paper A Method for Synthesizing Sequential Circuits, and Edward Moore’s 1956 paper Gedanken-experiments on Sequential Machines.

Although the authors presented contrasting models of state machine formalism, they were similar in that for both models…

  • All actions occurred during transitions
  • No hierarchal relationships existed between the states
  • Moore’s Model
  • Mealy’s Model

These models, later refined and compiled in Arthur Gill’s 1962 paper, Introduction to the Theory of Finite-State Machines, became ubiquitous in computer programming, notably for roboticists, in the control of hardware devices such as vending machines, alarm clocks, turnstiles, calculators and digital watches.. Collectively, these types of state machines are referred to as protocol state machines.

Harel (1987)

In 1987, David Harel, while consulting for the R&D division of Israeli Aircraft Industries, wrote his pivotal work, Statecharts: A visual formalism for complex systems.

In this paper, Harel extended the formalism of State Machine diagrams to include three new capabilities…

  • Depth, via Hierarchical or “Nested” States
  • Concurrency, via the concept of Othorgonality
  • Absrtact Transition Rules, such as History

A 2016 paper by Wachter et al provides a nice summary…

The concept of statecharts as new formalism to represent and describe complex systems was presented first by Harel (1987) and Harel and Politi (1998). The concept extends the finite state machines (FSM) proposed by Gill et al. (1962) to a powerful representation, which significantly reduces the complexity for system developers by introducing several notations features. Like FSMs, statecharts consist in their core of states and transitions between these states and extend FSMs by the following features. The most important addition is the introduction of hierarchically nested states.

Harel introduced inter-level-transitions to allow
direct transitions into sub-states as well as orthogonality to allow parallel execution of different states at the same statechart level. Moreover, a history-connector was added to provide states with a memory, which store the information about which sub-state should be reactivated when a state is revisited. Condition connectors control to which subsequent state a transition leads. Finally, each state can be connected to actions being triggered during different phases of the state: entering, leaving, and an action that is executed repeatedly as long as the state is active.

UML

The UML specifications (formal) can be found here: http://www.omg.org/cgi-bin/doc?formal/03-03-01 (see chapters 2.12 and 3.74)

C++ Template Metaprogramming

Boost Statechart

https://www.boost.org/doc/libs/1_68_0/libs/statechart/doc/definitions.html

ROS

Actionlib

Assorted References

Concurrent Models of Computation in State Machines – Lee07