迭代器生成器与解释器

for x in range(10**9) 不会先造出十亿个整数，for line in open('huge.log') 也不会把整个文件读进内存。for 怎么知道”下一个”是什么，又怎么知道该停了？这一篇先拆开 for 循环，看到迭代器和生成器，理解”需要时才计算”的惰性求值。然后再拆一层更大的东西：用不到 80 行 Python 写一个 Scheme 解释器，看一门语言本身是怎么跑起来的。前三篇的环境模型、闭包、递归，到这里会全部变成代码。

前置：函数与环境模型、高阶函数与递归、数据抽象与对象

拆开 for 循环：迭代器协议

先手动做 for 做的事：

s = [10, 20, 30]
it = iter(s)
print(next(it), next(it), next(it))
try: next(it)
except StopIteration: print('StopIteration')
it = iter(s)
print(next(it), list(it), list(it))

10 20 30
StopIteration
10 [20, 30] []

iter(s) 从列表得到一个迭代器（iterator），它是一个记住”走到哪了”的对象。每次 next(it) 返回下一个元素并前进一步；没有元素时抛出 StopIteration。第二段说明迭代器是一次性的：next 取走 10，list(it) 取走剩下的 20、30，再 list(it) 就是空的，因为位置已经到了末尾。

这就是 for x in s: body 的全部真相，它等价于：

it = iter(s)
while True:
    try:
        x = next(it)
    except StopIteration:
        break
    body

这里有两个角色要分清：

• 可迭代对象（iterable）：能被 iter() 调用、返回一个迭代器的东西。列表、字符串、字典、range 都是。它本身不记位置，可以反复遍历。
• 迭代器（iterator）：有 __next__ 方法、记着位置的东西。它的 __iter__ 返回自己，所以迭代器也是可迭代对象，但只能走一遍。

这又是上一篇的特殊方法：iter(x) 调用 x.__iter__()，next(it) 调用 it.__next__()。自己实现一个迭代器类：

class Countdown:
    def __init__(self, start): self.cur = start
    def __iter__(self): return self
    def __next__(self):
        if self.cur <= 0: raise StopIteration
        self.cur -= 1
        return self.cur + 1
print(list(Countdown(3)))

[3, 2, 1]

任何定义了这两个方法的对象都能放进 for、list()、sum()、zip()。这就是协议（protocol）的力量：for 不关心你是列表、文件还是网络流，只要会回答”下一个是什么”。

停一下，检查理解单选

it = iter([1, 2, 3])，执行 a = list(it) 再执行 b = list(it)，b 是什么？

[1, 2, 3]，因为 list() 会从头重新遍历[]，因为迭代器已经走到末尾，不会自己回到开头抛出 StopIteration[3]

检查答案

生成器：让函数暂停

写 Countdown 要手动维护 self.cur，要写 raise StopIteration，状态分散在三个方法里。同样的东西用**生成器函数（generator function）**写只要几行：

def countdown(n):
    print('start')
    while n > 0:
        yield n
        n -= 1
g = countdown(3)
print(type(g).__name__)
print(next(g)); print(next(g))
print(list(g))

generator
start
3
2
[1]

函数体里只要出现 yield，调用它就不执行函数体，而是返回一个生成器对象。注意 start 是在第一次 next(g) 时才打印的，不是在 countdown(3) 时。之后：

• 每次 next(g)，函数体从上次停下的地方继续执行，直到遇到下一个 yield，把 yield 后面的值交出去，然后暂停。
• 函数体执行到末尾（或 return），生成器抛出 StopIteration。

用环境模型看：普通函数返回后，它的帧就用完了；生成器的帧在两次 next 之间被冻结保留，局部变量 n 和”执行到第几行”都还在。原来要写在 self.cur 里的状态，现在就是普通的局部变量，控制流就是普通的 while。生成器是写迭代器最省事的方法。

yield from 把另一个可迭代对象的元素逐个转交出去，适合递归结构：

def flatten(t):
    for x in t:
        if isinstance(x, list): yield from flatten(x)
        else: yield x
print(list(flatten([1, [2, [3, 4]], 5])))

[1, 2, 3, 4, 5]

每一层递归都是一个生成器，yield from 把内层产出的值原样传到外层。代码结构仍然是第二篇的递归模板：遇到子列表就递归，遇到元素就交出去。

停一下，检查理解单选

def gen(): print('A'); yield 1; print('B'); yield 2。执行 g = gen() 和一次 next(g) 后，屏幕上打印了什么？

什么都没有，打印要等到生成器耗尽只有 AA 和 B调用 gen() 时打印 A，next(g) 时打印 B

检查答案

惰性求值：需要时才计算

生成器只在被要求时才算下一个值，这叫惰性求值（lazy evaluation）。它带来两个直接的好处。

第一是省内存：

import sys
print(sys.getsizeof([x for x in range(10**6)]), sys.getsizeof(x for x in range(10**6)))

8448728 112

列表推导式立即造出一百万个元素，8 MB；把方括号换成圆括号得到生成器表达式，它只是一个 112 字节的对象，记着”怎么算下一个”。处理大文件、数据流时，这个区别决定了程序能不能跑起来。

第二是可以表示无限序列：

def naturals():
    n = 0
    while True:
        yield n; n += 1
def take(k, it):
    return [x for _, x in zip(range(k), it)]
evens_sq = (x * x for x in naturals() if x % 2 == 0)
print(take(5, evens_sq))

[0, 4, 16, 36, 64]

naturals() 永远不会结束，如果是列表根本造不出来。但 evens_sq 只是在它上面叠了一层”过滤 + 平方”的描述，take 要五个，它就只从 naturals 拉够需要的数。整条管道从下游往上游按需拉取。

内置的 map、filter、zip 在 Python 3 里返回的也是惰性迭代器：

m = map(lambda x: print('compute', x) or x * 10, [1, 2, 3])
print('map created')
print(next(m))

map created
compute 1
10

map 创建时一个元素也没算，next 时才算第一个。这里的 print(...) or x * 10 借用了第一篇讲的短路：print 返回 None（假），于是 or 返回右边的值。

把惰性流推到极致，可以写出一个”无限质数流”：

def primes():
    def sieve(s):
        p = next(s)
        yield p
        yield from sieve(x for x in s if x % p != 0)
    yield from sieve(n for n in naturals() if n >= 2)
print(take(10, primes()))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

每找到一个质数 p，就在剩下的流上再套一层”去掉 p 的倍数”的过滤。这是埃拉托斯特尼筛法的惰性版本，代码几乎就是算法的定义。代价是每个质数多一层生成器嵌套和递归，第几百个质数时就会碰到递归上限，所以它是一个展示思想的例子，不是高效实现。

惰性也有代价：迭代器只能走一遍；值是在被拉取的那一刻才算的，如果计算依赖会变的外部状态，结果取决于何时拉取。

停一下，检查理解多选

关于 g = (x * x for x in range(10**9))，下面哪些说法正确？

创建 g 几乎不花时间和内存next(g) 返回 0，再次 next(g) 返回 1len(g) 返回 10**9sum(g) 之后再 sum(g) 会得到同样的结果

检查答案

一门语言需要什么：Scheme 子集

现在换一个更大的问题：Python 本身是怎么”运行”一段代码的？与其去读 CPython 的几十万行 C，不如自己写一门小语言的解释器。CS61A 选的是 Scheme，Lisp 家族的一员。它的语法简单到几乎没有语法：

(+ 1 (* 2 3))                              ; 调用表达式：(操作符 操作数 ...)
(define square (lambda (x) (* x x)))       ; 绑定名字
(if (= n 0) 1 (* n (fact (- n 1))))        ; 条件

所有东西都是括号包起来的表达式，第一个元素是操作符，后面是操作数。(+ 1 (* 2 3)) 就是 Python 的 add(1, mul(2, 3))。这一点让 Scheme 成了写解释器的理想对象：程序的文本形式本身就是一棵树，几乎不需要处理优先级、缩进、关键字。

我们要支持的子集只有四种东西：

• 整数和名字（原始表达式）
• (define 名字 表达式)：在当前帧绑定
• (if 条件 then else)：条件分支
• (lambda (形参 ...) 函数体)：创建函数
• 其他所有括号表达式都是调用

够不够？lambda 带来函数，if 带来分支，函数可以调用自己带来循环（递归），闭包带来数据（第三篇用闭包表示了分数）。这几样凑起来已经是一门图灵完备的语言。

解释器的工作分两步：parse（把文本变成树）和 eval（对树求值）。

parse：从文本到树

第一步分词（tokenize），把字符串切成记号；第二步解析（parse），按括号把记号组装成嵌套列表：

def tokenize(src):
    return src.replace('(', ' ( ').replace(')', ' ) ').split()
 
def parse(tokens):
    tok = tokens.pop(0)
    if tok == '(':
        expr = []
        while tokens[0] != ')':
            expr.append(parse(tokens))
        tokens.pop(0)
        return expr
    try:
        return int(tok)
    except ValueError:
        return tok

print(tokenize('(+ 1 (* 2 3))'))
print(parse(tokenize('(+ 1 (* 2 3))')))

['(', '+', '1', '(', '*', '2', '3', ')', ')']
['+', 1, ['*', 2, 3]]

