Fog Creek Software
Discussion Board




Finite State Machines

I've recently inherited some code from someone who I had previously assumed to be a reasonably good developer.

However, I reckon it's all spaghetti. The reason - he's coded the whole thing in a finite state machine.

For example : there is a single function - ProcessStateMachine(). This checks a module level variable, performs a series of actions depending on its value, and sets the module level variable to something.

Why don't I like it? Well, I find it very difficult to tell exactly what each call to ProcessStateMachine is actually going to do, as it depends on what value an internal variable that I can't see from outside is set to at runtime.

What are your thoughts?

Better than being unemployed...
Friday, February 21, 2003

Not all processes can be modelled as state machines. If the dynamics of the process cannot be expressed as:

X' = A*X + B*I
O = C*X + D*I

where X is the state, I the input and O the output, ABCD constants

then there are huge problems implementing the state machine.

Secondly, if the dimension of the state is not finite again, huge problems.

Lastly, usually the state of a system is not directly accessible and must estimated based on the input and the output. In most cases, not all states can be estimated and the state is inaccessible.

Good candidates for state machine implementations are protocols (communication protocols in general) and object life cycle controllers (as in MVC). Out of my experience I found out is better to implement a FSM as a blackbox and try different transitions before actually changing the state of an object. This works around asynchronous state transitions (usually in communication protocols) and object transactioning (in object life cycle controllers).

The code would look something like:

interface StateAccessible {
    public State getCurrentState();
    public void setState(State state);
}

class MyClass implements StateAccessible {
    private FSM fsm;

    public MyClass() {
        this.fsm = new SpecificFSM();
    }
    ...

    public State getCurrentState() {
        // ...
    }

    public void setState(State state) {
        // ...
    }

    void onEvent(Event event) {
        try {
            synchronized(this) {
                // Critical section
                State endState = fsm.fireEvent(getCurrentState(), translateEvent(event));
                setState(endState);
            }

            // your processing here ...

        } catch (TransitionImpossibleException tie) {
                // transition is not possbile, rollback any changes
        }
    }

    class SpecificFSM extends FSM {
        // ... implement the FSM, mainly provide the state transition map
        // Some synchronization may be required
    }
}

I hope this makes sense.

Cheers
Dino

Dino
Friday, February 21, 2003

The finite state machine is a very useful concept and I have made frequent use of it.  The original post on this thread doesn't make it clear what the problem is.  You seem to be arguing that it's a problem because it is a FSM.  And what do you mean by you "reckon it's all spaghetti"?  Have you read the code?  Just being an FSM doesn't automatically make it spaghetti code.

You can't tell what it is going to do because you don't know its state?  Why is that a problem for you?

At least draw up a state diagram.  They are real useful for understanding a FSM.

I am taking up a lot of space here just trying to ask "What is the problem?"

mackinac
Friday, February 21, 2003

Well, having had a look, I think the problem isn't so much with the FSM per se as the implementation of it, and the code surrounding it. I think Dino's suggestion looks fine.

What seems to be the principal problem is that the actions taken on each state aren't factored out into separate functions. So you've just got one huge ProcessStateMachine() function with all manner of different things in it. Looks like it's just a matter of splitting that up into separate parts. Oh, and putting a few useful comments in (such as a brief state transition diagram at the top).

Thanks for your suggestions.

Better than being unemployed...
Friday, February 21, 2003

Normally I don't see code like that except
during the optimization phase of software
development.. and hopefully only to an
isolated group of code. If it is at all
possible it really ought to be avoided. :-(
It is just odd trying to read them, writing
them feels weird too. There are a few
software out there (usually parallel
programmming) that will force you to
structure your software like this to make it
scale, but yuck.
I really hate to write code like that too,
it's normally hard to justify. Some causes
for it is programmer inexperience, code
maintenance (if you are comfortable with the
way state machines work sometimes it runs,
or just rush work. I think the best route is
to investigate whether parts of it can be
changed back into a more normal logic if
then statement. If the coding cost is not
too high ask the programmer to write an
alternate version that uses conventional
method.
Speaking of which, now I feel kinda guilty,
there were parts of my code in the last
project that passes the state from function
to function!! :-) Back to the drawing borad.
:-)
-- David

Li-fan Chen
Friday, February 21, 2003

Just a side note: I think in the future more and more software will be using FSM as plumbing.. to the extent that it is possible.. business logic can remain in conventional procedural stuff.. it sucks but that's one of the few cheap ways you can scale your software.. and all software scale in the future. :)
And with that in mind, I think most of us will get so used to that way of coding it will come second nature. And with proper documentation and understanding it is no more difficult or "weird" than how we used to do things.

Li-fan Chen
Friday, February 21, 2003

I don't see what the fuss about FSMs is all about. They are simply another technique for structuring code and are useful for certain kinds of situations.


The "spaghetti" arises from forcing a problem that natually consists of managing multiple state transitions into a procedural context instead of an FSM.


I implement most logic that must parse or analyze text files, for instance, as a finite state machine. The logic to analyze a file containing metadata of financial forms, for instance, would be something like:


state = entry;

while( not eof(f) )
{
  read(f);
  switch( state )
  {
      case entry:
        if analyze_some_way then
            state =  first_state;
          break;
      case first_state:
        if is_data_element then
        {
            state = in_data_element;
            start_data_element;
        }
        break;
      case in_data_element:
          if still_data_element then
          {
              append_data_element;
          }
          else
          {
              terminate_data_element;
              state = entry;
          }           
  }
}
The point is, the state variable is just a way to keep track of where you are in a process and it's simply a model for the real world you're interfacing with. The FSM approach mandates that you become very clear in your own mind about the necessary state transitions. The FSM itself can be tiny, and the working code that handles the data that the FSM generates can be separated out. If the FSM works correctly in all cases, then that is saying that the designer REALLY understood the process!
I even find debugging code like this to be easier in some instances than a strict procedural approach. I can look at the state variable in a debugger to see where the code thinks it's "at".

