[译] PEP 255--简单的生成器

PEP 原文https://www.python.org/dev/peps/pep-0255

创建日期:2001-05-18

合入版本:2.2

译者豌豆花下猫Python 猫 公众号作者)

摘要

这个 PEP 想在 Python 中引入生成器的概念,以及一个新的表达式,即 yield 表达式。

动机

当一个生产者函数在处理某些艰难的任务时,它可能需要维持住生产完某个值时的状态,大多数编程语言都提供不了既舒服又高效的方案,除了往参数列表中添加回调函数,然后每生产一个值时就去调用一下。

例如,标准库中的tokenize.py采用这种方法:调用者必须传一个 tokeneater 函数给 tokenize() ,当 tokenize() 找到下一个 token 时再调用。这使得 tokenize 能以自然的方式编码,但程序调用 tokenize 会变得极其复杂,因为它需要记住每次回调前最后出现的是哪个 token(s)。tabnanny.py中的 tokeneater 函数是处理得比较好的例子,它在全局变量中维护了一个状态机,用于记录已出现的 token 和预期会出现的 token 。这很难正确地工作,而且也挺难让人理解。不幸的是,它已经是最标准的解决方法了。

有一个替代方案是一次性生成 Python 程序的全部解析,并存入超大列表中。这样 tokenize 客户端可以用自然的方式,即使用局部变量和局部控制流(例如循环和嵌套的 if 语句),来跟踪其状态。然而这并不实用:程序会变得臃肿,因此不能在实现整个解析所需的内存上放置先验限制;而有些 tokenize 客户端仅仅想要查看某个特定的东西是否曾出现(例如,future 声明,或者像 IDLE 做的那样,只是首个缩进的声明),因此解析整个程序就是严重地浪费时间。

另一个替代方案是把 tokenize 变为一个迭代器【注释 1】,每次调用它的 next() 方法时再传递下一个 token。这对调用者来说很便利,就像前一方案把结果存入大列表一样,同时没有内存与“想要早点退出怎么办”的缺点。然而,这个方案也把 tokenize 的负担转化成记住 next() 的调用状态,读者只要瞄一眼 tokenize.tokenize_loop() ,就会意识到这是一件多么可怕的苦差事。或者想象一下,用递归算法来生成普通树结构的节点:若把它投射成一个迭代器框架实现,就需要手动地移除递归状态并维护遍历的状态。

第四种选择是在不同的线程中运行生产者和消费者。这允许两者以自然的方式维护其状态,所以都会很舒服。实际上,Python 源代码发行版中的 Demo/threads/Generator.py 就提供了一个可用的同步通信(synchronized-communication)类,来完成一般的任务。但是,这在没有线程的平台上无法运用,而且就算可用也会很慢(与不用线程可取得的成就相比)。

最后一个选择是使用 Python 的变种 Stackless 【注释 2-3】来实现,它支持轻量级的协程。它与前述的线程方案有相同的编程优势,效率还更高。然而,Stackless 在 Python 核心层存在争议,Jython 也可能不会实现相同的语义。这个 PEP 不是讨论这些问题的地方,但完全可以说生成器是 Stackless 相关功能的子集在当前 CPython 中的一种简单实现,而且可以说,其它 Python 实现起来也相对简单。

以上分析完了已有的方案。其它一些高级语言也提供了不错的解决方案,特别是 Sather 的迭代器,它受到 CLU 的迭代器启发【注释 4】;Icon 的生成器,一种新颖的语言,其中每个表达式都是生成器【注释 5】。它们虽有差异,但基本的思路是一致的:提供一种函数,它可以返回中间结果(“下一个值”)给它的调用者,同时还保存了函数的局部状态,以便在停止的位置恢复(译注:resum,下文也译作激活)调用。一个非常简单的例子:

def fib():
a, b = 0, 1
while 1:
yield b
a, b = b, a+b

