简单理解Python中基于生成器的状态机

简单生成器有许多优点。生成器除了能够用更自然的方法表达一类问题的流程之外，还极大地改善了许多效率不足之处。在 Python 中，函数调用代价不菲；除其它因素外，还要花一段时间解决函数参数列表（除了其它的事情外，还要分析位置参数和缺省参数）。初始化框架对象还要采取一些建立步骤（据 Tim Peters 在 comp.lang.python 上所说，有 100 多行 C 语言程序；我自己还没检查 Python 源代码呢）。与此相反，恢复一个生成器就相当省力；参数已经解析完了，而且框架对象正“无所事事地”等待恢复（几乎不需要额外的初始化）。当然，如果速度是最重要的，您不应该使用字节码已编译过的动态语言；但即使在速度不是主要考虑因素的情况下，快点总比慢点好。
回忆状态机

在“可爱的 Python”前面的另一篇文章中，我介绍了StateMachine 类 ，给定的机器需要多少状态处理程序，它就允许用户添加多少状态处理程序。在模型中，将一个或多个状态定义为终态（end state），仅将一个状态定义为初始状态（start state）（调用类方法对此进行配置）。每个处理程序都有某种必需的结构；处理程序将执行一系列操作，然后过一会儿，它带着一个标记返回到 StateMachine.run() 方法中的循环内，该标记指出了想得到的下一个状态。同样，用 cargo 变量允许一个状态把一些（未处理的）信息传递给下一个状态。

我介绍的 StateMachine 类的典型用途是以一个有状态的方式使用输入。例如，我所用的一个文本处理工具（Txt2Html）从一个文件中读取数行内容；依据每行所属的类别，需要以特殊的方式对其进行处理。然而，您经常需要看看前面几行提供的上下文来确定当前行属于哪个类别（以及应该怎样处理它）。构建在 StateMachine 类上的这个过程的实现可以定义一个 A 处理程序，该处理程序读取几行，然后以类似 A 的方式处理这些行。不久，满足了一个条件，这样下一批的几行内容就应该由 B 处理程序来处理了。 A 把控制传递回 .run() 循环，同时指示切换到 B 状态 ― 以及任何 A 不能正确处理的、 B 应该在阅读额外的几行之前处理的额外的行。最后，某个处理程序将它的控制传递给某个被指定为终态的状态，处理停止（halt）。

对于前面一部分中的具体代码示例，我使用了一个简化过的应用程序。我处理由迭代函数产生的数字流，而不是处理多行内容。每个状态处理程序仅打印那些在期望的数字范围内的数字（以及关于有效状态的一些消息）。当数字流中的一个数字传到一个不同的范围内，另一个不同的处理程序就会接管“处理”。对于这一部分，我们将看看另一种用生成器实现相同数字流处理的方式（有一些额外的技巧和功能）。但是，一个更复杂的生成器示例有可能对更象上一段中提到的输入流进行处理。我们再来看看前一个状态机删减过代码的版本：
清单 1. statemachine_test.py

from statemachine import StateMachine
def ones_counter(val):
  print "ONES State:  ",
  while 1:
    if val <= 0 or val >= 30:
      newState = "Out_of_Range" ; break
    elif 20 <= val < 30:
      newState = "TWENTIES";   break
    elif 10 <= val < 20:
      newState = "TENS";     break
    else:
      print " @ %2.1f+" % val,
    val = math_func(val)
  print " >>"
  return (newState, val)
# ... other handlers ...
def math_func(n):
  from math import sin
  return abs(sin(n))*31
if __name__== "__main__":
  m = StateMachine()
  m.add_state("ONES", ones_counter)
  m.add_state("TENS", tens_counter)
  m.add_state("TWENTIES", twenties_counter)
  m.add_state("OUT_OF_RANGE", None, end_state=1)
  m.set_start("ONES")
  m.run(1)

读者如果接下来对导入的 StateMachine 类以及它的方法如何工作感兴趣，应该看看前面的文章。

使用生成器

基于生成器的状态机的完整版本比我更愿意在本专栏中介绍的代码样本略长。不过，下面的代码样本是完整的应用程序，而且不需要导入单独的 statemachine 模块以提供支持。总的来说，这个版本比基于类的那个版本要短一些（我们将看到它有一些特别之处，而且还非常强大）。
清单 2. stategen_test.py

from __future__ import generators
import sys
def math_gen(n):  # Iterative function becomes a generator
  from math import sin
  while 1:
    yield n
    n = abs(sin(n))*31
