FSMs are great! I’ve worked a lot with state machines, in telecom (to model different parts of 4G connections) as well as in capital markets (to model trades, transactions etc.).
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.
> My opinion is that FSMs are best implemented on a higher abstraction layer than directly in code itself.
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.
TLA+ is a great example of a modeling tool that allows you to create FSMs relatively easily. It can also check properties of your model which gives more confidence in the final design.
> You are now planning to build your next big system as a state machine,
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.
Having been both an EE (first) and a software engineer, I have noticed this: as an EE, I would never randomly attack a problem with multiple independent FSMs. Whereas in the s/w realm, I've seen seasoned professionals, without hesitation, do exactly that.
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
I disagree with that - as an EE you almost certainly regularly attack a problem with multiple independent state machines. For example - 3 devices hanging off an I2C bus. Each of those devices will be implementing the I2C state-machine to interpret SCK/SDA.
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.
Yeah, from that angle, yes, you'd do that. But within any one of those devices, would you carve the insides into independent FSMs? Probably a 'yes' qualifed with 'if they were very independent problems anyway'.
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.
Modern software development is about management of complexity. That's why you have abstraction, that's why you have CI, that's why you have automated tests.
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?
Oh absolutely. Part of what I was getting at was that this larger meta-FSM often 'just happens', w/o really being fully intentionally designed. But of course the product that you actually ship is that meta-FSM, so it's the behavior of that thing that matters.
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.
What makes them reusable is dependent on how you implement them.
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.
Thank you David. Your xstate repo on github brought my attention to state machines and state-charts. Which I guess is why I'm interacting with this thread right now.
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).
You probably are already familiar, but if not, this is exactly the entire concept behind Elm (in fact that signature is exactly the update function at the heart of the Elm architecture). And indeed the Elm community has a lot of ideas on how to split that basic idea to make it reusable.
At a previous company we used statemachines to debounce signals, implement protocols, and sequence robot moves. While they were designed so that the actions executed on state entry were pluggable (i.e. all action were executed by calling through a C# interfaxe), in practice we did not use it. Instead were abstracted at a slightly higher level: components that wrapped statemachines with some extra logic and nice APIs. The inputs for the statemachines were also pluggable, so different sources of digital inputs or motor control could be used.
I found languages with TCO even easier to implement FSM in: a state is simply a procedure, and going from one state to another is just a procedure call.
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.
Function objects, including closures, can be serializable - they are in Erlang/Elixir. You can send a lambda/closure over to another node (on another machine) to execute. It's actually one of the basic building blocks of OTP.
Seems like trampolining would be useful to make it interruptible while still mostly preserving the ergonomics of viewing state transitions as procedure calls
Serializable closures (even serializable continuations) are available in a number of languages, including probably most often ones which also have TCO.
Tail Call Optimization, better called Tail Call Elimination. Haskell, OCaml, Erlang/Elixir, Scala with @tailrec, Scheme, Lua(!), most other functional languages.
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.
I prefer FSM implemented in Rust. Having valid transitions checked at compile time is a life saver as soon as is gets a bit complex - at least in my case being able to "prove" an embedded system wouldn't trigger its watchdog during operation was very important.
The advice given in the article is to enumerate your states. Since usually when I'm designing an FSM I have an approximate idea of what's required, I find it generally much more instructive to dive right in.
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.
I recently released a version of my free and open-source text editor, KeenWrite, that embeds requests to Kroki[0]. Kroki provides a REST API for generating many types of diagrams, including Mermaid diagrams. KeenWrite provides users with the ability to reference variables within the text. Combined, they make it easy to apply the DRY principle to documentation.[1] Even though the request goes over HTTPS, the diagrams are drawn in nearly real-time (and cached).
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.
FSM are the solution to a lot of coding problems that in the beginning just look like bunch of if..thens. Of course, there are a lot of problems that scream "FINITE STATE MACHINE" in their definition, but I'd say that applying FSM early on as a sort of "preemptive optimization" can save a lot of headaches.
For example an ecommerce order tracking system with different status (in cart, paid, shipped, returned, so on). Spree solves it very elegantly, look at those "events", "transitions".
I also happened to work in a very huge C++ project for the business logic component of a call center, using CORBA and the Reactor pattern from ACE to integrate different parts of the user / ACD / 1st agent / specialist / CTI combo.
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.
How is that relevant to the parent's point? Non-determinism has no relation to a system with infinite states, and the NFSM -> FSM construction algorithm provides no help in that case.
Is the letter "T" somehow associated with FSMs? I'm taken right back to one of the hardest assignments I ever had, which was learning C in order to write an interpreter for a FSM descriptor language (called "T") our professor had invented.
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.
x-state is easily the best js library for modelling state-machines on the front-end. the art is lost to many frontend engineers that UI is a series of states responding to inputs. so yeah, David thanks for your library.
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.