4 ms·

State machines are a powerful approach for programming, but often expressing them in structured languages can be inelegant- state machines and error handling ar

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.

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.