As a programmer you've either yet to, or have already, coded a state machine; for the remainder of this article, I'll assume the latter. First, a little bit of history.

The monkey-patch

In its most simplistic implementation, a state machine is coded as a series of flags: variables whose combination of values mean something.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double currency
int inventory

...

// Take action based on current state.
if(inventory > 0) {
    // No currency state

    if(currency > 0) {
        // Has currency state
    }
} else {
    // Sold out state
}

The proverbial wheel

A step above this crude monkey-patched state machine is initializing and maintaining the current state in a variable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
enum State {
    SOLD_OUT,
    NO_CURRENCY,
    HAS_CURRENCY
}

State state
double currency
int inventory

// Set initial state.
if(inventory > 0) {
    state = State.NO_CURRENCY

    if(currency > 0) {
        state = State.HAS_CURRENCY
    }
} else {
    state = State.SOLD_OUT
}

...

// Take action based on current state.
switch(state) {
    case SOLD_OUT:
        // Do something.
        break
    ...
}

Then came along the state machine design pattern, which for the purpose of this article I'll refer to as a compile-time state machine.

The compile-time state machine

You may be onto me. I've hinted at my yet-to-be-revealed hypothesis. But, as I was saying, the state machine design pattern suggests representing each state as a class and having a mechanism to maintain the current state and context.

Static class diagram

When the state machine is used, it delegates work to the current state.

Static sequence diagram

Here is an implementation of a compile-time state machine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
interface State {
    StateMachine.StateEnum fill(int count)
    StateMachine.StateEnum insertCurrency()
    StateMachine.StateEnum purchase()
    StateMachine.StateEnum eject() 
}

class StateImpl {
    StateMachine.StateEnum fill(int count) {
        throw createException('fill')
    }

    StateMachine.StateEnum insertCurrency() {
        throw createException('insertCurrency')
    }

    StateMachine.StateEnum purchase() {
        throw createException('purchase')
    }

    StateMachine.StateEnum eject() {
        throw createException('eject')
    }
    
    private Exception createException(String actionName) {
        new RuntimeException("'$actionName' is an invalid action for state '${getClass().name}'.")
    }
}

@groovy.transform.TupleConstructor
class SoldOut extends StateImpl implements State {
    StateMachine sm

    StateMachine.StateEnum fill(int count) {
        sm.inventory = sm.inventory + count
        sm.inventory > 0 ? StateMachine.StateEnum.NO_CURRENCY : StateMachine.StateEnum.SOLD_OUT
    }
}

class NoCurrency extends StateImpl implements State {

    StateMachine.StateEnum insertCurrency() {
        StateMachine.StateEnum.HAS_CURRENCY
    }
}

@groovy.transform.TupleConstructor
class HasCurrency extends StateImpl implements State {
    StateMachine sm

    StateMachine.StateEnum purchase() {
        --sm.inventory
        sm.inventory > 0 ? StateMachine.StateEnum.NO_CURRENCY : StateMachine.StateEnum.SOLD_OUT
    }

    StateMachine.StateEnum eject() {
        StateMachine.StateEnum.NO_CURRENCY
    }
}

class StateMachine implements State {
    int inventory 
    State state
    
    private State soldOut
    private State noCurrency
    private State hasCurrency
    private Map<StateEnum, State> stateMap    

    enum StateEnum {
        SOLD_OUT,
        NO_CURRENCY,
        HAS_CURRENCY
    }

    StateMachine(int inventory) {
        this.inventory = inventory

        soldOut = new SoldOut(this)
        noCurrency = new NoCurrency()
        hasCurrency = new HasCurrency(this)
        
        stateMap = [
            (StateEnum.SOLD_OUT): soldOut,
            (StateEnum.NO_CURRENCY): noCurrency,
            (StateEnum.HAS_CURRENCY): hasCurrency
        ]

        state = inventory > 0 ? noCurrency : soldOut
    }
    
    StateMachine.StateEnum fill(int count) {
        changeState(state.fill(count))
    }
    
    StateMachine.StateEnum insertCurrency() {
        changeState(state.insertCurrency())
    }
    
    StateMachine.StateEnum purchase() {
        changeState(state.purchase())
    }
    
    StateMachine.StateEnum eject() {
        changeState(state.eject())
    }
    
    private StateEnum changeState(StateEnum newState) {
         state = stateMap[newState]
         
         return newState
    }
}

def sm = new StateMachine(0)

sm.fill(2)

sm.insertCurrency()
sm.purchase()
assert sm.state.class.name == 'NoCurrency'

