Sunday, January 20, 2013

Hey, some programming content, at last! Finite State Machines!

So I decided that I've been using this blog as a ranting place instead of an informing place.  That;s not really what I was intending when I got started, so I'm going to try and focus on informational content for a while.  Not quite a New Year's Resolution, but it's worth a try

Today's Topic:  Finite State Machines
Finite State Machines (FSMs) are a powerful tool for handling program behavior in a flexible manner without losing track of the details.  If you are not familiar with FSMs, here's the Wikipedia article on them, which is a bit obtuse, but gives some of the details.

Typically, you will use an FSM in a situation where you have a set of behaviors you need to model, and the actions that get taken on certain inputs depend on the state of the object.  Most examples use mechanical devices, like turnstiles, automatic doors, traffic lights, and vending machines.

The real power of FSMs comes from when you combine a generator utility (easily found online) to generate the skeleton code for the state transitions, and the Command pattern to encapsulate the events/inputs.  This leads to compact code for the transistions, and lets you concentrate on the meat of your functionality.

The GoF State pattern might be appear to be useful here, but that is more helpful when you have something that does multiple things depending on its internal state, as opposed to the FSM itself.  The example in the link shows that this is less about the transitions and more about the actions, with the transitions not doing useful work, or being almost dataless signals.  The typical FSM even is more diverse, being a value or a signal whose meaning will differ.

One of the drawbacks to FSMs is that the logic of the transitions can be absent from the code, making it difficult to follow.  This is of course solvable with good documentation, but you need to keep it clear.  Most of the FSM generating programs have a data file that drives the process, so keep the descriptions there, and link to the in the generated/skeleton code, or if you generate skeletons and then modify them manually, in that code.

One other common use of FSMs is in regular expression recognition, but that's fairly tightly tied into the fields of compilers and interpreters, which is a really complex subject to cover.

No comments: