sect05.htm

Pythn design pattern

state to the next is often a <I>Template Method</I>, as seen in the following
framework for a basic state machine.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_144">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Each state can be <B>run(&#160;)</B> to
perform its behavior, and (in this design) you can also pass it an
&#147;input&#148; object so it can tell you what new state to move to based on
that &#147;input&#148;. The key distinction between this design and the next
is that here, each <B>State</B> object decides what other states it can move to,
based on the &#147;input&#148;, 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 <B>State</B> object has its own little <B>State</B> table, and in the
subsequent design there is a single master state transition table for the whole
system.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_145">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#: c04:statemachine:State.py
# A State has an operation, <font color=#0000ff>and</font> can be moved
# into the next State given an Input:

<font color=#0000ff>class</font> State:
  <font color=#0000ff>def</font> run(self): 
    <font color=#0000ff>assert</font> 1, <font color=#004488>"run not implemented"</font>
  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>assert</font> 1, <font color=#004488>"next not implemented"</font>
#:~</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">This class is clearly
unnecessary, but it allows us to say that something is a <B>State</B> 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:
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_146">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE><font color=#0000ff>class</font> State: <font color=#0000ff>pass</font></PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">because we
would still get exceptions if <B>run(&#160;)</B> or <B>next(&#160;)</B> were
called for a derived type, and they hadn&#146;t been implemented.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_147">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>StateMachine</B> keeps track of
the current state, which is initialized by the constructor. The
<B>runAll(&#160;)</B> method takes a list of <B>Input</B> objects. This method
not only moves to the next state, but it also calls <B>run(&#160;)</B> for each
state object &#150; thus you can see it&#146;s an expansion of the idea of the
<B>State</B> pattern, since <B>run(&#160;)</B> does something different
depending on the state that the system is in.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_148">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#: c04:statemachine:StateMachine.py
# Takes a list of Inputs to move <font color=#0000ff>from</font> State to 
# State using a template method.

<font color=#0000ff>class</font> StateMachine:
  <font color=#0000ff>def</font> __init__(self, initialState):
    self.currentState = initialState
    self.currentState.run()
  # Template method:
  <font color=#0000ff>def</font> runAll(self, inputs):
    <font color=#0000ff>for</font> i <font color=#0000ff>in</font> inputs:
      <font color=#0000ff>print</font> i
      self.currentState = self.currentState.next(i)
      self.currentState.run()
#:~</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">I&#146;ve also treated
<B>runAll(&#160;)</B> as a template method. This is typical, but certainly not
required &#150; you could concievably want to override it, but typically the
behavior change will occur in <B>State</B>&#146;s <B>run(&#160;)</B> instead.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_149">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">At this point the basic framework for
this style of <I>StateMachine</I> (where each state decides the next states) is
complete. As an example, I&#146;ll use a fancy mousetrap that can move through
several states in the process of trapping a
mouse</FONT><A NAME="fnB13" HREF="#fn13">[13]</A><FONT FACE="Georgia">. The
mouse classes and information are stored in the <B>mouse</B> package, including
a class representing all the possible moves that a mouse can make, which will be
the inputs to the state machine:
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_150">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#: c04:mouse:MouseAction.py

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

# Static fields; an enumeration of instances:
MouseAction.appears = MouseAction(<font color=#004488>"mouse appears"</font>)
MouseAction.runsAway = MouseAction(<font color=#004488>"mouse runs away"</font>)
MouseAction.enters = MouseAction(<font color=#004488>"mouse enters trap"</font>)
MouseAction.escapes = MouseAction(<font color=#004488>"mouse escapes"</font>)
MouseAction.trapped = MouseAction(<font color=#004488>"mouse trapped"</font>)
MouseAction.removed = MouseAction(<font color=#004488>"mouse removed"</font>)
#:~
</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">You&#146;ll note that
<B>__cmp__(&#160;)</B> has been overidden to implement a comparison between
<B>action</B> values. Also, each possible move by a mouse is enumerated as a
<B>MouseAction</B> object, all of which are static fields in <B>MouseAction</B>.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_151">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">For creating test code, a sequence of
mouse inputs is provided from a text file:
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_152">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#:! c04: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
#:~</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">With these tools in place,
it&#146;s now possible to create the first version of the mousetrap program.
Each <B>State</B> subclass defines its <B>run(&#160;)</B> behavior, and also
establishes its next state with an <B>if-else</B> clause:
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_153">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#: c04:mousetrap1:MouseTrapTest.py
# State Machine pattern using '<font color=#0000ff>if</font>' statements
# to determine the next state.
<font color=#0000ff>import</font> string, sys
sys.path += ['../statemachine', '../mouse']
<font color=#0000ff>from</font> State <font color=#0000ff>import</font> State
<font color=#0000ff>from</font> StateMachine <font color=#0000ff>import</font> StateMachine
<font color=#0000ff>from</font> MouseAction <font color=#0000ff>import</font> MouseAction
# A different subclass <font color=#0000ff>for</font> each state:

<font color=#0000ff>class</font> Waiting(State):
  <font color=#0000ff>def</font> run(self): 
    <font color=#0000ff>print</font> <font color=#004488>"Waiting: Broadcasting cheese smell"</font>

  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>if</font> input == MouseAction.appears:
      <font color=#0000ff>return</font> MouseTrap.luring
    <font color=#0000ff>return</font> MouseTrap.waiting

<font color=#0000ff>class</font> Luring(State):
  <font color=#0000ff>def</font> run(self):
    <font color=#0000ff>print</font> <font color=#004488>"Luring: Presenting Cheese, door open"</font>

  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>if</font> input == MouseAction.runsAway:
      <font color=#0000ff>return</font> MouseTrap.waiting
    <font color=#0000ff>if</font> input == MouseAction.enters:
      <font color=#0000ff>return</font> MouseTrap.trapping
    <font color=#0000ff>return</font> MouseTrap.luring

<font color=#0000ff>class</font> Trapping(State):
  <font color=#0000ff>def</font> run(self):
    <font color=#0000ff>print</font> <font color=#004488>"Trapping: Closing door"</font>

  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>if</font> input == MouseAction.escapes:
      <font color=#0000ff>return</font> MouseTrap.waiting
    <font color=#0000ff>if</font> input == MouseAction.trapped:
      <font color=#0000ff>return</font> MouseTrap.holding
    <font color=#0000ff>return</font> MouseTrap.trapping

<font color=#0000ff>class</font> Holding(State):
  <font color=#0000ff>def</font> run(self):
    <font color=#0000ff>print</font> <font color=#004488>"Holding: Mouse caught"</font>

  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>if</font> input == MouseAction.removed:
      <font color=#0000ff>return</font> MouseTrap.waiting
    <font color=#0000ff>return</font> MouseTrap.holding

<font color=#0000ff>class</font> MouseTrap(StateMachine):
  <font color=#0000ff>def</font> __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(<font color=#004488>"..</font><font color=#004488>/mouse</font><font color=#004488>/MouseMoves.txt"</font>).readlines())
MouseTrap().runAll(map(MouseAction, moves))
#:~</PRE></FONT></BLOCKQUOTE><DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>StateMachine</B> class
simply defines all the possible states as static objects, and also sets up the
initial state. The <B>UnitTest</B> creates a <B>MouseTrap</B> and then tests it
with all the inputs from a <B>MouseMoveList</B>.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_154">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">While the</FONT><FONT FACE="Georgia"> use
of <B>if</B> statements inside the <B>next(&#160;)</B> methods is perfectly
reasonable, managing a large number of these could become difficult. Another
approach is to create tables inside each <B>State</B> object defining the
various next states based on the input.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_155">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">Initially, this seems like it ought to be
quite simple. You should be able to define a static table in each <B>State</B>
subclass that defines the transitions in terms of the other <B>State</B>
objects. However, it turns out that this approach generates cyclic
initialization dependencies. To solve the problem, I&#146;ve had to delay the
initialization of the tables until the first time that the <B>next(&#160;)</B>
method is called for a particular <B>State</B> object. Initially, the
<B>next(&#160;)</B> methods can appear a little strange because of this.
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_156">Add Comment</A></FONT><BR></P></DIV>
<DIV ALIGN="LEFT"><P><FONT FACE="Georgia">The <B>StateT</B> class is an
implementation of <B>State</B> (so that the same <B>StateMachine</B> class can
be used from the previous example) that adds a <B>Map</B> and a method to
initialize the map from a two-dimensional array. The <B>next(&#160;)</B> method
has a base-class implementation which must be called from the overridden derived
class <B>next(&#160;)</B> methods after they test for a <B>null Map</B> (and
initialize it if it&#146;s <B>null</B>):
<A HREF="http://www.mindview.net/Books/TIPython/BackTalk/FindPage/A_157">Add Comment</A></FONT><BR></P></DIV>

<BLOCKQUOTE><FONT SIZE = "+1"><PRE>#: c04:mousetrap2:MouseTrap2Test.py
# A better mousetrap using tables
<font color=#0000ff>import</font> string, sys
sys.path += ['../statemachine', '../mouse']
<font color=#0000ff>from</font> State <font color=#0000ff>import</font> State
<font color=#0000ff>from</font> StateMachine <font color=#0000ff>import</font> StateMachine
<font color=#0000ff>from</font> MouseAction <font color=#0000ff>import</font> MouseAction

<font color=#0000ff>class</font> StateT(State):
  <font color=#0000ff>def</font> __init__(self):
    self.transitions = None
  <font color=#0000ff>def</font> next(self, input):
    <font color=#0000ff>if</font> self.transitions.has_key(input):
      <font color=#0000ff>return</font> self.transitions[input]
    <font color=#0000ff>else</font>:
      <font color=#0000ff>raise</font> <font color=#004488>"Input not supported for current state"</font>

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

<font color=#0000ff>class</font> Luring(StateT):
  <font color=#0000ff>def</font> run(self):
    <font color=#0000ff>print</font> <font color=#004488>"Luring: Presenting Cheese, door open"</font>
  <font color=#0000ff>def</font> next(self, input):
    # Lazy initialization:
    <font color=#0000ff>if</font> <font color=#0000ff>not</font> self.transitions:
      self.transitions = {
        MouseAction.enters : MouseTrap.trapping,
        MouseAction.runsAway : MouseTrap.waiting
      }