# Jump targets not state-sensitive, only to simplify example
def jump_to(val):
  if  0 <= val < 10: return 'ONES'
  elif 10 <= val < 20: return 'TENS'
  elif 20 <= val < 30: return 'TWENTIES'
  else:        return 'OUT_OF_RANGE'
def get_ones(iter):
  global cargo
  while 1:
    print "\nONES State:   ",
    while jump_to(cargo)=='ONES':
      print "@ %2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def get_tens(iter):
  global cargo
  while 1:
    print "\nTENS State:   ",
    while jump_to(cargo)=='TENS':
      print "#%2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def get_twenties(iter):
  global cargo
  while 1:
    print "\nTWENTIES State: ",
    while jump_to(cargo)=='TWENTIES':
      print "*%2.1f " % cargo,
      cargo = iter.next()
    yield (jump_to(cargo), cargo)
def exit(iter):
  jump = raw_input('\n\n[co-routine for jump?] ').upper()
  print "...Jumping into middle of", jump
  yield (jump, iter.next())
  print "\nExiting from exit()..."
  sys.exit()
def scheduler(gendct, start):
  global cargo
  coroutine = start
  while 1:
    (coroutine, cargo) = gendct[coroutine].next()
if __name__ == "__main__":
  num_stream = math_gen(1)
  cargo = num_stream.next()
  gendct = {'ONES'    : get_ones(num_stream),
       'TENS'    : get_tens(num_stream),
       'TWENTIES'  : get_twenties(num_stream),
       'OUT_OF_RANGE': exit(num_stream)     }
  scheduler(gendct, jump_to(cargo))

关于基于生成器的状态机，要研究的地方还很多。第一点在很大程度上是表面性的。我们安排 stategen_test.py 只能使用函数，不能使用类（至少按我的意思，生成器更有一种函数编程的感觉而非面向对象编程（OOP）的感觉）。但是，如果希望的话，您可以很容易地把相同的通用模型包装到一个或多个类中。

我们的样本中的主函数是 scheduler() ，它完全是一般性的（但是比前面的模式中的 StateMachine 要短许多）。函数 scheduler() 要求生成器-迭代器对象字典（“实例化的”生成器）作为参数。给每个生成器取的字符串名称可以是您所希望的任意名称 ― 生成器工厂函数的字面名称是一个显而易见的选择，但是我在示例中使用大写的关键字名称。 scheduler() 函数还接受“初始状态”作为参数，但如果您希望的话，也许可以自动选择一个缺省值。

每个“已调度的”生成器遵循一些简单的惯例。每个生成器运行一段时间，然后产生一对值，包含期望的跳转和某个“cargo” ― 就像用前面的模型一样。没有生成器被明确地标记为“终态”。相反，我们允许各个生成器选择产生错误来结束 scheduler() 。特殊情况下，如果生成器“离开”终态或者到达一个 return 状态，生成器将产生 StopIteration 异常。如果需要的话，您可以捕获这个异常（或者是一个不同的异常）。在我们的例子中，我们使用 sys.exit() 来终止应用程序，在 exit() 生成器中会遇到这个 sys.exit()。

要注意关于代码的两个小问题。上面的样本使用一个更简洁的循环生成器-迭代器，而不是使用迭代函数来生成我们的数字序列。生成器仅随着每个后续的调用发出一个（无穷的／不确定的）数字流，而不是连续返回“最后的值”。这是一个虽然小但却好用的生成器样本。而且，上面把“状态转换”隔离在了一个单独的函数中。在实际程序中，状态转变跳转更是上下文相关的，而且可能要在实际的生成器体内决定。该途径简化了样本。尽管可能用处不大，但是您姑且听听，我们完全可以通过一个函数工厂产生生成器函数从而进一步简化；但是一般情况每个生成器都不会与其它生成器相似到足以使这种方法切实可行。

协同程序和半协同程序

细心的读者可能注意到了，实际上我们不知不觉地进入了一种比最初所表明的要有用得多的流控制结构。在样本代码中，不仅仅只是有了状态机。事实上，上面的模式是一个很有效的协同程序通用的系统。大多数读者在此或许会需要一些背景知识。

协同程序是程序功能的集合，它允许任意地分支到其它的控制上下文中 以及从分支点任意恢复流。我们在大多数编程语言中所熟悉的子例程是通用协同程序的一种极为有限的分支情况。子例程仅从顶端的一个固定点进入并且只退出一次（它不能被恢复）。子例程还总是把流传送回它的调用者处。本质上，每个协同程序代表一个可调用的延续 ― 尽管添加一个新的单词并不一定能向不知道这个单词的人阐明它的意思。Randall HydeAn 的 The Art of Assembly中的“Cocall Sequence Between Two Processes”插图对于解释协同程序大有帮助。 参考资料上有到此图的链接。参考资料中还有到 Hyde 的综合讨论的链接，该讨论相当不错。

