State Machines

http://blog.markwshead.com/869/state-machines-computer-science/

by fogus • 14 years ago

67 31 14 years ago

blog.markwshead.com

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

0fa2• 14 years 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• 14 years ago

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.

aerique• 14 years ago

Here's a fun Scheme example: 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• 14 years 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• 14 years 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.

amsaarin• 14 years 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

[1] http://doc.akka.io/docs/akka/snapshot/scala/fsm.html

eru• 14 years 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.

charliesome2• 14 years 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• 14 years 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).

charliesome2• 14 years ago

Ah, thanks for the correction!

vibrunazo• 14 years 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/apr20...

bhrgunatha• 14 years 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/

[2] https://class.coursera.org/compilers

patrickg• 14 years 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• 14 years 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

And here's graphical editor for graphs: https://github.com/ajuc/jsDotForPefjs

gurraman• 14 years 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...

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

jacquesm• 14 years ago

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.

akhleung• 14 years ago

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.

perlgeek• 14 years ago

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

ahelwer• 14 years 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-t...

ralph• 14 years ago

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

signa11• 14 years ago

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

userdeveloper2• 14 years 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• 14 years ago

Zed Shaw's article about building state machines with ragel might interest you: http://www.zedshaw.com/essays/ragel_state_charts.html

userdeveloper2• 14 years 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• 14 years ago

nano_o• 14 years 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/...

[2] https://research.microsoft.com/en-us/um/people/lamport/

[3] https://en.wikipedia.org/wiki/Abstract_state_machines

husted• 14 years 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• 14 years 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/

k4st• 14 years 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.

[1] http://www.ioreader.com/2011/03/15/pattern-matching-in-grail

State Machines

Related Stories