SpecialistOff.NET / Вопросы / Статьи / Фрагменты кода / Резюме / Метки / Помощь / Файлы

StateMachine

Метки: python

While State has a way to allow the client programmer to change the implementation, StateMachine imposes a structure to automatically change the implementation from one object to the next. The current implementation represents the state that a system is in, and the system behaves differently from one state to the next (because it uses State). Basically, this is a “state machine” using objects.

The code that moves the system from one state to the next is often a Template Method, as seen in the following framework for a basic state machine.

Each state can be run( ) to perform its behavior, and (in this design) you can also pass it an “input” object so it can tell you what new state to move to based on that “input”. The key distinction between this design and the next is that here, each State object decides what other states it can move to, based on the “input”, whereas in the subsequent design all of the state transitions are held in a single table. Another way to put it is that here, each Stateobject has its own little State table, and in the subsequent design there is a single master state transition table for the whole system:

# StateMachine/State.py
# A State has an operation, and can be moved
# into the next State given an Input:

class State:
    def run(self):
        assert 0, "run not implemented"
    def next(self, input):
        assert 0, "next not implemented"

This class is clearly unnecessary, but it allows us to say that something is a State object in code, and provide a slightly different error message when all the methods are not implemented. We could have gotten basically the same effect by saying:

class State: pass

because we would still get exceptions if run( ) or next( ) were called for a derived type, and they hadn’t been implemented.

The StateMachine keeps track of the current state, which is initialized by the constructor. The runAll( ) method takes a list of Input objects. This method not only moves to the next state, but it also calls run( ) for each state object - thus you can see it’s an expansion of the idea of the State pattern, since run( ) does something different depending on the state that the system is in:

# StateMachine/StateMachine.py
# Takes a list of Inputs to move from State to
# State using a template method.

class StateMachine:
    def __init__(self, initialState):
        self.currentState = initialState
        self.currentState.run()
    # Template method:
    def runAll(self, inputs):
        for i in inputs:
            print(i)
            self.currentState = self.currentState.next(i)
            self.currentState.run()

I’ve also treated runAll( ) as a template method. This is typical, but certainly not required - you could concievably want to override it, but typically the behavior change will occur in State‘s run( ) instead.

At this point the basic framework for this style of StateMachine (where each state decides the next states) is complete. As an example, I’ll use a fancy mousetrap that can move through several states in the process of trapping a mouse [1]. The mouse classes and information are stored in the mousepackage, including a class representing all the possible moves that a mouse can make, which will be the inputs to the state machine:

# StateMachine/mouse/MouseAction.py

class MouseAction:
    def __init__(self, action):
        self.action = action
    def __str__(self): return self.action
    def __cmp__(self, other):
        return cmp(self.action, other.action)
    # Necessary when __cmp__ or __eq__ is defined
    # in order to make this class usable as a
    # dictionary key:
    def __hash__(self):
        return hash(self.action)

# Static fields; an enumeration of instances:
MouseAction.appears = MouseAction("mouse appears")
MouseAction.runsAway = MouseAction("mouse runs away")
MouseAction.enters = MouseAction("mouse enters trap")
MouseAction.escapes = MouseAction("mouse escapes")
MouseAction.trapped = MouseAction("mouse trapped")
MouseAction.removed = MouseAction("mouse removed")

You’ll note that __cmp__( ) has been overidden to implement a comparison between action values. Also, each possible move by a mouse is enumerated as a MouseAction object, all of which are static fields in MouseAction.

For creating test code, a sequence of mouse inputs is provided from a text file:

# StateMachine/mouse/MouseMoves.txt
mouse appears
mouse runs away
mouse appears
mouse enters trap
mouse escapes
mouse appears
mouse enters trap
mouse trapped
mouse removed
mouse appears
mouse runs away
mouse appears
mouse enters trap
mouse trapped
mouse removed

With these tools in place, it’s now possible to create the first version of the mousetrap program. Each State subclass defines its run( ) behavior, and also establishes its next state with an if-else clause:

# StateMachine/mousetrap1/MouseTrapTest.py
# State Machine pattern using 'if' statements
# to determine the next state.
import string, sys
sys.path += ['../stateMachine', '../mouse']
from State import State
from StateMachine import StateMachine
from MouseAction import MouseAction
# A different subclass for each state:

class Waiting(State):
    def run(self):
        print("Waiting: Broadcasting cheese smell")

    def next(self, input):
        if input == MouseAction.appears:
            return MouseTrap.luring
        return MouseTrap.waiting