当 fib() 首次被调用时,它将 a 设为 0,将 b 设为 1,然后生成 b 给其调用者。调用者得到 1。当 fib 恢复时,从它的角度来看,yield 语句实际上跟 print 语句相同:fib 继续执行,且所有局部状态完好无损。然后,a 和 b 的值变为 1,并且 fib 再次循环到 yield,生成 1 给它的调用者。以此类推。 从 fib 的角度来看,它只是提供一系列结果,就像用了回调一样。但是从调用者的角度来看,fib 的调用就是一个可随时恢复的可迭代对象。跟线程一样,这允许两边以最自然的方式进行编码;但与线程方法不同,这可以在所有平台上高效完成。事实上,恢复生成器应该不比函数调用昂贵。

同样的方法适用于许多生产者/消费者函数。例如,tokenize.py 可以生成下一个 token 而不是用它作为参数调用回调函数,而且 tokenize 客户端可以以自然的方式迭代 tokens:Python 生成器是一种迭代器,但是特别强大。

设计规格:yield

引入了一种新的表达式:

yield_stmt:“yield”expression_list

yield 是一个新的关键字,因此需要一个 future 声明【注释 8】来进行引入:在早期版本中,若想使用生成器的模块,必须在接近头部处包含以下行(详见 PEP 236):

from __future__ import generators

没有引入 future 模块就使用 yield 关键字,将会告警。 在后续的版本中,yield 将是一个语言关键字,不再需要 future 语句。

yield 语句只能在函数内部使用。包含 yield 语句的函数被称为生成器函数。从各方面来看,生成器函数都只是个普通函数,但在它的代码对象的 co_flags 中设置了新的“CO_GENERATOR”标志。

当调用生成器函数时,实际参数还是绑定到函数的局部变量空间,但不会执行代码。得到的是一个 generator-iterator 对象;这符合迭代器协议【注释 6】,因此可用于 for 循环。注意,在上下文无歧义的情况下,非限定名称 “generator” 既可以指生成器函数,又可以指生成器-迭代器(generator-iterator)。

每次调用 generator-iterator 的 next() 方法时,才会执行 generator-function 体中的代码,直至遇到 yield 或 return 语句(见下文),或者直接迭代到尽头。

如果执行到 yield 语句,则函数的状态会被冻结,并将 expression_list 的值返回给 next() 的调用者。“冻结”是指挂起所有本地状态,包括局部变量、指令指针和内部堆栈:保存足够的信息,以便在下次调用 next() 时,函数可以继续执行,仿佛 yield 语句只是一次普通的外部调用。

限制:yield 语句不能用于 try-finally 结构的 try 子句中。困难的是不能保证生成器会被再次激活(resum),因此无法保证 finally 语句块会被执行;这就太违背 finally 的用处了。

限制:生成器在活跃状态时无法被再次激活:

>>> def g():
... i = me.next()
... yield i
>>> me = g()
>>> me.next()
Traceback (most recent call last):
...
File "<string>", line 2, in g
ValueError: generator already executing

设计规格:return

生成器函数还可以包含以下形式的 return 语句:

return

注意,生成器主体中的 return 语句不允许使用 expression_list (然而当然,它们可以嵌套地使用在生成器里的非生成器函数中)。

当执行到 return 语句时,程序会正常 return,继续执行恰当的 finally 子句(如果存在)。然后引发一个 StopIteration 异常,表明迭代器已经耗尽。如果程序没有显式 return 而执行到生成器的末尾,也会引发 StopIteration 异常。

请注意,对于生成器函数和非生成器函数,return 意味着“我已经完成,并且没有任何有趣的东西可以返回”。

注意,return 并不一定会引发 StopIteration :关键在于如何处理封闭的 try-except 结构。 例如:

>>> def f1():
... try:
... return
... except:
... yield 1
>>> print list(f1())
[]

因为,就像在任何函数中一样,return 只是退出,但是:

