9 ms·

Why Developers Never Use State Machines

237 points by fogus 15y ago

JoeAltmaier 15y ago
Use them all the time, have for all my career. 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.
- moondowner 15y ago
  True, it's better to have a set of states instead of a dozen boolean values. It gives better code, and better organized databases too.
davedx 15y ago
This man has never heard of video game A.I. programming :)
- fs111 15y ago
  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.
- pagekalisedown 15y ago
  I had the same reaction. Almost nothing but FSMs in game AI. Makes me wonder if we need to look beyond FSMs for the next level of intelligence.
  - RodgerTheGreat 15y ago
    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?
    - tomjen3 15y ago
      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.
    - davedx 15y ago
      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'.
  - xtracto 15y ago
    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 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.
    - slowpoke 15y ago
      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.
  - _delirium 15y ago
    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.
  - swaits 15y ago
    We use hierarchical state machines (i.e. statecharts) quite a bit in our games.
- signa11 15y ago
  hmm, i thought behavior-trees are predominantly used for large scale / fairly complicated games.
wccrawford 15y ago
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: https://github.com/stephenb/coffee-machine https://github.com/stephenb/coffee-machine
masklinn 15y ago
It's used a lot in Erlang, FWIW. It's used so much that OTP has a built-in finite state machine behavior[0]. 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://www.erlang.org/doc/design_principles/fsm.html
wslh 15y ago
State Machines are also useful when you need to develop on asynchronous environments but think in a more synchronous way.
conductor 15y ago
If you are a C developer, try Ragel [http://www.complang.org/ragel http://www.complang.org/ragel]. I use it lot, also can be easily pared with the Lemon parser generator.
- tom_b 15y ago
  For more re: Ragel, look at http://zedshaw.com/essays/ragel_state_charts.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.
hessenwolf 15y ago
I think in state machines all the time, and I have it second hand that telecoms services in South America mostly run on state machines.
splicer 15y ago
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 ;)
mmahemoff 15y ago
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.
super_mario 15y ago
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).
- bradfa 15y ago
  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.
- Roboprog 15y ago
  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.
- Nelson69 15y ago
  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.
bmcleod 15y ago
I've been adding a state machine whenever I find myself adding a state column for a couple of years now. I have always found this streamlining at least one change in the couple of months after initial implementation.
foobarbazoo 15y ago
SproutCore has an entire statechart framework built into it. Not sure where the OP is getting his data...
moondowner 15y ago
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: Java Secret: Using an enum to build a State machine: http://vanillajava.blogspot.com/2011/06/java-secret-using-enum-as-state-machine.html http://vanillajava.blogspot.com/2011/06/java-secret-using-en...
kennu 15y ago
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.
- caf 15y ago
  Parsing textual formats in general usually ends up being a state machine - eg. CSV is another one.
probablyrobots 15y ago
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!
sid0 15y ago
most state machines you're likely to need in your day-to-day development have nothing in common with their computing theory counterparts I don't follow this? The core of whichever state machines I write seem to be DFAs, with the alphabet being events causing transitions.
- amouat 15y ago
  I think the point is that you don't need to know all the dry theory and the names for everything.
gte910h 15y ago
There are over 10 occasions I can remember using one specifically in a project. I'm sure I've used them several more times. Then again, I think they're far more common in the embedded world than elsewhere.
fab13n 15y ago
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.
- Symmetry 15y ago
  What he said. State machines make doing things like figuring out how to from random power loss much, much easier.
- ajross 15y ago
  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.
  - ErrantX 15y ago
    Hoi! I am an EE "cast off" :) 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.
  - snikolov 15y ago
    So they suck in a bad implementation choice because it looks pretty to them An implementation choice that looks pretty is often a good implementation choice.
philgo20 15y ago
We use FSM to deal with the hiring/applicant flow at http://matchfwd.com http://matchfwd.com 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.
oinksoft 15y ago
I think the author should bold, quote, and italicize more phrases.
erikb 15y ago
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.
tseabrooks 15y ago
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.
- Fluxx 15y ago
  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.
