Why developers never use state machines (2011)
skorks.com
skorks.com
They are not as common in software because software is one giant state machine already. Variables hold state, there is state within state (classes, composition etc). Sometimes entities in game design have explicit state machines for their behavior but that's to minimize complexity rather than due to absolute necessity
I suspect this unintuitiveness is the main reason why we don't see more state machines, as even in the case where they're an optimal solution many SWEs will shy away from them.
Locally-rendered UIs are probably one of the best examples of where state machines shine. State-machine based ImGuis lower complexity by orders of magnitude, yet, people still resist.
SWEs (at least those with formal CS training) understand state-machines perfectly well. It is the kernel of regular expressions and parsing. Mapping it to a product UI just doesn't make sense all the time.
I'm no CS major. But isn't that what Hierarchical state machines are supposed handle? Or was that all hat no cattle and/or a lost knowledge when UML style stuff got tossed away?
Maybe there's some math-ey way of saying everything we do is an FSM, but I don't think of it that way.
Just as an example, imagine you have two states you want to model, A and B. Let’s say the transition between A and B requires 3 async operations. You then need 8 total states: A, A_before_step_1, A_before_step_2, A_before_step3, B, B_before_step_1, B_before_step_2, and B_before_step_3. It just becomes totally unmanageable.
You could have your loading state handle every little detail but then what was the point of the state machine anyway?
If there are fundamentally transitions that are impossible (or errors) then just only define the transitions that make sense and have the rest map to a error condition if they ever come up.
Also, if the state space is factorisable (like in your example) then it is easy to represent. You never need to name every state separately if e.g. you use 2 enums (or more generally a GADT) instead of trying to fit it all into 1 variable for every possible state.
https://doc.akka.io/docs/akka/current/typed/fsm.html
https://doc.akka.io/docs/akka/current/typed/persistence-fsm....
Is ^ demonstrating the equivalence between FSMs and event streams? or are they not quite identical just closely related?
Also, the full state representation is not the problem, that’s easy enough to do with a reasonable type system. The problem is defining the transitions. But if you need the full transition matrix (or even any substantial subset), then you have a lot of things to do. But it’s things you’d have to do with a non-state machine based approach.
Realistically the only overhead with a sparse state machine representation is adding is the “catch-all” error branch you need to deal with any forbidden transitions. Everything else, you’d need to deal with anyway for normal operation. And you probably want the catch-all branch anyway, for debuggability when it breaks.
So they are not at all rare but not exposed to programmers explicitly.
That said, even modern pcre uses state machines
https://github.com/rurban/pcre/blob/master/src/pcre2_dfa_mat...
Annoying sure, but necessary right? With or without a state machine you have to handle all the states, and if you don't bother quantifying all possible states of your model and just winging it, it's not like those extra transition states magically disappear. Instead you just run into weird multithreading bugs and after banging your head against the wall for 5 hours you realize you forgot about a transitory state
And just to clarify, I don't mean handling every single state possible, because that's most likely infinite. But if you specify a finite number of states your app can be in, and then mark the invalid transitions to take you to an invalid state, then you can figure out when your app is in an invalid state immediately instead of having the weird bugs crop up randomly.
No, not necessary. The key insight here is that the transitions are the hard part. One way to solve this is to write your transitions as a series of asynchronous steps that feed into each other. The end result is an asynchronous chain of operations.
E.g. if you have a video app, playing a video might look like:
1) Read the user metadata from disk.
2) Use the user metadata to make a network request for the video metadata.
3) Deserialize the video metadata on a background thread.
4) Present the video player with the video metadata on the main thread.
You compose each step into a chain of operations. Each step in the chain contains async work as well as logic that “cleans up” the work. So when you want to play a video, your code says “start the complicated video chain.” When you want to stop the video, your code says “stop the video chain.” The chains are a generic sequence of steps, so they can be stopped in the middle. Each step contains its own cleanup logic, so the cleanup of any pending work can happen automatically upon stopping the chain.
tldr: “state” the user is in at any given time is so complex that it’s impossible model with a state machine. It’s easier to think of cascading asynchronous steps instead. A good library for writing this kind of code is called Rx.
That is to say, you can kinda both be right here. ;)
Couldn't you do the equivalent of a join to transition to B?
Even better, if you picked the right abstraction for the T state machine, that same set of modeling can be used elsewhere. (Note, no panacea. You can still pick the wrong abstractions here. Or one that just doesn't help you later, even if it isn't wrong.)
And this is exactly how it is in the physical world. The "payment acceptor" state machine of a vending machine is independent of the vending aspect of the vending machine. It is there solely to create the signal of "payment received" to the machine. Whether that comes from coins, credit cards, phone taps, whatever.
Thus all the instances where you want to enumerate your state come off as seeming unnecessarily formal, so the code just drives straight towards a ball of mud and the programmers, looking for a way out, look for abstract techniques to eliminate the state(pure functions, dataflow, constraints, etc.) or sweep it under the rug(objects and configuration mechanisms) instead of "cleaning their room" by drawing up a giant decision table that enumerates all possible transitions.
I've made the transition table. It works. It produces a painful "rip off the bandaid" moment in that it forces out more of the specification all at once instead of allowing to accumulate iteratively. I'm pretty sure this makes it politically undesirable in many orgs.
send 1,2 -> receive 1, receive 2, process
send 1,2 -> receive 2, receive 1, process
send 1,2 -> receive 1, timeout 2, process, receive 2 (which is ignored)
send 1,2 -> receive 1, timeout 2, process (2 is lost)
send 1,2 -> receive 2, timeout 1, process, receive 1 (which is ignored)
send 1,2 -> receive 2, timeout 1, process (1 is lost)
send 1,2 -> timeout 1,2, process, receive 1,2 (which are ignored)
send 1,2 -> timeout 1,2, process, receive 2,1 (which are ignored)
send 1,2 -> timeout 1,2, process, receive 1 (which is ignored; 2 is lost)
send 1,2 -> timeout 1,2, process, receive 2 (which is ignored; 1 is lost)
send 1,2 -> timeout 1,2, process (1,2 are lost)
As I was leaving, there was talk of making a third concurrent request. States start exploding here. Maybe if there were languages that made this easy to implement they would be used more often (the code in question was in a mixture of C89/C++98).
I do it regularly. They compose well (and you can pass them state for context).
The only time I've ever used a state machine in real code is when parsing text one token at a time or something like that. It's a useful skill to remember for those situations. And this kind of problem is very over-represented in SWE interviews.
[1] https://en.wikipedia.org/wiki/State_diagram#Harel_statechart
[3] https://www.wisdom.weizmann.ac.il/~harel/papers/Statecharts....
Why Developers Never Use State Machines - https://news.ycombinator.com/item?id=20875583 - Sept 2019 (1 comment)
Why Developers Never Use State Machines (2011) - https://news.ycombinator.com/item?id=16470262 - Feb 2018 (161 comments)
Why Developers Never Use State Machines (2011) - https://news.ycombinator.com/item?id=12204038 - Aug 2016 (1 comment)
Why Developers Never Use State Machines - https://news.ycombinator.com/item?id=2949543 - Sept 2011 (92 comments)
It took more time to program than a bunch of messy if-else logic would, but it was well worth it. The knowledge that your GUI can't find itself in an invalid state is realy reasuring, and also it's preety easy to add new states/logic after you get over the initial hump.
At the framework level they might be pretty useful, but they rarely appear at the first version, but as a result of refactoring.
The problems are obvious. It's built on magic and indirection. This leads to difficult to debug state machine problems. For anything beyond simple state machines you quickly lose any idea of what your object is doing.
I’m unaffiliated, just have used a lot of Ruby SM libraries.
Most text language based state machines are a mess and difficult to reason about.
FWIW I maintain a state machine library for Ruby called wicked that (IMHO) isn’t too bad, but can still get gnarly if you’re not careful.
I ended up working as an “applications engineer” which is a glorified way to say “support”. And I saw some really gnarly code. Just literally spaghetti.
I think though the big problem with much of the bad code is that it wasn’t architected and modularized (at all). As the tool is sold as “it’s so intuitively obvious anyone can use it”
I don’t think many people train to use it the same way we were trained. That’s a big bit of the problem.
Hell is always someone else’s code, but if I every had to refactor some labview today, one of the first tools I would reach for would be state machines.
This idea that modular code matters is bullshit.
Enterprise fizz buzz or spaghetti nightmare.
Learning things isn’t the point, talent is.
Speaking as someone who used to think this stuff mattered, then realized they’d just been wasting their life, instead of isomorphically rearranging thinking patterns on the deck of the trendtanic.
It's true that they have limitations and are not always the right tool, but it's often valuable to realize that you implicitly have a state machine already whether you wish you did or not.
...beyond trivial stuff like pong, the natural pattern is just a big collection of state machines (as entities) interacting with each other.
() Many years ago I was tasked with coding a replacement for a device that operated from discrete logic involving a number of inputs, timers, decisions and actions based on all of these. The first thing I did was to model it as a state machine and everything went well except for one part where it was not clear what the next state should be based on the inputs. I reviewed this with an engineer familiar with the existing logic and he shared with me that the actual behavior of the device was indeterminate in that particular situation. That was easily fixed with the state machine.
- State machine libraries are good at expressing an existing state machine but often the workflow for upgrading or modifying it in production is lacking. If you want to remove a state for instance, it's still very hard and the tooling just makes it more obtuse.
- The reason class hierarchies as a way to model your problem are overused in most programming languages is not because it's good, but because it's a language feature that's taught by every book that covers that language. If state machines had language-level support/keywords, more people would use them.
(Interestingly, I think part of why class hierarchies can be a trap is similar to the first issue above with state machines: they are hard to change down the road as you learn more about your problem space.)
I use state machines all the time, mostly in FPGA's yet also in software, embedded and beyond. Yes, you do have to develop a sense of when and how to use them.
One of my software techniques is to use a state machine to initially solve and understand a problem. Once done and working, you can start to chip away at the state machine, eliminate states and sometimes refactor the code into something faster or more efficient that completely eliminates the state machine.
The other aspect of this is that state machines can, in some cases, add a layer of safety and failure mitigation.
In the end, it really depends on the nature of the project.
That being said, for some types of problems a high-latency finite state machine greatly simplifies the complexity of handling data stream consolidation efficiently. The trick is knowing when it should be avoided like in shared-state awareness problems... you know, the "lets pause the internet while I do this one op" guy we all work with sometimes... =)
Respectfully… wha?
While I don't agree with many of his points (riffs on Erlang/Elixir are silly), there is still some good hints in the talk.
Hope it helps =)
My problem with most state machines is that they are tied to your implementation language. And they are ad hoc.
An implementation programming language is itself a state machine - if you think of memory as being the states the machine can be in.
My state machine serialization supports and defines behaviour between concurrent threads and collections.
It defines a state machine between threads in async/await thread pool
Here is the serialization:
next_free_thread = 2
task(A) thread(1) assignment(A, 1) = running_on(A, 1) | paused(A, 1)
running_on(A, 1)
thread(1)
assignment(A, 1)
thread_free(next_free_thread) =
fork(A, B)
| send_task_to_thread(B, next_free_thread)
| running_on(B, 2) paused(B, 1)
running_on(A, 1)
| { yield(B, returnvalue) | paused(B, 2) }
{ await(A, B, returnvalue) | paused(A, 1) }
| send_returnvalue(B, A, returnvalue)
But I think that a lot of the dialogue I see around state machines in programming is effectively strawperson. Much like the dialogue around DSLs in programming. People end up debating over weak examples, and then dismissing valuable ideas.
However, there can also be complexity. Different customers inevitably want different sets of states and different behaviors on transitions. The pre-transition and post-transition logic can get complex. And it can sometimes be difficult in retrospect to figure out what happened if you didn't log and directly relate the transition event to other things (common if you're using a separate generic state machine library). And sometimes you can end up needing overrides to allow a transition from one state to another that isn't normally allowed, in order to fix bad data or mistakes.
But you can control some of that, and the state machine makes a lot of things easier to reason about.
Rust is awesome for state machine. The "enum" type can hold data, and modern Rust has a bunch of convenient ways for destructuring enum's.
Edit: eh, that comment didn’t really say much. What I meant was that there are classes of algorithms that are stateless. Maybe the most useful are proofs.
Look, I’m a C++ dev. I live and breathe state. Weird, mostly-working gadgets are the real humans of the world.
But that doesn’t mean I don’t use linear types and write unit tests for my function composition. Sure, I’ll let closures capture their context, and I’ll allow pass-by-reference in my APIs, but that doesn’t mean I encourage it.
Can you give me an example?
This property becomes more useful when you’re trying to prove something about a function’s behavior over a bunch of well-defined types.
Languages like Haskell and Agda have these properties.
Rust also has some of these properties by default. It has an affine type system (the borrow checker) enforces some guardrails on ad-hoc state manipulation. C++ has linear-esque types in its pointers and higher-kinded types in the concepts and constraints features.
An algorithm that does the same thing given the same input is deterministic aka referentially transparent aka pure, not stateless.
Even this little snippet of Haskell is stateful:
statefulFunction :: Int -> Int
statefulFunction x =
let y = x * x
y + y
People seem to use "stateless" as a word for "doesn't mutate anything", which is kind of weird. Mutability has _nothing_ to do with having state.
The computation I’m talking about is whether you’re for more of a von neumann target or a lambda calc target.
Oh, wrong universe.
Edit:
I use state, too. I get it. I just dislike it. It doesn’t usually compose and is rarely safe.
For a trivial example, objects defining the Applicable trait.
I could see a monad being defined as a list of (typed) states with a functor. But they’re still stateless.
I could also see immutable data structures being implemented in a stateful way (they usually are in non-FP languages).
Or more generically, look into Hierarchical State Machines.
There's a few insights that you can apply to your state machines that will give you most of the power you'll ever need:
1. Rather than storing an enum in your state variable, store a function pointer to state-functions.
2. Rather than have the states check outward for data to operate on, pass in a generic event type. There will still be some amount of looking outward, perfection is the enemy of good (a simple enum that the state function switch()-es on is enough to experiment with the idea).
3. Have a single entry point that takes an event and dispatches it to the states. That way you can trigger an arbitrary number of events to the state machine for any one external event (like after a transition, sending in "state exited" and "state entered" events).
4. Hierarchy: Add a mechanism by which a state-function can ignore the event, and the dispatching code sends the event to the state's parent state instead.
I think the rest that I gained from reading about and working with complex state machines is about creating good APIs for dealing with the ideas above, and to design the state diagram on paper before implementing. I rarely use the full complexity of the "QHsm" described in the book I linked, but the concepts aren't strangers and I'll often start with a switch(_state){} and sprinkle in features as needed.
One thing I've found is that the end result can still be spaghetti with an FSM, but if you have tools to edit these things graphically, it becomes very manageable spaghetti!
It was overly complex for what it produced.
.... We needed an API.. everything got rewritten 3 times before it was actually released because it was too complex and served zero purpose.
I have even written code generators that auto generate hierarchical state machines. Because they are really useful for managing complex logic.
The number of possible states a program represents is normally very, very large, and the transition rules are very complicated and often mixed up with, e.g., multiplier circuits. So we use familiar programming languages instead, which help to organize it all. A program emulating another state machine tends to raise the question why the (or anyway some) programming language is not being used to manage its complexity.
So in practice we emulate only the simplest of state machines explicitly. A programmer writing such a program is sometimes said to be in a state of sin.
Now, I fully grant that there can easily be an explosion of states. I still find it odd to see so much pushback to trying to force a limit on the number of states that we want to support on a UI. We seem to want to allow any number of inner states to transition on a page at any time, and then we wonder at the complexity of the interfaces that we have built up.
However, its really hard to program a Turing machine, so we invented assembly language, which is really hard to program, so we invented higher-level programming languages....
Basically, the programming languages we have are the best way we've figured out how to make state machines...
So I guess that making a state machine involves clearly separating the write-protected parts that make it from the rest of the program, and forbidding tampering ?
Also, all computing is not (directly) state machines or even Turing machines : quantum computing and generally analogic computing come to mind.
P.S.: Also, seems like (because of that restriction ?) you cannot have multithreading inside a state machine ?
There is a conceptual thing called a "finite state machine", which has no memory except a set of finite states. It can, of course, "recognize" the elements of any finite set, but the question is, what infinite sets can it recognize? There is another conceptual thing called a "Turing machine". It has all the same capabilities that an FSM has, plus the ability to read from, and write to, an infinite long tape with a finite set of symbols writable to that tape. Again, the question, what infinite sets can this conceptual machine recognize? Another machine, a push down automaton, has memory capability greater than the FSM, but lesser than the TM. Again the same question.
So, yes, in this context, a TM can do anything an FSM can do, but the converse is very much not true.
That said, real life computers do not have infinite tape; they are actually very very powerful FSMs. So when we talk about the applicability of these ideas to the practical day-to-day writing of software, there are several layers of metaphor involved in why we care at all.
And so another thing that I thought would matter for software development is that you should be able to actually make the FSM write "outside of itself" without losing its FSM-ness, in the sense of not being able to later read it - which makes no sense talking generally, but does make sense in this context of emulation ?
What you've written is correct, but someone who's not reading carefully might mistake "capability" for "capacity". Both pushdown automatons and Turing machines have infinite storage capacity, but the Turing machine can seek to any position in its infinite tape while the pushdown atomaton can only access the top of its infinite stack.