State

Not cleanly defined. However, per wikipedia, “a system is described as stateful if it is designed to remember preceding events or user interactions; the remembered information is called the ‘state’ of the system. The set of states in a system is known as its state space”.

State transition

when a state changes in a state machine, the system is said to be going through a state transition. A state transition is the set of operations that occurs between one state and another.

Finite state machine

“A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition.”

Initial State

the default (or beginning) state of a finite state machine.

Final State

the state of a state machine at the end of computation. Essentially the end of the flowchart.

Event

A callback raised when a state transition occurs.

Turing machine

“a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules.” This is the mathematical basis of computing. This was defined (in 1936) by Alan Turing.

Turing Completeness

the ability of a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers. Nearly all programming languages are Turing complete if the limitations of finite memory are ignored (aka, Microsoft Teams…?).

Why you aren’t going to use a state machine without memory.

Note that a finite state machine doesn’t have memory. As such, it has limited utility for most of us. Typically, your model is more likely to use memory, making it more of a push down automata. Most developers will still call it a “state machine” however, because that’s the part that is actually relevant for the task at hand (ie., developers NEVER assume a lack of memory on anything). Just go with it – it’s wrong, but they are still going to call it that. The main consideration is the organization of code into states and the transitions between those states.

Indications that you might need a state machine

You are working with an entity that has a status column and some operations are locked/unlocked based on status. Some operations emit events that are consumed by other parts of the system. Your domain model has a lot of spaghetti code or nested if/else clauses in the code. You are beginning to run into a lot of errors because the system gets into weird combinations of other state that you didn’t expect. You can’t transition between certain states because there is no reason to do so. This is a fixed piece of code that is extremely unlikely to change as a result of project plans, market changes, etc.

When to avoid a state machine

Your domain is volatile (usually due to the business changing their rules), forcing regular reworking of the code. You have a large (or infinite) number of possible states. You can’t break the code into discrete states. You want to execute several states in parallel. Your code is too simple to justify the overhead. Your coworkers won’t understand it and will rip it out when you are gone

An example state machine (an easy one).

A vending machine from the 90s, selling cokes for 50 cents each.

Buying a coke is 50c and the machine accepts only coins (nickels, dimes, and quarters). The machine has an initial state of “accepting payment”, which means that you can’t select an item, and you’ll get no change.

As you add money, the machine goes into an ” continue accepting payment” state until a total of 50c is placed in the machine. Note that during this state, you could also initiate a “refund” action which zeroes out the amount of money and returns your coins to you.

Once this amount is reached, the machine enters a “dispensing” state, where you are allowed to make your selection. Once you make your selection, the machine enters a “vending” state, dispensing your drink.

At this point, 50c is subtracted from the total amount entered. If this is zero, we return to the initial state. If not, we return to “Give Change” state, dispense the remainder of the coins back to the user, and then return to the initial state. Note that this is a very simplistic (and not-inflation-adjusted) version of what you can do with a state machine.

How to actually implement a state machine successfully

This is best done in a non-agile fashion. This means diagramming everything out beforehand and actually planning ahead. State machines are rather annoying to do in an iterative fashion and the debugging can become obnoxious as well if invariants change.

The goal of the design is to limit the state machine to a few distinct, non-overlapping states, with clear transitions between them. State transitions should be defined as things that either occur automatically within the system or as a result of user input. They should be unambiguous and easy to define as having occurred in a way that can be processed by the system.

Be especially careful about workflows that could place the system into a non-working or invalid state. These will need to be actively guarded against using validation logic. It is generally recommended to put a lot of tests around any implementation of a state machine, both to verify correctness and to help future developers avoid major system problems. This is typically not done for transient or easily changed business processes, and is most appropriate for critical processes that seldom change.

Complex UIs

If you are implementing things like wizards and other complex workflows, you’ll periodically run into implementations that use one (or more) state machines to control that complexity.

Network-oriented code

If you are dealing with network connections, especially at a low level, you might find a state machine helpful. For instance, you might have states for connected, disconnected, and the various steps involved in establishing a connection, while relying on the state to indicate what actions you can take.

Payment processing and order tracking systems

Payments and orders tend to move through a number of phases during their lifetime, during which some operations are valid and others are not. They also tend to be fairly complex, due to the inherent complexity in both processes.

Interfacing with mechanical systems

Because mechanical systems take time to respond (due to existing in the physical world and being under real world constraints, including safety constraints), a state machine is often useful for making sure that you CAN execute an action before you try it.

Heavy string processing

Heavy string processing sometimes uses state machines as well. Regular expressions describe patterns that can be recognized by finite state machines.

UML State diagrams

UML State machine diagrams are typically used to show state dependent behavior for an object. A state is considered to occupy an interval of time. A state is often associated with an abstraction of attribute values of an entity satisfying some conditions.

An entity changes state as a consequence of an input, but it is also dependent on some past history of its inputs. UML state diagrams model initial state as a solid circle, and uses arrows for state transitions.

States are denoted with a rectangle. The initial state is the first state (following the arrows) after the initial state. The final state is denoted with concentric circles. Sometimes a state machine doesn’t have a final state. In this case, it would loop back to some prior state and continue execution until the system terminates. State diagrams are a logical view of the totality of the state machine’s interactions.

Sequence diagrams

Sequence diagrams are used to show a single set of interactions, rather than the full scope of what could happen in a state machine. They are often very useful for troubleshooting why a particular set of interactions doesn’t make sense.

Flowcharts

You’ll often see state machines diagrammed using old school flowcharts. It doesn’t show them well, but flowcharts are widely understood and you’ll see people try to shoehorn a state machine into them.

No Diagram

You’ll also find that people describe state machines and their workflows without using diagrams at all. Rather, you’ll usually see these people explain a state machine with an actual narrative. Sometimes it will be a paragraph or more of text, sometimes it’ll just be a series of statements. Get used to translating these into a UML state diagram (or a few sequence diagrams).