>>> def f2():
... try:
... raise StopIteration
... except:
... yield 42
>>> print list(f2())
[42]

因为 StopIteration 被一个简单的 except 捕获,就像任意异常一样。

设计规格:生成器和异常传播

如果一个未捕获的异常——包括但不限于 StopIteration——由生成器函数引发或传递,则异常会以通常的方式传递给调用者,若试图重新激活生成器函数的话,则会引发 StopIteration 。 换句话说,未捕获的异常终结了生成器的使用寿命。

示例(不合语言习惯,仅作举例):

>>> def f():
... return 1/0
>>> def g():
... yield f() # the zero division exception propagates
... yield 42 # and we'll never get here
>>> k = g()
>>> k.next()
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 2, in g
File "<stdin>", line 2, in f
ZeroDivisionError: integer division or modulo by zero
>>> k.next() # and the generator cannot be resumed
Traceback (most recent call last):
File "<stdin>", line 1, in ?
StopIteration
>>>

设计规格:Try/Exception/Finally

前面提过,yield 语句不能用于 try-finally 结构的 try 子句中。这带来的结果是生成器要非常谨慎地分配关键的资源。但是在其它地方,yield 语句并无限制,例如 finally 子句、except 子句、或者 try-except 结构的 try 子句:

>>> def f():
... try:
... yield 1
... try:
... yield 2
... 1/0
... yield 3 # never get here
... except ZeroDivisionError:
... yield 4
... yield 5
... raise
... except:
... yield 6
... yield 7 # the "raise" above stops this
... except:
... yield 8
... yield 9
... try:
... x = 12
... finally:
... yield 10
... yield 11
>>> print list(f())
[1, 2, 4, 5, 8, 9, 10, 11]
>>>

示例

# 二叉树类
class Tree:

def __init__(self, label, left=None, right=None):
self.label = label
self.left = left
self.right = right

def __repr__(self, level=0, indent=" "):
s = level*indent + `self.label`
if self.left:
s = s + "\n" + self.left.__repr__(level+1, indent)
if self.right:
s = s + "\n" + self.right.__repr__(level+1, indent)
return s

def __iter__(self):
return inorder(self)

# 从列表中创建 Tree
def tree(list):
n = len(list)
if n == 0:
return []
i = n / 2
return Tree(list[i], tree(list[:i]), tree(list[i+1:]))

# 递归生成器,按顺序生成树标签
def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x

# 展示:创建一棵树
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# 按顺序打印树的节点
for x in t:
print x,
print

# 非递归生成器
def inorder(node):
stack = []
while node:
while node.left:
stack.append(node)
node = node.left
yield node.label
while not node.right:
try:
node = stack.pop()
except IndexError:
return
yield node.label
node = node.right

# 练习非递归生成器
for x in t:
print x,
print
Both output blocks display:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

问答

为什么重用 def 而不用新的关键字

请参阅下面的 BDFL 声明部分。

为什么用新的关键字 yield 而非内置函数

Python 中通过关键字能更好地表达控制流,即 yield 是一个控制结构。而且为了 Jython 的高效实现,编译器需要在编译时就确定潜在的挂起点,新的关键字会使这一点变得简单。CPython 的实现也大量利用它来检测哪些函数是生成器函数(尽管一个新的关键字替代 def 就能解决 CPython 的问题,但人们问“为什么要新的关键字”问题时,并不想要新的关键字)。

为什么不是其它不带新关键字的特殊语法

例如,为何不用下面用法而用 yield 3:

return 3 and continue
return and continue 3
return generating 3
continue return 3
return >> , 3
from generator return 3
return >> 3
return << 3
>> 3
<< 3
* 3

我没有错过一个“眼色”吧?在数百条消息中,我算了每种替代方案有三条建议,然后总结出上面这些。不需要用新的关键字会很好,但使用 yield 会更好——我个人认为,在一堆无意义的关键字或运算符序列中,yield 更具表现力。尽管如此,如果这引起足够的兴趣,支持者应该发起一个提案,交给 Guido 裁断。

为什么允许用 return,而不强制用 StopIteration

“StopIteration”的机制是底层细节,就像 Python 2.1 中的“IndexError”的机制一样:实现时需要做一些预先定义好的东西,而 Python 为高级用户开放了这些机制。尽管不强制要求每个人都在这个层级工作。 “return”在任何一种函数中都意味着“我已经完成”,这很容易解读和使用。注意,return 并不总是等同于 try-except 结构中的 raise StopIteration(参见“设计规格:Return”部分)。

那为什么不允许 return 一个表达式

也许有一天会允许。 在 Icon 中,return expr 意味着“我已经完成”和“但我还有最后一个有用的值可以返回,这就是它”。 在初始阶段,不强制使用return expr的情况下,使用 yield 仅仅传递值,这很简单明了。

BDFL 声明

Issue

引入另一个新的关键字(比如,gen 或 generator )来代替 def ,或以其它方式改变语法,以区分生成器函数和非生成器函数。

Con

实际上(你如何看待它们),生成器函数,但它们具有可恢复性。使它们建立起来的机制是一个相对较小的技术问题,引入新的关键字无助于强调生成器是如何启动的机制(生成器生命中至关重要却很小的部分)。

Pro

实际上(你如何看待它们),生成器函数实际上是工厂函数,它们就像施了魔法一样地生产生成器-迭代器。 在这方面,它们与非生成器函数完全不同,更像是构造函数而不是函数,因此重用 def 无疑是令人困惑的。藏在内部的 yield 语句不足以警示它们的语义是如此不同。

BDFL

def 留了下来。任何一方都没有任何争论是完全令人信服的,所以我咨询了我的语言设计师的直觉。它告诉我 PEP 中提出的语法是完全正确的——不是太热,也不是太冷。但是,就像希腊神话中的 Delphi(译注:特尔斐,希腊古都) 的甲骨文一样,它并没有告诉我原因,所以我没有对反对此 PEP 语法的论点进行反驳。 我能想出的最好的(除了已经同意做出的反驳)是“FUD”(译注:缩写自 fear、uncertainty 和 doubt)。 如果这从第一天开始就是语言的一部分,我非常怀疑这早已让安德鲁·库奇林(Andrew Kuchling)的“Python Warts”页面成为可能。(译注:wart 是疣,一种难看的皮肤病。这是一个 wiki 页面,列举了对 Python 吹毛求疵的建议)。

参考实现

当前的实现(译注:2001 年),处于初步状态(没有文档,但经过充分测试,可靠),是 Python 的 CVS 开发树【注释 9】的一部分。 使用它需要您从源代码中构建 Python。

这是衍生自 Neil Schemenauer【注释 7】的早期补丁。

脚注和参考文献

[1] PEP-234, Iterators, Yee, Van Rossum

http://www.python.org/dev/peps/pep-0234/

[2] http://www.stackless.com/

[3] PEP-219, Stackless Python, McMillan

http://www.python.org/dev/peps/pep-0219/

[4] “Iteration Abstraction in Sather” Murer, Omohundro, Stoutamire and Szyperski

http://www.icsi.berkeley.edu/~sather/Publications/toplas.html

[5] http://www.cs.arizona.edu/icon/

[6] The concept of iterators is described in PEP 234. See [1] above.

[7] http://python.ca/nas/python/generator.diff

[8] PEP 236, Back to the future, Peters

http://www.python.org/dev/peps/pep-0236/

[9] To experiment with this implementation, check out Python from CVS according to the instructions at http://sf.net/cvs/?group_id=5470 ,Note that the std test Lib/test/test_generators.py contains many examples, including all those in this PEP.

版权信息

本文档已经放置在公共领域。源文档:https://github.com/python/peps/blob/master/pep-0255.txt

(译文完)