sm.insertCurrency()
sm.purchase()
assert sm.state.class.name == 'SoldOut'

The State interface defines the available actions/transitions. But since each state only needs to implement a subset of those actions, I added StateImpl to provide default implementations. In comparison to previous approaches, the state's business logic is spread out across multiple classes. Finally, construction of the state machine is handled by StateMachine's constructor.

We can learn a few things from compile-time state machines:

  • Each state may only need to implement a subset of the available actions.
  • A state machine is assembled from various components: states, context, and a supervisor (the state machine itself).
  • State machines are quite similar in functionality, yet each needs a concrete implementation.

And it is this last point that I want to emphasize. Even though state machines do the same thing, a complete compile-time state machine must be coded for each implementation. This is due to the static dispatching that's used when calling methods. Consider the following example:

1
2
3
4
5
class StateMachine { /* I don't declare any methods. Ha ha! */ }

def sm = new StateMachine()

sm.doSomething()

It results in an exception because the StateMachine.doSomething() method was not found. But languages with multiple/dynamic dispatching, such as Groovy, allow us to intercept these missing methods as they are called and do something useful. This is the basis for what I call a run-time state machine.

The run-time state machine

Simply put, a state machine consists of:

  • a list of possible states
  • the ability to delegate work to the current state
  • the ability to change states
  • and maybe some context to maintain data across state changes

That's really it.

With languages which use dynamic dispatching to execute methods, it's possible to create a run-time state machine. By this I mean a single set of classes which can be used to create various state machine implementations.

Run-time class diagram

When an action is executed against the state machine and it delegates to the current state, the state looks up the action in its Map of actions and executes it.

Run-time sequence diagram

I went a different route with the state changes: the current State returns the name of the next state to the StateMachine, which then changes the current State. Here's an implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class StateMachine {
    Map context
    Map<String, State> states
    State state
    
    def methodMissing(String name, args) {
        def action = state.actions[name]
        
        if(action instanceof GroovyCallable) {
            action.delegate = context
            state = states[action(*args)] ?: state
            return null
        } else if(action instanceof String) {
            state = states[action] ?: state
        } else {
            throw new RuntimeException("'$name' is an invalid action for state '$state.name'.")
        }        
    }
}

class State {
    String name
    Map actions = [:]
}

The example above consists of just two classes: StateMachine and State. StateMachine attempts to delegate method calls to the current State, and then changes the current state based on the method's output. State.actions is a list of supported actions/transitions. A context object is made the delegate of each action so that information can be maintained across state changes. Being generic, this state machine does not have state implementations; It doesn't have any business logic. Lets see what it's like to construct an implementation using this generic state machine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def sm = new StateMachine(
    context: [inventory: 0],
    states: [
        SoldOut: [
            fill: { count ->
                delegate.inventory = delegate.inventory + count
                delegate.inventory > 0 ? 'NoCurrency' : 'SoldOut'
            }
        ],
        NoCurrency: [
            insertCurrency: 'HasCurrency'
        ],
        HasCurrency: [
            purchase: {
                --delegate.inventory
                delegate.inventory > 0 ? 'NoCurrency' : 'SoldOut'
            },
            eject: 'NoCurrency'
        ]
    ].collectEntries { name, actions -> [name, new State(name: name, actions: actions)] }
)

The example above uses the generic state machine to build a concrete implementation. The State instances are build from a Map. Each Map entry represents a state, with the value being a Map of Closures (or Strings). Each Closure implements a state action.

As a bonus, if the action merely changes to another state, then a String with the state's name can be used instead of a Closure.

Notice how unlike the compile-time state machine, here each state only needs to implement the actions that pertain to the state. No dummy method implementations are needed whatsoever.

Here's what it's like to use the state machine.

1
2
3
4
5
6
7
8
9
10
sm.state = sm.context.inventory > 0 ? sm.states.NoCurrency : sm.states.SoldOut
sm.fill(2)

sm.insertCurrency()
sm.purchase()
assert sm.state.name == 'NoCurrency'

sm.insertCurrency()
sm.purchase()
assert sm.state.name == 'SoldOut'

It works just like a compile-time state machine, and uses 44% less code. The most glaring difference being that the initial state must be set. Since we're dealing with a generic state machine, it has no idea which state to start with, yet.

Making it better

I think the run-time state machine is rather neat. Particularly the fact that it can easily be reused to implement any number of state machines. However, there's one thing that bugs me about it: building one is rather yucky. Check out part 2 to see a better way to build run-time state machines.