How to Implement a Fsm - Finite State MAChine in Java

How to implement a FSM - Finite State Machine in Java

The heart of a state machine is the transition table, which takes a state and a symbol (what you're calling an event) to a new state. That's just a two-index array of states. For sanity and type safety, declare the states and symbols as enumerations. I always add a "length" member in some way (language-specific) for checking array bounds. When I've hand-coded FSM's, I format the code in row and column format with whitespace fiddling. The other elements of a state machine are the initial state and the set of accepting states. The most direct implementation of the set of accepting states is an array of booleans indexed by the states. In Java, however, enumerations are classes, and you can specify an argument "accepting" in the declaration for each enumerated value and initialize it in the constructor for the enumeration.

For the machine type, you can write it as a generic class. It would take two type arguments, one for the states and one for the symbols, an array argument for the transition table, a single state for the initial. The only other detail (though it's critical) is that you have to call Enum.ordinal() to get an integer suitable for indexing the transition array, since you there's no syntax for directly declaring an array with a enumeration index (though there ought to be).

To preempt one issue, EnumMap won't work for the transition table, because the key required is a pair of enumeration values, not a single one.

enum State {
    Initial( false ),
    Final( true ),
    Error( false );
    static public final Integer length = 1 + Error.ordinal();

    final boolean accepting;

    State( boolean accepting ) {
        this.accepting = accepting;
    }
}

enum Symbol {
    A, B, C;
    static public final Integer length = 1 + C.ordinal();
}

State transition[][] = {
    //  A               B               C
    {
        State.Initial,  State.Final,    State.Error
    }, {
        State.Final,    State.Initial,  State.Error
    }
};

How to implement a cyclic FSM with Java enum

• Create one enum value per state.
• Return the next state in doSomething.
• Start with some state and cycle with doSomething until you reach it again.

Practically this will be something like:

public enum State {

    S1 {
        @Override
        State doSomething() {
            // Do something useful
            return S2;
        }
    },
    S2 {
        @Override
        State doSomething() {
            // Do something useful
            return S3;
        }
    },
    // ...
    SN {
        @Override
        State doSomething() {
            // Do something useful
            return S1;
        }
    },
    abstract State doSomething();
}

Then:

State state = initialState;
do {
    // Do something useful with state
}
while((state = initialState.doSomething()) != initialState);

To be honest I wouldn't be a big fan of implementing the FSM with enums as you planned above as it makes FSM pretty much hardcoded in the enum.

Java enum-based state machine (FSM): Passing in events

So you want to dispatch events to their handlers for the current state.

To dispatch to the current state, subscribing each state as it becomes active, and unsubscribing it as it becomes inactive is rather cumbersome. It is easier to subscribe an object that knows the active state, and simply delegates all events to the active state.

To distinguish events, you can use separate event objects, and then distinguish them with the visitor pattern, but that's quite a bit of boilerplate code. I'd only do this if I have other code that treats all events the same (for instance, if events must be buffered before delivery). Otherwise, I'd simply do something like

interface StateEventListener {
    void onEventX();
    void onEventY(int x, int y);
    void onEventZ(String s);
}

enum State implements StateEventListener {
    initialState {
        @Override public void onEventX() {
            // do whatever
        }
        // same for other events
    },
    // same for other states
}

class StateMachine implements StateEventListener {
    State currentState;

    @Override public void onEventX() {
        currentState.onEventX();
    }

    @Override public void onEventY(int x, int y) {
        currentState.onEventY(x, y);
    }

    @Override public void onEventZ(String s) {
        currentState.onEventZ(s);
    }
}

Edit

If you have many event types, it might be better to generate the boring delegation code at runtime using a bytecode engineering library, or even a plain JDK proxy:

class StateMachine2 {
    State currentState;

    final StateEventListener stateEventPublisher = buildStateEventForwarder(); 

    StateEventListener buildStateEventForwarder() {
        Class<?>[] interfaces = {StateEventListener.class};
        return (StateEventListener) Proxy.newProxyInstance(getClass().getClassLoader(), interfaces, new InvocationHandler() {
            @Override
            public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
                try {
                    return method.invoke(currentState, args);
                } catch (InvocationTargetException e) {
                    throw e.getCause();
                }
            }
        });
    }
}

This makes the code less readable, but does eliminate the need to write delegation code for each event type.

Finite State Machine and inter-FSM signaling

I agree that switch statements should be out of the question... they eventually lead to maintenance nightmares. Can't you use the State Pattern to implement your FSM? Depending on your actual implementation, you could use actors (if you have multiple FSM collaborating - hm... is that possible?). The nice thing about actors is that the framework for passing messages is already there.

An example of using State would be:

trait State {
  def changeState(message: Any): State
}

trait FSM extends Actor {
  var state: State

  def processMessage(message: Any) {
    state = state.changeState(message)
  }

  override def act() {
    loop {
      react {
        case m: Any => processMessage(m)
      }
    }
  }
}

This is very basic code, but as I don't know more of the requirements, that's the most I can think of. The advantage of State is that every state is self-contained in one class.

Finite State Machine program

First, get a list of all the states (N of them), and a list of all the symbols (M of them). Then there are 2 ways to go, interpretation or code-generation:

1. Interpretation. Make an NxM matrix, where each element of the matrix is filled in with the corresponding destination state number, or -1 if there is none. Then just have an initial state variable and start processing input. If you get to state -1, you fail. If you run out of input symbols without getting to the success state, you fail. Otherwise you succeed.

2. Code generation. Print out a program in C or your favorite compiler language. It should have an integer state variable initialized to the start state. It should have a for loop over the input characters, containing a switch on the state variable. You should have one case per state, and at each case, have a switch statement on the current character that changes the state variable.

If you want something even faster than 2, and that is sure to get you flunked (!), get rid of the state variable and instead use goto :-) If you flunk, you can comfort yourself in the knowledge that that's what compilers do.

P.S. You could get your F changed to an A if you recognize loops etc. in the state diagram and print out corresponding while and if statements, rather than using goto.

---

Related Topics