A C# Developer Delves Into Java- Finite State Machine

Friday February 21 2014 - , , , ,

StateMachineUmlIn a radical departure from my normal fare, I decided to have a got at writing some Java. I’ve looked at other people’s Java code and often thought how much like C# it looked, it is certainly understandable to a C# programmer, but as I discovered, the languages actually have some significant differences.

Something that has come up in my conversations a few times recently is the concept of Finite State Machines. It is a powerful technique, especially for real time systems that I think is under-used, or used badly. I set myself of writing a general purpose FSM framework as an excuse to write my first Java code. I’m using JDK7, in case that is important.

What is a State Machine?

I cannot put this any better than the definition from Wikipedia:

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.

So, what are the goals for my state machine?

  • It should be general purpose and flexible enough to be adapted to a wide range of uses
  • It should be simple to configure and use.
  • It should be thread-safe
  • It should ideally be developed test-first
  • No use of static fields, so it is possible to create and use multiple instances.
  • It should have a way of tracing its operation

I will not go through my development process blow-by-blow. I’ll just describe some of the important parts of the implementation and my learnings on Java. See the end of the article for a link to the code.

Overview of the State Machine

To create a state machine at runtime, one has to first create an instance of StateMachine, one or more instances of State and for each state, zero or more instances of Transition.

States have OnEnter and OnExit actions (more on action methods shortly) so that it can perform actions as the machine moves through its states.

States have zero or more Transition objects, each of which defines a valid transition to another state and a validation rule. Each Transition has a trigger() method that can be called to trigger the transition to another state, this is how the state machine is driven. It’s up to your app to call the trigger methods. As a convenience, Transition also implements the ActionListener interface, so it can be directly connected up to user interface controls such as buttons; the listener simply calls trigger() internally.

Obviously a transition can only occur out of a state if the state machine is ‘in’ that state – that is, it is the current state. Any trigger may be called at any time, including from multiple threads, but unless they belong to the current state, they are silently ignored.

In addition to requiring that their state is the ‘curent’ state, Transitions can also define a validation rule, which must evaluate to true for the transition to be allowed. One constructor overload for Transitions takes a ‘rule’ parameter, which can be a class implementing the following interface:

public interface TransitionRule extends EventListener
{
public boolean transitionIsAllowed();
}

When a transaction is triggered, the rule (defined in the transitionIsAllowed() method) is evaluated and must return true for the transition to proceed, otherwise it is silently ignored. If no rule is provided, then the transition is always allowed.

Notable Implementation Details

The UML class diagram here shows the three main classes involved, Transition is nested within State, which is nested within StateMachine. In java, an ‘inner’ (nested) class can only exist within an instance of its ‘outer’ class. So in this case, to create a State, you must first have an instance of the StateMachine. Let’s say we have a StateMachine instance called ‘fsm’, we’d create a State instance using syntax like this:

StateMachine.State stateName = fsm.new State("State Name");

This syntax will look a bit strange to C# developers. I make plenty of use of this way of associating my state machine data, which is why (for example) you will not find a collection of states anywhere. The association is implicit in the way they are created. The state we just created above can access its associated instance of StateMachine (fsm) like so:

State currentState = StateMachine.this.getCurrentState();

My state machine went though several different forms during development and discovering this language features radically altered my design. I was initially dismayed to discover that Java has no direct equivalent of C# delegates, hence no lambda expressions, but what it does have is something called ‘anonymous inner classes’ that cna be used to great effect along with interfaces. The syntax for declaring these is a bit ‘clunky’ but it gets the job done. Perhaps an example is in order. In my state machine, each state can have an OnEnter action and an OnExit action. The actions are defined as an interface like this:

public interface StateTransitionAction
{
public void action();
}

Easy enough.

Actions, Events and Anonymous Inner Classes

When declaring a state, I have provided a constructor overload that accepts ‘action methods’ as parameters. Strictly, these parameters require ‘an instance of a class implementing the StateTransitionAction interface’ – but my C# persona really wants them to be delegates! The State constructor looks like this:

public State(String name, StateTransitionAction onEnter, StateTransitionAction onExit)
{...}

Now comes the interesting bit. Something called an anonymous inner class can be declared inline, like this:

StateMachine.State state =
fsm.new State("State Name",
new StateTransitionAction()
{
@Override
public void action()
{
// action code goes here
}
},
null);

