State Machines

State machines are a powerful approach for programming, but often expressing them in structured languages can be inelegant- state machines and error handling are the primary applications of "goto" in C. They aren't an impassible obstacle, though, if you're working with a language that can define new syntax easily.<p>I am reminded of a particularly interesting DSL[1] for Forth that makes state machines look like their transition tables:<p><pre><code> 4 WIDE FSM: &#60;Fixed.Pt#&#62; \ input: | other? | num? | minus? | dp? | \ state: --------------------------------------------- ( 0 ) DROP &#62;0 EMIT &#62;1 EMIT &#62;1 EMIT &#62;2 ( 1 ) DROP &#62;1 EMIT &#62;1 DROP &#62;1 EMIT &#62;2 ( 2 ) DROP &#62;2 EMIT &#62;2 DROP &#62;2 DROP &#62;2 ; </code></pre> [1]<a href="http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html" rel="nofollow">http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm....</a>

One absolutely phenomenal implementation of a state machine is in Intel's Thread Building Blocks library. They (somewhat[1]) recently added a feature called flow graphs, which is an abstraction over tasks (themselves an abstraction over threads). I've yet to find a better control structure for concurrent scheduling problems.<p>TBB isn't NUMA-aware though, which limits its use in HPC.<p>[1] <a href="http://software.intel.com/en-us/blogs/2011/09/08/the-intel-threading-building-blocks-flow-graph-is-now-fully-supported/" rel="nofollow">http://software.intel.com/en-us/blogs/2011/09/08/the-intel-t...</a>

He neglected to mention PDAs (push-down automaton) - which is basically the same concept as a DFA or NFA but with a stack.<p>State transitions can manipulate the stack, and the top of a stack can be used to pick which state to move to.<p>PDAs aren't as powerful as Turing machines, but they are able to parse any context free grammar, so they are able to recognize languages that contain any number of 'a' characters followed by the same number of 'b' characters.

It may be worthwhile realizing that most programming or specification languages describe State Machines [1], more or less explicitly (sorry if this is obvious). Moreover State Machines can be described using ordinary mathematics instead of custom programming languages or logics. Hence State Machines could be used as a common denominator to describe all kinds of computation, similarly to what equations written using ordinary mathematics are to physics. According to Leslie Lamport, from whom the ideas in this comment are borrowed, State Machines are also a powerful teaching tool that prevents language from getting in the way of concepts [1].<p>State Machines described in ordinary mathematics have other advantages. For example, substitution distributes over operators in mathematics (but not in most programming languages). This is very handy for deriving an implementation from a specification. Another example is that composition can be treated uniformly by using a single state space for all State Machines.<p>If you are interested in the applications and advantages of describing computation by State Machines you may like reading the works of Leslie Lamport [2] or texts about the ASM method [3].<p>[1] <a href="https://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf" rel="nofollow">https://research.microsoft.com/en-us/um/people/lamport/pubs/...</a><p>[2] <a href="https://research.microsoft.com/en-us/um/people/lamport/" rel="nofollow">https://research.microsoft.com/en-us/um/people/lamport/</a><p>[3] <a href="https://en.wikipedia.org/wiki/Abstract_state_machines" rel="nofollow">https://en.wikipedia.org/wiki/Abstract_state_machines</a>

Udacity's course on programming languages (CS262) explains State Machines, among many other things. Their teaching format is genius. Highly recommended.<p><a href="http://www.udacity.com/overview/Course/cs262/CourseRev/apr2012" rel="nofollow">http://www.udacity.com/overview/Course/cs262/CourseRev/apr20...</a>

I do have a degree in computer science so I know about state machines. Yet I don't use them at all in my code. Am I missing a great opportunity? I know it is close to impossible to answer that question without knowing the problem space, but perhaps there is a nice article about solving (common) problems with state machines?

State machines just seem natural to me. I actually sketched out a state machine before I even knew what a state machine was. The other concept I really like is lookup tables. Reminds me of truth tables. Are state machines really just a form of lookup table? I guess it's just how my mind works because these tables seem natural to me.<p>This is great thread. I have only used lex/flex to make my state machines. I'd like to try something new eventually.

For those interested in symbolically manipulating [1] state machines (NFAs), pushdown automata (PDAs), and context-free grammars (CFGs), take a look at <a href="http://www.grailplus.org" rel="nofollow">http://www.grailplus.org</a>.<p>[1] <a href="http://www.ioreader.com/2011/03/15/pattern-matching-in-grail" rel="nofollow">http://www.ioreader.com/2011/03/15/pattern-matching-in-grail</a>

This is great timing and a really digestible summary. There's a talk on StateManager in Ember.js tonight [1] and I was embarrassed to know nothing about state machines. Glad to be able to attend a little more knowledgeable<p>[1] <a href="http://www.meetup.com/Sproutcore-NYC/events/59870422/" rel="nofollow">http://www.meetup.com/Sproutcore-NYC/events/59870422/</a>

<i>nothing</i> teaches state machines like networking protocols, just look at the server &#38; client fsm's for tftp (rfc-1350).

I use a lot of state machines in my embedded projects. Perhaps it's because I was a developer on a state chart to C converter (www.visualstate.com) some time ago and that have colored me. I find it strange that it isn't more widely used. Perhaps it's a lack of tools for checking deadlocks etc?

1