5 ms·

State Machines

67 points by fogus 14y ago

RodgerTheGreat 14y ago
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. I am reminded of a particularly interesting DSL[1] for Forth that makes state machines look like their transition tables: 4 WIDE FSM: <Fixed.Pt#> \ input: | other? | num? | minus? | dp? | \ state: --------------------------------------------- ( 0 ) DROP >0 EMIT >1 EMIT >1 EMIT >2 ( 1 ) DROP >1 EMIT >1 DROP >1 EMIT >2 ( 2 ) DROP >2 EMIT >2 DROP >2 DROP >2 ; [1]http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm....
- 0fa2 14y ago
  You can use coroutines as long as your state machine can be structured like code. Loops are Kleene closures, Ifs are alternation, and lists of statements are concatenation. I used nested C# Enumerators to implement a parser which didn't turn into too much of a mess, but it was a small project. Structured programming limits you in the state machines you can construct, but probably in a good way.
- jpadkins 14y ago
  State machines are very useful in game programming. Unrealscript supports state machines at the language level. http://udn.epicgames.com/Three/UnrealScriptStates.html http://udn.epicgames.com/Three/UnrealScriptStates.html it's fairly simple syntax, using goto's.
- aerique 14y ago
  Here's a fun Scheme example: http://ll1.ai.mit.edu/shriram-talk.pdf http://ll1.ai.mit.edu/shriram-talk.pdf The state machine would look something like this: (define a (automaton init (init : (c -> loop)) (loop : (a -> loop) (d -> loop) (r -> end)) (end : )))
- nova 14y ago
  I like the approach of "Practical UML Statecharts in C/C++", at least the simple one. More or less, keep the state on a function pointer, each state is represented by a function which gets incoming messages or events and returns the next state. I used it for a RS485 protocol running on a microcontroller quite successfully.
  - pierrebouchet 14y ago
    There is also the HSM (hierarchical state machine) extension of this concept (by the same author, not sure it's in the same book) where a given state either handles an event or returns a pointer to a "superstate" that handles it. This kind of "behavioral inheritance" allows for a much more compact code. Compact and efficient state machines are immensely useful when working with small microcontrollers that don't even run an OS.
    - nickmain 14y ago
      The other nice thing about HSMs are concurrent sub-states. They allow clean modeling of the orthogonal aspects of the state.
- amsaarin 14y ago
  An clean way to implement finite-state machines is Akka FSM [1]. I recently wrote a blog post about it: http://news.ycombinator.com/item?id=3976558 http://news.ycombinator.com/item?id=3976558 [1] http://doc.akka.io/docs/akka/snapshot/scala/fsm.html http://doc.akka.io/docs/akka/snapshot/scala/fsm.html
- eru 14y ago
  > [...] state machines and error handling are the primary applications of "goto" in C. Yes, though tail call optimization will allow also handle this problem well.
charliesome 14y ago
He neglected to mention PDAs (push-down automaton) - which is basically the same concept as a DFA or NFA but with a stack. State transitions can manipulate the stack, and the top of a stack can be used to pick which state to move to. 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.
- alecbenzer 14y ago
  > PDAs... are able to parse any context free grammar To be complete, _non-deterministic_ PDAs can recognize any context-free language. Afaik you can't use a normal, deterministic parser to recognize things like the language of all palindromes (which is context-free).
  - charliesome 14y ago
    Ah, thanks for the correction!
vibrunazo 14y ago
Udacity's course on programming languages (CS262) explains State Machines, among many other things. Their teaching format is genius. Highly recommended. http://www.udacity.com/overview/Course/cs262/CourseRev/apr2012 http://www.udacity.com/overview/Course/cs262/CourseRev/apr20...
- bhrgunatha 14y ago
  Coursera are currently running a whole course on Automata [1] and some similar material is covered in their Compilers course [2]. I'm not sure if you can still enroll or if they'll be repeated in the future. [1] https://class.coursera.org/automata/ https://class.coursera.org/automata/ [2] https://class.coursera.org/compilers https://class.coursera.org/compilers
patrickg 14y ago
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?
- ajuc 14y ago
  It's possible you use state machines and don't know it :) Have you ever used loop with if inside, that dispatches based on value of some variable? That's state machine implementation in structured language. I've encountered such code many times in our codebase. Or maybe you used some business process engine (like jbpm) - that's also state machine. I've even made jbpm-like engine in javascript for my html5 game - I use it to write quests in my game, and I plan to refactor dialog trees to also use it. It's graph with nodes and transitions, nodes specify actions game should do, transitions specify conditions player has to do to move to next node. Here's code if anybody's interested: https://github.com/ajuc/pefjs https://github.com/ajuc/pefjs And here's graphical editor for graphs: https://github.com/ajuc/jsDotForPefjs https://github.com/ajuc/jsDotForPefjs
