6 ms·

I'm an EEE, and one of the strange things I've noticed is that, for whatever reason, people from a CompSci background is really, really have trouble building an

I'm an EEE, and one of the strange things I've noticed is that, for whatever reason, people from a CompSci background is really, really have trouble building and understanding even simple state machines. 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.

KRAKRISMOTT 4y ago
They do not scale well. It is why Elm-style explicit message passing UIs are not popular. State machines work for state localised to a widget, but the moment you scale up to something moderately complex (spreadsheets, datagrids, forms etc.), your diagrams balloons in size. For non safety-critical applications, it is better to have implicit state and potential bugs than to have your engineering team waste time proving the correctness of a button when they could be building features instead. 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.
- Multicomp 4y ago
  > but the moment you scale up to something moderately complex (spreadsheets, datagrids, forms etc.), your diagrams balloons in size 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?
  - hot_gril 4y ago
    Hierarchical state machine = object-oriented programming in the SWE world. You'd have one state machine in each object. It's just rare to see that because even the individual objects tend to have practically non-finite states, like counters and stuff, and just be too complex in general for FSMs. Maybe there's some math-ey way of saying everything we do is an FSM, but I don't think of it that way.
  - KingMob 4y ago
    Having worked on a large hierarchical state machine implementation (using statecharts), I can say that nested FSMs help a bit, but are still nowhere close to capturing the necessary complexity. 80% hat, only 20% cattle.
bryanlarsen 4y ago
I was trained as an EE and occasionally use a state machine in my code. Every other time I've encountered a state machine it was also written by someone trained as an electrical engineer or similar.
- SAI_Peregrinus 4y ago
  I tend to use them a lot when dealing with hardware (I'm an embedded software dev, so that happens reasonably often). Most hardware devices have some sort of state machine you need to keep track of. So hardware drivers tend to model the state machine, to track what the hardware is doing.
- sweetjuly 4y ago
  This was my experience as well. I could've gone my entire CS education without even needing to think about state machines outside of a short discussion in a formal methods class and regex, but taking a digital logic class really opened my eyes to the power of state machines. They clarify so much of software design by making implicit and adhoc parts of the design explicit. It really is a shame that most CS degrees don't seem to give state machines the credit they deserve.
rcme 4y ago
In software, it’s rare that two states can be transitioned between synchronously. Or at least, modeling a problem in terms of states that have synchronous transitions is hard. Waiting for user input, making a network request, disk IO, etc. are all asynchronous. This makes it annoying to design a state machine. 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.
- AgentOrange1234 4y ago
  Can’t you still just model A and B, and have your transitioning logic compute and wait for whatever is necessary to make the full transition? If you keep the ephemeral stuff in aux memory, you can have keep your number of states more manageable.
  - rcme 4y ago
    No, because resources are limited. Like if a user indicates they want to go from A to B, and then half way thorough the transition decides they want to go back to A, then you need to cancel and clean up everything for the transition to B. Otherwise you’re wasting battery, network bandwidth, main thread cycles, etc. on useless work.
- ericmcer 4y ago
  I would just consider all those intermediary states as one “loading” state. It is pretty simple to have a “loading” and “error” state in addition to your other ones.
  - jayd16 4y ago
    If you do that then you can't pipeline the response handling and you can't show loaded data until you fully transition to B. Any error would equate to every error. You could have your loading state handle every little detail but then what was the point of the state machine anyway?
smoyer 4y ago
I've had the same experience ... The other fun thing that blows mind is to use Karnaugh Maps to minimize the logic needed in complex condition statements.
syntheweave 4y ago
I believe the intuition of most programmers tends to stem from the development environments being designed around ease of mutable state. If you want to "add state" you just grab some variable and branch on it, done. 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.
spc476 4y ago
Here's a real-world example from my previous job. A process makes two simultaneous requests (we're on a tight dead line here). Here is the enumerated states we have to code for: 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) You might think that after the process step, we can ignore anything we receive, but we need to make sure we ignore the timed out replies, because this "state machine" is running a few dozen/hundred times a second, depending upon load. 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).
- e-dant 4y ago
  Wouldn’t be hard to make a combinator with function pointers in C. I do it regularly. They compose well (and you can pass them state for context).
hot_gril 4y ago
Usually your state is more complicated than just one enum. You'll have counters, buffers, etc. 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.
- BlueTemplar 4y ago
  Well yes, because state machines are identical to regular expressions... though regular expressions tend to be used quite a lot ?
  - hot_gril 4y ago
    Yeah, in most cases I won't even get into manual parsing and will use a regex instead. But sometimes I have to break out the FSM.

