Hacker News Reader

Comment by RodgerTheGreat | Hacker News Reader

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

View on HN

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

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.

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.

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

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.

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.

Reply on news.ycombinator.com