- gurraman 14y ago
  They're generally useful when you need to process input and keep track of what to do "next". Here's an example where the author manages comet connections using gen_fsm in Erlang: http://www.letsyouandhimfight.com/2010/01/31/comet-in-erlang-with-mochiweb-and-a-finite-state-machine/ http://www.letsyouandhimfight.com/2010/01/31/comet-in-erlang... The FSM starts in state "waiting" (waiting for a connection/request). When a request arrives, the state is transitioned to "have_request". When/if a packet arrives when there's a request connected (packet -> have_request), the data is sent to the client (that then disconnects; the nature of this comet implementation) and the next state is set to "waiting". When a packet arrives when the current state is "waiting", it's added to a buffer and the next state is set to "have_packet". When a request is made and the state is "have_packet" - as opposed to when it was in "waiting" - the packet is immediately sent to the client, and the next state is set to "waiting". There are many other states and "events" in the code, but I think this illustrates how easy FSMs make it to reason about these kind of implementations (protocols).
ahelwer 14y ago
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. TBB isn't NUMA-aware though, which limits its use in HPC. [1] http://software.intel.com/en-us/blogs/2011/09/08/the-intel-threading-building-blocks-flow-graph-is-now-fully-supported/ http://software.intel.com/en-us/blogs/2011/09/08/the-intel-t...
- ralph 14y ago
  What do you prefer about TBB over CSP-style channels, as in #golang?
signa11 14y ago
nothing teaches state machines like networking protocols, just look at the server & client fsm's for tftp (rfc-1350).
userdeveloper 14y ago
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. This is great thread. I have only used lex/flex to make my state machines. I'd like to try something new eventually.
- endgame 14y ago
  Zed Shaw's article about building state machines with ragel might interest you: http://www.zedshaw.com/essays/ragel_state_charts.html http://www.zedshaw.com/essays/ragel_state_charts.html
  - deleted 14y ago
    [deleted]
  - userdeveloper 14y ago
    That write-up contains a little too much hype for my tastes. And as soon as I saw the words Java and C++ I lost 95% of any curiousity I have about ragel.
baseonmars 14y ago
1
nano_o 14y ago
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]. 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. 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]. [1] https://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf https://research.microsoft.com/en-us/um/people/lamport/pubs/... [2] https://research.microsoft.com/en-us/um/people/lamport/ https://research.microsoft.com/en-us/um/people/lamport/ [3] https://en.wikipedia.org/wiki/Abstract_state_machines https://en.wikipedia.org/wiki/Abstract_state_machines
husted 14y ago
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?
sudonim 14y ago
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 [1] http://www.meetup.com/Sproutcore-NYC/events/59870422/ http://www.meetup.com/Sproutcore-NYC/events/59870422/
k4st 14y ago
For those interested in symbolically manipulating [1] state machines (NFAs), pushdown automata (PDAs), and context-free grammars (CFGs), take a look at http://www.grailplus.org http://www.grailplus.org. [1] http://www.ioreader.com/2011/03/15/pattern-matching-in-grail http://www.ioreader.com/2011/03/15/pattern-matching-in-grail

67 points by fogus 14y ago

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. I am reminded of a particularly interesting DSL[1] for Forth that makes state machines look like their transition tables: 4 WIDE FSM: <Fixed.Pt#> \ input: | other? | num? | minus? | dp? | \ state: --------------------------------------------- ( 0 ) DROP >0 EMIT >1 EMIT >1 EMIT >2 ( 1 ) DROP >1 EMIT >1 DROP >1 EMIT >2 ( 2 ) DROP >2 EMIT >2 DROP >2 DROP >2 ; [1]http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm....