parse 是一个递归下降解析器：读到 ( 就开一个新列表，反复递归解析里面的子表达式直到遇到对应的 )；读到别的就是一个原子，能转成整数的转整数，否则当作名字（字符串）。嵌套的括号自然变成嵌套的列表，数据的递归结构和函数的递归结构又一次一一对应。

parse 之后，程序就变成了一个普通的 Python 数据结构。接下来的 eval 只和这个树打交道，不再关心原始文本长什么样。

eval 与 apply：两个互相递归的函数

求值器需要环境。照搬第一篇的模型：帧是一张表加一个父帧指针，查找沿父帧向上。用户定义的函数要记住定义时的环境：

class Frame:
    def __init__(self, bindings, parent):
        self.bindings, self.parent = bindings, parent
    def lookup(self, name):
        f = self
        while f is not None:
            if name in f.bindings:
                return f.bindings[name]
            f = f.parent
        raise NameError(name)
 
class Lambda:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env

Lambda 对象就是 Composing Programs 环境图里的 func f(x) [parent=...]：形参、函数体、父帧，一样不少。然后是整个解释器的核心：

def scheme_eval(expr, env):
    if isinstance(expr, int):
        return expr
    if isinstance(expr, str):
        return env.lookup(expr)
    head = expr[0]
    if head == 'define':
        _, name, value = expr
        env.bindings[name] = scheme_eval(value, env)
        return name
    if head == 'if':
        _, test, conseq, alt = expr
        return scheme_eval(conseq if scheme_eval(test, env) else alt, env)
    if head == 'lambda':
        _, params, body = expr
        return Lambda(params, body, env)
    proc = scheme_eval(head, env)
    args = [scheme_eval(arg, env) for arg in expr[1:]]
    return scheme_apply(proc, args)
 
def scheme_apply(proc, args):
    if callable(proc):
        return proc(*args)
    frame = Frame(dict(zip(proc.params, args)), proc.env)
    return scheme_eval(proc.body, frame)
 
import operator as op
global_env = Frame({'+': op.add, '-': op.sub, '*': op.mul, '=': op.eq, '<': op.lt}, None)
 
def run(src):
    return scheme_eval(parse(tokenize(src)), global_env)

逐段对照前几篇：

• 整数求值为自身，名字沿环境查找：第一篇的”原始表达式”。
• define、if、lambda 在求值操作数之前就被拦下单独处理：它们是第一篇说的特殊形式。if 只求值一个分支，这就是为什么 fact 的递归能停下来；lambda 根本不求值函数体，只把它连同当前环境 env 打包起来。
• 其他情况是调用表达式：先求值操作符和所有操作数，再交给 scheme_apply。这就是第一篇那条递归的求值规则，原样写成了代码。
• scheme_apply 对内置函数直接调用 Python 函数；对用户函数，新建一个帧，父帧是 proc.env，在新帧里求值函数体。这一行就是词法作用域。

eval 调用 apply，apply 又调用 eval，这对互相递归的函数就是整个解释器。跑起来：

print(run('(+ 1 (* 2 3))'))
print(run('(define square (lambda (x) (* x x)))'), run('(square 12)'))
run('(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))')
print(run('(fact 20)'))
run('(define make-adder (lambda (n) (lambda (k) (+ n k))))')
print(run('((make-adder 3) 4)'))

7
square 144
2432902008176640000
7

递归能跑，闭包也能跑：make-adder 返回的内层 Lambda 记住了外层调用的帧，n 被找到。我们没有为闭包写任何专门的代码，它是”lambda 记下当前环境 + 调用时父帧取 proc.env”这两条规则自然的结果。

把 scheme_apply 里的 proc.env 换成调用者的环境，就得到动态作用域。用第一篇开头的谜题测试两个版本：

run('(define x 1)')
run('(define f (lambda () x))')
run('(define g (lambda (x) (f)))')
print('lexical:', run('(g 2)'))

lexical: 1
dynamic: 2

（dynamic 那一行来自把父帧改成调用者 env 的另一版求值器。）一门语言的作用域规则，在解释器里就是一个参数填什么。

停一下，检查理解单选

为什么 if 必须在 scheme_eval 里作为特殊形式处理，而不能做成一个放在 global_env 里的内置函数？

因为 Python 的 if 是关键字，不能作为字典的值因为调用内置函数前会先求值所有操作数，if 却必须只求值其中一个分支因为 if 需要访问全局环境，内置函数访问不到为了让解释器跑得更快

检查答案

停一下，检查理解单选

解释器里没有任何专门处理闭包的代码，((make-adder 3) 4) 却能返回 7。是哪两处代码共同实现了闭包？

parse 把内层 lambda 解析成嵌套列表，Frame.lookup 遍历全局帧求值 lambda 时把当前环境 env 存进 Lambda 对象，scheme_apply 新建帧时用 proc.env 作为父帧global_env 里预先存了 n 的值scheme_eval 在调用结束后不删除帧

