State Machines

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.

it's fairly simple syntax, using goto's.

The state machine would look something like this:

    (define a
       (automaton init
                 (init : (c -> loop))
                 (loop : (a -> loop)
                         (d -> loop)
                         (r -> end))
                 (end : )))

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

Yes, though tail call optimization will allow also handle this problem well.

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

[1] https://class.coursera.org/automata/

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

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

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

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.

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