State Machines(blog.markwshead.com)
blog.markwshead.com
State Machines
http://blog.markwshead.com/869/state-machines-computer-science/
12 comments
Here's a fun Scheme example: http://ll1.ai.mit.edu/shriram-talk.pdf
The state machine would look something like this:
The state machine would look something like this:
(define a
(automaton init
(init : (c -> loop))
(loop : (a -> loop)
(d -> loop)
(r -> end))
(end : )))State machines are very useful in game programming. Unrealscript supports state machines at the language level.
http://udn.epicgames.com/Three/UnrealScriptStates.html
it's fairly simple syntax, using goto's.
it's fairly simple syntax, using goto's.
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.
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.
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
[1] http://doc.akka.io/docs/akka/snapshot/scala/fsm.html
[1] http://doc.akka.io/docs/akka/snapshot/scala/fsm.html
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.
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.
Compact and efficient state machines are immensely useful when working with small microcontrollers that don't even run an OS.
The other nice thing about HSMs are concurrent sub-states. They allow clean modeling of the orthogonal aspects of the state.
> [...] 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.
Yes, though tail call optimization will allow also handle this problem well.
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-t...
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-t...
What do you prefer about TBB over CSP-style channels, as in #golang?
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.
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.
> 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).
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).
Ah, thanks for the correction!
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/...
[2] https://research.microsoft.com/en-us/um/people/lamport/
[3] https://en.wikipedia.org/wiki/Abstract_state_machines
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/...
[2] https://research.microsoft.com/en-us/um/people/lamport/
[3] https://en.wikipedia.org/wiki/Abstract_state_machines
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/apr20...
http://www.udacity.com/overview/Course/cs262/CourseRev/apr20...
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/
[2] https://class.coursera.org/compilers
[1] https://class.coursera.org/automata/
[2] https://class.coursera.org/compilers
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?
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
And here's graphical editor for graphs: https://github.com/ajuc/jsDotForPefjs
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
And here's graphical editor for graphs: https://github.com/ajuc/jsDotForPefjs
Anything that implements a series of transactions that change internal variables of some structure is an ideal candidate for a state machine.
OLTP software, network stacks, computer games, object based simulations and so on are all good examples of things that you could probably implement a lot easier using state machines than you could ever implement them using some other coding technique (likely you'd be re-implementing state machines anyway, just not by name and in a warped form).
Statemachines get rid of the endless series of flags and ugly error handling that would otherwise govern a re-start of a chunk of code at a later date without assigning a thread to each datum that passes through the system.
OLTP software, network stacks, computer games, object based simulations and so on are all good examples of things that you could probably implement a lot easier using state machines than you could ever implement them using some other coding technique (likely you'd be re-implementing state machines anyway, just not by name and in a warped form).
Statemachines get rid of the endless series of flags and ugly error handling that would otherwise govern a re-start of a chunk of code at a later date without assigning a thread to each datum that passes through the system.
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...
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).
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...
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).
There's a lot of code that doesn't benefit from state machines at all.
But when code does profit from a state machine, it's often easy to recognize from the many 'if' statements that check several flags (like ' if (seen_input && !eof && ..)')
But when code does profit from a state machine, it's often easy to recognize from the many 'if' statements that check several flags (like ' if (seen_input && !eof && ..)')
I once wrote a toy video-player program, and I was able to implement robust, interactive playback controls fairly cleanly by structuring it as a state machine.
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.
This is great thread. I have only used lex/flex to make my state machines. I'd like to try something new eventually.
Zed Shaw's article about building state machines with ragel might interest you: http://www.zedshaw.com/essays/ragel_state_charts.html
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.
[deleted]
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.
[1] http://www.ioreader.com/2011/03/15/pattern-matching-in-grail
[1] http://www.ioreader.com/2011/03/15/pattern-matching-in-grail
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/
[1] http://www.meetup.com/Sproutcore-NYC/events/59870422/
nothing teaches state machines like networking protocols, just look at the server & 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?
I am reminded of a particularly interesting DSL[1] for Forth that makes state machines look like their transition tables:
[1]http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm....