From List Comprehensions to Generator Expressions

英文原文链接: http://python-history.blogspot.com/2010/06/from-list-comprehensions-to-generator.html

原文作者: Guido van Rossum

From List Comprehensions to Generator Expressions

从 List Comprehension 到 Generator Expression

List comprehension 在 Python 2.0版本添加进来。这一特性始于Greg Ewing的一套补丁，Skip Montanaro 和 Thomas Wouters参与贡献。(如果我没记错，Tim Peters也很提倡这个想法。)本质上，可以看做众所周知的数学家采用的集合符号的Pythonic化解释。例如，通常认为如下

{x | x > 10}

代表所有满足x > 10的x组成的集合。数学里这种形式隐含了读者可接受的全集(例如根据上下文，可能是所有实数或者所有整数)。在Python中没有全集的概念，在 Python 2.0 时连集合的概念也没有。(Sets是一个有趣的故事，我将来会在另一篇博文讨论。)

基于此以及其它方面考虑，Python中采用如下语法形式来表示：

[f(x) for x in S if P(x)]

这条语句产生一个list(列表)，包含的值来自 sequence (序列) S，满足 predicate (判定) P，且被function(函数) f map (映射)。if-从句是可选项，且可以存在多个for-从句(每个for-从句可以有自己可选的if-从句)来表示嵌套循环(多for-从句会把多维元素映射到一维列表中，这一需求比较少见，因此实用中不常用)。

List comprehension 提供了内置函数map() 和 filter() 的替代。 map(f, S) 等价于 [f(x) for x in S]，filter(P, S) 等价于 [x for x in S if P(x)]。或许有人认为 map() 和 filter() 的语法形式更紧凑，所以 list comprehension 没有多少值得推荐的。然而，如果考察一个更加实际的例子，观点或许就会改变了。假设我们想对一个list中的每个元素增加1，生产一个新的list。list comprehension 的写法是 [x+1 for x in S] 。map() 的写法是 map(lambda x: x+1, S)。这儿的"lambda x: x+1" 部分是Python语法中用于内嵌的匿名函数。

两种形式(list comprehension和map()/reduce())孰优孰劣引起了争论，有人认为争论的关键在于 Python 的 lambda 语法过于繁琐，如果匿名函数能有更简洁的表示形式，那么map()就更有吸引力了。我不同意，我发觉 list comprehension 形式比函数式语法更易读，尤其是当映射函数变得复杂时。另外 list comprehension 比 map和lambda 执行速度更快。这是因为调用一个 lambda 函数就创建了一个新的堆栈结构(stack frame)，而 list comprehension 中的表达式无需创建新的堆栈结构。

在list comprehension获得成功，在发明generator(关于generator，将来会在另外一篇展开)之后，Python 2.4 增加了一种近似的语法用以表示结果构成的序列(sequence)，但是并不将它具体化(concrete)为一个实际的list。新特征称作 "generator expression"。例如：

sum(x**2 for x in range(1, 11))

这条语句调用内置函数 sum()，参数为一个generator expression, 它 yield 从1到10(包括10)的平方。 sum() 函数把参数中的值加和起来，得到答案385。该语句相对于 sum([x**2 for x in range(1, 11)]) 的优势应当是明显的。后者生成了一个包含所有平方数的list，然后再遍历一次，最后(得到结果后)丢弃该list。对于数量较大的数据，前者在内存方面的节省是一个重要考虑因素。

我还应该提到 list comprehension 和 generator expression 微妙的区别。例如，在Python 2，如下是一个有效的 list comprehension：

[x**2 for x in 1, 2, 3]

然而，这是一个无效的 generator expression：

(x**2 for x in 1, 2, 3)

我们可以通过给"1, 2, 3"部分添加括号来修复它：

(x**2 for x in (1, 2, 3))

在Python 3，你甚至对list comprehension也必须使用括号了：

[x**2 for x in (1, 2, 3)]

然而，对于"常规的"或者"显式的"for-循环，你仍然可以省略括号：

