延迟计算: 关于 Python 的 yield

在 SICP 第 3 章中，有一段部分内容是以 stream 为核心而展开的。而 stream 的特点就是 lazy evaluation / delayed evaluation （惰性求值 / 延迟计算）。在接触 stream 之时，我便立即联想到 Python 具有类似的功能 — yield。

yield 的意义

使用 yield 的目的是为了生成器，而使用生成器的一个特点是每次只向你返回一个结果。基于这个特点，生成器可以产生的结果数量甚至可以是无限的。因此，生成器在用于表示一些 list 不便或无法表示的超多元素的集合时将表现出很好的便捷性。

例如:

In [68]: def fib():
   ....:     former, latter = 0, 1
   ....:     yield former
   ....:     yield latter
   ....:     while True:
   ....:         former, latter = latter, latter + former
   ....:         yield latter

In [69]: select = lambda x :x and x % 1377 == 0

In [70]: for i, item in enumerate(fib()):
   ....:     if select(item):
   ....:         print(i, item)
   ....:         break

在这里，我先定义了一个生成器函数 fib，用于生成 fibonacci 数列，以及另一个普通函数 select，用于筛选出能被 1377 整除的数。接着用一个循环找出第一个满足 select 的条件的数。在这里，使用生成器的好处是你不需要实现估计需要计算多少个 fibonacci 数列中的元素。因为 fib() 可以产生第无穷个 fibonacci 数列中的元素，加入你换成一个 list：

In [70]: for i, item in enumerate(fib_lst):
   ....:     if select(item):
   ....:         print(i, item)
   ....:         break

这里就有一个明显的顾虑：fib_lst 中应该放多少个元素？放 100 个够不够？1000 个呢？10000 个呢？

假使你运气好，发现对于例子中 select 函数， 1000 个够了，但如果更改 select 为 lambda x: x and x % 3119 == 0。那么 1000 个还会够么。可能需要 10000 个。同时，你每次生成 10000 个甚至 1000000 个元素的列表，那么生成和保存一个如此大的列表在时间上和空间上会使巨大的浪费。而相比于此，生成器没有保存所有元素，因此至少在空间上有极大的便利。

Q：不用生成器，不也有办法达到类似的效果么？

或许有人会举出这么一个反例，既然 fib() 函数产生的生成器只是每次临时计算而已，那不用列表或生成器不也有办法可以很方便么？例如:

In [63]: former, latter = 0, 1

In [64]: i = 2

In [65]: while True:
   ....:     former, latter = latter, former + latter
   ....:     if select(latter):
   ....:         print(i, latter)
   ....:         break
   ....:     i += 1

虽然这个方法也可以，但是仔细想想，这个方法的可读性和可移植性说不上很好。一个原因是在进行 select 的代码中糅合了 fibonacci 数列元素计算的过程，使得逻辑上分离的两个部分连在了一起。另一个原因是，生成器将 fibonacci 数列的元素进行了封装，那么在其他模块中也只需要用 fib() 即可调用；而在这个方法中，每一次计算 fibonacci 数列都需要重新写一遍计算的代码，欠缺方便。

写法优化

在上例中，我用一个简单的循环求得了第一个满足要求的元素。而在 Python 中，大多简单的循环又可以写成类似列表表达式的方式，而上一个例子也是如此。

In [74]: next((i, item) for i, item in enumerate(fib()) if select(item))

在这里，(i, item) for i, item in enumerate(fib()) if select(item) 本身代表了一个生成器表达式

In [77]: ((i, item) for i, item in enumerate(fib()) if select(item))
Out[77]: <generator object <genexpr> at 0x104674258>

In [78]: gen = ((i, item) for i, item in enumerate(fib()) if select(item))

In [79]: next(gen)
Out[79]:
(1316,
 47670484598039529967308137755285220283067857159635666308572483292852087741971817495430736032322993914141991666526048221816855193212853932963317951773586445466676607895893764927922577383975888691399916203755485478472365658305444586740978034474331219811230599774368887776557837)

In [80]: next(gen)
Out[80]:
(2632,
 5081408804827217679483690811505190320468896152614650981083661467793773636093281628433780640132913496539149358258875736128851767346736337537150191351612842042674073125589815465376413058371692145091298387648676549040287922078680500401041910184918357118604215905739580720823641807065276860800035024575275858699179043965222324466320661415297713837965844699076750589037980732572303226178214876864049241381018710405651898072419680038625628403496847878874630005198585018290768191523976457263007140359513843497547268641482458809531359561789398938836874997259)

