doc/examples/simplestates_test.py.txt

   1 ..  #!/usr/bin/env python
   2   # -*- coding: utf8 -*-
   3
   4 simplestates_test.py:
   5 *********************
   6 Test the simplestates.py generic state machine
   7 ==============================================
   8
   9 :Status:    draft
  10 :Date:      2006-12-01
  11 :Copyright: 2006 Guenter Milde.
  12             Released under the terms of the GNU General Public License
  13             (v. 2 or later)
  14
  15 .. default-role:: literal
  16
  17 .. contents:: :depth: 2
  18
  19
  20 Abstract State Machine Class
  21 ----------------------------
  22
  23 First version of an abstract state machine
  24 ::
  25
  26   class SimpleStates1:
  27       """generic state machine acting on iterable data
  28
  29       Class attributes
  30       init_state -- name of the first state_handler method
  31       """
  32       init_state = 'start'
  33
  34 Initialisation
  35
  36 * sets the data object to the `data` argument.
  37 * remaining keyword arguments are stored as class attributes (or methods, if
  38   they are function objects) overwriting class defaults (a neat little trick
  39   I found somewhere on the net)
  40 * the `state_handler` attribute is set to the method named in `init_state`
  41
  42 ::
  43
  44       def __init__(self, data, **keyw):
  45           """data   --  iterable data object
  46                         (list, file, generator, string, ...)
  47              **keyw --  all remaining keyword arguments are
  48                         stored as class attributes
  49           """
  50           self.data = data
  51           self.__dict__.update(keyw)
  52
  53 The special `__iter__` method returns an iterator_. This allows to use
  54 a  class instance directly in an iteration loop.  We define it as is a
  55 generator_ method that sets the initial state and then iterates over the
  56 data calling the state methods::
  57
  58       def __iter__(self):
  59           self.state_handler = getattr(self, self.init_state)
  60           for token in self.data:
  61               yield self.state_handler(token)
  62
  63 To use class instances as callable objects, we add a `__call__` method::
  64
  65       def __call__(self):
  66           """Run state-machine and return tokens as a list"""
  67           return [token for token in self]
  68
  69 Example 1: A two-state machine sorting numbers
  70 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  71
  72 Our small example state machine subclasses the `SimpleStates1` class::
  73
  74   class Example1(SimpleStates1):
  75       """A silly example two-state machine sorting numbers
  76       in the categories "low" (< 3) and "high" (>= 3).
  77       """
  78
  79 It will be completed by two state methods and a `__str__` method.
  80
  81 State Methods
  82 """""""""""""
  83
  84 State methods are functions that are called to iterate over the data. They
  85 will typically
  86
  87 * test the data token for a change of state indicator
  88 * return the data token after some processing
  89
  90 In our example, the `low` method switches to `high` (and calls it with the
  91 data token), if token is bigger than 3. If not, it returns "l(token)"::
  92
  93       def low(self, token):
  94           # print "low(", token, ")",
  95           if token > 3:
  96               self.state_handler = self.high
  97               # backtracking
  98               return self.state_handler(token)
  99           return "l(%d)"%token
 100
 101 The `high` method switches to `low`, if token is bigger than 3. If not, it
 102 returns "h(token)"::
 103
 104       def high(self, token):
 105           # print "high(", token, ")",
 106           if token <= 3:
 107               self.state_handler = self.low
 108               # backtracking
 109               return self.state_handler(token)
 110           return "h(%d)"%token
 111
 112 Conversion of the class instance to a string is done by joining the list
 113 that is returned by a call to the instance with spaces::
 114
 115       def __str__(self):
 116           return " ".join(self())
 117
 118 Test
 119 """"
 120
 121 Testing is done with the nose_ test framework. This will collect and
 122 execute all test functions and methods (basically everything that starts or
 123 ends with "[Tt]est"). This is similar to the more known "py.test".
 124
 125 .. _nose: http://somethingaboutorange.com/mrl/projects/nose/
 126
 127 We set up some test data::
 128
 129   testdata = [1, 2, 3, 4, 5, 4, 3, 2, 1]
 130
 131 and define a test function::
 132
 133   def test_Example1():
 134       statemachine = Example1(testdata, init_state='low')
 135       for result in statemachine:
 136           print result,
 137       print
 138
 139       # Calling an instance should return a list of results
 140       print statemachine()
 141       assert statemachine() == ['l(1)','l(2)','l(3)',  # low numbers
 142                                'h(4)','h(5)','h(4)',  # high numbers
 143                                'l(3)','l(2)','l(1)']  # low again
 144
 145       # Converting to a string should call the __str__ method::
 146       print str(statemachine)
 147       assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 148
 149 Discussion
 150 """"""""""
 151
 152 The sorting works as expected. However, as the state handlers get the data
 153 token by token, acting on subsequent tokens or tests that combine the
 154 knowledge of several tokens are hard to achieve.
 155
 156 An example would be a state handler that sums up the data tokens and
 157 returns the result if it exceeds a threshold.
 158
 159
 160
 161 Varied State Machine Class Template
 162 -----------------------------------
 163
 164 The second version of an abstract state machine converts the test data to an
 165 iterator which is shared by the state methods.
 166
 167 There is no need to pass this on via arguments, as class methods share the
 168 class instances attributes (class variables).
 169
 170 We subclass our first version and modify to our needs::
 171
 172   class SimpleStates2(SimpleStates1):
 173       """second version of the abstract state machine class
 174       """
 175
 176 We add the initialisation of the data to the `__iter__` method. The data is
 177 transformed into an iterator_ first. ::
 178
 179       def __iter__(self):
 180           self.data_iterator = iter(self.data)
 181           self.state_handler = getattr(self, self.init_state)
 182           # do not pass data tokens as argument
 183           # (state methods should call self.data_iterator.next() instead)
 184           while True:
 185               yield self.state_handler()
 186
 187 Iterators "use up" the data, so the state methods will always get a "new"
 188 token until the data is fully "used up" and `StopIteration` is raised
 189 aborting the iteration.
 190
 191 Doing the conversion from iterable to iterator in `__iter__` and not in
 192 `__init__` allows repeated iteration over the class instance (if the data is
 193 a list or a file and not already a generator) as the "used up" generator is
 194 replaced by a new one.
 195
 196 Example 2: Another two-state machine sorting numbers
 197 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 198
 199 Our small example state machine subclasses the `SimpleStates2` class
 200 and adds 2 methods as state handlers. ::
 201
 202   class Example2(SimpleStates2):
 203       """An example two-state machine sorting numbers
 204       in the categories "low" (< 3) and "high" (>= 3).
 205       """
 206
 207 State methods
 208 """""""""""""
 209
 210 This time, the state methods will get the data tokens not as argument but
 211 take them from the `data_iterator`. Note that *backtracking* is impossible
 212 with a standard iterator. See below for the problem this causes for our
 213 sorting algorithm. ::
 214
 215       def low(self):
 216           # print "low(", token, ")",
 217           token = self.data_iterator.next()
 218           if token > 3:
 219               self.state_handler = self.high
 220           return "l(%d)"%token
 221       def high(self):
 222           # print "high(", token, ")",
 223           token = self.data_iterator.next()
 224           if token <= 3:
 225               self.state_handler = self.low
 226           return "h(%d)"%token
 227
 228 Test
 229 """"
 230
 231 Define a second test function::
 232
 233   def test_Example2():
 234       statemachine = Example2(testdata, init_state='low')
 235
 236 Calling an instance should return a list of results. However, as
 237 we cannot backtrack on a normal iterator, the result is not as we expected:
 238 There is a "hysteresis" the "switch triggering" token is always processed by
 239 the "old" state::
 240
 241       print statemachine()
 242       assert statemachine() == ['l(1)', 'l(2)', 'l(3)', # low numbers
 243                                'l(4)', 'h(5)', 'h(4)', # high numbers
 244                                'h(3)', 'l(2)', 'l(1)'] # low numbers
 245
 246 Discussion
 247 """"""""""
 248
 249 Missing backtracks break our number sorting machine. The remedy
 250 is the use of an iterator with an appendleft() method (known from the
 251 dqueue() standard class). We will come to this in `Example 4`__
 252
 253 __ `Example 4: A two-state machine with generators and backtracking`_
 254
 255 OTOH, as the state methods do the fetching of data tokens themself, a state
 256 handler that sums up the data tokens and returns the result if it exceeds a
 257 threshold would be easy to implement. We will do this in our next example
 258 using state handler generators.
 259
 260
 261 State Machine class using state_handler generators
 262 --------------------------------------------------
 263
 264 The variations in `StateMachine2` complicate the StateMachine design. They
 265 makes sense, however, if we use generated iterators to handle the states.
 266 No changes are needed to the abstract base class, so that Example 3 can
 267 build on `StateMachine2`::
 268
 269   class Example3(SimpleStates2):
 270
 271 Example 3: A two-state machine with state handler generators
 272 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 273
 274 State Generators
 275 """"""""""""""""
 276
 277 State Generators generate and return an iterator that will handle the next
 278 data token(s) if its .next() method is called. This is easily achieved with a
 279 for loop over self.data and the `yield` keyword.
 280 ::
 281
 282       def high_handler_generator(self):
 283           """Return an iterator, whose next() method
 284           returns "h(token)" and switches to `low`, if token > 3
 285           """
 286           for token in self.data_iterator:
 287               if token <= 3:
 288                   self.state_handler = self.low
 289               yield "h(%d)"%token
 290       #
 291       def low_handler_generator(self):
 292           """Return an iterator, whose next() method sums up data tokens.
 293           If the sum exceeds 8, it is returned and the state
 294           switches to `high`.
 295           """
 296           sum = 0
 297           for token in self.data_iterator:
 298               sum += token
 299               if sum > 8:
 300                   self.state_handler = self.high
 301                   yield "s=%d"%sum
 302                   sum = 0 # next iteration continues here
 303           # no more tokens but sum not reached
 304           yield "p=%d"%sum # partial sum
 305
 306 The iterator must instantiate the state-iterators before starting the
 307 iteration loop::
 308
 309       def __iter__(self):
 310           """Generate and return an iterator
 311
 312           * convert `data` to an iterator
 313           * convert the state generators into iterators
 314           * (re) set the state_handler attribute to the init-state
 315           * pass control to the active states state_handler
 316             which should call and process self.data_iterator.next()
 317           """
 318           self.data_iterator = iter(self.data)
 319           self.high = self.high_handler_generator().next
 320           self.low = self.low_handler_generator().next
 321           # init state
 322           self.state_handler = getattr(self, self.init_state)
 323           # now start the iteration, aborts if data is empty
 324           while True:
 325               yield self.state_handler()
 326
 327 Test
 328 """"
 329
 330 Again define a test function that gets an instance of the Example3 class ::
 331
 332   def test_Example3():
 333       statemachine = Example3(testdata, init_state='low')
 334
 335 Calling statemachine() should iterate over the test data and return the
 336 processed values as list::
 337
 338       print statemachine()
 339       assert statemachine() == ['s=10','h(5)','h(4)','h(3)', 'p=3']
 340
 341 Backtracking
 342 ------------
 343
 344 the iterqueue module provides an "extensible" iterator with, e.g.,
 345 an `appendleft` method to push back values::
 346
 347   from iterqueue import XIter
 348
 349 Thus we can prepend a non-processed data item
 350 to the data iterator for use by the next state handler
 351
 352 Example 4: A two-state machine with generators and backtracking
 353 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 354
 355 Again we start from the `SimpleStates2` base class::
 356
 357   class Example4(SimpleStates2):
 358       """two-state machine with generators and backtracking
 359       """
 360
 361 Let the iterator wrap the data in an XIter instance with `appendleft`
 362 method::
 363
 364       def __iter__(self):
 365           """Generate and return an iterator
 366
 367           * convert `data` to an iterator queue
 368           * convert the state generators into iterators
 369           * (re) set the state_handler attribute to the init-state
 370           * pass control to the active states state_handler
 371             which should call and process self.data_iterator.next()
 372           """
 373           self.data_iterator = XIter(self.data) # queue with `appendleft` method
 374           self.high = self.high_handler_generator().next
 375           self.low = self.low_handler_generator().next
 376           self.state_handler = getattr(self, self.init_state)
 377           # now start the iteration
 378           while True:
 379               yield self.state_handler()
 380
 381 Add state method generators that use the "backtracking" feature::
 382
 383       def high_handler_generator(self):
 384           """Return an iterator, whose next() method
 385           returns "h(token)" and switches to `low`, if token > 3
 386           """
 387           for token in self.data_iterator:
 388               # print "high got", token
 389               if token <= 3:
 390                   # push back data token
 391                   self.data_iterator.appendleft(token)
 392                   # set the new state
 393                   self.state_handler = self.low
 394                   # return non-value indicating the state switch
 395                   yield None
 396               else:
 397                   yield "h(%d)"%token
 398       #
 399       def low_handler_generator(self):
 400           """Return an iterator, whose next() method
 401           returns "l(token)" and switches to `high`, if token <=3
 402           """
 403           for token in self.data_iterator:
 404               # print "low got", token
 405               if token > 3:
 406                   self.data_iterator.appendleft(token) # push back
 407                   # set and run the new state
 408                   self.state_handler = self.high
 409                   # alternatively, return the token processed by the new
 410                   # state handler
 411                   yield self.state_handler()
 412               else:
 413                   yield "l(%d)"%token
 414
 415 The `__str__` converter should ignore the switch-indicator::
 416
 417       def __str__(self):
 418           tokens = [token for token in self() if token != None]
 419           return " ".join(tokens)
 420
 421 Test
 422 """"
 423
 424 Again define a test function. This time with an instance of the Example4
 425 class ::
 426
 427   def test_Example4():
 428       statemachine = Example4(testdata, init_state='low')
 429
 430 Calling statemachine() should iterate over the test data and return the
 431 processed values as list. If the state of the machine changes, the special
 432 "non-value" `None` is returned. ::
 433
 434       print statemachine() # only printed if something goes wrong
 435       assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 436                                'h(4)', 'h(5)', 'h(4)', None, # switch indicator
 437                                'l(3)', 'l(2)', 'l(1)']
 438
 439 Converting to a string should skip the `None` values::
 440
 441       print statemachine
 442       assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 443
 444 Discussion
 445 """"""""""
 446
 447 The `XIter` class allows backtracking also in a state machine with state
 448 handlers acting on a common iterator object. The "high" and "low" handlers
 449 demonstrate two possible actions for the state-transition with backtrack:
 450 Either call the new state handler from the current one
 451 (like the `low_handler_generator`) or return a "non-value" that signifies
 452 that processing the data token did not produce any output data.
 453
 454 Using generators made the state handlers shorter and (once the concept of a
 455 generator is clear) easier. Further advantages of the generator concept are
 456
 457 * internal variables are easily saved over subsequent invocations
 458 * no function-call overhead (not relevant in this example but maybe for a
 459   state machine that has to process long data lists.
 460
 461
 462 Converting all state method generators with a generic function
 463 --------------------------------------------------------------
 464
 465 In `Example4`, we had to redefine the `__iter__` method to convert the
 466 method state generators into iterators. It would be nice if this could be
 467 done in the base class.
 468
 469 `SimpleStates3` adds a generic function for this task that relies on a
 470 simple naming convention: functions whose name matches
 471 `<state>_handler_generator` should be converted to iterators and their
 472 `.next()` method stored as `<state>`.
 473 ::
 474
 475   class SimpleStates5(SimpleStates2):
 476       """generic state machine acting on iterable data
 477       """
 478       def _initialize_state_generators(self):
 479           """Generic function to initialise state handlers from generators
 480
 481           functions whose name matches `[^_]<state>_handler_generator` should
 482           be converted to iterators and their `.next()` method stored as
 483           `<state>`.
 484           """
 485           suffix = "_handler_generator"
 486           shg_names = [name for name in dir(self)
 487                         if name.endswith(suffix)
 488                         and not name.startswith("_")]
 489           for name in shg_names:
 490               shg = getattr(self, name)
 491               print shg
 492               setattr(self, name[:-len(suffix)], shg().next)
 493
 494
 495       def __iter__(self):
 496           """Generate and return an iterator
 497
 498           * convert `data` to an iterator queue
 499           * convert the state generators into iterators
 500           * (re) set the state_handler attribute to the init-state
 501           * pass control to the active states state_handler
 502             which should call and process self.data_iterator.next()
 503           """
 504           self.data_iterator = XIter(self.data) # queue with `appendleft` method
 505           self._initialize_state_generators()
 506           self.state_handler = getattr(self, self.init_state)
 507           # now start the iteration
 508           while True:
 509               yield self.state_handler()
 510
 511 Example 5
 512 ~~~~~~~~~
 513
 514 The next example combines the state handlers from Example 4 and the new
 515 class.::
 516
 517   class Example5(Example4, SimpleStates5):
 518       """one more example"""
 519       pass
 520
 521 Test
 522 """"
 523
 524 A function that has the generator-suffix but is prefixed with an underscore,
 525 should be skipped by the `_initialize_state_generators` method::
 526
 527   class Test_SimpleStates5:
 528       E5 = Example5(testdata)
 529       E5._bogus_handler_generator = "low"
 530       def test_initialize_state_generators(self):
 531           self.E5._initialize_state_generators()
 532
 533 A test function. This time with an instance of the Example5 class ::
 534
 535   def test_Example5():
 536       statemachine = Example5(testdata, init_state='low')
 537       print statemachine.__dict__
 538
 539 Calling statemachine() should iterate over the test data and return the
 540 processed values as list. If the state of the machine changes, the special
 541 "non-value" `None` is returned. ::
 542
 543       print statemachine() # only printed if something goes wrong
 544       assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 545                                'h(4)', 'h(5)', 'h(4)', None, # switch indicator
 546                                'l(3)', 'l(2)', 'l(1)']
 547
 548 Converting to a string should skip the `None` values::
 549
 550       print statemachine
 551       assert str(statemachine) == "l(1) l(2) l(3) h(4) h(5) h(4) l(3) l(2) l(1)"
 552
 553 Putting it together
 554 -------------------
 555
 556 The file `simplestates.py` contains the full definition of the `SimpleStates5`
 557 class in a self-contained version.
 558
 559 Example 6
 560 ~~~~~~~~~
 561
 562 The final Example is used to test whether we have put it together well. It
 563 subclasses SimpleStates and adds state method generators for "high" and
 564 "low"::
 565
 566   import simplestates
 567   class Example6(simplestates.SimpleStates):
 568       """two-state machine with generators and backtracking
 569       """
 570       def high_handler_generator(self):
 571           """Return an iterator, whose next() method
 572           returns "h(token)" and switches to `low`, if token > 3
 573           """
 574           for token in self.data_iterator:
 575               # print "high got", token
 576               if token <= 3:
 577                   # push back data token
 578                   self.data_iterator.appendleft(token)
 579                   # set the new state
 580                   self.state_handler = self.low
 581                   # return the token processed by the new state handler
 582                   yield self.state_handler()
 583               else:
 584                   yield "h(%d)"%token
 585       #
 586       def low_handler_generator(self):
 587           """Return an iterator, whose next() method
 588           returns "l(token)" and switches to `high`, if token <=3
 589           """
 590           for token in self.data_iterator:
 591               # print "low got", token
 592               if token > 3:
 593                   self.data_iterator.appendleft(token) # push back
 594                   # set and run the new state
 595                   self.state_handler = self.high
 596                   # return the token processed by the new state handler
 597                   yield self.state_handler()
 598               else:
 599                   yield "l(%d)"%token
 600
 601 Test
 602 """"
 603
 604 In order not to make it dependent on the iterqueue module, the final
 605 `SimpleStates` does not wrap the data in an XIter instance. This step should
 606 be done at the instantiation of a state machine. ::
 607
 608   def test_Example5():
 609       statemachine = Example5(XIter(testdata), init_state='low')
 610       print statemachine.__dict__
 611
 612 Calling statemachine() should iterate over the test data and return the
 613 processed values as list::
 614
 615       print statemachine() # only printed if something goes wrong
 616       # reset the data iterator as it is "used up" now
 617       statemachine.data = XIter(testdata)
 618       assert statemachine() == ['l(1)', 'l(2)', 'l(3)',
 619                                'h(4)', 'h(5)', 'h(4)', None,
 620                                'l(3)', 'l(2)', 'l(1)']
 621
 622 Index
 623 -----
 624
 625
 626 :_`generator`: A function with a `yield` keyword. Calling this function will
 627                return an iterator_
 628
 629 :_`iterator`: An object with a `next()` method. Calling `<iterator>.next()`
 630               will (typically) return one data token (list element, line in
 631               a file, ...). If there is no more data the `StopIteration`
 632               exception is raised.
 633
 634 Command line usage
 635 ------------------
 636
 637 running this script should explore it in the "nose" test framework::
 638
 639   if __name__ == "__main__":
 640       import nose, doctest
 641       # first run any doctests
 642       doctest.testmod()
 643       # then run nose on this module
 644       nose.runmodule() # requires nose 0.9.1