不管算不算负面影响，您还是会注意到，在许多语言中臭名昭著的 goto 语句也允许任意分支，但是在一个不太结构化的上下文中，它能导致“通心粉 代码”。

Python 2.2+ 的生成器向协同程序迈进了一大步。这一大步是指，生成器 ― 和函数／子例程不同 ― 是可恢复的，并且可以在多个调用之后得到值。然而，Python 生成器只不过是 Donald Knuth 所描述的“半协同程序”。生成器是可恢复的，并且可以在别处分支控制 ― 但是它只能分支控制回到直接调用它的调用者处。确切的说，生成器上下文（和任何上下文一样）可以自己调用其它生成器或函数 ― 甚至可以它自己进行递归调用 ― 但是每个最终的返回必须经由返回上下文的线性层次结构传递。Python 生成器不考虑“生产者”和“消费者”的常见协同程序用法（可以随意从对方的中间位置继续）。

幸运的是，用 Python 生成器模仿配备齐全的的协同程序相当容易。简单的窍门就是和上面样本代码中生成器十分类似的 scheduler() 函数。事实上，我们所提出的状态机本身就是一个常见得多的协同程序框架模式。适应这种模式能克服 Python 生成器中仍存在的小缺陷（让粗心大意的程序员也能发挥出通心粉代码的全部力量）。

操作中的 Stategen

要想准确了解 stategen_test.py 中发生了什么，最简单的办法就是运行它：
清单 3. 运行 STATEGEN（手工跳转控制）

% python stategen_test.py
ONES State:    @ 1.0
TWENTIES State:  *26.1  *25.3
ONES State:    @ 4.2
TWENTIES State:  *26.4  *29.5  *28.8
TENS State:    #15.2  #16.3  #16.0
ONES State:    @ 9.5  @ 3.8
TENS State:    #18.2  #17.9
TWENTIES State:  *24.4
TENS State:    #19.6
TWENTIES State:  *21.4
TENS State:    #16.1  #12.3
ONES State:    @ 9.2  @ 6.5  @ 5.7
TENS State:    #16.7
TWENTIES State:  *26.4  *30.0
[co-routine for jump?] twenties
 ...Jumping into middle of TWENTIES
TWENTIES State:
TENS State:    #19.9
TWENTIES State:  *26.4  *29.4  *27.5  *22.7
TENS State:    #19.9
TWENTIES State:  *26.2  *26.8
Exiting from exit()...

这个输出和前面的 statemachine_test.py 中的输出基本上是完全相同的。结果中的每一行分别表示在特定的处理程序或生成器中使用的流；在行的开头声明了流上下文。但是，每当另一个协同程序分支转到生成器内时，生成器版本 恢复执行（在一个循环内），而不仅仅是再次 调用处理程序函数。假设所有的 get_*() 协同程序体都包含在无限循环中，这点差异就不那么明显了。

要了解 stategen_test.py 中的本质差异，看看 exit() 生成器中发生了什么。第一次调用生成器-迭代器时，从用户处收集一个跳转目标（这是现实中的应用中有可能利用的事件驱动分支决策的一种简单情况）。然而，当再次调用 exit() 时，它位于生成器的一个稍后的流上下文中 ― 显示退出消息，并调用 sys.exit() 。交互作用样本中的用户完全可以直接跳转到“out_of_range”，不用转到另一个“处理程序”就退出（但是它 将执行一个到这个相同生成器内的递归跳转）。

结束语

我在介绍中说过，我期望状态机版本的协同程序运行速度大大超过前面介绍的带回调处理程序的类（class-with-callback-handler）"版本的速度。恢复生成器-迭代器效率要高得多。特定的示例如此简单，几乎不足以作为评判标准，但是我欢迎读者对具体结果进行反馈。

但不管我介绍的“协同程序模式”在速度方面可能取得什么样的进展，在它实现的惊人的通用流控制面前都会黯然失色。comp.lang.python 新闻组上的许多读者都曾询问过 Python 的新生成器有多通用。我想，我所描述的框架的可用性作了回答：“和您想要的一样！”对于大多数和 Python 有关的事情，对某些事情 编程通常比 理解它们要简单得多。试试我的模式；我想您会发现它很有用。