Hacker News Reader

Comment by monocasa | Hacker News Reader

One helpful hint for dealing with state machines isn't listed (arguably because it's not state machine specific).

The most common way to abstractly describe state machines is the directed graph, but (like nearly all graph problems) it's often just as illuminating if not more to decompose the graph into a matrix as well. So rows are states, columns are events, and the intersections are transitions. Being able to run down a column and see what happens in each of the states when a certain event is processed has made a lot of bugs much more obvious for me.

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

View on HN

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!

It can also be useful for other reasons, the one that I think of is the interview question involving the knight jumping on the telephone keypad. Using the matrix instead of the graph, you can leverage matrix maths. Multiply the matrix by itself and miraculously you can see where the knight can go in two jumps. Use the power of 7 and sum the rows and you can count how many valid phone numbers are possible from any starting position!

Never crossed my mind either - seconded.

> 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

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.

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.

Potentially you could see about adapting the https://graphviz.org/docs/layouts/patchwork/ layout?

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.

Just write one yourself. It's really trivial to do.

    Foreach node
      Foreach node.transition
        Matrix(node, transition.event) = transition.destination

And the other way:

    Foreach node
      Foreach event
        Destination = matrix(node, event)
        Graph(node).add(event, destination)

I wrote a tool at work for this. Using python to read in an Excel workbook with states and events in rows and columns that outputs a PlantUML state machine description. Worked really nicely, but not available for open sourcing at the moment.

Using python it's quite straightforward to convert between numpy arrays and sparse arrays, which are basically the graph represtation of the same data.

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

Reply on news.ycombinator.com