Welcome, guest | Sign In | My Account | Store | Cart

Provides is a module that gives support for implementing state machines. States are implemented as subclasses, derived from the state machine class. Methods that are state dependant or which cause transitions are declared using decorators. Because states can be subclasses of other states, common behaviour among several states is easily supported. The implementation allows for implementing multiple states or substates within a class.

This module best support statem achines implemeting controllers for embedded systems, implementing user interfaces, or in discrete event model simulation. Parsers, which generally have many states and where you would need to define a Transaction method for each different character encountered would be more easily implemented by other means.

Python, 448 lines
  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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
"""
Supports implementation of state pattern.

State Machine is defined a class containing one or more StateTable objeects, 
and using decorators to define Events and Transitions that are handled by the 
state machine.  Individual states are Subclasses of the state machine, with 
a __metaclass__ specifier.

Author: Rodney Drenth
Date:   January, 2009
Version: Whatever

Copyright 2009, Rodney Drenth

Permission to use granted under the terms and conditions of the Python Software
Foundation License
 (http://www.python.org/download/releases/2.4.2/license/)

"""
#! /usr/bin/env Python
#

import types

class _StateVariable( object ):
   """Used as attribute of a class to maintain state.

      State Variable objects are not directly instantiated in the user's state machine class
      but are instantiated by the StateTable class attribute defined within the state machine.
   """

   def __init__(self, stateTable):
      """ Constructs state variable and sets it to the initial state
      """
      self._current_state = stateTable.initialstate
      self._next_state = stateTable.initialstate
      self.sTable = stateTable

   def _toNextState(self, context):
      """Sets state of to the next state, if new state is different. 
      calls onLeave and onEnter methods
      """
      if self._next_state is not self._current_state:
         if hasattr(self._current_state, 'onLeave'):
            self._current_state.onLeave(context)
         self._current_state = self._next_state
         if hasattr(self._current_state, 'onEnter'):
            self._current_state.onEnter(context)

   def name(self):
      """Returns ame of current state."""
      return self._current_state.__name__

   def setXition(self, func):
      """ Sets the state to transitionto upon seeing Transition event"""
#      next_state = self.sTable.nextStates[self._current_state][func.__name__]
      next_state = self._current_state.nextStates[func.__name__]
      if next_state is not None:
         self._next_state = next_state

   def getFunc(self, func):
      """ Gets event handler function based on current State"""
      funky = getattr( self._current_state, func.__name__)
#      print 'current State:', self._current_state.__name__
      if funky is None:
         raise NotImplementedError('%s.%s'%(self.name(),func.__name__))

      # when funky.name is objCall, it means that we've recursed all the
      # way back to the context class and need to call func as a default
      return funky if funky.__name__ != 'objCall' else func


class StateTable( object ):
   """Defines a state table for a state machine class

   A state table for a class is associated with the state variable in the instances
   of the class. The name of the state variable is given in the constructor to the 
   StateTable object.  StateTable objects are attributes of state machine classes, 
   not intances of the state machine class.   A state machine class can have more
   than one StateTable.
   """

   def __init__(self, stateVarblName):
      """State Table initializer

      stateVarblName is the name of the associated state variable, which will
      be instantiated in each instance of the state machine class
      """
      self.inst_state_name = stateVarblName
      self.eventList = []
      self.initialstate = None
      nextStates = {}

   def initialize(self, obj ):
      """Initialization of StateTable and state varible

      obj is the instance of the state machine being initialized. This method
      must be called in the __init__ method of the user's state machine.
      """
      obj.__dict__[self.inst_state_name] = _StateVariable( self )

   def _addEventHandler(self, funcName):
      """Notifies State table of a method that's handle's an transition.

      This is called by @Transition and @TransitionEvent decorators,
      whose definitions are below.
      """
      self.eventList.append(funcName)

   def nextStates(self, subState, nslList):
      """Sets up transitions from the state specified by subState

      subState is a state class, subclassed from user's state machine class
      nslList is a list of states that will be transitioned to upon Transitions.
      This functions maps each @Transition decorated method in the state machine
      class to a to the corresponding state in this list.  None can be specified
      as a state to indicate the state should not change.
      """
      if len(nslList) != len(self.eventList):
         raise RuntimeError( "Wrong number of states in transition list.")
      subState.nextStates = dict(zip(self.eventList, nslList))
#      self.nextStates[subState] = dict(zip( self.eventList, nslList))

