Finite State Machines
adlrocha.substack.com
adlrocha.substack.com
My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself. FSMs tend to reflect the business domain very closely, are very easy to reason and talk about with non-tech domain experts but also tend to change often. Therefore we have always implemented the framework for the FSM along with some kind of event kernel, and then left the actual setup and configuration of the FSMs to a configuration layer.
It has worked very well and has made it so much easier to talk about how the system works with non-techies.
I really love Rust async/await for this. Under the hood, the compiler is simply assembling a big FSM, and polling a Future is equivalent stepping through allowed transitions which are available to it.
You can even use this to build FSMs which are designed to be manually driven, by coordinating generator inputs and outputs via RefCell and one-shot channels and calling `poll` yourself.
Often people don't actively decide to write a state machine, but do so anyway. I think the big takeaway of FSMs is how to recognize them in an idea or implementation and actively using them as a nice abstraction.
I know from University CS training, that s/w engineers most likely all would recognize that any piece of software would, taken as a whole, constitute a single FSM. But as s/w engineers, we usually turn a blind eye toward that fact, seemingly bc there's too much complexity, we perceive the pieces as independent, and need to divide the problems in order to conquer them.
This bears some thinking about. For now, just saying, the difference in perspective is interesting
Idk, just woolgathering here anyway. One thing that drives me nuts is when people take a linear sequence of code, chop it into little pieces, give each piece to a thread, sometimes give such threads little pieces of other task sequences, then bodge it all back together with various kinds of thread synchronization methods. What you end up with is almost impervious to analysis. So clearly keeping linear sequences of code intact has advantages. Thinking that maybe by thinking about which assemblages of such sequences form relatively independent FSMs, one might, as a s/w developer, be able to make better decisions about how to organize the larger scale structure of software.
It's a question of what abstraction level you are looking at. In a complex system you need multiple components abstracted from each other and high levels of the system. In those cases, the building blocks will have their own state machine.
The same is true in software, although in software it's much easier to reach a high level of complexity. Your average protocol stack (be it IP, LTE, or Bluetooth) is composed of a number of separate layers. These communicate between themselves with messages, and update their internal state-machine. This is a great way to model a system.
The same is true in 'closer to hardware' land. An FPGA implementation will often include many explicit state machines, and even more implicit ones.
I did say I needed to think about it more. Guess if there were to eventually be a point I'd try to make, it would be that s/w seems to have a tendency to be structured more like an entire complex system, than like nice tight clean self contained state machines.
Idk if this has to be so or not, but in recent years with the rise of multicore processing, I've seen a huge gravitation toward splintering s/w into threads, without, seemingly, well planned combination of those threads. It's sort of like if, as an EE you were going to build a whole computer, declared "I'm going to need counters and adders and registers (etc)", and then set about designing great counters and adders etc, but then just lashed them together somewhat haphazardly and kind of just hoped to get the system you wanted.
Having multiple independent state machines isn't necessarily a failure of system thinking. To extend your processor argument, do you think there is only one state machine in (each core of) an x86 processor?
It seems it would be powerful if they were treated as re-usable lego bricks of state and logic.
Apps could then pull these in, connect the wires to any potential backend, and style the interactive components.
A state machine that is the simple relation:
(state, event) => [state', actions]
has a very reusable interface, as long as it doesn't execute the actions (effects, commands, etc.) itself. It's just a pure function that can be used anywhere to get the next state and the actions to execute as a result of receiving an event.
Then you can do exactly what you're describing: connect the wires, style the components according to state, etc.
I often wonder what would happen if we could find ways to build complex applications by creating re-usable blocks using state machines (state, logic), json-schemas (structure, data-model), and React* (presentation).
All of these are serializable documents. Imagine being able to search a collective collaboration of components and schemas and piece it together. Could probably be graphical interface like Figma.
There are certainly other pieces that could be also used (graphql to describe data-fetching, markdown (mdx) for content).
*or similar
The difference is small, but once you start getting hairy state machines I have found that it leads to smaller mental overhead for me.
The same would be true for something like a recursive descent parser.
Basically, if there's a call to a function B at the very end of function A, there's no need to create a new stack frame for the call to B - you can reuse the frame created for call to A. It both saves memory and improves performance. A special case is when A and B are both the same function, in which case we say A is tail-recursive.
Start with the "initial" state and start mapping out transitions -- at each node, list out all the transitions (exhaustively) from that node and assign them states. Walk through the happy path to the terminal state, then start fleshing out the various branches from there. Once you've got the graph, start merging states together as necessary, and since you've been making sure that your transitions are exhaustive at each step, it will be complete.
The next step is to step back and look at the entire machine for simplifications, but trying too hard to shoehorn two disparate states into the same state often leads to strange behavior (because transitions from one don't make sense in the other), so it's best to wait until you have some idea of the entire machine before you start combining states.
The screenshots show GraphViz diagrams, but changing "graphviz" to "mermaid" at the start of the code block will permit drawing Mermaid diagrams. See the video[2] for more ideas on how to mix variables with documentation.
[0]: https://kroki.io/
https://github.com/spree/spree/blob/4687e608b49236c2850500b0...
Also, Spree has this nice intro to FSMs
https://github.com/Humane-Documentation/Spree/blob/master/re...
But it was a telco project, so the "let's use a FSM" was well thought from the beginning. Turns out you could easily know what the system would do just by reading a huge Smartdraw document, and this also allowed for reasoning on new use case scenarios. It did not matter that the main file was a horrendous 40kLOC C++ class because the Smartdraw diagram was the documentation and everything else was just trivial code.
Regex is probably the most common FSM compiler in modern computing. s/find.a.string/replacement/... Yeah, those regex.
It worked great but the system was fairly simple and wasn't changed often. In my opinion, it's nicer when the state machine can be defined as configuration (in XML or whatever) and then generate the code. Unfortunately that's not possible with vanilla pytransitions, but I suppose you could build a layer on top of it.
> Unfortunately that's not possible with vanilla pytransitions
Can you elaborate?
https://github.com/pytransitions/transitions/blob/master/exa...
Still a work-in-progress, but hope to make this production-ready this year.