class Luring(State):
    def run(self):
        print("Luring: Presenting Cheese, door open")

    def next(self, input):
        if input == MouseAction.runsAway:
            return MouseTrap.waiting
        if input == MouseAction.enters:
            return MouseTrap.trapping
        return MouseTrap.luring

class Trapping(State):
    def run(self):
        print("Trapping: Closing door")

    def next(self, input):
        if input == MouseAction.escapes:
            return MouseTrap.waiting
        if input == MouseAction.trapped:
            return MouseTrap.holding
        return MouseTrap.trapping

class Holding(State):
    def run(self):
        print("Holding: Mouse caught")

    def next(self, input):
        if input == MouseAction.removed:
            return MouseTrap.waiting
        return MouseTrap.holding

class MouseTrap(StateMachine):
    def __init__(self):
        # Initial state
        StateMachine.__init__(self, MouseTrap.waiting)

# Static variable initialization:
MouseTrap.waiting = Waiting()
MouseTrap.luring = Luring()
MouseTrap.trapping = Trapping()
MouseTrap.holding = Holding()

moves = map(string.strip,
  open("../mouse/MouseMoves.txt").readlines())
MouseTrap().runAll(map(MouseAction, moves))

The StateMachine class simply defines all the possible states as static objects, and also sets up the initial state. The UnitTest creates a MouseTrap and then tests it with all the inputs from a MouseMoveList.

While the use of if statements inside the next( ) methods is perfectly reasonable, managing a large number of these could become difficult. Another approach is to create tables inside each State object defining the various next states based on the input.

Initially, this seems like it ought to be quite simple. You should be able to define a static table in each State subclass that defines the transitions in terms of the other State objects. However, it turns out that this approach generates cyclic initialization dependencies. To solve the problem, I’ve had to delay the initialization of the tables until the first time that the next( ) method is called for a particular State object. Initially, the next( ) methods can appear a little strange because of this.

The StateT class is an implementation of State (so that the same StateMachine class can be used from the previous example) that adds a Map and a method to initialize the map from a two-dimensional array. The next( ) method has a base-class implementation which must be called from the overridden derived class next( ) methods after they test for a null Map (and initialize it if it’s null):

# StateMachine/mousetrap2/MouseTrap2Test.py
# A better mousetrap using tables
import string, sys
sys.path += ['../stateMachine', '../mouse']
from State import State
from StateMachine import StateMachine
from MouseAction import MouseAction

class StateT(State):
    def __init__(self):
        self.transitions = None
    def next(self, input):
        if self.transitions.has_key(input):
            return self.transitions[input]
        else:
            raise "Input not supported for current state"

class Waiting(StateT):
    def run(self):
        print("Waiting: Broadcasting cheese smell")
    def next(self, input):
        # Lazy initialization:
        if not self.transitions:
            self.transitions = {
              MouseAction.appears : MouseTrap.luring
            }
        return StateT.next(self, input)

class Luring(StateT):
    def run(self):
        print("Luring: Presenting Cheese, door open")
    def next(self, input):
        # Lazy initialization:
        if not self.transitions:
            self.transitions = {
              MouseAction.enters : MouseTrap.trapping,
              MouseAction.runsAway : MouseTrap.waiting
            }
        return StateT.next(self, input)

class Trapping(StateT):
    def run(self):
        print("Trapping: Closing door")
    def next(self, input):
        # Lazy initialization:
        if not self.transitions:
            self.transitions = {
              MouseAction.escapes : MouseTrap.waiting,
              MouseAction.trapped : MouseTrap.holding
            }
        return StateT.next(self, input)

class Holding(StateT):
    def run(self):
        print("Holding: Mouse caught")
    def next(self, input):
        # Lazy initialization:
        if not self.transitions:
            self.transitions = {
              MouseAction.removed : MouseTrap.waiting
            }
        return StateT.next(self, input)

class MouseTrap(StateMachine):
    def __init__(self):
        # Initial state
        StateMachine.__init__(self, MouseTrap.waiting)

# Static variable initialization:
MouseTrap.waiting = Waiting()
MouseTrap.luring = Luring()
MouseTrap.trapping = Trapping()
MouseTrap.holding = Holding()

moves = map(string.strip,
  open("../mouse/MouseMoves.txt").readlines())
mouseMoves = map(MouseAction, moves)
MouseTrap().runAll(mouseMoves)

The rest of the code is identical - the difference is in the next( ) methods and the StateT class.

If you have to create and maintain a lot of State classes, this approach is an improvement, since it’s easier to quickly read and understand the state transitions from looking at the table.