State-Transition Tables | Hacker News Reader

State-Transition Tables

bytes.zone

49 pointstodsacerdoti13 comments

After working with state transition tables I've got an opinion that much more often than not they're write only :(

Large tables are quite hard to understand, especially if there's no tooling around that, or the tooling was one-off hack and now it's lost

What you are seeing is the "state explosion".

Once you get to the need for hierarchical state machines, finding the optimum decomposition into system/sub-systems and choice of this breakdown is by far the hardest part of and sizeable state machine implementation, in my experience.

I guess if you get there it’s enough of a reason to pull out the TLA+ nuclear weapon.

Exactly my thought. if your state modeling is so in-depth and advanced, either decompose it into smaller state tables and analyze those individually or go full-formal with TLA+.

Semi-related: State Chart XML (SCXML): State Machine Notation for Control Abstraction

https://www.w3.org/TR/scxml/

https://news.ycombinator.com/item?id=24783057

Adding to SCXML, I should also point out that Qt uses SCXML to specify state machines that drive the GUI, and also offers tooling to edit statecharts.

https://doc.qt.io/qtcreator/creator-scxml.html

I find in practice that is very hard to keep the table up-to-date with code changes and graphics are easier to inspect than table for complex flows.

I have written a state machine generator that both produces the table and the code (no allocation, as fast as hand optimized, suitable for embedded) for my multithreading runtime to visually detect logic/design bugs in the code used:

https://github.com/mratsim/Synthesis

Any general concepts/theory/previous code you based your work from?

The main driver are no allocation, thread-safety, easy to generate visualization and code and within performance 1% of hand-optimized code. Ergonomics have been slightly sacrificed in exchange but is still significantly better than writing everything by hand.

For the theory, mostly reading the following references (in the README) and ensuring that I don't stray too much from what they describe to ease formal verification and code audits in the future:

## References

- [Mealy State Machine](https://en.wikipedia.org/wiki/Mealy_machine)

- [Pushdown Automaton](https://en.wikipedia.org/wiki/Pushdown_automaton)

- [Communicating Finite State Machines](https://en.wikipedia.org/wiki/Communicating_finite-state_mac...)

- [Petri Nets](https://en.wikipedia.org/wiki/Petri_net)

- [Kahn Process Networks](https://en.wikipedia.org/wiki/Kahn_process_networks)

Extras

- [Overview/Slides from Marquette Embedded SystemS Laboratory](https://www.dejazzer.com/ece777/ECE777_3_system_modeling.ppt...)

- [Berkeley's Ptolemy project](https://ptolemy.berkeley.edu/index.htm)

Is this not essentially just a different way to represent state diagrams with undefined cases explicitly drawn out?

Yeah, although this kind of "matrix" representation is pretty useful for reasoning over causal states in, say, Numpy.

A TLA+ model would complement this article very well. Such a simple system is perfect to learn the basics of model checking.

Using the table over the chart creates definitions of behaviour the are both exhaustive and unambiguous.

Often I find forcing people to use the state table creates all sorts of problems, but all of them are related to the specifier actually having to know what they want, and being confronted by having to define it to the final detail.

Reply on news.ycombinator.com