def Event( state_table ):
   """Decorator for indicating state dependant method

   Decorator is applied to methods of state machine class to indicate that
   invoking the method will call state dependant method.   States are implemented
   as subclasses of the state machine class with a metaclass qualification.
   """
   stateVarName = state_table.inst_state_name

   def wrapper(func):
      # no adding of event handler to statetable...
      def objCall( self, *args, **kwargs):
         state_var = getattr(self, stateVarName )
         retn = state_var.getFunc(func)(self, *args, **kwargs)
         return retn

      return objCall
   return wrapper


def Transition( state_table ):
   """Decorator for indicating the method causes a state transition.

   Decorator is applied to methods of the state machine class. Invokeing
   the method can cause a transition to another state.  Transitions are defined
   using the nextStates method of the StateTable class
   """
   stateVarName = state_table.inst_state_name

   def wrapper(func):
      state_table._addEventHandler( func.__name__)

      def objCall( self, *args, **kwargs):
         state_var = getattr(self, stateVarName )
         state_var.setXition(func)
         rtn = func(self, *args, **kwargs)
         state_var._toNextState(self)
         return  rtn

      return objCall
   return wrapper


def TransitionEvent( state_table ):
   """Decorator for defining a method that both triggers a transition and
   invokes a state dependant method.

   This is equivalent to, but more efficient than using
   @Transition(stateTable)
   @Event(stateTable)
   """
   stateVarName = state_table.inst_state_name

   def wrapper(func):
      state_table._addEventHandler( func.__name__)

      def objCall( self, *args, **kwargs):
         state_var = getattr(self, stateVarName )
#         if not issubclass( state_var._current_state, self.__class__):
#            raise TypeError('expecting instance to be derived from %s'% baseClasss.__name__)
         state_var.setXition(func)
         retn = state_var.getFunc(func)(self, *args, **kwargs)
         state_var._toNextState(self)
         return retn

      return objCall
   return wrapper


class _stateclass(type):
   """ A stateclass metaclass 
   
   Modifies class so its subclass's methods so can be called as methods
   of a base class. Is used for implementing states
   """

   def __init__(self, name, bases, cl_dict):
      self.__baseClass__ = _bcType              # global - set by stateclass(), which follows
      if not issubclass(self, _bcType):
         raise TypeError( 'Class must derive from %s'%_bcType.__name__ )
      type.__init__(self, name, bases, cl_dict)

   def __getattribute__(self, name):
      if name.startswith('__'):
            return type.__getattribute__(self, name)
      try:
         atr = self.__dict__[name]
         if type(atr) == types.FunctionType:
            atr = types.MethodType(atr, None, self.__baseClass__)
      except KeyError, ke:
         for bclas in self.__bases__:
            try:
               atr = getattr(bclas, name)
               break
            except AttributeError, ae:
               pass
         else:
            raise AttributeError( "'%s' has no attribute '%s'" % (self.__name__, name) )
      return atr


def stateclass( statemachineclass ):
   """A method that returns a metaclass for constructing states of the
   users state machine class
   """
   global _bcType
   _bcType = statemachineclass
   return _stateclass

#  vim : set ai sw=3 et ts=6 :
-----------------------------------------------------------
"""
Example of setting up a state machine using the EasyStatePattern
module.
"""
import EasyStatePattern as esp
import math


class Parent(object):
    """ the context for the state machine class """
    moodTable = esp.StateTable('mood')

    def __init__(self, pocketbookCash, piggybankCash):
      """Instance initializer must invoke the initialize method of the StateTable """
      Parent.moodTable.initialize( self)
      self.pocketBook = pocketbookCash
      self.piggyBank = piggybankCash

    """The Transiton decorator defines a method which causes transitions to other
    states"""
    @esp.Transition(moodTable)
    def getPromotion(self): pass

    @esp.Transition(moodTable)
    def severalDaysPass(self): pass


    """The Event decorator defines a method whose exact method will depend on the
    current state. These normally do not cause a state transition.
    For this example, this method will return an amount of money that the asker is to receive,
    which will depend on the parent's mood, the amount asked for, and the availability of
    money."""
    @esp.Event(moodTable)
    def askForMoney(self, amount): pass

    """The TransitionEvent decorator acts like a combination of both the Transition
    and Event decorators.  Calling this causes a transition(if defined in the state
    table) and the called function is state dependant."""
    @esp.TransitionEvent(moodTable)
    def cashPaycheck(self, amount): pass

    @esp.TransitionEvent(moodTable)
    def getUnexpectedBill(self, billAmount ): pass

    """onEnter is called when entering a new state. This can be overriden in
    the individual state classes.  onLeave (not defined here) is called upon
    leaving a state"""
    def onEnter(self):
      print 'Mood is now', self.mood.name()

