Facts about State Machines

Hmm. I wonder if the dot language (which is how I draw state machines) can be turned into a matrix as easily as it can a graph. Don't see why not.

Do you know of a tool to draw a graph from a matrix or vice-versa.

It doesn't sound too hard but I'm sure there are wrinkles.

This is the way to go. I have taught teams to use state machines a couple of times, and it is so useful to just write down a list of all the events that could possibly happen. The user types something, they click on something, an api response arrives, and so on. Figuring out the list of states can be harder, so I usually start with the most obvious and draw the graph as we fill out the matrix. Usually answering the question of what goes in any particular cell is easy, and with the graph it is often easier to see when you have to add a state rather than go back to an existing one.

The best result was the time we spent an hour at the whiteboard, then the team split up and we each re–wrote part of the code (there was message–passing between components involved, so we just each took one component; I had cleverly used the events between components in the state machine in addition to external events). We all committed by the end of the day, and the next day QA said it was perfect. (Eventually I think some automated tests got written, but whatever.) Compare that to the prior months where QA would find some weird problem, someone would debug it, write a patch, and declare it fixed without realizing that they had broken some other edge case. There were never any bugs found in that thing ever again.

I find myself drawing graphs of state machines a lot and they can help, but I have never considered doing a matrix representation. I have a problem I am working on with a very bad state machine at work and I think maybe putting in a matrix may help me untangle the madness way better, so I will give it a shot. Thanks!

Definitely. The graph is great for checking that all you specified is implemented. The matrix or complete table of possible transitions is great for checking there are no unwanted ones.

That's a good advice. I can see it working. All ever used isUnity Animation panel.

> Now when documentating a state machine enough to actually draw out the graph, I always include a matrix representation as well for that reason.

Incidence matrices[1] might be an effective way to represent graphs, but the sparse nature of state machines combined with large numbers of input events and states end up making it hard to represent non-trivial state machines.

Also, state machines are often organized into sub-state machines, which are not adequately represented with incidence matrices.

[1] https://en.m.wikipedia.org/wiki/Incidence_matrix

Good catch. The author directly contradicts themselves here. Can’t help but wonder if the rest is worth reading now.

Finite state machines are equivalent to finite automaton, but non finite state machines are not.

The most obvious difference is that a state machine can have infinite transitions and infinite states. The most obvious example is a counter machine that simply keep tracks of how many events it received.

Such state machines can be Turing complete, but also allow to add restrictions to limit their expressiveness

https://en.m.wikipedia.org/wiki/Pushdown_automaton

Edit: to add more context Turing machines are essentially finite state machines with an unlimited memory attached and specific input events (the alphabet of the memory eg bits) and output states (move left/right, write, halt; with possibly multiple state for each output)

I'm not super familiar with it, but I seem to remember using the `ucontext` library in my college OS class in a way pretty similar to this. If I recall correctly (and was using it correctly at the time, which is itself potentially an unlikely assumption), it entailed instantiating a struct that would be available as memory to each "state", and then doing basically what you describe with function pointers for state transitions. I remember being vaguely aware that I was essentially creating a directed graph that would be used to determine what to run next, but looking back, I don't think I made the final logical step from there to realizing that this was just an implementation of state machines (which I knew about from my more theory-oriented classes); at the time, I remember thinking that it was a rather cumbersome way to specify what code to run next instead of just writing out everything I wanted in order. I hope my TAs were as amused reading what must have been a giant heap of spaghetti code as I am thinking about it now, but I probably wouldn't be amused actually having it in front of me and having to read it along side a few dozen other project submissions that were written similarly.

> Function pointers as state machines has been a favorite trick of mine for very embedded C stuff. Each function sets the next state function.

This is the basis of OO's State pattern.

https://en.wikipedia.org/wiki/State_pattern

In a similar vein: https://sketch.systems

Why not? Don't they compose easily with sub-state-machines?

Hence the many mentions of statecharts in the linked document. A graph written using your library would translate trivially to a statechart.

> State machines are a brilliant tool, and turn up more often than you expect once you have the background and experience to see them.

"A Computer is a state machine. Threads are for people who can't program state machines." - Alan Cox

It really depends on your programming language. In C it's not much more then a switch case over an enum where every enum value is a concrete state. It languages with pattern matching and ADTs it's much more ergonomic since a state machine then is just a function from a state and an input to a new state and an output.

The primer is simple: if you notice that your code is using too many if statements, especially nested ones, and you are starting to wonder if you are covering all alternatives and cases, then using the rigor of a state machine may help.

You know, that kind of code:

  if(start) {
    if(!running) ...
  }
  
  if(stopped & !jumping) {
  } else if(running) ...