0fa2 14y ago
You can use coroutines as long as your state machine can be structured like code. Loops are Kleene closures, Ifs are alternation, and lists of statements are concatenation. I used nested C# Enumerators to implement a parser which didn't turn into too much of a mess, but it was a small project. Structured programming limits you in the state machines you can construct, but probably in a good way.
jpadkins 14y ago
State machines are very useful in game programming. Unrealscript supports state machines at the language level. http://udn.epicgames.com/Three/UnrealScriptStates.html http://udn.epicgames.com/Three/UnrealScriptStates.html it's fairly simple syntax, using goto's.
aerique 14y ago
Here's a fun Scheme example: http://ll1.ai.mit.edu/shriram-talk.pdf http://ll1.ai.mit.edu/shriram-talk.pdf The state machine would look something like this: (define a (automaton init (init : (c -> loop)) (loop : (a -> loop) (d -> loop) (r -> end)) (end : )))
nova 14y ago
I like the approach of "Practical UML Statecharts in C/C++", at least the simple one. More or less, keep the state on a function pointer, each state is represented by a function which gets incoming messages or events and returns the next state. I used it for a RS485 protocol running on a microcontroller quite successfully.
- pierrebouchet 14y ago
  There is also the HSM (hierarchical state machine) extension of this concept (by the same author, not sure it's in the same book) where a given state either handles an event or returns a pointer to a "superstate" that handles it. This kind of "behavioral inheritance" allows for a much more compact code. Compact and efficient state machines are immensely useful when working with small microcontrollers that don't even run an OS.
  - nickmain 14y ago
    The other nice thing about HSMs are concurrent sub-states. They allow clean modeling of the orthogonal aspects of the state.
amsaarin 14y ago
An clean way to implement finite-state machines is Akka FSM [1]. I recently wrote a blog post about it: http://news.ycombinator.com/item?id=3976558 http://news.ycombinator.com/item?id=3976558 [1] http://doc.akka.io/docs/akka/snapshot/scala/fsm.html http://doc.akka.io/docs/akka/snapshot/scala/fsm.html
eru 14y ago
> [...] state machines and error handling are the primary applications of "goto" in C. Yes, though tail call optimization will allow also handle this problem well.

charliesome 14y ago

He neglected to mention PDAs (push-down automaton) - which is basically the same concept as a DFA or NFA but with a stack. State transitions can manipulate the stack, and the top of a stack can be used to pick which state to move to. 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.

alecbenzer 14y ago
> PDAs... are able to parse any context free grammar To be complete, _non-deterministic_ PDAs can recognize any context-free language. Afaik you can't use a normal, deterministic parser to recognize things like the language of all palindromes (which is context-free).
- charliesome 14y ago
  Ah, thanks for the correction!

vibrunazo 14y ago

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

bhrgunatha 14y ago
Coursera are currently running a whole course on Automata [1] and some similar material is covered in their Compilers course [2]. I'm not sure if you can still enroll or if they'll be repeated in the future. [1] https://class.coursera.org/automata/ https://class.coursera.org/automata/ [2] https://class.coursera.org/compilers https://class.coursera.org/compilers

patrickg 14y ago

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?

ajuc 14y ago
It's possible you use state machines and don't know it :) Have you ever used loop with if inside, that dispatches based on value of some variable? That's state machine implementation in structured language. I've encountered such code many times in our codebase. Or maybe you used some business process engine (like jbpm) - that's also state machine. I've even made jbpm-like engine in javascript for my html5 game - I use it to write quests in my game, and I plan to refactor dialog trees to also use it. It's graph with nodes and transitions, nodes specify actions game should do, transitions specify conditions player has to do to move to next node. Here's code if anybody's interested: https://github.com/ajuc/pefjs https://github.com/ajuc/pefjs And here's graphical editor for graphs: https://github.com/ajuc/jsDotForPefjs https://github.com/ajuc/jsDotForPefjs
gurraman 14y ago
They're generally useful when you need to process input and keep track of what to do "next". Here's an example where the author manages comet connections using gen_fsm in Erlang: http://www.letsyouandhimfight.com/2010/01/31/comet-in-erlang-with-mochiweb-and-a-finite-state-machine/ http://www.letsyouandhimfight.com/2010/01/31/comet-in-erlang... The FSM starts in state "waiting" (waiting for a connection/request). When a request arrives, the state is transitioned to "have_request". When/if a packet arrives when there's a request connected (packet -> have_request), the data is sent to the client (that then disconnects; the nature of this comet implementation) and the next state is set to "waiting". When a packet arrives when the current state is "waiting", it's added to a buffer and the next state is set to "have_packet". When a request is made and the state is "have_packet" - as opposed to when it was in "waiting" - the packet is immediately sent to the client, and the next state is set to "waiting". There are many other states and "events" in the code, but I think this illustrates how easy FSMs make it to reason about these kind of implementations (protocols).

ahelwer 14y ago

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. TBB isn't NUMA-aware though, which limits its use in HPC. [1] http://software.intel.com/en-us/blogs/2011/09/08/the-intel-threading-building-blocks-flow-graph-is-now-fully-supported/ http://software.intel.com/en-us/blogs/2011/09/08/the-intel-t...

ralph 14y ago
What do you prefer about TBB over CSP-style channels, as in #golang?

signa11 14y ago

nothing teaches state machines like networking protocols, just look at the server & client fsm's for tftp (rfc-1350).

userdeveloper 14y ago

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. This is great thread. I have only used lex/flex to make my state machines. I'd like to try something new eventually.

endgame 14y ago
Zed Shaw's article about building state machines with ragel might interest you: http://www.zedshaw.com/essays/ragel_state_charts.html http://www.zedshaw.com/essays/ragel_state_charts.html
- deleted 14y ago
  [deleted]
- userdeveloper 14y ago
  That write-up contains a little too much hype for my tastes. And as soon as I saw the words Java and C++ I lost 95% of any curiousity I have about ragel.

baseonmars 14y ago

nano_o 14y ago

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]. 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. 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]. [1] https://research.microsoft.com/en-us/um/people/lamport/pubs/state-machine.pdf https://research.microsoft.com/en-us/um/people/lamport/pubs/... [2] https://research.microsoft.com/en-us/um/people/lamport/ https://research.microsoft.com/en-us/um/people/lamport/ [3] https://en.wikipedia.org/wiki/Abstract_state_machines https://en.wikipedia.org/wiki/Abstract_state_machines

husted 14y ago

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?

sudonim 14y ago

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 [1] http://www.meetup.com/Sproutcore-NYC/events/59870422/ http://www.meetup.com/Sproutcore-NYC/events/59870422/

k4st 14y ago

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