# 
# Below are defined the states. Each state is a class, States may be derived from
# other states. Topmost states must have a __metaclass__ = stateclass( state_machine_class )
# declaration.
#
class Normal( Parent ):
    __metaclass__ = esp.stateclass( Parent )
    """Normal becomes the name of the state."""

    def getPromotion(self): 
        """This shouldn't get called, since get was defined as a transition in
        the Parent context"""
        pass

    def severalDaysPass(self): 
       """neither should this be called."""
       pass

    def askForMoney(self, amount): 
        amountToReturn = min(amount, self.pocketBook )
        self.pocketBook -= amountToReturn
        if  40.0 < self.pocketBook:
            print 'Here you go, sport!'
        elif 0.0 < self.pocketBook < 40.00:
            print "Money doesn't grow on trees, you know."
        elif 0.0 < amountToReturn < amount:
            print "Sorry, honey, this is all I've got."
        elif amountToReturn == 0.0:
            print "I'm broke today ask your aunt."
            self.mood.nextState = Broke
        return amountToReturn

    def cashPaycheck(self, amount): 
        self.pocketBook += .7 * amount
        self.piggyBank += .3*amount

    def getUnexpectedBill(self, billAmount ): 
        amtFromPktBook = min(billAmount, self.pocketBook)
        rmngAmt = billAmount - amtFromPktBook
        self.piggyBank -= rmngAmt
        self.pocketBook -= amtFromPktBook
        

class Happy( Parent ):
    __metaclass__ = esp.stateclass( Parent )
    """Grouchy becomes the name of the state."""

    def askForMoney(self, amount): 
        availableMoney = self.pocketBook + self.piggyBank
        amountToReturn = max(min(amount, availableMoney), 0.0)
        amountFromPktbook =  min(amountToReturn, self.pocketBook)
        self.pocketBook -= amountFromPktbook
        self.piggyBank -= (amountToReturn - amountFromPktbook)

        if 0.0 < amountToReturn < amount:
            print "Sorry, honey, this is all I've got."
        elif amountToReturn == 0.0:
            print "I'm broke today ask your aunt."
            self.mood.nextState = Broke
        else:
            print 'Here you go, sport!'
        return amountToReturn

    def cashPaycheck(self, amount): 
        self.pocketBook += .75 * amount
        self.piggyBank += .25*amount

    def getUnexpectedBill(self, billAmount ): 
        print "why do these things always happen?"
        amtFromPktBook = min(billAmount, self.pocketBook)
        rmngAmt = billAmount - amtFromPktBook
        self.piggyBank -= rmngAmt
        self.pocketBook -= amtFromPktBook
        
    def onEnter(self):
      print 'Yippee! Woo Hoo!', self.mood.name()*3

class Grouchy( Parent ):
    __metaclass__ = esp.stateclass( Parent )
    """Grouchy becomes the name of the state."""

    def askForMoney(self, amount): 
       print """You're always spending too much. """
       return 0.0

    def cashPaycheck(self, amount): 
        self.pocketBook += .70 * amount
        self.piggyBank += .30*amount

    def getUnexpectedBill(self, billAmount ): 
        print 'These things always happen at the worst possible time!'

        amtFromPktBook = min(billAmount, self.pocketBook)
        rmngAmt = billAmount - amtFromPktBook
        self.piggyBank -= rmngAmt
        self.pocketBook -= amtFromPktBook
        

class Broke( Normal ):
    #   __metaclass__ = esp.stateclass( Parent )
    """ No metaclass declaration as its as subclass of Grouchy. """

    def cashPaycheck(self, amount): 
        piggyBankAmt = min ( amount, max(-self.piggyBank, 0.0))
        rmngAmount = amount - piggyBankAmount
        self.pocketBook += .40 * rmngAmount
        self.piggyBank += (.60 * rmngAmount + piggyBankAmt)

    def askForMoney(self, amount): 
        amountToReturn = min(amount, self.pocketBook )
        self.pocketBook -= amountToReturn
        if  40.0 < self.pocketBook:
            print 'Here you go, sport!'
        elif 0.0 < self.pocketBook < 40.00:
            print "Spend it wisely."
        elif 0.0 < amountToReturn < amount:
            print "This is all I've got."
        elif amountToReturn == 0.0:
            print "Sorry, honey, we're broke."
            self.mood.nextState = Broke
        return amountToReturn