KRAKRISMOTT 4y ago

They do not scale well. It is why Elm-style explicit message passing UIs are not popular. State machines work for state localised to a widget, but the moment you scale up to something moderately complex (spreadsheets, datagrids, forms etc.), your diagrams balloons in size. For non safety-critical applications, it is better to have implicit state and potential bugs than to have your engineering team waste time proving the correctness of a button when they could be building features instead. 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.

Multicomp 4y ago
> but the moment you scale up to something moderately complex (spreadsheets, datagrids, forms etc.), your diagrams balloons in size 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?
- hot_gril 4y ago
  Hierarchical state machine = object-oriented programming in the SWE world. You'd have one state machine in each object. It's just rare to see that because even the individual objects tend to have practically non-finite states, like counters and stuff, and just be too complex in general for FSMs. Maybe there's some math-ey way of saying everything we do is an FSM, but I don't think of it that way.
- KingMob 4y ago
  Having worked on a large hierarchical state machine implementation (using statecharts), I can say that nested FSMs help a bit, but are still nowhere close to capturing the necessary complexity. 80% hat, only 20% cattle.

bryanlarsen 4y ago

I was trained as an EE and occasionally use a state machine in my code. Every other time I've encountered a state machine it was also written by someone trained as an electrical engineer or similar.

SAI_Peregrinus 4y ago
I tend to use them a lot when dealing with hardware (I'm an embedded software dev, so that happens reasonably often). Most hardware devices have some sort of state machine you need to keep track of. So hardware drivers tend to model the state machine, to track what the hardware is doing.
sweetjuly 4y ago
This was my experience as well. I could've gone my entire CS education without even needing to think about state machines outside of a short discussion in a formal methods class and regex, but taking a digital logic class really opened my eyes to the power of state machines. They clarify so much of software design by making implicit and adhoc parts of the design explicit. It really is a shame that most CS degrees don't seem to give state machines the credit they deserve.

rcme 4y ago

In software, it’s rare that two states can be transitioned between synchronously. Or at least, modeling a problem in terms of states that have synchronous transitions is hard. Waiting for user input, making a network request, disk IO, etc. are all asynchronous. This makes it annoying to design a state machine. 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.

AgentOrange1234 4y ago
Can’t you still just model A and B, and have your transitioning logic compute and wait for whatever is necessary to make the full transition? If you keep the ephemeral stuff in aux memory, you can have keep your number of states more manageable.
- rcme 4y ago
  No, because resources are limited. Like if a user indicates they want to go from A to B, and then half way thorough the transition decides they want to go back to A, then you need to cancel and clean up everything for the transition to B. Otherwise you’re wasting battery, network bandwidth, main thread cycles, etc. on useless work.
ericmcer 4y ago
I would just consider all those intermediary states as one “loading” state. It is pretty simple to have a “loading” and “error” state in addition to your other ones.
- jayd16 4y ago
  If you do that then you can't pipeline the response handling and you can't show loaded data until you fully transition to B. Any error would equate to every error. You could have your loading state handle every little detail but then what was the point of the state machine anyway?

smoyer 4y ago

I've had the same experience ... The other fun thing that blows mind is to use Karnaugh Maps to minimize the logic needed in complex condition statements.

syntheweave 4y ago

I believe the intuition of most programmers tends to stem from the development environments being designed around ease of mutable state. If you want to "add state" you just grab some variable and branch on it, done. 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.

spc476 4y ago

Here's a real-world example from my previous job. A process makes two simultaneous requests (we're on a tight dead line here). Here is the enumerated states we have to code for: 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) You might think that after the process step, we can ignore anything we receive, but we need to make sure we ignore the timed out replies, because this "state machine" is running a few dozen/hundred times a second, depending upon load. 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).

e-dant 4y ago
Wouldn’t be hard to make a combinator with function pointers in C. I do it regularly. They compose well (and you can pass them state for context).

hot_gril 4y ago

Usually your state is more complicated than just one enum. You'll have counters, buffers, etc. 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.

BlueTemplar 4y ago
Well yes, because state machines are identical to regular expressions... though regular expressions tend to be used quite a lot ?
- hot_gril 4y ago
  Yeah, in most cases I won't even get into manual parsing and will use a regex instead. But sometimes I have to break out the FSM.