I use them extensively for Appointment Reminder. In addition to modeling the business logic pretty intuitively (particular types of input can cause an appointment to go from :scheduled to :confirmed, :confirmed appointments should not generate additional reminder calls but :scheduled ones should, etc), they're virtually indispensable for doing Twilio applications. I'll have more to say about that at TwilioConf (and will probably post my presentation afterwards). If you do not model call state with a state machine, anything more complicated than "Hit 1 to talk to sales, hit 2 to talk to support" turns into an ugly ball of spaghetti code with lots of sharp edges, poor testability, and crushing amounts of technical debt getting in the way of maintaining or extending anything.
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.
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.
FST's are used a lot in natural language processing, for example in speech recognition and dialogue systems. In these cases the state transitions are given probabilities (weights), which makes it a weighted 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.
Interestingly I ran into the Twilio example... yesterday.
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.
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.
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.
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.
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.
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!
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.
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.
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.
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.
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.
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.
State machines are useful because they're
1) computationally fast
2) simple to implement
3) easy to read [up to a certain size]
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.
Good points. Sometimes it's nice to be able to visualize an explicit directed graph of states (vertices) and events (edges), though. It helps identify inescapable states and unhandled events.
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).
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.
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.
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:
Can anyone recommend a good introduction to using state machines in code? Especially something in javascript/python? I know what an SM is and how it works, I just want to know how to use an SM library to actually do all these cool things.
A lot of the IBM Developer articles are apparently crap, but I found this one interesting and well done, some years ago.
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.
Your reply motivated me to look, and my vague recollection is correct: I exchanged a couple of brief emails with the author back in 2007, when the articles did indeed first come out.
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.
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 ;)
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.
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'.
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.
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.
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.
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.
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.
I discovered how state machines can be practical when checking the source code of Spree, the rails e-commerce engine. The checkout-process is a state machine.
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.
Basically each step in your form is a state in the state machine. When a user submits one step, you move the state machine to the next state. You can add conditionals for when to skip a step, and you can specify validations for each step that need to be run before a state-change (e.g. credit card needs to check out before moving from the credit card step to the confirm step).
anybody writing networking-protocol code, embedded systems etc. cannot help but use them. to me it seems that the entire article is pretty narrowly focussed on folks doing web development exclusively.
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
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.
They're used all the time. A workflow engine is basically a big state machine. They're used all the time in the Enterprise.
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.
I didn't get a CS degree and therefore had no experience with state machines until I started programming professionally. Maybe that's why I took to them so quickly and used them from the get-go on my personal project. Their usefulness is so obvious.
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!
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.
This is a stupid statement. Pretty much every code depends on a state (i.e. the content of the heap memory) and is thus a state machine (by its most generic definition).
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).
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.