# After defining the states, The following lines set up the transitions.
# We've set up four transitioning methods, 
# getPromotion, severalDaysPass, cashPaycheck, getUnexpectedBill 
# Therefore there are four states in each list, the ordering of the states in the
# list corresponds toorder that the transitioning methods were defined.

Parent.moodTable.nextStates( Normal, ( Happy, Normal, Normal, Grouchy ))
Parent.moodTable.nextStates( Happy, ( Happy, Happy, Happy, Grouchy ))
Parent.moodTable.nextStates( Grouchy, ( Happy, Normal, Grouchy, Grouchy ))
Parent.moodTable.nextStates( Broke, ( Normal, Broke, Grouchy, Broke ))

# This specifies the initial state. Instances of the Parent class are placed
# in this state when they are initialized.
Parent.moodTable.initialstate = Normal


def Test():
    dad = Parent(50.0, 60.0)
    amount = 20.0
    print amount, dad.askForMoney(amount)
    print amount, dad.askForMoney(amount)
    dad.cashPaycheck( 40.0)
    print amount, dad.askForMoney(amount)
    dad.cashPaycheck( 40.0)
    dad.severalDaysPass()
    print amount, dad.askForMoney(amount)
    dad.getUnexpectedBill(100.0 )
    print amount, dad.askForMoney(amount)
    dad.severalDaysPass()
    print amount, dad.askForMoney(amount)
    dad.severalDaysPass()
    dad.cashPaycheck( 100.0)
    print amount, dad.askForMoney(amount)
    dad.cashPaycheck( 50.0)
    print amount, dad.askForMoney(amount)
    dad.getPromotion()
    dad.cashPaycheck( 200.0)
    amount = 250
    print amount, dad.askForMoney(amount)

Test()

First part of above code is the module which supports the state pattern. The second part is an example of a state machine implemented using the module.

Techniques - Decorators provide code which wraps the methods in the main state machine class (MyDevice) with code that calls the method appropriate for the current state. They also are responsible for transitioning between states based on the table that's defined with the calls to 'nextStates'.

The methods in the derived classes are able to be called as if they were declared in the base state machine class because of the __metaclass__ declaration.

The actual state variable in the state machine instance is more or less hidden behind the scenes. It's implicitly created when the StateTable's initialize() method is called in the __init__ method of the state machine class. The next state can be explicitly set if needed. For example when the next state also depends on the data to the event.

When leaving a state, an onLeave() method is called if one is defined. Similarly when entering a state (except for initial state), an onEnter() method is called. These methods may be defined in the base state machine class, or they may be overriden in the individual state classes.

A good discussion of modelling with states can be found in Real Time UML by Bruce Powell Douglass, copyright 1998 Addison Wesley Longman Inc.

15-Jun-09 - revised to provide better example. With this infrastructure it is possible to implement a context with not only a main state, but with substates as well. Also its possible to subclass the context and add additional states or to provide a different state transition table. For instance, one could implement a StingyParent subclass of Parent which never doles out any money, no matter what mood their in.

11 comments

Jack Trainor 12 years, 10 months ago  # | flag

I'm looking for good reusable state machine code and maybe this is good code for that, but frankly it's hard to tell.

The sample code (TwoX, Sigmoid, etc.) seems to be an arbitrary mathematical example. I can't tell at a glance whether the program output make sense (is 0.000335350130466 right?), much less distinguish the difference between "calculate" and "compute" or develop insights for building a state machine of my own.

I suspect I'd need a day or two of poking and tracing this code before I understood it well enough to reuse.

I suggest a more down-to-earth, practical example, such as text processing (which is what I use state machines for), with more explanation telling readers what they specifically need to do to build their own state machines on the Easy State Machine pattern.

It'd also be nice to know how this recipe compares to http://code.activestate.com/recipes/146262/.

Rodney Drenth (author) 12 years, 10 months ago  # | flag

Jack Trainor,

Thanks for the comment. I'll try to come up with a better example, and I'll work on the discussion some more. I added a comment to indicate the types of applications where this method is best suited, and a reference to more information.