for x in 1, 2, 3: print(x**2)

为何有这种区别，而且为何在Python 3 对 list comprehension 变得更严格了？影响设计包括反向兼容，避免歧义，注重等效，和语言的进化等因素。最初，Python(还没有版本号的时候:-)只有明确的for-循环形式。在'in'之后的部分不会带来歧义，因为它总是最后伴随着一个冒号。我清楚你要做的是对一些已知数值进行循环，因此，你不需要因为必须增加括号而烦恼。写到这里，又让我想起来在Algol-60，你可以这样写：

for i := 1, 2, 3 do Statement

Algol-60 还额外支持利用step-until从句决定表达式的步长，如下:

for i := 1 step 1 until 10, 12 step 2 until 50, 55 step 5 until 100 do Statement

(追忆往事，如果当初Python的foo-循环也能这样支持对多个序列的遍历，也挺酷的，哎。。。)

当我们在Python 2.0 中增加 list comprehension 时，原来的规则依然有效：序列表达式只可能被伴随的右中括号 ']' 或者 'for' 关键词或者 'if' 关键词结束。而且这是好事。

但是，到了 Python 2.4 增加 generator expression 时，我们遇到了歧义性方面的问题: 语法上看一个 generator expression 的括号部分并不是它语法上必须的部分。例如下面例子：

sum(x**2 for x in range(10))

外括号是属于被调用的函数sum()的一部分，里面的 "裸" generator expression 作为第一个参数。因此理论上，如下语句可以有两种解释：

sum(x**2 for x in a, b)

可以有意解释为这样:

sum(x**2 for x in (a, b))

也可以解释为:

sum((x**2 for x in a), b)

(如果我没记错)犹豫了一阵子之后，我决定这种情况不应该猜测，而是 generator comprehension 的 'in' 关键词之后必须是单个表达式(当然，它是 iterable 的)。但是当时我们也不想破坏已存在于 list comprehension 中的代码，因为它已经广为流行了。

设计 Python 3 时，我们决定 list comprehension:

[f(x) for x in S if P(x)]

完全等价于如下利用内置函数 list() 展开的 generator expression:

list(f(x) for x in S if P(x))

于是我们将稍微更严格的 generator expression 语法也同样适用于 list comprehension。

在 Python 3 我们还做了另外的变动，以增加 list comprehension 和 generator expression 的等效程度。Python 2时，list comprehension 会"泄露" 循环控制变量到外边：

x = 'before'
a = [x for x in 1, 2, 3]
print x # this prints '3', not 'before'

这是最初的 list comprehension 实现造成现象；也是数年间 Python 的"肮脏的小秘密"之一。开始由于这样可以使得 list comprehension 性能"越快越好"而作为折衷保留了，虽然偶然会刺痛人毕竟对新手来说算不上常见缺陷。然而对于 generator expression 我们不会再这样做了。 Generator expression 利用 generator 实现，执行 generator 时需要一个隔离的执行帧(separate execution frame)。由此还使得 generator expression (特别是在遍历比较短的序列时) 比 list comprehension 效率略低。

然而到了 Python 3，我们决心利用和 generator expression 的同样实现策略来修缮这个 list comprehension 的 "肮脏的小秘密"。 于是在 Python 3，上例(当然，最后一句修改为 print(x) :-) 将会打印 'before', 这证明 list comprehension 中的'x'只是暂时遮蔽而不是直接使用 list comprehension 之外的'x'。

在你开始担心 list comprehension 在 Python 3 中变慢之前要说的是：感谢大量的 Python 3 实现方面的努力，list comprehension 和 generator expressions 都比 Python 2 中更快了！(而且两者也不再有速度上的差别。)

更新: 当然，我忘了说 Python 3 还支持 set comprehension 和 dictionary comprehension。这是 list comprehension 思路的自然推广。

Method Resolution Order

Method Resolution Order

英文原文链接: http://python-history.blogspot.com/2010/06/method-resolution-order.html
原文作者: Guido van Rossum