phamilton 15y ago
While I don't use state machines in code that often, I do use them on paper all the time.
CPlatypus 15y ago
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.
perfunctory 15y ago
I never understood why one needs a framework or a library for state machines. Can't you just write a switch statement.
- marshray 15y ago
  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.
albertzeyer 15y ago
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).
- marshray 15y ago
  Well the memory available to the processor for state is finite, too. Thus, every classical computer is a finite state machine. 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.
  - deepinit_a 15y ago
    Well said!
schiptsov 15y ago
guess what is nginx? ^_^
ender7 15y ago
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.
- pasbesoin 15y ago
  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. http://www.ibm.com/developerworks/library/wa-finitemach1/ 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-finitemach2... http://www.ibm.com/developerworks/web/library/wa-finitemach3/index.html http://www.ibm.com/developerworks/web/library/wa-finitemach3...
  - rhizome 15y ago
    I have to think that somewhere around 2007 IBM started offering massive bonuses for writing site content and HOWTOs.
    - pasbesoin 15y ago
      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.
- qohen 15y ago
  There are other JS FSM libraries, but I ran into this one recently, which has an online demo: The blogpost about it: http://codeincomplete.com/posts/2011/8/19/javascript_state_machine_v2/ http://codeincomplete.com/posts/2011/8/19/javascript_state_m... The online demo: http://codeincomplete.com/posts/2011/8/19/javascript_state_machine_v2/example/ http://codeincomplete.com/posts/2011/8/19/javascript_state_m...
relix 15y ago
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.
- IProgrammer 15y ago
  >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?
  - relix 15y ago
    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). You can check out Spree's state machine for the checkout process here: https://github.com/spree/spree/blob/master/core/app/models/order.rb https://github.com/spree/spree/blob/master/core/app/models/o... (starts at line 83). Notice that the Order model is the state machine.
Maro 15y ago
I spent the last 3 years writing a distributed database which is basically a state machine (it's built on top of Paxos). http://github.com/scalien/scaliendb http://github.com/scalien/scaliendb
mas644 15y ago
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.
- Roboprog 15y ago
  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.
patio11 15y ago
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.
- enjo 15y ago
  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. It works like a charm:)
bchallenor 15y ago
The Rust language (by Mozilla) is putting statically verifiable state machines in the type system: http://lambda-the-ultimate.org/node/4009 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-typestate.pdf http://www.cs.cmu.edu/~aldrich/papers/classic/tse12-typestat... I hope this idea catches on in other programming languages.
UrLicht 15y ago
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.
signa11 15y ago
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 http://www.dabeaz.com/coroutines/index.html
whatgoodisaroad 15y ago
I literally just finished writing a state machine before opening Hacker News.
deleted 15y ago
[deleted]
KevinMS 15y ago
Mail servers are state machines. The SMTP protocol is all about state. 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 http://www.erlang.org/doc/design_principles/fsm.html
pnathan 15y ago
I don't understand the problem. State machines always seemed like a reasonable choice to a stateful system making transitions between states. It's possible to build some gorgeous state machine networks with lambda functions and dictionaries.
radicalbyte 15y ago
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.
swah 15y ago
Do you guys think a drawing program should be more easily modeled with a FSM?
nkh 15y ago
Can anyone recommend a good python library for state machines and example code of its use?
pointyhat 15y ago
In my experience, why "developers" never use state machines: 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".
- cbs 15y ago
  Unfortunately for our industry, a lot of your post is right, and it doesn't just apply to state machines, but a lot of solid programming practices.
deleted 15y ago
[deleted]
jonutzz 15y ago
too bad I am a web developer!
cpeterso 15y ago
"A Computer is a state machine. Threads are for people who can't program state machines." -- Alan Cox
alanh 15y ago
This article inspired me to go ahead and actually use a state machine for what I’ve been working on. I love the resulting clarity in my code. ❤

