神奇的yield

We find two main senses for the verb "to yield" in dictionaries: to produce or to give way.

Luciano Ramalho 在他的《Fluent Python》協程一節中如是寫道。yield 是一個在很多語言中都有的關鍵字和特性，和它有關的種種概念——生成器，協程……可能讓人費解，但一旦真正理解了它們的含義，一扇新的大門將為我們展開。

代替遞歸

很多時候，生成器可以用來代替遞歸。眾所周知，遞歸實現的演算法簡潔，優雅，但對於Python來說，性能很差，而且還有遞歸深度限制。當然我們可以把某些遞歸改寫成循環和迭代的形式，但生成器可以幫助我們寫出既優雅又高性能的代碼。

我們先來個簡單的例子——生成斐波那契數列。

def fib_rec(n): if n==0 or n==1: return 1 else: return fib_rec(n-2) + fib_rec(n-1)def fib_gen(): before2 = 0 #原諒變數名起的渣 before1 = 1 while True: now = before2 + before1 yield now before2, before1 = before1 , now

這個例子很簡單，而且好像生成器版本的代碼也不怎麼優雅和易讀，但是理解了程序流就會覺得很好理解。

開胃小菜過後，我們來道可口的。

David Beazley 在他的《Python Cookbook（第三版）》中的一節中介紹了如何使用生成器來改寫訪問者類的遞歸版本。讓人拍案。

首先我們看一下改寫的基礎代碼

import typesclass Node: passclass NodeVisitor: def visit(self, node): stack = [node] last_result = None while stack: try: last = stack[-1] if isinstance(last, types.GeneratorType): stack.append(last.send(last_result)) last_result = None elif isinstance(last, Node): stack.append(self._visit(stack.pop())) else: last_result = stack.pop() except StopIteration: stack.pop() return last_result def _visit(self, node): methname = "visit_" + type(node).__name__ meth = getattr(self, methname, None) if meth is None: meth = self.generic_visit return meth(node) def generic_visit(self, node): raise RuntimeError("No {} method".format("visit_" + type(node).__name__))

遞歸的調用

class UnaryOperator(Node): def __init__(self, operand): self.operand = operandclass BinaryOperator(Node): def __init__(self, left, right): self.left = left self.right = rightclass Add(BinaryOperator): passclass Sub(BinaryOperator): passclass Mul(BinaryOperator): passclass Div(BinaryOperator): passclass Negate(UnaryOperator): passclass Number(Node): def __init__(self, value): self.value = value# A sample visitor class that evaluates expressionsclass Evaluator(NodeVisitor): def visit_Number(self, node): return node.value def visit_Add(self, node): return self.visit(node.left) + self.visit(node.right) def visit_Sub(self, node): return self.visit(node.left) - self.visit(node.right) def visit_Mul(self, node): return self.visit(node.left) * self.visit(node.right) def visit_Div(self, node): return self.visit(node.left) / self.visit(node.right) def visit_Negate(self, node): return -self.visit(node.operand)if __name__ == "__main__": # 1 + 2*(3-4) / 5 t1 = Sub(Number(3), Number(4)) t2 = Mul(Number(2), t1) t3 = Div(t2, Number(5)) t4 = Add(Number(1), t3) # Evaluate it e = Evaluator() print(e.visit(t4)) # Outputs 0.6

一旦嵌套過深，就會出現問題

>>> a = Number(0)>>> for n in range(1, 100000):... a = Add(a, Number(n))...>>> e = Evaluator()>>> e.visit(a)Traceback (most recent call last):... File "visitor.py", line 29, in _visitreturn meth(node) File "visitor.py", line 67, in visit_Addreturn self.visit(node.left) + self.visit(node.right)RuntimeError: maximum recursion depth exceeded>>>

而我們用生成器的方式來調用，一切又都可以運行了

class Evaluator(NodeVisitor): def visit_Number(self, node): return node.value def visit_Add(self, node): yield (yield node.left) + (yield node.right) def visit_Sub(self, node): yield (yield node.left) - (yield node.right) def visit_Mul(self, node): yield (yield node.left) * (yield node.right) def visit_Div(self, node): yield (yield node.left) / (yield node.right) def visit_Negate(self, node): yield - (yield node.operand)

