The Old Joel on Software Forum: Part 3 (of 5)

State Machines

hello to all,
any one know of any good books, sites or papers on applying state machines or its other variants like state charts to software engineering?

i am currently reading Practical Statecharts in C/C++: Quantum Programming for Embedded Systems by Miro Samek.

thanks

edd
Sunday, December 14, 2003

What exactly are you looking for?

State machines are a fundamental concept, only slightly less basic than looping and variables.

Ori Berger
Sunday, December 14, 2003

"State machines are a fundamental concept, only slightly less basic than looping and variables."

Id be really interested in hearing a description of exactly what they define.
I guess because of my education (and lack of) Ive never really covered that concept, although Ive heard it referred to from time to time...

anyone wanto give me a quickie overview? (or an indepth description if that appeals more....)

FullNameRequired
Sunday, December 14, 2003

I learnt about finite state machines, which I presum "state machine" is an abbreviation of (they must all be finite in some sense...).

http://www.google.co.uk/search?hl=en&ie=UTF-8&oe=UTF-8&c2coff=1&q=define%3A+%22Finite+State+Machine%22+&meta=

http://en.wikipedia.org/wiki/Finite_state_machine

r1ch
Sunday, December 14, 2003

Been covered before:

http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=30520&ixReplies=18

Bored Bystander
Sunday, December 14, 2003

Here's a really good book describing the Statemate design method - a method based on hierarchical state machines. It includes a graphical notation for describing them as well:

Modeling Reactive Systems With Statecharts : The Statemate Approach
by David Harel, Michal Politi

http://www.amazon.com/exec/obidos/asin/0070262055

For a fundamental presentation of state machines, Jeffrey Ullman, John Hopcroft, and Alfred Aho have (in various combination) produced a number of excellent books on the topic (and other fundamental topics). My personal favorite is this one:

Introduction to Automata Theory, Languages, and Computation (1ed)
by John E. Hopcroft, Jeffrey D. Ullman

http://www.amazon.com/exec/obidos/asin/020102988X

I prefer the first edition to the more recent updated version, but you can hardly go wrong with any book by these fellows.

Also, there are some good presentations of the material from other engineering disciplines (certain branches of EE especially) and discrete mathematics.

hum
Sunday, December 14, 2003

here's a good article about implementing state machines
http://www-106.ibm.com/developerworks/linux/library/l-pygen.html

Tom Vu
Sunday, December 14, 2003

Here is a link to an article in IEEE Software on state machines:

http://www.pragmaticprogrammer.com/articles/nov_02_state.pdf

Pedro
Sunday, December 14, 2003

and don't forget that unless your state machine does what you want it to, and does not do what you don't want it to, it'll be pretty useless. Also, you or somebody else on your team will have to demonstrate that the system has only correct behaviors (once you've figured out just what they are, of course).

This requires proper analysis and test design, as well as implementing certain features to make it practical to test state machines efficiently.

Anyway, Robert V. Binder in "testing object-oriented systems: models, patterns, and tools", ISBN 0201809389, contains invaluable info about how to ensure you do these things correctly, as well as great references you can use to further your learning. Though much is couched in OO-speak, most of the knowledge is readily applicable to non-OO implementations as well, at least from the analytical and testing perspectives, anyway.

anonQAguy
Sunday, December 14, 2003

This is an OK site, the book is pretty good, and very practicle.
The introdutory chapters cover the usual implementations of state machines, even if you don't like the statechart/event driven method.
http://www.quantum-leaps.com/

Doug Withau
Monday, December 15, 2003