237 points by fogus 15y ago

Use them all the time, have for all my career. 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.

moondowner 15y ago
True, it's better to have a set of states instead of a dozen boolean values. It gives better code, and better organized databases too.

davedx 15y ago

This man has never heard of video game A.I. programming :)

fs111 15y ago
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.
pagekalisedown 15y ago
I had the same reaction. Almost nothing but FSMs in game AI. Makes me wonder if we need to look beyond FSMs for the next level of intelligence.
- RodgerTheGreat 15y ago
  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?
  - tomjen3 15y ago
    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.
  - davedx 15y ago
    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'.
- xtracto 15y ago
  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 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.
  - slowpoke 15y ago
    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.
- _delirium 15y ago
  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.
- swaits 15y ago
  We use hierarchical state machines (i.e. statecharts) quite a bit in our games.
signa11 15y ago
hmm, i thought behavior-trees are predominantly used for large scale / fairly complicated games.

wccrawford 15y ago

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: https://github.com/stephenb/coffee-machine https://github.com/stephenb/coffee-machine

masklinn 15y ago

It's used a lot in Erlang, FWIW. It's used so much that OTP has a built-in finite state machine behavior[0]. 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://www.erlang.org/doc/design_principles/fsm.html

wslh 15y ago

State Machines are also useful when you need to develop on asynchronous environments but think in a more synchronous way.

conductor 15y ago

If you are a C developer, try Ragel [http://www.complang.org/ragel http://www.complang.org/ragel]. I use it lot, also can be easily pared with the Lemon parser generator.

tom_b 15y ago
For more re: Ragel, look at http://zedshaw.com/essays/ragel_state_charts.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.

hessenwolf 15y ago

I think in state machines all the time, and I have it second hand that telecoms services in South America mostly run on state machines.

splicer 15y ago

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 ;)

mmahemoff 15y ago

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.

super_mario 15y ago

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).

bradfa 15y ago
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.
Roboprog 15y ago
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.
Nelson69 15y ago
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.

bmcleod 15y ago

I've been adding a state machine whenever I find myself adding a state column for a couple of years now. I have always found this streamlining at least one change in the couple of months after initial implementation.

foobarbazoo 15y ago

SproutCore has an entire statechart framework built into it. Not sure where the OP is getting his data...

moondowner 15y ago

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: Java Secret: Using an enum to build a State machine: http://vanillajava.blogspot.com/2011/06/java-secret-using-enum-as-state-machine.html http://vanillajava.blogspot.com/2011/06/java-secret-using-en...

kennu 15y ago

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.

caf 15y ago
Parsing textual formats in general usually ends up being a state machine - eg. CSV is another one.

probablyrobots 15y ago

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!

sid0 15y ago

most state machines you're likely to need in your day-to-day development have nothing in common with their computing theory counterparts I don't follow this? The core of whichever state machines I write seem to be DFAs, with the alphabet being events causing transitions.

amouat 15y ago
I think the point is that you don't need to know all the dry theory and the names for everything.

gte910h 15y ago

There are over 10 occasions I can remember using one specifically in a project. I'm sure I've used them several more times. Then again, I think they're far more common in the embedded world than elsewhere.

fab13n 15y ago

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.

Symmetry 15y ago
What he said. State machines make doing things like figuring out how to from random power loss much, much easier.
ajross 15y ago
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.
- ErrantX 15y ago
  Hoi! I am an EE "cast off" :) 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.
- snikolov 15y ago
  So they suck in a bad implementation choice because it looks pretty to them An implementation choice that looks pretty is often a good implementation choice.

philgo20 15y ago

We use FSM to deal with the hiring/applicant flow at http://matchfwd.com http://matchfwd.com 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.

oinksoft 15y ago

I think the author should bold, quote, and italicize more phrases.

