[tnovelli]

Oh yeah, software state machines are silly, considering that microprocessors are very efficient state machines. It's funny how algorithms that make perfect sense in Assembler can become so slow and convoluted in an HLL. Coroutines, continuations, and GOTOs are some remedies for this high/low-level disconnect.

I wonder, are software FSMs ever really necessary?

[Hexstream]

I recently used a FSM approach to simultaneously match multiple patterns against a tree in one walk, to know what rules match at each node and with what pattern variable values (dictionary). Specifically, to associate the ordered list of suitable error renderers for each specific validation error that can occur.

The way I normally do pattern-matching is simply to walk the pattern and the tree to match against simultaneously, but of course this approach breaks down if you want to match multiple patterns against one tree in one pass. So I compiled each pattern into a list of closures, each closure representing one step of pattern-matching, a state. Then I walk the input tree normally and at each node, I call "push" on each of the patterns. If the current state of the pattern matches, I push the next state and the new dictionary variable values that were matched at this step. If the match is invalid, I push :invalid on the stack. After visiting the node I call pop on all the patterns.

Sorry if this is confusing. That's just to illustrate that learning the concept of a FSM let me implement something I wouldn't have known how to do otherwise.

Anyway, understanding the concept of a FSM is valuable in itself even if you never were to implement one because thinking about all possible states, inputs (symbols) and transitions helps you think more formally about some problems.

And even if the CPU itself is a state-machine, what if you want to make an emulator for that CPU?

[stcredzero]

I've seen good patterns for state machines in Smalltalk with states as objects and states as methods (on an FSM object).

With states as methods, you have an instance variable for "state" and you just run a loop:

    [ self state == #final ]
        whileFalse:
            [self getNextInput.
            self state: (self perform: self state)]

Each method then becomes a concise description of the state transitions:

    code
        self atEndOfInput 
            ifTrue: 
                [^#final].           "Go to #final State"
        self input == $"
            ifTrue: 
                [ self writeToOutput.
                ^#insideComment].    "Go to #insideComment"
        ^#code                       "Stay in #code"
    
    insideComment
        self input == $" 
            ifTrue: 
                [^#code].            "Go to to #code"
        ^#insideComment              "Stay in #insideComment"

Then debugging just becomes a matter of putting breakpoints in methods. #perform: is almost as fast a a regular message send, and the methods themselves are mostly #ifTrue: statements, which are bytecode optimized, so this is mostly JIT-ed to machine code.

[jcl]

Zed Shaw has a lot to say about the benefits of explicit software state machines:

http://www.zedshaw.com/essays/ragel_state_charts.html

[bkovitz]

In my C programming days, I used FSMs heavily. They enabled me to write code to handle extremely tricky, bug-prone problems of various kinds. I wrote them as static data with a tiny interpreter. They took almost no memory, they were super-fast, and they almost always worked the first time. I can't say that FSMs are particularly readable, but they were definitely more readable than tangles of while loops and if statements.

It's always been a disappointment that FSMs work so badly in most high-level languages. They are indeed a good fit to microprocessors.