4 ms·

Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in pr

Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.

chas 14y ago
I first learned about them from a digital logic perspective, so they were already very practical tools for me when I ran into them in my theory classes. One of the best free resources I can find in short order is the wiki article on them. http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Finite-state_machine The wiki page on deterministic finite automata would be useful to see the CS theory/language side of the idea. http://en.wikipedia.org/wiki/Deterministic_finite_automaton http://en.wikipedia.org/wiki/Deterministic_finite_automaton
jacquesm 14y ago
Hm, I never thought there would be anybody interested in this stuff so it's all over the place. Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread. The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating). Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :) The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes. The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros. Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines. The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling. I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable. Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment. Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined. I hope this all makes sense (it's 6:15 am and I haven't slept yet...)
- bstpierre 14y ago
  It sounds like we've had similar experiences. I converted a handful of ad hoc "state machines" in a telephony system to FA. The original code was loaded with exceptions and special cases (and bugs). Converting to FA required detailed analysis of the existing system to extract the distinct events and states. I used a tool I wrote [1] to generate C state tables and an event loop from a description of the states+events. While the state machines that came out of the analysis were a big improvement, they still weren't perfect. We came across a few bugs later on. Using a strict representation of the state machines was a huge advantage in debugging and maintenance. When everything is moving through the same event loop, it's easy to add logging in the form "[timestamp] state A: event X -> state B". Adding a new state or event to the machine (to fix a bug or add a new feature) is much easier when everything is in one place. In a couple of cases, the state machine started to become large and unwieldy. Usually the cause was that there would be a couple of "meta" states: we'd have states A, B, and C, but then we'd need to represent "states B and C when X is true; states A and B when Y is true". Pulling X and Y into a separate machine simplified the parent state machine -- every X and Y moved into the child divides the number of states in the parent by as much as half. Then the parent can inject events into the child, and the child can fire events back to the parent. [1] http://bstpierre.org/Projects/smc/ http://bstpierre.org/Projects/smc/
  - rubyrescue 14y ago
    This was one of the reasons Erlang was invented - big state machine + telephony.
  - jacquesm 14y ago
    Indeed, it really sounds like a very similar experience, up to and including the code generation. One more thing I ended up adding (that isn't on your list above) is a true string type to the 'C' language (backwards compatible, works with pre-defined strings as well), including garbage collection. I found that in order to get the right level of abstraction the C string type was simply inadequate, it kept forcing things into the foreground that should not even be visible at that level. The one thing still missing is copy-on-write for string duplication, but that's a pretty tricky thing to implement in a thread safe and portable way. This would give a huge performance boost, but at the moment that would be just another case of premature optimization.
Goladus 14y ago
If someone asked for my recommendations for reading on state machines I would point them to Michael Sipser's Introduction to Theory of Computation. http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae... Though I get the impression you're looking for something a bit more like an oreilly cookbook or nutshell book.
erichocean 14y ago
This book[1] seems to really help people (don't be put off by the title): Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems In particular, it discusses the main implementation strategies and why you'd want to use them. Also, the specific codebase described in the book is excellent. I use it all the time in implementing server software. [1] http://www.amazon.com/Practical-UML-Statecharts-Second-Event-Driven/dp/0750687061 http://www.amazon.com/Practical-UML-Statecharts-Second-Event...

Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.

chas 14y ago

I first learned about them from a digital logic perspective, so they were already very practical tools for me when I ran into them in my theory classes. One of the best free resources I can find in short order is the wiki article on them. http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Finite-state_machine The wiki page on deterministic finite automata would be useful to see the CS theory/language side of the idea. http://en.wikipedia.org/wiki/Deterministic_finite_automaton http://en.wikipedia.org/wiki/Deterministic_finite_automaton

jacquesm 14y ago

Hm, I never thought there would be anybody interested in this stuff so it's all over the place. Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread. The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating). Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :) The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes. The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros. Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines. The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling. I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable. Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment. Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined. I hope this all makes sense (it's 6:15 am and I haven't slept yet...)

bstpierre 14y ago
It sounds like we've had similar experiences. I converted a handful of ad hoc "state machines" in a telephony system to FA. The original code was loaded with exceptions and special cases (and bugs). Converting to FA required detailed analysis of the existing system to extract the distinct events and states. I used a tool I wrote [1] to generate C state tables and an event loop from a description of the states+events. While the state machines that came out of the analysis were a big improvement, they still weren't perfect. We came across a few bugs later on. Using a strict representation of the state machines was a huge advantage in debugging and maintenance. When everything is moving through the same event loop, it's easy to add logging in the form "[timestamp] state A: event X -> state B". Adding a new state or event to the machine (to fix a bug or add a new feature) is much easier when everything is in one place. In a couple of cases, the state machine started to become large and unwieldy. Usually the cause was that there would be a couple of "meta" states: we'd have states A, B, and C, but then we'd need to represent "states B and C when X is true; states A and B when Y is true". Pulling X and Y into a separate machine simplified the parent state machine -- every X and Y moved into the child divides the number of states in the parent by as much as half. Then the parent can inject events into the child, and the child can fire events back to the parent. [1] http://bstpierre.org/Projects/smc/ http://bstpierre.org/Projects/smc/
- rubyrescue 14y ago
  This was one of the reasons Erlang was invented - big state machine + telephony.
- jacquesm 14y ago
  Indeed, it really sounds like a very similar experience, up to and including the code generation. One more thing I ended up adding (that isn't on your list above) is a true string type to the 'C' language (backwards compatible, works with pre-defined strings as well), including garbage collection. I found that in order to get the right level of abstraction the C string type was simply inadequate, it kept forcing things into the foreground that should not even be visible at that level. The one thing still missing is copy-on-write for string duplication, but that's a pretty tricky thing to implement in a thread safe and portable way. This would give a huge performance boost, but at the moment that would be just another case of premature optimization.

Goladus 14y ago

If someone asked for my recommendations for reading on state machines I would point them to Michael Sipser's Introduction to Theory of Computation. http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae... Though I get the impression you're looking for something a bit more like an oreilly cookbook or nutshell book.

erichocean 14y ago

This book[1] seems to really help people (don't be put off by the title): Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems In particular, it discusses the main implementation strategies and why you'd want to use them. Also, the specific codebase described in the book is excellent. I use it all the time in implementing server software. [1] http://www.amazon.com/Practical-UML-Statecharts-Second-Event-Driven/dp/0750687061 http://www.amazon.com/Practical-UML-Statecharts-Second-Event...