检查答案

尾递归：不占栈的递归

这个解释器有一个毛病。写一个计数函数，它的递归调用是函数体最后一件事：

run('(define count (lambda (n acc) (if (= n 0) acc (count (- n 1) (+ acc 1)))))')
print(run('(count 100 0)'))
try: print(run('(count 5000 0)'))
except RecursionError: print('RecursionError')

100
RecursionError

Scheme 的每一层调用都对应 Python 里 scheme_eval → scheme_apply → scheme_eval 的几层调用，很快就撞上 Python 的 1000 层上限。但是仔细看 count：递归调用 (count (- n 1) (+ acc 1)) 的结果直接就是当前调用的结果，返回之后什么也不用做。这样的调用叫尾调用（tail call），处在尾位置上的递归叫尾递归。

对比 fact 的 (* n (fact (- n 1)))：递归调用返回后还要乘以 n，所以当前帧必须留着等结果。count 的当前帧没有任何待完成的工作，留着它纯属浪费。第二篇说过，循环版 fact_iter 把”还剩什么没做”放在变量里；尾递归的 count 把它放在参数 acc 里，调用自己时就已经带上了全部状态。

Scheme 语言标准要求实现正确处理尾调用：无论尾递归多少层，只用常数空间。在我们的解释器里做到这一点，只需要把”在尾位置上递归调用 scheme_eval”改成”更新 expr 和 env，回到循环开头”：

def scheme_eval(expr, env):
    while True:
        if isinstance(expr, int):
            return expr
        if isinstance(expr, str):
            return env.lookup(expr)
        head = expr[0]
        if head == 'define':
            env.bindings[expr[1]] = scheme_eval(expr[2], env)
            return expr[1]
        if head == 'if':
            _, test, conseq, alt = expr
            expr = conseq if scheme_eval(test, env) else alt
            continue
        if head == 'lambda':
            return Lambda(expr[1], expr[2], env)
        proc = scheme_eval(head, env)
        args = [scheme_eval(a, env) for a in expr[1:]]
        if callable(proc):
            return proc(*args)
        expr, env = proc.body, Frame(dict(zip(proc.params, args)), proc.env)
 
run('(define count (lambda (n acc) (if (= n 0) acc (count (- n 1) (+ acc 1)))))')
print(run('(count 100000 0)'))
run('(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))')
try: print(run('(fact 2000)'))
except RecursionError: print('RecursionError')

100000
RecursionError

输出的第一行是 (count 100000 0)：十万层尾递归顺利完成。第二行是 (fact 2000)：它仍然报错，因为 (* n (fact ...)) 里的递归调用是 * 的操作数，不在尾位置，求值操作数时 Python 照样要递归调用 scheme_eval。

改动只在两处：if 选好分支后不递归，而是把分支当成新的 expr 继续循环；调用用户函数时不再调用 scheme_apply，而是把函数体和新帧当成新的 expr、env 继续循环。哪些位置是”尾位置”，正是这两处：if 的分支，和函数体本身。Python 自己没有尾调用优化（Guido 的理由是会丢失 traceback 里的帧信息，不利于调试），所以在 Python 里写深递归仍然要改成循环。

停一下，检查理解多选

下面哪些 Scheme 函数中的递归调用处在尾位置，能被上面的解释器以常数栈空间执行？

(define (f n) (if (= n 0) 0 (f (- n 1))))(define (f n) (if (= n 0) 0 (+ 1 (f (- n 1)))))(define (f n acc) (if (= n 0) acc (f (- n 1) (* acc n))))(define (f n) (if (= n 0) 1 (* n (f (- n 1)))))

检查答案

记住这三件事

1. for 循环就是反复调用 next 直到 StopIteration；生成器是冻结在 yield 处的函数帧，用它写迭代器最简单，而且天然惰性。
2. 解释器就是 parse 加上互相递归的 eval 和 apply；特殊形式不求值全部操作数，词法作用域和闭包只是”lambda 记下环境、调用时以它为父帧”两行代码。
3. 尾位置上的调用不需要保留当前帧，把它改成循环就是尾调用优化；不在尾位置的递归仍然占栈。

延伸阅读

• Composing Programs 4.2 Implicit Sequences（迭代器、生成器、流，CC BY-SA）
• Composing Programs 3.2 Functional Programming 与 3.5 Interpreters for Languages with Abstraction（Scheme 与解释器，CC BY-SA）
• CS61A 课程主页（Scheme 解释器项目，含尾调用优化的可选部分）
• Peter Norvig: (How to Write a (Lisp) Interpreter (in Python))
• SICP 4.1 The Metacircular Evaluator
• Python 文档：Iterator types