Bored Bystander
Friday, February 21, 2003

Bored Bystander you cool roxer

Li-fan Chen
Friday, February 21, 2003

About 16 years ago on my first project using C, I implemented a user keyboard interface as a FSM.  It was a fun project.  The code that implemented the FSM didn't do anything else itself.  It called other functions to execute state transition processing. Most of the application specific FSM coding was done in a C initialization statement which defined the state transition table.  This made for clean code layout, but might have been a little difficult for anyone else to read until they got the idea of what was going on.  Of course, I always try to comment my code.

mackinac
Friday, February 21, 2003

I have a soft spot for FSM's. The trick is to recognize when an FSM is sufficient. If you need memory beyond the system state, an FSM doesn't cut it anymore. However, a LOT of algorithms don't need that.

If you're interested, there's a neat tool called Libero:

http://www.imatix.com/html/libero/index.htm

that takes an FSM defined in a text file and generates the code that implements it in your choice of programming language. The advantage here is that it's much easier to see the actual state machine, since it's not lost in the C plumbing.

Chris Tavares
Friday, February 21, 2003

Now that I'm thinking about it, perhaps the only time I've used a state machine was in a library meant to read configuration files... it was a quick hack, and I'm very proud of it :-)

Leonardo Herrera
Friday, February 21, 2003

A state machine diagram is actually very readable.  Probably the original developer had this documented (Visio?  More likely scribbled on a pad of paper).  If you can back track you're in luck.

There's a number of tools that will either automatically generate FSM code, or will turn a regular expression into an FSM into FSM procedural code. This is a legitimate approach to coding as long as you realize the "source file" is actually the original FSM or a original regular expression.  (so you need to keep a copy).  Compiler tools like javacc are essentially FSM generaters. 

(before someone jumps on me, technically a compiler tools generates a FSM for lexing and a Context Free Grammer machine for parsing).

Will
Friday, February 21, 2003

I think there are two places that the FSM pattern has been adopted in a bad way - VB Forms and ASP pages.

I worked on a project in VB where they wanted it to feel like a wizard.  For example, one process would have about 10 screens that branch, so that in any one usage 5 would be used.

It was handled by placing all of the required components onto one form, and then keeping track of the page with a state variable.

Then, everytime next was clicked, the handler would hide the old controls and make the new controls visible.  Urrgh.

The worst part of it was that all of the benefits of using VB - the forms designer - are completely lost.  All of the controls overlap and while your trying to get to one control you end up moving another.  Every noticed that VB6 form designer does not support undo.

When a FSM is used to separate code in a logical manner, then I find it very useful.  The problem I always find is when it is used to keep everything in one place.  Like the above example, or when a single ASP page is used to handle everything (without even using an include!)

Ged Byrne
Monday, February 24, 2003

> I worked on a project in VB where they wanted it to feel like a wizard.  For example, one process would have about 10 screens that branch, so that in any one usage 5 would be used.

Isn't there a page frame control in VB?  That treats it all as a bunch of separate containers?  Something would still have to manage the current page to display of course.

Simon Lucy
Monday, February 24, 2003

Simon,

That was the most frustrating part of it.  It was clear that the original developers were not experienced VBers.

Ged Byrne
Monday, February 24, 2003

Ahhhh.

Simon Lucy
Monday, February 24, 2003

I've seen a similar problem in VB wizards. There's just too much code lumped together.

I ended up creating a custom wizard object which you could pass a list of user controls in at runtime which implemented an interface used for marshalling data between them. The code to drive the wizard is a bit more complex, but it makes understanding the underlying logic of each wizard page much easier.

Better than being unemployed...
Monday, February 24, 2003

Here are two links to a book called "Practical Statecharts in C/C++". It is geared to embedded developers. The first few chapters describe all types of state machines an the various ways to implement them. Very useful stuff.
It even includes a VB example!
http://www.cmpbooks.com/cgi-bin/shopspecific/store/products/1578201101.htm
http://www.quantum-leaps.com/about.htm

Doug Withau
Monday, February 24, 2003

I'm biased against them right now, as I'm trying to maintain a program someone stupidly thought would be good to implement as an FSM.  It's unmaintainable.

Now don't get me wrong.  FSM's are great tools; I've used them a few times for text parsing.  But for managing a Windows GUI, they are horribly misplaced.

Don't Shoot Me, I'm Just the Programmer
Tuesday, February 25, 2003

An FSM is often part of a larger State Machine.

I usually write network code as a state machine. The socket is itself considered a "finite state machine", with states "DNS-resolving, connecting, connected, closing, closed, error" with "connected" having substates "can-read", "can-write", "can-read-and-write" and "can't-read-or-write". The socket transitions on input from either the program (request to connect, request to close), or the network (DNS resolution completed, DNS resolution failed, Connect succeeded, Connect failed, Data available, Error on socket, ...). You should be able to work out the transition diagram yourself.

The network object has "non-finite" state, such as no. of bytes received, processing stage, etc.

I consider it a state machine because 1) all state is _explicity_ declared, and 2) there's usually one feed() method that feeds a new event to the state machine, and makes it transition (some events are fed internally - e.g., a network disconnect while trying to write - conceptually, however, there is only one explicit entry point that causes a change in the machine state.

Ori Berger
Monday, December 15, 2003

*  Recent Topics

*  Fog Creek Home