# Notes for my future self on states and state machines

## The problem, which is impossible to forget

100 bits can encode more combinations than there are atoms in the visible universe. Computers have many more than 100 bits.¹

We can talk about the state of these bits the way we talk about the "state of play" on a chessboard.

A computer program is a dynamical network that converts a current state of bits -- based on signals from the real world -- into a new state of bits.

A program would be impossible to get right if every bit might contribute to every other bit.

Fortunately, we work in the real world with extremely sparse networks. Each bit can only ever affect a few other bits. Many combinations of bits are impossible.

Still, it's easy to end up with a sparse network that isn't sparse enough. Too many bits contribute to the next state of a single bit. Spaghetti.

(In this, programming is akin to Poker. Poker operates at the edge of tiny probabilities a human can reason about. Programming operates at the edge of the densest possible networks a human can reason about.)

## Framing

Programming requires reasoning about all possible states a program might encounter. Controlling the number of states and transitions is an essential activity in programming.

The most basic tool to control the space of states is decomposition. Being able to stare at a subset of bits with the certain knowledge that none of the other bits is relevant. There are few edges from outside into these bits.

State machines are a nice way to formalize the word "few" above. All the edges from outside a subset flow into an initial state. Then the subset evolves entirely according to self-contained edges until converging on a final state that is accessible outside the subset. All edges entering the subset go to the initial state, all edges leaving the subset exit from the final state.

Programs build up state machines hierarchically out of other state machines. There are only a few useful state machines operating on (small numbers of) bits. Everything else is composed out of them.

Functions and types are handy tools for composing state machines out of other state machines. Types help to exclude states a program can never get into. Functions help to exclude transitions between the states that remain.

Immutability is a handy tool to exclude many states in dynamically determined periods of time.

Constructing programs out of all these handy conventional tools suffers from arguably the major problem of programming: it's easy to lose the forest of a program's state at the highest level amidst the trees of all the different rules enforcing sparseness at lower levels.

Free-form prose and images can help combat this problem, if you can keep them in sync with the program over long periods. The ideal would be to encode high-level states right in the program, where the computer can automatically check for inconsistencies.

Sequencing is a powerful tool when encoding states in a program. If one state always leads to another, laying them out next to each other eliminates the need to encode the transition.

## Recommendations

Concurrency and blocking are useful tools in minimizing the number of states and transitions. You could encode polling into a state machine, but it's better to deal with it at a lower level of the hierarchy that signals events to the higher level. Closures, async/await syntax, messages and channels in various languages can all help here.

When staring at a program, some questions come up repeatedly, at any level of detail:

1. What states are possible?
   
2. What state is the program in when ___?
   
3. What transitions between states are possible?
   
4. Are there any dead-end states the program can get stuck in?
   
5. What bits of data are relevant to each state?
   

The cleanest way to encode 1 and 2 is directly in the program. Create an enum with the names of possible states, and store the current enum value somewhere.

The cleanest way to encode 3 is as functions in some sort of namespace (like an object). Particularly if functions outside the namespace are forbidden from mutating the state (e.g. using access modifiers or ADTs), the namespace comprehensively lists all permitted transitions.

There's value in separating the space of possible transitions from the events that trigger them, or the logic that selects between them. Keep such logic outside the namespace so that 3 remains easy to answer -- and 4 becomes tractable to answer -- over time.

Question 5 requires carefully modeling types. In particular, sum types (tagged unions) exclude more states than product types (records), and they're often under-used. For example, consider the following state machine for loading an image.



It's very common in many languages to represent the state here as a struct that packages up other relevant information. For example:

  ```
  struct state {
    enum { No_image, Pending_image, Draw_image } tag
    time next_check
  }
  ```
  

Here `next_check` is only applicable when tag is `Pending_image`, but that bit of sparseness is not encoded in the representation.

A better representation is the following:

  ```
  type state =
    No_image |
    Pending_image time |
    Draw_image
  ```
  

Books² and tutorials³ often encourage such mistakes, either by focusing on simple state machines that need no additional state or by lazily attaching a single struct with everything needed by all states.

Haskell does a good job encouraging the second representation, and so does Rust with its powerful Enum facility. Other languages often require specifying the space of possible tags separately from attributes for individual ids, which can foster bad habits. But you can encode the sparseness of a problem in its types in any language if you're attentive. A little verbosity here can yield large returns.

## Colophon

This post is a consequence of a simple state machine I made heavy weather of, and ended up describing in detail. I ended up getting some nice suggestions for alternative implementations, many containing ideas I'd been immersed in 10 years ago and then forgotten. Comparing them and trying to arrive at a synthesis led to these notes, which I will hopefully not forget. Thanks in particular to Paul Tarvydas, Zac Nowicki, Konrad Hinsen, Jack Rusher, Christopher Shank, William Taysom and Lu Wilson.

I tried not to make any assumptions that the encoding of a program has to be textual, but I'm left with the sense that textual languages are fine for this particular problem. ducks rotten fruit

I composed these notes in lines.love and then exported them to html and SVG using lines2html before lightly editing the results to fit into my website's style.

## Footnotes

1. For a nice exposition, watch the first few minutes of this talk

2. See, for example, listing 1.1 in Practical Statecharts in C/C++ (pdf)

3. See, for example, this FSM implementation

Comments gratefully appreciated. Please send them to me by any method of your choice and I'll include them here.