Good protocols are usually made in layers. You would typically want to have some state machine describing lower part of application protocol on which you build higher level of your application protocol, composed of specific functions.

This way you can modify functionality without necessarily touching low level implementation.

I can give an example.

I have worked with credit card terminals and I have implemented entire application from scratch.

There is a protocol to communicate between the terminal and the acquirer's system (ISO 8583).

This protocol specifies a flow and format of messages. For example, if you send a transaction request, you will get a response. If you don't get a response you may or may not retry it, etc. If you send a transaction advice (ie. transaction has already happened) you must be retrying sending it until you get a response, but every retransmission after first must include a bit that says it is retransmission. If the request or advice has been sent and transaction was cancelled, you need to be sending cancellations until you get an acknowledgement.

Now, all those messages have a huge amount of fields that change regularly as requirements change, but the basic flow of the protocol is fairly constant and has been constant for many years.

I have implemented the protocol as a tree of state machines telling the application what to do based on events and I believe the code has not been touched in over 10 years even though the application was in constant development.

As parent has noted, FSM models are flexible boundary abstractions and you can apply them repeatedly to reach the desired level of granularity.

For example, you might start with a large block of code with many inputs and many side effects.

You can map this block of code into a FSM directly - as a "giant switch statement" of all conditional combinations and copy-pasted side effects - or you can devise a way of specifying it that makes it an "input FSM" and an "output FSM" where the input FSM enumerates the types of side effects, and the output FSM acts upon them.

You can also hybridize FSM behaviors with simple constraint optimization to create "smart" solvers: Define a heuristic for solution goodness. Then run the FSM speculatively with various combinations of inputs and rank which combo best fits the heuristic.

Edit: looks like they're talking about this: https://en.wikipedia.org/wiki/TLA%2B

What I describe below is not related.

----

Not the OP, but here's a stab at it...

In state machines commonly used in embedded C code, each state is represented either by a function or by a struct that contains a function pointer. The state machine calls the current state function in a loop or whenever relevant events happen, and that function returns a pointer to the next state, calculated based on inputs. If there is no state transition, then the function returns NULL or returns its own state.

See the above reply where I gave an example with both representations.

Agreed, the machine representation is independent of the machine itself, it's the same mathematical object. So what I was talking about was how to represent using only a relation which describes the possible next states given the current one. This is the most common definition of a state machine, and for me, it's a cleaner representation since you avoid referring to each edge in the state graph explicitly.

> A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels.

This is true. The technical term for this is a "multigraph."

> (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.)

You gave the formula for the number of edges in an undirected graph. The number of edges in a complete directed graph is n^2 - n when transitions from a state to itself is not considered. I take liberty with that fact, and often just say there are n^2 edges in a complete directed graph, since transitions to self don't usually harm the design. Either way, it's O(n^2).

As you said though, state diagrams can be multigraphs. In that case, I'm not aware of a general formula for the number of states. But I imagine it would still be O(n^2), just with possibly more edges.

Really not sure what you mean. A code example would be helpful.

First of all, that sounded negative and I'm totally not knocking Xstate. I'm pro any library that encourages people to think about state machines :D

I'm really speaking tactically about how best to represent the machine, more of an optimization thing. For that, the features that you mentioned do help, no question there. Statecharts is a great formalism overall. But in my opinion, they help more at the macro level, like when thinking about the entire UI as a single state machine and how to modularize that.

Hierarchy and orthogonality are not always present - sometimes state variables truly interact. I'm speaking more about that scenario. I'll take an example right from the Xstate documentation:

  list: {
    initial: 'none',
    states: {
      none: {
        on: { BULLETS: 'bullets', NUMBERS: 'numbers' }
      },
      bullets: {
        on: { NONE: 'none', NUMBERS: 'numbers' }
      },
      numbers: {
        on: { BULLETS: 'bullets', NONE: 'none' }
      }
    }
  }

Here, we have a state machine that looks like it powers some logic in a word processor, where a user can create lists. You can toggle bulleted or numbered lists on and off, as well as switch between them once either has been selected. Since each state can transition to each other state, each state references each other state in the transition description. What happens when you add another state there, let's say we can have a list with letters as indexes. You'd have to add another transition from each existing state to the new one, and add a transition from the new state to all the other ones. This is an O(N) operation as we agreed since every new state means there are N possible edges from it to all other states, and each existing state can have an edge to the new state. I believe this is what people mean when state machines are "hard to modify."

What if instead we used variables to represent the state, and had a single function which determined the next state to go to based on the existing state:

  type State = {
    showingBullets: Boolean,
    showingNumbers: Boolean,
  } 

  enum Action {
    ToggleBullets,
    ToggleNumbers,
  }

  function next(state: State, action: Action): State {
    let nextState = { showingBullets: false, showingNumbers: false };

    switch (action) {
    case Action.ToggleBullets:
      nextState.showingBullets = !state.showingBullets;
      break;
    case Action.ToggleNumbers:
      nextState.showingNumbers = !state.showingNumbers;
      break;
    };

    return nextState;
  }

Now, the process of adding a new state would be just adding a new case in the switch statement. That's constant time, O(1). This is because the next function is actually a relation - it can map a single state to multiple next states.

I will admit, this may be personal preference. With the Xstate approach, where you specify all transitions explicitly, there's no thinking. You just read which state maps to which next state. A relation has logic, which means you have to compute in your head all of the possible next states. It's the tradeoff between expressive power and explicitness.

Nomenclature challenges are a negative code smell