erikb 15y ago

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.

tseabrooks 15y ago

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.

Fluxx 15y ago
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.

phamilton 15y ago

While I don't use state machines in code that often, I do use them on paper all the time.

CPlatypus 15y ago

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.

perfunctory 15y ago

I never understood why one needs a framework or a library for state machines. Can't you just write a switch statement.

marshray 15y ago
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.

albertzeyer 15y ago

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).

marshray 15y ago
Well the memory available to the processor for state is finite, too. Thus, every classical computer is a finite state machine. 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.
- deepinit_a 15y ago
  Well said!

schiptsov 15y ago

guess what is nginx? ^_^

ender7 15y ago

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.

pasbesoin 15y ago
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. http://www.ibm.com/developerworks/library/wa-finitemach1/ 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-finitemach2... http://www.ibm.com/developerworks/web/library/wa-finitemach3/index.html http://www.ibm.com/developerworks/web/library/wa-finitemach3...
- rhizome 15y ago
  I have to think that somewhere around 2007 IBM started offering massive bonuses for writing site content and HOWTOs.
  - pasbesoin 15y ago
    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.
qohen 15y ago
There are other JS FSM libraries, but I ran into this one recently, which has an online demo: The blogpost about it: http://codeincomplete.com/posts/2011/8/19/javascript_state_machine_v2/ http://codeincomplete.com/posts/2011/8/19/javascript_state_m... The online demo: http://codeincomplete.com/posts/2011/8/19/javascript_state_machine_v2/example/ http://codeincomplete.com/posts/2011/8/19/javascript_state_m...

relix 15y ago

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.

IProgrammer 15y ago
>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?
- relix 15y ago
  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). You can check out Spree's state machine for the checkout process here: https://github.com/spree/spree/blob/master/core/app/models/order.rb https://github.com/spree/spree/blob/master/core/app/models/o... (starts at line 83). Notice that the Order model is the state machine.

Maro 15y ago

I spent the last 3 years writing a distributed database which is basically a state machine (it's built on top of Paxos). http://github.com/scalien/scaliendb http://github.com/scalien/scaliendb

mas644 15y ago

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.

Roboprog 15y ago
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.

patio11 15y ago

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.

enjo 15y ago
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. It works like a charm:)

bchallenor 15y ago

The Rust language (by Mozilla) is putting statically verifiable state machines in the type system: http://lambda-the-ultimate.org/node/4009 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-typestate.pdf http://www.cs.cmu.edu/~aldrich/papers/classic/tse12-typestat... I hope this idea catches on in other programming languages.

UrLicht 15y ago

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.

signa11 15y ago

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 http://www.dabeaz.com/coroutines/index.html

whatgoodisaroad 15y ago

I literally just finished writing a state machine before opening Hacker News.

deleted 15y ago

[deleted]

KevinMS 15y ago

Mail servers are state machines. The SMTP protocol is all about state. 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 http://www.erlang.org/doc/design_principles/fsm.html

pnathan 15y ago

I don't understand the problem. State machines always seemed like a reasonable choice to a stateful system making transitions between states. It's possible to build some gorgeous state machine networks with lambda functions and dictionaries.

radicalbyte 15y ago

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.

swah 15y ago

Do you guys think a drawing program should be more easily modeled with a FSM?

nkh 15y ago

Can anyone recommend a good python library for state machines and example code of its use?

pointyhat 15y ago

In my experience, why "developers" never use state machines: 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".

cbs 15y ago
Unfortunately for our industry, a lot of your post is right, and it doesn't just apply to state machines, but a lot of solid programming practices.

deleted 15y ago

[deleted]

jonutzz 15y ago

too bad I am a web developer!

cpeterso 15y ago

"A Computer is a state machine. Threads are for people who can't program state machines." -- Alan Cox

alanh 15y ago

This article inspired me to go ahead and actually use a state machine for what I’ve been working on. I love the resulting clarity in my code. ❤