They organize complex code, dissect complex set-flag-here-and-test-there spaghetti into a matrix of states and events that can be exhaustively examined and debugged.
Yes you have to organize your code to feed the machine (Vol is hungry! We must feed Vol!) But you have to organize your code somehow, and feeding a state machine can actually be easier to understand that flag-setting. In fact, it makes it absolutely clear what an event is associated with - the machine it feeds.
Not everyone can be a game A.I. programmer, so it's nice to get introduced to new tools or undusting old but forgotten tools, b/c they look complicated from where you are standing right now.
The natural next step is a PDA. Perhaps you could use this type of system to model an AI that can get distracted or become faced with an intermediate task and then return later to the original objective?
For those of you who don't know what a PDA (Push Down Automaton) is, it is basically a standard finite automaton but with a stack that you can push things to and pop things of -- you can then react differently if you get input a in state B versus getting input a in state Q.
Many parsers make use of PDAs when they parse source code.
I've used PDA in games A.I. programming several times too. In fact I'd be surprised to see anything beyond a casual game that didn't use high level 'task stacks'.
About 10 years ago when I was reading a lot about AI game dev I remember reading about Fuzzy State Machines ( http://www.coniserver.net/wiki/index.php/FuSM ) which were seen as an improvement from classical FSM.
I think I read it in one of the "AI programming Gems" books.
Going by the name, those are based on Fuzzy Logic, I assume - which makes sense. Some people say that the first nation to develop a true AI will be Japan, because they've been studying Fuzzy Logic theory as a field of science since decades.
It's fairly common these days to use something beyond FSMs, e.g. simple planning (whether classical or hierarchical), or hierarchical behavior trees. In other cases, more emergent "smart world" type methods, like influence maps or smart-objects.
Upon reading this, I realized I had never really looked into state machines much. In my searching, I found a Coffeescript state machine that has a nice chess-based example:
FSMs are very common on the embedded systems I work on. In fact, I often find that my coworkers use them too much. For instance, sometimes a DSP filter would be a much cleaner and maintainable solution. That said, if you work on embedded systems and you've never used a FSM, you're probably doing it wrong ;)
State machines are a form of declarative logic as opposed to procedural, and declarative is often superior for modelling real-world activity.
Procedural logic tends to be brittle - small changes have unintended consequences. Declarative models tend to be more robust and, especially with domain-specific languages, safer for domain experts to manipulate. You can certainly design domain-specific languages for the subset of declarative systems that are state machines.
I've happily used state machines in enterprise projects. One was tracking rates of financial instruments, where they would be in various states of validity (i.e. is it a live offer?). Another was a logistics app, where data would move through various states of being cleansed and approved, or rejected. We built a UI around it. By isolating the state definitions and their transitions, it was easy to validate the program's model with business exprts.
Simple, because most developers are not computer scientists i.e. no formal training in finite automata, computability, complexity, nondeterminism, regular expressions, non regular languages, context free grammars and languages, Turing machines, halting problem and underlying math in general.
If they did, trust me they would use state machines without too much reservation where appropriate. But as it is, the concept is foreign to most and good ones intuit their way into implementing one perhaps (just guessing here).
It'd be interesting to poll programmers who have computer science degrees, electrical engineering degrees, and are self taught to understand the percentage of each who understands state machines, even just at a basic level.
I'll wager electrical engineers understand state machines more often than the other two categories. Stage machines are rather useful in designing hardware.
Indeed. It gets so tiresome looking at yet another 500 line subroutine with else-if after else-if snaking down page after page.
That said, I managed to get through my BSCS without taking the "Finite State Automata" class. I had to pick up table driven methods later, first just fetching values out of a "table", then later generalizing to code-blocks/functions.
At least one way of conceptualizing and implementing a state machine can be simply summed up for the newb:
* Where am I?
* What just happened?
* What do I do next because of it?
Generate an enum for each of the first 2, and put code references into some kind of "sparsely populated" 2-D array, and you're off to the races. TMTOWTDI, but this approach goes a long way towards demystifying the topic.
Couldn't you just say: all developers use state machines, some just aren't sophisticated enough to know it?
I'd even say that today, most developers use fairly explicitly defined state machines (like there is even a code entity called "state machine" somewhere.) Every time they fire up a regular expression.
I (as a Java developer) use state machines often - and know other developers who do same too. I use mostly enums (though there are other ways of achieving it), as explained in this post:
I've always used a state machine whenever I've parsed XML using an event based parser (SAX).
Although lately I've been replacing an explicit state variable with a stack containing the current element path, since that's pretty easy to do using modern languages.
I agree with the discussion here. State machines are very useful. The best thing about them is how easy they makes documentation. You just draw a state diagram and you're done!
Having used state machines a lot for embedded development, I find that they have one huge drawback: the resulting C code is unreadable, which turns maintenance into a nightmare.
SM have a key quality: they are a compact and unambiguous way for specifying a behavior. If your system's behavior is set in stone, it's worth specifying it as a SM and implementing it as one. This SM is also great to include in a spec, standard, RFC etc. But if the system evolves, small changes can require dramatic reshaping of the machine.
Also, they can lead to very efficient implementations, especially if you don't have the benefits of a serious OS with a fancy scheduler underneath.
Amen. I think the only reason state machines are popular in microcontroller work (not really "embedded" -- big SoC software looks like desktop software) is that they're a common hardware implementation choice. And most of those uC programmers are EE cast offs who look to hardware for their reference of taste and not "software engineering".
So they suck in a bad implementation choice because it looks pretty to them. Not so different than the way most Java development works, honestly.
But, yes, you are probably right. When I was taught embedded systems we did do software work, usually on small memory footprints, and state machines were what was taught.
Except, as I was careful to point out, when it's bad. I hoped my example was useful: people think the OO hell ("class Point", "class Length", ...) in Java is "pretty" too. Aesthetics are squishy. It's easy to point to great code and infer that it's beautiful to other great coders.
But that doesn't change the fact that most people have pretty awful taste. The affinity of uC hackers to state machines, IMHO, is a good example of this.
I am not sure that the accusation of unreadability is valid.
The advantage of a state machine is that you can enforce invariants - if you're in state X, then you know categorically that preconditions { X0,X1... Xn} have been met.
Any enum with clear transition logic is effectively a state machine. However, if you try to implement SMs as separate classes/objects with explicit transition functions, than it does become an unreadable mess. The logic in your code stops representing behavior. I think that's what the grandparent post refers to. Also, "explicit" state machines don't allow to use recursion, which can made code much more readable.
Is it really so unreadable? It's not crystal-clear like perfectly linear code as you sometimes have to follow the flow of the state machine through various functions, but syntax-wise once I discovered structs and typedefs, managing state was simple and concise.
Exactly my experience. Over the years we've tried many different ways of coding state machines and it's very hard to keep them readable. Still we continue to use them, the pros outweigh the cons.
There's a pretty interesting RTOS approach based on state machines (www.state-machine.com, no less) that uses single-stack run-to-completion "tasks". They also have some kind of wizard approach to generate code but I haven't had enough time to evaluate it.
For anyone who finds state machines in HLLs unreadable, try looking at a state machine implemented in ladder logic on a PLC!
It seems to me that, if all of your state machines follow a common pattern, seeing enough of them would make it easier to decipher any given state machine. To a programmer who's never seen an event loop with states represented in a switch block or as function pointers, it may seem unreadable.
The readability really depends on your tools. There are state-machines compilers that generate code with e.g. #line directives that hint to the debugger what you want, and even full-fledged IDEs that show the state-transition.
Now if there is a bug in your state-machine compiler, that can be hairy (and it does happen) but the same is true if there is a bug in your C compiler.
Event-driven programming is a popular model for writing programs for tiny embedded systems and sensor network nodes. While event-driven programming can keep the memory overhead down, it enforces a state machine programming style which makes many programs difficult to write, main- tain, and debug. We present a novel programming abstraction called protothreads that makes it possible to write eventdriven programs in a thread-like style, with a memory overhead of only two bytes per protothread. We show that protothreads significantly reduce the complexity of a number of widely used programs previously written with event-driven state machines. For the examined programs the majority of the state machines could be entirely removed. In the other cases the number of states and transitions was drastically decreased. With protothreads the number of lines of code was reduced by one third. The execution time overhead of protothreads is on the order of a few processor cycles.
FSM are very common in video games. I've also worked with one in a (very very) big engineering/CAD software when FSM was managing the whole approval/review/audit flow .
It seems there just less common with web dev in general.
Not sure if I understand the author correctly, but it seems to me, that he advises to write the state machine behaviour down as code (in form of a class? api? little frameowork?) when you start a project, so that you will be able to use a cleanly written interface for your state machine when the project gets bigger. Is my understanding correct?
From my experience a state machine is more of a pattern then a real object. Implementing it on the fly is what worked best so far, for me. Of course there is a point where it gets nasty because of complexity. But first that is always the case (complexity IS nasty) and second overcommiting to structure and architecture increases the complexity already in the beginning and might hurt more then it helps. At least fully coding all possible state machine behaviour as the first default task ifor every new project doesn't seem to be a smart thing to do.
Pretty much every embedded system used for a consumer electronics device is driven by a state-machine. They are really fairly fundamental to embedded development. I suspect this guy is talking about (and dealing with) mostly web developers and people who don't sit so close to the metal.
In my current position it's entirely expected and reasonable to write some code and then half way through go back and rip parts of it out and turn it into a statemachine. Though generally we produce fairly detailed designs of our SMs first.
The act of going back over previously written code that is headed down the wrong path to refactor it to be more flexible/modular before you write your next feature with that code is almost always worth it. It's not worth it if you're never going to extend this feature ever again, but chances are, if you're revisiting a feature right now you'll revisit it again later.
I disagree with the author; most developers' attitudes toward state machines are poisoned not by academic experience but by experience with other developers' half-assed state machines. Back in '93 or so I used state machines extensively for protocol handling within HACMP's cluster manager. It worked very well, but there were still complaints which all came down to the broken-up control flow that state machines introduce:
* The code can be harder to understand, even for those accustomed to the model, because of the need to maintain context manually across states and events. Let's face it: having your variables on the stack is awfully convenient, even if there are good reasons not to do things that way.
* Speaking of stacks, the #1 complaint I used to get was that with the FSM stack traces would only go back to the FSM engine with no history of previous transitions. This is why IMO any decent FSM implementation must keep some history itself.
* A related issue is that static code analysis can't follow through the transition table to recognize the actual flows of control. A good FSM-based program must therefore include stub programs (which can be automatically generated) which will invoke actions in expected sequences so that code checkers can find invalid references, leaks, missing unlocks, and son on.
I like FSMs and think they should be used more. Nonetheless, if you gave me a state machine with ad hoc context management, no history and no reasonable way to generate test stubs, I'd barf too. If more people implemented good state machines, more people would recognize their benefits.
Yes, but sometimes you need logic that takes place on all exits from a state, on all entries to a state, or even form a hierarchy of nested state. Often there's more "state" involved (like accumulating intermediate values) and a switch statement isn't friendly to scoping that.
I love writing switch statements (even with gotos) for small things like lexical analyzers, but when it comes to maintainability and extensibility, a well-designed framework is the way to go.
The Boost C++ libraries supply two of them. I've used one of them and am eying the other. They claim its template magic can make the result actually faster than a typical switch-driven design.
95 comments
[ 3.3 ms ] story [ 158 ms ] threadThey organize complex code, dissect complex set-flag-here-and-test-there spaghetti into a matrix of states and events that can be exhaustively examined and debugged.
Yes you have to organize your code to feed the machine (Vol is hungry! We must feed Vol!) But you have to organize your code somehow, and feeding a state machine can actually be easier to understand that flag-setting. In fact, it makes it absolutely clear what an event is associated with - the machine it feeds.
Many parsers make use of PDAs when they parse source code.
I think I read it in one of the "AI programming Gems" books.
https://github.com/stephenb/coffee-machine
Of course having nicely isolated processes probably helps noticing that you have an ad-hoc state machine on your hands.
[0] http://www.erlang.org/doc/design_principles/fsm.html
http://zedshaw.com/essays/ragel_state_charts.html
What I really like there is the idea of a DSL that generates your state machine code for a protocol.
Procedural logic tends to be brittle - small changes have unintended consequences. Declarative models tend to be more robust and, especially with domain-specific languages, safer for domain experts to manipulate. You can certainly design domain-specific languages for the subset of declarative systems that are state machines.
I've happily used state machines in enterprise projects. One was tracking rates of financial instruments, where they would be in various states of validity (i.e. is it a live offer?). Another was a logistics app, where data would move through various states of being cleansed and approved, or rejected. We built a UI around it. By isolating the state definitions and their transitions, it was easy to validate the program's model with business exprts.
If they did, trust me they would use state machines without too much reservation where appropriate. But as it is, the concept is foreign to most and good ones intuit their way into implementing one perhaps (just guessing here).
I'll wager electrical engineers understand state machines more often than the other two categories. Stage machines are rather useful in designing hardware.
That said, I managed to get through my BSCS without taking the "Finite State Automata" class. I had to pick up table driven methods later, first just fetching values out of a "table", then later generalizing to code-blocks/functions.
At least one way of conceptualizing and implementing a state machine can be simply summed up for the newb:
* Where am I?
* What just happened?
* What do I do next because of it?
Generate an enum for each of the first 2, and put code references into some kind of "sparsely populated" 2-D array, and you're off to the races. TMTOWTDI, but this approach goes a long way towards demystifying the topic.
I'd even say that today, most developers use fairly explicitly defined state machines (like there is even a code entity called "state machine" somewhere.) Every time they fire up a regular expression.
They're not using state machines, in that case it just happens to be an implementation detail of the regular expression library they're using.
I have always found this streamlining at least one change in the couple of months after initial implementation.
Java Secret: Using an enum to build a State machine: http://vanillajava.blogspot.com/2011/06/java-secret-using-en...
Although lately I've been replacing an explicit state variable with a stack containing the current element path, since that's pretty easy to do using modern languages.
I don't follow this? The core of whichever state machines I write seem to be DFAs, with the alphabet being events causing transitions.
Then again, I think they're far more common in the embedded world than elsewhere.
SM have a key quality: they are a compact and unambiguous way for specifying a behavior. If your system's behavior is set in stone, it's worth specifying it as a SM and implementing it as one. This SM is also great to include in a spec, standard, RFC etc. But if the system evolves, small changes can require dramatic reshaping of the machine.
Also, they can lead to very efficient implementations, especially if you don't have the benefits of a serious OS with a fancy scheduler underneath.
So they suck in a bad implementation choice because it looks pretty to them. Not so different than the way most Java development works, honestly.
But, yes, you are probably right. When I was taught embedded systems we did do software work, usually on small memory footprints, and state machines were what was taught.
An implementation choice that looks pretty is often a good implementation choice.
But that doesn't change the fact that most people have pretty awful taste. The affinity of uC hackers to state machines, IMHO, is a good example of this.
There's a pretty interesting RTOS approach based on state machines (www.state-machine.com, no less) that uses single-stack run-to-completion "tasks". They also have some kind of wizard approach to generate code but I haven't had enough time to evaluate it.
For anyone who finds state machines in HLLs unreadable, try looking at a state machine implemented in ladder logic on a PLC!
It seems to me that, if all of your state machines follow a common pattern, seeing enough of them would make it easier to decipher any given state machine. To a programmer who's never seen an event loop with states represented in a switch block or as function pointers, it may seem unreadable.
Now if there is a bug in your state-machine compiler, that can be hairy (and it does happen) but the same is true if there is a bug in your C compiler.
"Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems" http://www.sics.se/~adam/dunkels06protothreads.pdf
source files (~60 lines without comments): http://www.sics.se/~adam/pt/
abstract:
Event-driven programming is a popular model for writing programs for tiny embedded systems and sensor network nodes. While event-driven programming can keep the memory overhead down, it enforces a state machine programming style which makes many programs difficult to write, main- tain, and debug. We present a novel programming abstraction called protothreads that makes it possible to write eventdriven programs in a thread-like style, with a memory overhead of only two bytes per protothread. We show that protothreads significantly reduce the complexity of a number of widely used programs previously written with event-driven state machines. For the examined programs the majority of the state machines could be entirely removed. In the other cases the number of states and transitions was drastically decreased. With protothreads the number of lines of code was reduced by one third. The execution time overhead of protothreads is on the order of a few processor cycles.
I've been doing embedded development for a few years and I love our state machines, they're a pleasure to work with. Maybe yours just sucked.
FSM are very common in video games. I've also worked with one in a (very very) big engineering/CAD software when FSM was managing the whole approval/review/audit flow .
It seems there just less common with web dev in general.
From my experience a state machine is more of a pattern then a real object. Implementing it on the fly is what worked best so far, for me. Of course there is a point where it gets nasty because of complexity. But first that is always the case (complexity IS nasty) and second overcommiting to structure and architecture increases the complexity already in the beginning and might hurt more then it helps. At least fully coding all possible state machine behaviour as the first default task ifor every new project doesn't seem to be a smart thing to do.
In my current position it's entirely expected and reasonable to write some code and then half way through go back and rip parts of it out and turn it into a statemachine. Though generally we produce fairly detailed designs of our SMs first.
* The code can be harder to understand, even for those accustomed to the model, because of the need to maintain context manually across states and events. Let's face it: having your variables on the stack is awfully convenient, even if there are good reasons not to do things that way.
* Speaking of stacks, the #1 complaint I used to get was that with the FSM stack traces would only go back to the FSM engine with no history of previous transitions. This is why IMO any decent FSM implementation must keep some history itself.
* A related issue is that static code analysis can't follow through the transition table to recognize the actual flows of control. A good FSM-based program must therefore include stub programs (which can be automatically generated) which will invoke actions in expected sequences so that code checkers can find invalid references, leaks, missing unlocks, and son on.
I like FSMs and think they should be used more. Nonetheless, if you gave me a state machine with ad hoc context management, no history and no reasonable way to generate test stubs, I'd barf too. If more people implemented good state machines, more people would recognize their benefits.
I love writing switch statements (even with gotos) for small things like lexical analyzers, but when it comes to maintainability and extensibility, a well-designed framework is the way to go.
The Boost C++ libraries supply two of them. I've used one of them and am eying the other. They claim its template magic can make the result actually faster than a typical switch-driven design.