Stop and write a proper case statement (aka a state machine). You may discover that combinations of booleans (in my example, stopped & !jumping) deserve to be their own state. The insight is that the resulting code should be one clean case statement, with no nested ifs allowed. Then you know you cover all the states/cases.

I had a job interview question: "In Python, write a class to implement a state machine."

Me: So, each instance should represent a state, and include a list of states it could transition to, and methods to transition to them? Is that what you had in mind?

Them: Well, if that's what you think a state machine is, then sure.

Me: There are a million ways I could implement this. What context will this be used in? I can make sure I write something that meets those requirements.

Them: Do you not know what a state machine is?

Me: Of course. But how are you planning to use it?

Them: I can't believe you don't know what a state machine is.

So as far as I can tell, I have no idea how to implement one.

(I'm so glad I didn't get that job.)

A key thing I've seen people miss is that actions should be triggered by specific transitions, rather than by the States.

For example:

If a pull request goes from Draft->In Review the FSM might perform an "assign reviewer" action.

If a PR goes from Changes Requested->In Review, there is already a reviewer assigned, so it just performs "notify reviewer".

Basically an enum containing the possible states.

A long series of ifs/match/dictonary/whatever to match (current state + input → next state).

That's it.

It really depends on what you want in terms of implementation. On one hand, a big chunk of digital logic is about implementing large, high-speed state machines using circuits.

On the other hand, regular expressions and things like lexers are largely based on finite-state machines so there is a ton of information related to those, but they often implement things more complex than finite-state machines in order to be more expressive.

In terms of manually implementing them yourself, I think the naive implementation based on the mathematical definition of a deterministic finite automata is pretty good for a small number of states for things like tracking program state. In particular, explicitly listing the total set of expected inputs/transition criteria, explicitly listing the states, and having a single function that takes the current state and current transition-relevant data and produces a new state.

This representation is nice because it makes the behavior inspectable in one location. This makes it easier to notice the edge cases and prevent the state representation and possible transitions from getting spread all over code. The transition function can be a switch statement or a table. Really any way of writing a two-input function with a finite number of inputs and outputs will work. Many people have also explored strongly-typed versions of this, which are worth a look as well.

There're different ways to implement a state machine, table-driven, object-driven, function pointer driven, callback based, etc. If you just want a simple and hard coded sate machine, nothing beats switch statements. You can do something like the following.

    enum State { S1, S2, S3, S4, ... , END }
    
    State transition(State current_state, int input) {
        switch current_state
            case S1:
                switch input
                    case 100: new_state = S3
                              do_action1()
                    case 101: new_state = S4
                              do_action2()
                    default:  error()
            case S2:
                switch input
                    case 100: new_state = S3
                              do_action3()
                    case 206: new_state = S11
                              do_action4()
                    case 207: new_state = S12
                              do_action5()
                    case 208: new_state = S19
                              do_action6()
                    default:  error()
            case S3:
                switch input
                    ...
            ...
    
         return new_state
    }

    run_state_machine(int[] inputs) {
        State state = S1
        foreach input in inputs
            state = transition(state, input)

    }

That's it. It's simple to understand and it's clear what the legal transitions are from each state based on the input. You can attach actions and data update on each state transition to do something useful.

I talk about a couple of implementation styles for state machines in "Game Programming Patterns" here:

https://gameprogrammingpatterns.com/state.html

There are some good state chart compilers like http://www.colm.net/open-source/ragel/ (disclaimer - haven't used it in years) that you can look at the output of.

JavaScript has libraries for this (xstate) but I usually just do it something like this in typescript:

    enum State { A, B, C };
    enum Action { A, B };
    
    type StateData = 
      | { state: State.A, data: whatever }
      | { state: State.B, data: whatever }
      | { state: State.C, data: whatever };
    
    type ActionData = 
      | { type: Action.A, data: whatever }
      | { type: Action.B, data: whatever };

    function transition(prev: StateData, action: ActionData): StateData {
      switch(action.type) {
        case Action.A:
          return { type: State.B, data: whatever };
        case Action.B:
          return { type: State.C, data: whatever };
      }
    }

Then you can for example if you were using this in react do something like

    function MyComponent() {
        const [state, setState] = useState<StateData>({ state: State.A, data: whatever });

        return <button onClick={() => setState(transition(state, { action: Action.A, data: whatever }))}>Go!</button>;
    }

The XState (JS framework) docs and community are great. Spend a bit of time hanging out there and you'll get the idea. I'm a big fan.

https://xstate.js.org

For one possibility, look up the State design pattern.

Basically, you have a variable that holds an (immutable) object representing the current state. All states that can be assigned to that variable (all abstract states the system can be in) implement a common interface (the static type of the variable), which in particular includes a method (or methods) for asking the state what the next state is given a particular event. The method then returns the new state. Whenever an event occurs, you ask the current state stored in the variable (call its respective method) to compute the next state given the current event, and then you assign that new state returned by the method to your state variable.