When I first saw this, my eyes nearly bled! What this is actually doing is, on the fly, creating a new anonymous class definition that implements the StateTransitionAction interface, overriding its action() method and then creating an instance of that class! Its a neat idea, but this syntax  quickly leads to horribly bloated and unreadable declarations when done like this, but luckily it can be cleaned up a lot by declaring the action method as a field first, then just supplying the field as the argument (Refactor->Extract->Filed, if you have refactoring tools). IntelliJ-IDEA has a nice trick of collapsing the above code to make it look a lot like a C# lambda. Here’s a screen snipping showing the exact same code as above in IntelliJ-IDEA:

image

Note that this is just an editor trick, the code isn’t changed but the editor is smart enough to fold the mind-boggling longhand version above into the lambda-like form in the screen snipping, which makes it a *lot* easier to read, at least for me with my predilection for C#. Nice one, JetBrains!

So this is how things are wired up to the state machine classes and how transition validation rules are used on state transitions. A simple example is in order.

Turnstile Sample

I dreamt up a simple sample application to show how the state machine is used. My app simulates a coin-operated turnstile. The user has to put in at least 20p to unlock the gate of the turnstile. As they exit from the turnstile, they break an optical beam which re-locks the gate behind them. Simple. Here’s how I defined the state machine in code, this is pretty much the whole thing and shows the basic pattern for creating the state machine in ComposeStateMachine().

   1: package uk.co.tigranetworks.turnstile;
   2:  
   3: import com.codeproject.javaConsole.JavaConsole;
   4: import uk.co.tigranetworks.*;
   5:  
   6: import java.util.Scanner;
   7: import java.util.Timer;
   8: import java.util.TimerTask;
   9:  
  10: /**
  11:  * Created by Tim on 21/02/14.
  12:  */
  13: public class TurnstileApp implements TraceListener
  14: {
  15:     private final JavaConsole console              = new JavaConsole();
  16:     private final Scanner     scanner              = new Scanner(System.in);
  17:     private final Timer       gateLockTimer        = new Timer("Turnstile Gate Lock Timer");
  18:     private       Integer     moneyInCoinValidator = 0;
  19:     private StateMachine.State.Transition transitionUnlockedToLocked;
  20:     private StateMachine.State.Transition transitionLockedToUnlocked;
  21:     private StateTransitionAction         onEnterUnlocked;
  22:     private TransitionRule                transitionRuleLockedToUnlocked;
  23:     private StateTransitionAction         onEnterLocked;
  24:     private TimerTask                     taskLockGateWhenTimerExpires;
  25:     private StateMachine                  turnstile;
  26:  
  27:     public void run()
  28:     {
  29:         System.out.println("Finite-State Machine Turnstile simulation\n\n");
  30:         ComposeStateMachine();
  31:  
  32:         String userInput = "";
  33:         System.out.println("Please simulate coin validation by entering the amount of money inserted (in pence) and pressing enter. The gate will unlock at 20 pence.\n");
  34:         while (userInput != "exit")
  35:         {
  36:             userInput = scanner.next();
  37:             try
  38:             {
  39:                 int amount = Integer.parseInt(userInput);
  40:                 moneyInserted(amount);
  41:             }
  42:             catch (NumberFormatException ex)
  43:             {
  44:                 System.out.println("Invalid input\n");
  45:             }
  46:         }
  47:     }
  48:  
  49:     void unlockGate()
  50:     {
  51:         System.out.println("Gate unlocked");
  52:     }
  53:  
  54:     void lockGate()
  55:     {
  56:         System.out.println("Gate locked");
  57:     }
  58:  
  59:     private void moneyInserted(int amount)
  60:     {
  61:         moneyInCoinValidator += amount;
  62:         printMoneyTotal(amount, moneyInCoinValidator);
  63:         // Attempt to trigger the state transition to unlocked.
  64:         // This will only succeed if enough money has been inserted,
  65:         // because of the transition validation rule.
  66:         transitionLockedToUnlocked.trigger();
  67:     }
  68:  
  69:     private void printMoneyTotal(int inserted, int total)
  70:     {
  71:         System.out.printf("Amount entered: %d Running total: %d\n", inserted, total);
  72:     }
  73:  
  74:     private void clearMoneyTotal()
  75:     {
  76:         moneyInCoinValidator = 0;
  77:         System.out.println("Money total reset to 0.");
  78:     }
  79:  
  80:     /**
  81:      * Schedules the turnstile gate to lock in 5 seconds.
  82:      */
  83:     private void scheduleGateLocking()
  84:     {
  85:         taskLockGateWhenTimerExpires = new TimerTask()
  86:         {
  87:             @Override
  88:             public void run()
  89:             {
  90:                 SimulatePersonBreakingOpticalBeamAtExitOfTurnstile();
  91:             }
  92:         };
  93:         gateLockTimer.schedule(taskLockGateWhenTimerExpires, 5000l);
  94:     }
  95:  
  96:     /**
  97:      * A real turnstile would have some way of detecting when it has been used.
  98:      * It might be a sensor on the moving part, but in our simulation it is assumed
  99:      * to be an optical detector across the exit. The person breaks the beam as they
 100:      * exit from the turnstile and that resets it into the locked state.
 101:      */
 102:     private void SimulatePersonBreakingOpticalBeamAtExitOfTurnstile()
 103:     {
 104:         System.out.println("Person detected exiting the turnstile (simulated).");
 105:         transitionUnlockedToLocked.trigger();
 106:     }
 107:  
 108:     void ComposeStateMachine()
 109:     {
 110:         turnstile = new StateMachine();
 111:  
 112:         // OnEnter and OnExit action methods
 113:         onEnterLocked = new StateTransitionAction()
 114:         { // OnEnter - lock the gate and clear the money total.
 115:             @Override
 116:             public void action()
 117:             {
 118:                 lockGate();
 119:                 clearMoneyTotal();
 120:             }
 121:         };
 122:         onEnterUnlocked = new StateTransitionAction()
 123:         { // OnEnter - unlock the gate and schedule it to lock in 5 seconds.
 124:             @Override
 125:             public void action()
 126:             {
 127:                 unlockGate();
 128:                 scheduleGateLocking();
 129:             }
 130:         };
 131:  
 132:         // State definitions
 133:         StateMachine.State stateUnlocked = turnstile.new State("Gate Unlocked", onEnterUnlocked, null);
 134:         StateMachine.State stateLocked = turnstile.new State("Gate Locked", onEnterLocked, null);
 135:  
 136:         // Transition validation rules
 137:         transitionRuleLockedToUnlocked =
 138:                 new TransitionRule()
 139:                 {
 140:                     @Override
 141:                     public boolean transitionIsAllowed()
 142:                     {
 143:                         return (moneyInCoinValidator >= 20);
 144:                     }
 145:                 };
 146:  
 147:         // State transitions
 148:         transitionUnlockedToLocked = stateUnlocked.new Transition(stateLocked);
 149:         transitionLockedToUnlocked = stateLocked.new Transition(stateUnlocked, transitionRuleLockedToUnlocked);
 150:  
 151:         // Install diagnostic listeners
 152:         turnstile.setOnStateChangedListener(this);
 153:         turnstile.setOnTriggerListener(this);
 154:  
 155:         // Start the state machine and set the initial state to Locked.
 156:         try
 157:         {
 158:             turnstile.start(stateLocked);
 159:         }
 160:         catch (FalseStartException ex)
 161:         {
 162:             System.exit(-1);
 163:         }
 164:     }
 165:  
 166:     /**
 167:      * Listens for trace events from the state maching and prints them to the console.
 168:      *
 169:      * @param traceOutput The diagnostic output.
 170:      */
 171:     @Override
 172:     public void trace(String traceOutput)
 173:     {
 174:         System.out.println(traceOutput);
 175:     }
 176: }

 

Diagnostics

One more thing I forgot to mention earlier: diagnostics. I provide two events, OnStateChange and OnTrigger, that provide trace output of what the state machine is doing. Your app can hook into these ‘events’ and do whatever it likes with he trace output. In my sample above, I hook into the events on lines 152 and 153. My implementation of the TraceListener interface starts on line 171 and it just writes the output to the console. Here’s a screen shot of the app running:

image

 

Get the Code

All in all, I’m quite pleased with the result, considering it is my first ever bit of Java. I am sure there are many improvements that can be made and I would welcome any comments on style or substance! The code is up on GitHub at https://github.com/NameOfTheDragon/Java-Finite-State-Machine

You can assume that the license is MIT, i.e. anyone can do anything at all with the code, but whatever you do I’m not responsible.

If you do use the code, then please ping me @Tim_Long on twitter or contact me via GitHub just to let me know (always nice to know if anyone found your work useful). Likewise, forks and pull requests are welcome and encouraged.