方法解析顺序

在支持多重继承的编程语言中，查找方法具体来自那个类时的基类搜索顺序通常被称为方法解析顺序(Method Resolution Order)，简称MRO。(Python中查找其它属性也遵循同一规则。)对于只支持单重继承的语言，MRO十分简单；但是当考虑多重继承的情况时，MRO算法的选择非常微妙。Python先后出现三种不同的MRO：经典方式、Python2.2 新式算法、Python2.3 新式算法(也称作C3)。Python 3中只保留了最后一种，即C3算法。

经典类采用了一种简单MRO机制：查找一个方法时，搜索基类简单的深度优先从左到右。搜索过程中第一个匹配的对象作为返回结果。例如，考虑如下类：

class A:
 def save(self): pass

class B(A): pass

class C:
 def save(self): pass

class D(B, C): pass

对于类D的实例x，它的经典MRO结果是类D，B，A，C顺序。因此查找方法x.save()将会得到A.save()(而不是C.save())。这个机制对于简单情况工作良好，但是对于更复杂的多重继承关系，暴露出的问题就比较明显了。其中问题之一是关于"菱形继承"时的方法查找顺序。例如：

class A:
  def save(self): pass

class B(A): pass

class C(A):
  def save(self): pass

class D(B, C): pass

此处类D继承自类B和类C，类B和类C均继承自类A。应用传统的MRO，查找方法时在类中的搜索顺序是D, B, A, C, A。因此，语句x.save()将会如前一样调用A.save()。然而，这可能非你所需！既然B和C都从A继承，别人可以争辩说重新定义的方法C.save()可以被看做是比类A中的方法"更具体"(实际上，有可能C.save()会调用A.save())，所以C.save()才是你应该调用的。如果save方法是用于保持对象的状态，不调用C.save()将使C的状态被丢弃，进而程序出错。

虽然当时的Python代码很少存在这种多重继承代码，"新类"(new-style class)的出现则使之成为常见现象。这是由于所有的新类都继承自object这一基类。因此涉及到新类的多重继承总是会产生前面所述的菱形关系。例如：

class B(object): pass

class C(object):
  def __setattr__(self, name, value): pass

class D(B, C): pass

而且，object定义了一些方法(例如__setattr__())可以由子类扩展，这时解析顺序更是至关重要。上面代码所属例子中，方法C.__setattr__应当被应用到类D的实例。

为了解决在Python2.2引入的新类所带来的方法解析顺序问题，我采取的方案是在类定义时就计算出它的MRO，并存储为该类对象的一个属性。官方文档中MRO的计算方法为：深度优先，从左到右遍历基类，这个与经典MRO一致，但是如果任何类在搜索中是重复的，只有最后一个出现的位置被保留，其余会从MRO list中删除。因此我们前面这个例子中，搜索顺序将会是D, B, C, A(经典类采用经典MRO，则会是D, B, A, C, A)。

实际上MRO的计算比文档所说的要更复杂。我发现某些情况下新的MRO算法结果不理想。因此还存在一个特例，用于处理两个基类在两个不同的派生类中顺序不同，而这两个派生类又被另外一个类继承的情况。如下代码所示：

class A(object): pass
class B(object): pass
class X(A, B): pass
class Y(B, A): pass
class Z(X, Y): pass

利用文档中描述的新MRO算法，Z关于这些类的MRO为Z, X, Y, B, A, object。(这儿的object是通用基类。)。然而，我不希望结果中B出现在A之前。因此实际的MRO会交换其顺序，产生Z, X, Y, A, B, object。直观上说，算法尝试保持基类在搜索时过程中首次出现的顺寻。例如，对于类Z，他们基类X应当被首先搜索到，因为在继承的list中排序最靠前。既然X继承自A和B，MRO算法会尝试保持其顺寻。这是在我在Python2.2中实际实现的算法，但是文档只提到了前面的不包括特例处理的算法(我幼稚的认为这点小差别不需明言。)。

