Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why developers never use state machines (2011)

skorks.com

Post reply on HN
Print view View original

91–100 of 121 posts

Re: Why developers never use state machines (2011)

#91

Post by joshka »

rcme wrote: post #75
_gabe_ wrote: post #56

Earlier quoted context omitted.

> This makes it annoying to design a state machine. 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…

> Annoying sure, but necessary right? 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…

It's been a while since I wrote any Rx in earnest, but when I did, it was useful to look at it as almost exactly what you'd end up if you incorporated time (via ordered streams/publishers/observers/etc.) into a model that represents a state machine model.

That is to say, you can kinda both be right here. ;)

Re: Why developers never use state machines (2011)

#92

Post by joshka »

po wrote: post #53

My belief is that part of the reason state machines are not used often is: - 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…

Yep, the teaching is the problem (and this generalizes). I just went and took a bit of a look at my alma mata's IT degree. It's still teaching a variety of data orientated approaches to system design. I.e. state without transitions.

Re: Why developers never use state machines (2011)

#93

Post by jholman »

BlueTemplar wrote: post #88
rhelz wrote: post #79

Earlier quoted context omitted.

Here is a kind of bridge from the articles POV to yours: As the OP points out, state machines are very hard to develop by stepwise refinement. A "general solution" to that problem is...the universal Turing machine--a state machine which can emulate any other state machine. However, its really hard to program a Turing machine, so we invented assembly language, which is really hard to program, so we invented higher-lev…

I was also confused then realized that Turing machines that are allowed to write on their tape are not (always equivalent to ?) 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 an…

Here are some comments from the perspective of computing science (i.e. not from the perspective of software development).

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.

Re: Why developers never use state machines (2011)

#94

Post by gaudat »

emrah wrote: post #2

I've used state machines in the context of hardware design, particularly fpgas and asics. In hardware land, you use a state machine to implement something like software, where your circuit is able to remember what happened earlier so it can behave differently accordingly. It's very crude relative to their software counterparts. They are not as common in software because software is one giant state machine already. Va…

Speaking of CompSci people who cannot into state machines there was one time a contractor wrote some HDL that is a huge number of processes linked to each other with handshaking signals. There are zero state machines in their design. It was a pain to debug it and needless to say it was quite buggy.

Re: Why developers never use state machines (2011)

#95

Post by funcDropShadow »

dustingetz wrote: post #40
rcme wrote: post #33

Earlier quoted context omitted.

No, you need to represent every state. Like let’s say there are two async operations: a disk read, then a network request. When you transition, you need to know: did I start the disk read? If yes, cancel the disk read if it’s pending. Did the network request start? If it started but didn’t finish, then cancel it. So you can see that there is a huge amount of state you need to operate on that’s not directly captured b…

now add concurrency, the system state is a superposition of concurrent transitions

Finite state machines are an ideal mechanism to with concurrency if you put a concurrent queue in front of them. Such a program is easily coded with Akka's FSM trait. It even adds the possibility to trigger transition based on timer. As soon as you are in the realm of time sensitive programs, i.e. because of network requests, this is a very powerful and easy to understand way to program complicated parts of programs.

Re: Why developers never use state machines (2011)

#97

Post by dustingetz »

funcDropShadow wrote: post #95
dustingetz wrote: post #40

Earlier quoted context omitted.

now add concurrency, the system state is a superposition of concurrent transitions

Finite state machines are an ideal mechanism to with concurrency if you put a concurrent queue in front of them. Such a program is easily coded with Akka's FSM trait. It even adds the possibility to trigger transition based on timer. As soon as you are in the realm of time sensitive programs, i.e. because of network requests, this is a very powerful and easy to understand way to program complicated parts of programs.

for others:

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?

Re: Why developers never use state machines (2011)

#98

Post by sorenjan »

Does anyone have a recommendation for an article or similar about implementing state machines? I've only used the simple "switch on an enum" variant (switch(stateVar) case STATE1: doWork(); stateVar = STATE2; break;). I think it's pretty elegant, but it's limited to small and simple problems.

Re: Why developers never use state machines (2011)

#99

Post by dogleash »

sorenjan wrote: post #98

Does anyone have a recommendation for an article or similar about implementing state machines? I've only used the simple "switch on an enum" variant (switch(stateVar) case STATE1: doWork(); stateVar = STATE2; break;). I think it's pretty elegant, but it's limited to small and simple problems.

Practical Statecharts in C/C++: https://www.amazon.com/Practical-Statecharts-Quantum-Program...

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.

Re: Why developers never use state machines (2011)

#100

Post by BlueTemplar »

jholman wrote: post #93
BlueTemplar wrote: post #88

Earlier quoted context omitted.

I was also confused then realized that Turing machines that are allowed to write on their tape are not (always equivalent to ?) 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 an…

Here are some comments from the perspective of computing science (i.e. not from the perspective of software development). 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 h…

Yeah, as I understand it, this is actually more about emulating a (much more simple) FSM on a (finite, therefore pseudo-)TM ?

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 ?

Post reply on HN