[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.