如代码所示，这个表达式可以用于一直求下一个满足要求的数子，也可以认为是求第无限个满足要求的数字。这样的写法也与上面的例子的类似的道理，要用的时候再计算，要多少算多少。避免一次性算太多而带来的在时间上的延迟和内存上的紧张。

yield 的暂停

尽管在 yield 的帮助下可以产生近似无限长的列表，但这也并不是说生成器可以一直下去: 在有些情况下，我们还是希望 yield 能在某个条件下停下。而如果在生成器函数中使用了 return，那么 return 即意味这暂停。

例如，我们在每次做一次数学测试，一直生成随机数，直至满足某个条件为止。

In [81]: def random_test(select, start, end):
   ....:     while True:
   ....:         t = random.randint(start, end)
   ....:         if select(t):
   ....:             return
   ....:         else:
   ....:             yield t

In [82]: r = random_test(lambda x : x < 100, 0, 1000)

In [83]: for i, item in enumerate(r):
   ....:     print(i, item)

只要不满足 select 条件，这个测试也会一直进行下去，无论是进行多少次，不管是 100 次，还是 1000 次。

return 的在生成器中的含义

return 在生成器中表达的含义就是”一切已经结束了，没有更有趣的元素要返回了”

基于这个含义，如果在 return 后跟上一个返回值的话，那么这个返回值是不会被返回的。

In [84]: def return_test():
   ....:     return "Will I be returned?"
   ....:     yield "I know I will never be returned"

In [85]: r = return_test()

In [86]: next(r)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-86-0b5056469c9c> in <module>()
----> 1 next(r)

StopIteration: Will I be returned?

由此可见，执行 return 的时候，生成器就会停止，抛出 StopIteration 表示停止，不会再返回任何返回值。

return 等于 StopIteration ?

既然在上例中，执行 return 就会抛出 StopIteration 异常，那么在生成器函数中，是不是就意味着，StopIteration 是由 return 抛出的呢?

In [87]: def catch_stop():
   ....:     try:
   ....:         return
   ....:     except:
   ....:         yield "I catch it"

In [88]: c = catch_stop()

In [89]: next(c)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-89-73b012f9653f> in <module>()
----> 1 next(c)

StopIteration:

由代码可见，StopIteration 并没有被捕获，这说明 StopIteration 是在另一个地方抛出的。而至于是在哪里抛出的，目前据我了解，这可能涉及到 Python 底层解释器的实现，我尚不十分了解。

关于生成器函数的实现

生成器函数的实现一个重要点就是它保存了每次运行时的环境信息以及下一次的起点。对于普通函数，每一次运行的起点无疑都是从函数的最开头。而对于生成器函数，除了第一次运行的起点是在函数最开头， 每一次运行的起点都是上一次运行结束的终点。

另外虽然生成器函数保存了环境信息，但这并不说它保存了环境中每个变量的值。

n [105]: N = 0

In [106]: def test_sum():
   .....:     i = 0
   .....:     while True:
   .....:         yield N + i
   .....:         i += 1

In [107]: t = test_sum()

In [108]: next(t)
Out[108]: 0

In [109]: next(t)
Out[109]: 1

In [110]: N = 100

In [111]: next(t)
Out[111]: 102

由代码可见，生成器函数保存了环境变量中 N 的存在，但并没有在产生生成器时就将 N 的值定了下来，而仍是每次运行 next 时对其重新求值。

一些猜测

联想到 SICP 中对 stream 的实现，那么 Python 可能也有类似的做法，即将一个元素包装在函数里。
假如不做延时计算:

In [113]: ["how long will it be?", time.sleep(1), time.sleep(2)]
Out[113]: ['how long will it be?', None, None] # 3 seconds

这个输出将在 3 秒后输出，但如果讲每个元素包装在函数里:

In [114]: lst = [lambda: "how long will it be?",lambda: time.sleep(1),lambda: ti
   .....: me.sleep(2)]

In [115]: for item in lst:
   .....:     print(item())
how long will it be?
None # 1 second
None # 2 seconds

通过这个方法，每个元素也是在调用是才会被求值，因此我猜测 Python 在实现上可能有类似的做法。但具体是怎么做的，这是一个我接下来需要研究的话题。

后记

如果对 yield 想要更多的了解，建议查看 PEP 255 – Simple Generators, 其中更进一步的探讨了为什么要引入新的关键字 yield，而不是将其设置为一个内建函数，以及为什么不引入一个新的关键字代替 def 来更清楚地表示某个函数是生成器函数等等。

参考

1. PEP 255 – Simple Generators
2. Python and lazy evaluation