The common interface usually comprises further methods that define/implement the behavior of the system in the given state. For example, if the states correspond to the different modes of an editor, there could be a method that implements what happens when a key is pressed in the specific state.

Of all the other replies, it's interesting that no one has mentioned the simplest and probably most efficient implementation, the one based on gotos:

    state_x:
        ... do some stuff ...
        if(some_condition)
            goto state_y;
        else if(some_other_condition)
            goto state_z;
        else
            goto state_n;
        ...
    state_y:
        ...

At our company, we rely a lot on https://github.com/boost-ext/sml

There really isn't that much to it. E.g. in Python you can just use a dict.

    # (state, event) => (next state, action)
    FSM = {}

Add transitions (using enums):

    # Simple left down-[move*]-up sequences.
    FSM[STATE.clear,     EVENT.left_down  ] = STATE.set_caret, 'set_insertion_point'
    FSM[STATE.set_caret, EVENT.left_motion] = STATE.set_caret, 'set_insertion_point'
    FSM[STATE.set_caret, EVENT.left_up    ] = STATE.clear, 'nothing'

Then when an event happens you drive the FSM like so:

    new_state, action = FSM[state, event]

Check out https://git.sr.ht/~sforman/Xerblin/tree/trunk/item/xerblin/g... for an example.

There is also a DOT file (and SVG image) of the resulting state graph (the code to generate the DOT file directly from the FSM dict is at the bottom of the mousebindings.py file.)

I’ve always been fond of this pattern.

   state = state.next(context, data);

Context just holds the global stuff of the process, data is the new input into the machine and state is the current state.

A simple example is an SMTP server. State is the current command (or idle), context is email message being built, and data is the line read from the socket.

  Context context = new Context();
  sendSMTPBanner();
  State state = new IdleState();
  while (!state.isFinished) {
    String data = readLine();
    state = state.next(context, data);
  }

Conceptually pretty simple.

I am also in search for a elegant way to teach such implementations in Python. I do not want students to confuse this with OO, not sure if they see the value in functional programming so soon. My best idea so far is to teach the concept of state and state machines with Python generators…

Krishnamurthi's "Swine before Perl" and "Automata via macros" papers are particularly enlightening.

https://cs.brown.edu/~sk/Publications/Talks/SwineBeforePerl/

https://cs.brown.edu/~sk/Publications/Papers/Published/sk-au...

Game Programming Patterns by Robert Nystrom has a chapter on state machines. It’s both freely available online or for purchase if you really like it and want to support him.

http://gameprogrammingpatterns.com/state.html

On this scenerio each page has a starter machine and some components might as well. So you can in fact nest state machines.

Totally undeused concept I've been trying to implement since the VB6 days.

You might be missing Prof. Harel's innovations in the 1980s, which have seen and do continue to see use in a number of hardware/software engineering fields, but still seem to be mostly under appreciated:

https://www.wisdom.weizmann.ac.il/~harel/SCANNED.PAPERS/Stat...

Here's a one that tracks the state of a button with mouse interactions

https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/b...

I think the simplest one I ever did was basically a reimplementation of setTimeout in Javascript. It was really only intended as a demonstration, because of course setTimeout is right there, but with only a very slight extension you can save the time you’re supposed to activate to permanent storage so that you can set long timeouts (hours or days) and they still fire correctly if the user leaves the page and returns later. And the code is clear and obviously correct, and now the reader has some idea of how to use the code to create more interesting state machines.

State machine diagrams illuminate system semantics without code: “when an API returns 403, go to REQUEST_AUTH state.” The transitions/states can then be observed by outside code to trigger UI/side effects.

Done correctly, you can disentangle the decision-making code from the side effecting code to maximize reasoning ability.

My favorite example of this is the following write up: https://gist.github.com/andymatuschak/d5f0a8730ad601bcccae97...

That just means that the actual state machine has intermediate states for each transition.

Think about the following: The transitions from one state to another are triggered by specific events. What happens in the game when such an event occurs during the transition? Unless the event is outright ignored during transitions, the object (character) is in some state which defines how it reacts to that event. Maybe it’s a separate “transitioning” state, or maybe the character is logically already in the target state, even though the transition animation is still playing out.

The bottom line is: States are defined by how the system reacts to events. Insofar as the system always reacts to events in some way, it is always in a specific state.

Unrelated to javascript, but in the robotics industry there is a trend towards Behaviour Trees. https://www.behaviortree.dev/ is a C++ library that was originally designed for controlling robots via ROS, but it appears to be decoupled from the ROS ecosystem so it could be used for other projects.

There is a basic UI available for editing the tree https://github.com/BehaviorTree/Groot