>>> a = Number(0)>>> for n in range(1,100000):... a = Add(a, Number(n))...>>> e = Evaluator()>>> e.visit(a)4999950000>>>

神奇嗎？僅僅是將return換成了yield，就能有如此巨大的改變。

我們來梳理一下代碼。顯然，重要的地方是第一段中NodeVisitor的定義。他用一個stack來保存程序計算中的數據結構，一開始，這裡保存的是一個node的實例——t4。然後調用evaluator的visit方法，取出棧頂元素——此時是t4——保存在last中。判斷它是一個Node的實例，再對其調用evaluator的_visit方法，同時把它從棧中彈出。而_visit 方法基本就是一個典型的訪問者的設計模式的實現。然後，我們又看到，在後幾段代碼中，evaluator的visit_xxx方法的實現中將return換成了yield，這意味著，它將返回一個生成器——而不是和前面的實現中遞歸地調用。這個生成器被追加到了stack中。這時，Nodevisitor又檢查棧頂元素，是生成器，調用其send方法，參數是last_result（此時值是None）。根據evaluator的定義，它又將返回一個Node的實例，然後再把它轉換為一個生成器，或者如果是一個特定的子類（這裡是Number）的話，直接返回值，如此循環往複。要注意的是，如果直接返回了值，說明已經產生了一個結果，這時將它賦值給last_result（原來的值是None的哦），再由evaluator將其通過send方法傳給上一個層次的生成器，如此來實現結果的傳遞。直至最後計算出一個總的結果，返回。

思想是什麼呢？原先嵌套的調用（遞歸）是由python解釋器來處理的。現在，我們將每一次分解轉化為一個生成器保存在棧中，每次檢查棧頂元素的類型來決定執行什麼操作。如果是一個Node的實例，就再將其轉化為生成器，或者，直接返回值。如果是數值，將其保存在last_result中，將其從棧中彈出。如果是一個生成器，調用它的send方法，參數是last_result。這樣，原本面對很深的嵌套，我們可能會需要遞歸地調用很多次才能真正返回一個值。而現在，yield將執行權再次交還給了evaluator，告訴它先計算第一個節點，出結果之後，再計算下一個——恰好和遞歸的執行順序相反（雖然代碼極其相似）。而生成器依然保存著執行狀態，隨時等待調用。自然遞歸深度限制也就不會再有。

我們再來看看這個例子是如何將生成器的特性發揮的淋漓盡致的。

其實，我們已經不能把它叫成是單純的生成器，它還用到了協程的概念。首先，就像我們開頭說的，yield有兩個意思——to produce or to give way 。

yield (yield node.left) + (yield node.right)

這一句中的yield將node返回，既是produce 也是 give way，執行權交還給了evaluator，那evaluator怎麼將結果傳遞給生成器呢？這就是send方法的作用。send方法的參數就是生成器中yield生成的值，這句話好像有點難理解，就是說，生成器恢復執行之後，原先的yield產生的值就是send傳入的參數。而生成器會執行到下一個yield處，或者raise StopIteration。這時的生成器又會產生一個值，這個值哪了呢？它就是調用send方法後返回的值。所以我們才說還用到了協程的概念，事實上，協程的邏輯和這裡基本相同。

狀態機

ES6向Python借鑒了列表推導的語法糖，同時，它還添加了生成器的新特性（當然不是從Python中借鑒的）。

在阮一峰的《ES6標準入門》中，他介紹了使用生成器來定義狀態機，用yield來劃分不同狀態的技巧。我在Python書籍和社區中沒有見過（可能是我孤陋寡聞）。但仔細一想，python的標準庫中就有類似的用法——contextlib.contextmanager

它的用法就是使用yield來劃分代碼，之前的相當於上下文管理器的__enter__()，之後的相當於__exit__()。我們也可將其看作是一個狀態機，只不過控制它的是python解釋器。

協程

本想仔細說一說協程，但其基本邏輯前面已提到，而asyncio，async/await，又是一大篇文章。就不多說了。

最後

前面說的幾個例子，其實也就是用了關於yield的那幾個特性，只是要有想像力來充分的利用。希望我們都能讓它們變成改善代碼的好幫手。