然而，就在Python 2.2 引入新类不久，Samuele Pedroni就发现了文档中MRO算法与实际代码中观察到结果不一致的现象。而且，在上述特例之外也可能发生不一致情况。详细讨论的结果认为Python2.2采用的MRO是坏的，Python应当采用C3线性化算法，该算法详情见论文"A Monotonic Superclass Linearization for Dylan"(K. Barrett, et al, presented at OOPSLA'96)。

本质上，Python 2.2 MRO的主要问题在于不能保持单调性(monotonicity)。在一个复杂的多层次继承情况，每个继承关系都决定了一个直接的查找顺序，如果类A继承类B，则MRO明显应当先查找A后查找B。类似，如果类B多重继承类C和类D，则搜索顺序中类B应该在类C之前，且类C应该在类D之前。

在复杂的多层次继承情况，始终能满足这一规则就称为保持了单调性。也就是说，当你决定类A会在类B之前查找到，应当再也不会遇到类B需要在类A之前查找的情况(否则，结果是未定义的，应该拒绝这种情况下的多层次继承)。以前的MRO算法未能做到这一点，新的C3算法则在保证单调性方面发挥了效用。基本上，C3的目的在于让你依据复杂多层次继承中所有的继承关系进行排序，如果所有顺序关系都能满足，则排序结果就满足单调性。否则，无法得到确定的顺序，算法会报错，拒绝运行。

于是，在Python 2.3，摈弃了我手工作坊的 2.2 MRO算法，改为采用经过学术审核检验的C3算法。带来的结果之一就是当多层次继承中存在基类顺序不一致情况时，Python将会拒绝这种类继承。还是参加前面例子，对于类X和类Y就存在顺序上不一致，对于类X，规则判定类A应该在类B之前被检查。然而对于类Y，规则认为类B应该在类A之前被检查。单独情况下，这种不一致是可以接受的，但是如果X和Y共同作为另外一个类(例中定义的类Z)的基类，C3算法就会拒绝这种继承关系。这个也算是对应了Zen of Python的"errors should never pass silently"规则。

import antigravity

英文原文链接: http://python-history.blogspot.com/2010/06/import-antigravity.html
原文作者: Guido van Rossum

反重力(antigravity)模块源自一幅XKCD漫画，由Skip Montanaro 添加至Python 3中。进一步的详情可以参考如下链接，这是我所知道最早提及此事的出处: http://sciyoshi.com/blog/2008/dec/30/import-antigravity/


但是反重力(antigravity)模块实际起源于更早时候的Google App Engine!App Engine于2008年4月7号发布，反重力(antigravity)模块在临近发布前才添加进来。在距离发布前几周时间，App Engine大多数代码已经冻结，Google的App Engine项目组认为我们应对添加一个复活节彩蛋，当时征集到许多提案，有的过于复杂，有的难于理解，还有些则存在危险性，最后我们选择了“反重力(antigravity)”模块。App Engine的反重力(antigravity)模块比Python3中的对应实现稍微多了一点变化。它定义了一个fly函数可以随机的做如下两件事情之一：有10%的可能重定向到XKCD的反重力(antigravity)漫画；另外90%的可能则是简单的把漫画中的文字显示在HTML页面中(最后一行有漫画链接地址)。要在App Engine的应用中调用反重力(antigravity)模块，需要如下简单代码:

import antigravity

def main():
  antigravity.fly()

if __name__ == '__main__':
  main()

更新: Python 3 标准库中的反重力模块还有一个彩蛋中的彩蛋，如果你查看源码会发现它定义了一个实现XKCD 中 GEO 哈希算法(geohashing)的函数.

import this and The Zen of Python

英文原文链接: http://python-history.blogspot.com/2010/06/import-this-and-zen-of-python.html

原文作者: Guido van Rossum

Barry Warsaw 撰写了一篇关于import this和the Zen of Python的有趣博文，我希望更多人关注Python history上由于年代久远而变得晦暗的这一段： http://www.wefearchange.org/2010/06/import-this-and-zen-of-python.html 。