Why Developers Never Use State Machines
skorks.com
skorks.com
After I got more comfortable with actually using them for real work (as opposed to "cute toy from CS class"), I started seeing FSMs everywhere I looked in my projects.
For one thing, they make analytics a lot easier to slot into your system. For example, I record the fact of interesting events like e.g. purchases and send it off to KissMetrics or internal analytics stuff for graphing/reporting/auditing/etc. That gets done in my controllers, and it results in a whole lot of duplicative code which I often forget to write. (It's easy to miss that e.g. if I credit somebody manually for a purchase that should count as a purchase, even though it is under admin functions rather than the purchasing pathway. After all, if I forget to write that log code, all that happens is my stats get silently borked.)
This could get fairly easily solved by having the logging code aware of the change in the user's status, which is about three lines if you have a state machine, and won't put the logging logic in 12 different places in your app or cause you to have to pollute the user model with a big ol' case statement of doom. Plus, if you want to log more stuff, you naturally go into the log logic and make it do more things when the right events bubble to it, rather than chasing down a) who "owns" the event or b) where the event happens.
Essentially my first take at the phone stuff I had done (a bit over 3 years ago) was to just roll into a single view and hack my way through it. The requirements (at the time) were relatively simple and this served us well for 3 years.
Now our requirements for phone calls has really changed as we've added things like voice prompts, whisper files, user interaction, and a bunch of other doo-dads. Worse yet, the presence (and behavior) of these states can now vary by the customer that is using them.
So I broke that jumble of code into a state machine with clear transitions. Each state farms the actual functionality to defined strategies which can be specified on a per-customer basis.
It works like a charm:)
An FST allows you to accurately model 'outputs' on state transitions (where those outputs can be side-effects like 'make a call' or 'send an invoice.' This allows you to prove things about what sort of side-effects/outputs will necessarily have occurred by the time the FST is in a certain state.
I started with an FSM but, found in practice, I was using it like a poorly written FST.
Sometimes I used FSM's during the design phase of a project to model system behavior, but I'd end up implementing them pretty crudely with spaghetti code or case statements. Looking back, it would have made more sense to explicitly implement the FSM in the code.
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.
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.
enum {
APP_START,
APP_INIT,
APP_DO_TASK_A,
APP_DO ..
APP_FREE,
APP_QUIT
}
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.
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.
The big problem with state machines relates to the number 3 and regards the general concept of "state". Managing state is the challenge of computation! As you add states and transitions, the complexity increases dramatically, exponentially in some cases. This is why novice programmers struggle to manage developing large applications: they depend on global state and side-effects to perform computation rather than creating isolated components (classes, methods/functions)
That is why we use higher level abstractions provided by programming languages. We use state machines unknowingly in our code every time we have a switch or a conditional statement. When we use design patterns such as the GoF state pattern, we are implementing a state machine. When we build closures in functional languages, those can be considered state machines (in an abstract way). It's just that we're doing it in a more intuitive, higher-level way.
What I'm getting at is that computer programs inherently contain state machines. Recall from computer science that a a stored program computer (e.g. Turing machine, Von Neumann architecture) is just a state machine with an unlimited memory. When we deal with more complexity, it's not wise to attempt to model the problem with a state machine. Using the constructs of a high level language are easier to deal with and underneath the hood, the appropriate state machines are being created.
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.
Java Secret: Using an enum to build a State machine: http://vanillajava.blogspot.com/2011/06/java-secret-using-en...
Of course having nicely isolated processes probably helps noticing that you have an ad-hoc state machine on your hands.
http://lambda-the-ultimate.org/node/4009
It's based on Typestate, a really good 1986 paper:
http://www.cs.cmu.edu/~aldrich/papers/classic/tse12-typestat...
I hope this idea catches on in other programming languages.
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.
The article date looks different, now, and IBM has redesigned the site since I originally read it, but I think -- at a glance -- that it's the same article.
http://www.ibm.com/developerworks/library/wa-finitemach1/
http://www.ibm.com/developerworks/web/library/wa-finitemach2...
http://www.ibm.com/developerworks/web/library/wa-finitemach3...
However IBM did it, they were entered into some sort of site publishing schedule such that he'd lost track of just when they were coming out.
Seemed a nice enough fellow. From the articles and his bio, I imagine (perhaps incorrectly) his motivation was more pedagogical than remunerative.
The blogpost about it:
http://codeincomplete.com/posts/2011/8/19/javascript_state_m...
The online demo:
http://codeincomplete.com/posts/2011/8/19/javascript_state_m...
Many parsers make use of PDAs when they parse source code.
I think I read it in one of the "AI programming Gems" books.
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.
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.
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.
I'd highly recommend using state machines for multi-step forms. It feels very natural and keeps you sane, I believe it should be a best practice.
That's interesting. Can you elaborate on it, maybe with an example?
You can check out Spree's state machine for the checkout process here: https://github.com/spree/spree/blob/master/core/app/models/o... (starts at line 83). Notice that the Order model is the state machine.
also, fwiw, i think, couroutines are to state-machines as subroutines are to goto. the best tutorial on teh web on this is, imho, by dave-beazley here: http://www.dabeaz.com/coroutines/index.html
In a way any web app with a login is also a state machine - there's the logged in state, and the not logged in state.
erlang has a very effective state machine library(behavior). But the downside is that it's erlang. http://www.erlang.org/doc/design_principles/fsm.html
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.
In object orientated software engineering the State pattern is a pattern for cleanly implementing a state machine* whilst avoiding horrible switch or massive nested if-then statements.
It's possible to build some gorgeous state machine networks with lambda functions and dictionaries.
I have always found this streamlining at least one change in the couple of months after initial implementation.
Then again, I think they're far more common in the embedded world than elsewhere.
* 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.
a) Most I speak to had a Z-rate CS education which scraped a bit of OO design in Java and don't know they really exist.
b) Most languages they cut their first code in are about puking data around from SQL to the web which rarely if ever requires an FSM.
c) Someone thumped them over the head with "Windows Workflow for dummies" which is then assumed to be the answer to all stateful problems.
d) It looks hard so they don't bother.
e) "developers" should not be confused with "computer scientists". It's "builders" versus "engineers".
I don't follow this? The core of whichever state machines I write seem to be DFAs, with the alphabet being events causing transitions.
I think he is referring mostly to a finite state machine, though. But even then, you have that quite often somehow in your code (think of global boolean variables).
That said, some programs have state that is more finite than others. :-) Deep down, a "state machine-based design" is a mindset of the designer.