Tools like Ply, pyparsing, or ANTLR are a better way to develop text parsing functions. Comparing with Noel Spurrier's recipe, Using the TransactionEvent decorator when declaring a method is analogous to one of his inputs. States are classes here. The methods defined in the state class are the functions he associates with an input and a state in the add_action(?) call. His state machines are dynamically configured, here the state machines are in the coding and are completely defined prior to one being instantiated. Here the actions are really methods of the context and other data and functions of the instance are available. The actions of Spurrier's state machine are plain functions.

If you need to have multiple instances of the state machine exist simultaneously, and are handling asynchronous events, the Easy State Pattern is a good choice.

Jack Trainor 12 years, 10 months ago  # | flag

Rodney Drenth,

And thanks for the reply.

I'm not talking about parsing at the level of grammars, but text processing at a more general level that is simply stateful.

As David Mertz in "Text Processing in Python" published by Addison-Wesley (http://gnosis.cx/TPiP/chap4.txt) says "One of the programming problems most likely to call for an explicit state machine is processing text files."

See my earlier recipe, http://code.activestate.com/recipes/574430/ for an example. I've rewritten this and will repost shortly.

Jack Trainor 12 years, 10 months ago  # | flag

P.S. I'm less interested in the architectural differences between your work and Spurrier's and more interested in how the two patterns compare in solving problems with state machines.

Is it easier to use one or the other and for which types of problems?

My state machine recipe, for instance, is pretty easy but it is only useful for text processing on a line-by-line basis. Your recipe and Spurrier's provide more general purpose state machine patterns at the cost of some additional complexity.

Jack Trainor 12 years, 10 months ago  # | flag

Rodney,

I just checked in my new recipe: http://code.activestate.com/recipes/576624/ -- a simple state machine pattern for text processing. As an test implementation I solve the report processor example that David Mertz uses in his book "Text Processing in Python."

If you are still considering a new example showing how your state machine can be implemented, perhaps you could try your hand at the David Mertz report processor. I think it would be quite instructive to compare three different state machine solutions to that problem.

Rodney Drenth (author) 12 years, 5 months ago  # | flag

Revised to provide a better example. This implements a Parent whose moods are modeled by states. The amount of money a parent returns in response to a request for money is dictated by their current mood and the amount of money they've got in their pocketbook (and sometimes piggybank).

kam onn siew 12 years, 5 months ago  # | flag

Thanks Rodney for the recipe.

For the benefit of others, take note that this recipe only caters to state methods, not state attributes/variables. That means if Parent.label = 'Parent' and Normal.label = 'Parent' and in the Test() above, you include print dad.label, it will always print 'Parent' not the state it is in.

kam onn siew 12 years, 5 months ago  # | flag

Correction of previous comment:

For the benefit of others, take note that this recipe only caters to state methods, not state attributes/variables. That means if Parent.label = 'Parent' and Normal.label = 'Normal' and in the Test() above, you include print dad.label, it will always print 'Parent' not the state it is in.

Rodney Drenth (author) 12 years, 5 months ago  # | flag

Kam, your comment about state attributes/variables is correct.

One could, however, in a state's 'onEnter' method assign a variable to self and that attribute would be available to the other methods. For correctness, if you do this you should also provide an onLeave method for that state that deletes the variable using 'del'.

When the methods of a state are called, the self parameter is the context and will have the same class, and everything as the context. The classes that correspond to the states never get instantiated, funkiness behind the scenes with the metaclass and decorators.

I think that my current implementation still has some issues if you try to call other methods in the state that aren't ones corresponding to ones defined with a @Event or @TransitionEvent decorator in the context class. I'll have to work on that.

Sriram V Iyer 11 years, 9 months ago  # | flag

Not all events may be valid in all states - To specify handlers for all events in all states seems superfluous to me. For e.g., if I add another event, we need to add handlers to all states. I would like an implementation where we can specify handlers only for a subset of events.

Rodney Drenth (author) 11 years, 9 months ago  # | flag

To Sriram V Iyler, You have some valid points. I'm considering adding a method to the StateTable class whereby when you define the transitions for a state, you specify a dictionary with the transition method name as the keys and next state as values. You would only need to specify transitions for the events your interested in. I'm also thinking the code in the context class could be called in the case where you've not defined a transition for the event, and that code could throw an exception if it's appropriate.

I have a solution for the problem that Kam mentioned above, as well, but haven't yet updated this recipe..

Created by Rodney Drenth on Tue, 13 Jan 2009 (MIT)
Python recipes (4591)
Rodney Drenth's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks