项目四：Scheme 解释器ok 235 项通过

0. 这份作业在练什么

前三个项目都是「用一门语言解决一个问题」：Hog 练控制流，Cats 练序列处理，Ants 练面向对象。 这个项目换了个方向——你要写的程序本身就是一门语言。给它一段 Scheme 源码，它得读懂、算出结果、把结果打印出来。

说得再具体一点：整个学期我们都在问「Python 拿到 (f x) 之后一步步做了什么」。 以前这个问题的答案藏在 CPython 里，你只能靠环境图去猜。现在你要把那个「一步步做什么」亲手写成 Python 代码。 写完之后，环境图不再是黑板上的示意图，而是你 scheme_classes.py 里那个 Frame 类的实例； 「查名字要沿着 parent 链往上找」也不再是一句口诀，而是你写的 lookup 里那一行 return self.parent.lookup(symbol)。

做之前该掌握什么

整个项目分四个阶段：Phase 1（问题 1–5）让解释器能算内建过程调用， Phase 2（问题 6–10）加上用户自定义过程， Phase 3（问题 11–13）加上 mu 和逻辑特殊形式， Phase 4（问题 14–16）反过来用你写的解释器跑 Scheme 代码。 另外两道 Extra Challenge（EC1 的 let、EC2 的尾调用优化）不计分但极有价值，本仓库也都实现了。

本仓库在 proj/scheme/ 下执行 python3 ok --local 的结果是 235 个测试用例全部通过（其中 tests.scm 里 116 条 Scheme 级测试全过）， 包含 EC1 与 EC2。下面贴出的每一段代码都是这份真实通过的实现。

1. 先读懂脚手架：解释器的骨架长什么样

这个项目不像前几个可以「看到函数签名就动手」。你得先弄明白发下来的十几个文件之间是什么关系， 否则第一题就不知道自己在改哪。官方也知道这一点，所以专门给了一组不计分的概念题 （python3 ok -q eval_apply -u）。我们把这些概念题当作导览来走一遍。

读取（read）→ 求值（eval）→ 打印（print）

你在 scm> 提示符后敲的一行字，要经过三道工序：

概念题逐题拆

问：哪些类型的表达式用 Link 表示？ 选项有「只有调用表达式」「只有特殊形式」「调用表达式和特殊形式」「所有表达式都是 Link」。 正确答案是调用表达式和特殊形式。

为什么不是「所有表达式」？因为原子（atom）不是 Link： 数字 2 就是 Python 的 int 2，符号 x 就是 Python 字符串 'x'， 布尔 #t 就是 Python 的 True。 只有带括号的、非原子的表达式才是链表。为什么不是「只有调用表达式」？ 因为 (if a b c) 也带括号，读取器不知道也不关心 if 是特殊形式—— 它只管把括号里的东西串成链表，区分特殊形式和调用表达式是求值阶段的事。

问：scheme_eval 函数体里哪个表达式负责「找出一个名字的值」？ 答案是 env.lookup(expr)。这句话本身很浅，但它点出了一个关键设计： 名字的解析不是 scheme_eval 自己做的，而是委托给环境对象。 scheme_eval 只判断「这是不是一个符号」，具体怎么沿 parent 链往上找，是 Frame 的责任。 这就是抽象屏障——问题 1 你改 Frame.lookup 的时候，不需要动 scheme_eval 一个字。

问：怎么知道一个组合式（combination）是特殊形式？ 答案是「检查列表的第一个元素是不是符号，并且该符号在 SPECIAL_FORMS 字典里」。 两个条件缺一不可。只检查「在字典里」不行：SPECIAL_FORMS 的键是字符串， 而 first 可能是一个 Link（比如 ((lambda (x) x) 3) 的第一个元素）， 拿 Link 去查字典会因为 Link 没有 __hash__（它定义了 __eq__ 却没定义 __hash__）而报 TypeError。 只检查「是符号」更不行，那样 (+ 1 2) 也会被当成特殊形式。

问：应用内建过程和应用用户定义过程有什么区别？（多选）

所以答案是 I and II。第 III 条特别值得警惕：它把「Python 函数用 *args 接收任意个参数」 和「Scheme 过程的元数（arity）」搞混了。

问：表达式 (1) 应该抛出什么异常？ 答案是 SchemeError("1 is not callable")。 推理过程：(1) 是一个合法的列表，所以不会是 malformed list； 1 不是符号，所以不会走 lookup，也就不会是 unknown identifier； 它是自求值的，算出来还是 1；然后 1 被当作算子传给 scheme_apply， 而 scheme_apply 第一行就是 validate_procedure(procedure)——它发现 1 不是 Procedure 实例， 抛出 SchemeError。这道题其实在提醒你：算子求值完之后要交给 scheme_apply， 不要自己写 if isinstance(...) 去挡，否则错误消息就对不上了。

四个你要改的文件

2. 问题 1：Frame.define 与 Frame.lookup

题目要什么

把环境图里的「一个方框」实现出来。Frame 实例有两个属性： bindings 是一个 Python 字典，把 Scheme 符号（用 Python 字符串表示）映射到 Scheme 值； parent 是父帧，全局帧的 parent 是 None。

• define(symbol, value)：在当前这一帧里把 symbol 绑到 value。 注意是「当前这一帧」，不是「找到 symbol 所在的那一帧再改」——Scheme 的 define 永远是在当前帧新建/覆盖绑定。
• lookup(symbol)：从当前帧开始找，找不到就去 parent 帧找，一直找到全局帧。 全部找不到就抛 SchemeError，不是返回 None。

边界情况有两个容易被忽略的：其一，lookup 找到的必须是最内层的那个绑定 （同一个名字在多层帧里都有时，近的赢）；其二，值可能是 False 或 None， 所以判断「找到没有」必须用 symbol in self.bindings，不能用 if self.bindings.get(symbol): 这种真值判断。ok 的第二个测试用例里就有 second_frame.define("y", False) 紧接着 second_frame.lookup("y") 要返回 False， 专门卡这个坑。

怎么想到的

define 没什么可想的，一行字典赋值。麻烦的是 lookup。

第一反应可能是写个 while 循环：

frame = self
while frame is not None:
    if symbol in frame.bindings:
        return frame.bindings[symbol]
    frame = frame.parent
raise SchemeError(...)

这么写完全正确，ok 也会通过。但停下来想一秒：「查当前帧，查不到就在 parent 帧里做同样的事」 ——这句话本身就是递归的定义。父帧也是一个 Frame，它也有 lookup 方法， 那为什么不直接调用它？

写成递归还有一个隐性好处：base case 长什么样一目了然。 递归有两个出口——在本帧找到了（返回值），或者本帧没有且没有 parent 了（抛错）。 这两个出口在 while 版本里被循环条件搅在一起，容易写漏。

代码

    def define(self, symbol, value):
        """Define Scheme SYMBOL to have VALUE."""
        # BEGIN PROBLEM 1
        # A frame's bindings dict maps symbols (Python strings) to values.
        self.bindings[symbol] = value
        # END PROBLEM 1

    def lookup(self, symbol):
        """Return the value bound to SYMBOL. Errors if SYMBOL is not found."""
        # BEGIN PROBLEM 1
        # Search this frame first, then walk up the chain of parent frames.
        if symbol in self.bindings:
            return self.bindings[symbol]
        if self.parent is not None:
            return self.parent.lookup(symbol)
        # END PROBLEM 1
        raise SchemeError('unknown identifier: {0}'.format(symbol))

逐行说明：

• self.bindings[symbol] = value：直接赋值而不是先检查是否存在。 Scheme 里 (define x 1) 之后再 (define x 2) 是合法的重新绑定， ok 的第一个用例就连着 define 了两次 x。
• if symbol in self.bindings:：用 in 而不是 .get()，理由上面说过——值可能是 False。
• if self.parent is not None: return self.parent.lookup(symbol)： 注意这里是 return，不是光调用。忘记 return 是最常见的错误， 结果是函数继续往下走，落到 raise，于是「明明父帧里有这个名字却说找不到」。
• raise 写在 if 之外、方法末尾：只有当「本帧没有」且「没有父帧」时才会执行到这里。 这一行本来就在起始代码里，位置不用动——它同时兼任了两条路径失败后的汇合点。

验证

拿 ok 第四个测试用例走一遍，它构造了一棵帧树：

>>> first_frame = create_global_frame()
>>> first_frame.define("x", 1)
>>> second_frame = Frame(first_frame)
>>> third_frame = Frame(second_frame)
>>> fourth_frame = Frame(first_frame)
>>> fifth_frame = Frame(fourth_frame)

first_frame  (Global)   {x: 1}          parent = None
   ├── second_frame     {}              parent = first_frame
   │      └── third_frame  {}           parent = second_frame
   └── fourth_frame     {}              parent = first_frame
          └── fifth_frame {}            parent = fourth_frame

first_frame  {x: 1}
   ├── second_frame  {x: 2}
   │      └── third_frame {}
   └── fourth_frame  {}
          └── fifth_frame {}

完成这一题后，启动 python3 scheme.py 已经能查到内建过程的名字了：

scm> +
#[+]
scm> odd?
#[odd?]
scm> hello
SchemeError

为什么 + 显示成 #[+]？因为 create_global_frame() 已经把所有内建过程 以 BuiltinProcedure 实例的形式 define 进了全局帧，而 BuiltinProcedure.__str__ 返回的就是 '#[{0}]'.format(self.name)。你的 lookup 把这个对象取了出来，REPL 把它打印了。 但你还不能调用它——那是下一题。

3. 问题 2：scheme_apply 的 BuiltinProcedure 分支

题目要什么

让 (+ 1 2) 真的能算出 3。scheme_apply(procedure, args, env) 收到三样东西： 一个过程对象、一个Scheme 列表形式的实参值（Link 或 nil）、当前环境。 当 procedure 是 BuiltinProcedure 时，它背后是一个普通的 Python 函数 （存在 procedure.py_func 里），你要做的是：

1. 把 Scheme 列表 args 转成 Python 列表；
2. 如果 procedure.need_env 为真，把 env 追加到列表末尾；
3. 在给定的 try: 内部，用 * 解包调用 procedure.py_func 并返回结果。

已经给好的部分是：如果调用过程中抛 TypeError（说明参数个数不对）， except 会把它转成 SchemeError('incorrect number of arguments')。

边界情况：args 可能是 nil（零个参数，比如 (+) 要返回 0）； args.first 本身也可能是 nil（比如 (length nil)，此时 Python 列表是 [nil]，长度 1，不是 0）。 这两个「nil」意思完全不同，混起来就错。

怎么想到的

这题的核心矛盾是两个世界的参数表示法不一样。 Scheme 那边，实参是一条链表；Python 这边，函数要的是位置参数。 中间必须有个翻译层，而这个翻译层只能是「遍历链表，把每个 first 收进一个 Python list」。

为什么不能直接 procedure.py_func(args)？ 因为那样 scheme_add 会收到一个 Link 对象当作它的第一个参数， 然后试图对 Link 做加法，报 TypeError——而这个 TypeError 会被 except 抓住， 伪装成「参数个数不对」。这是本题最阴险的一个陷阱：写错了不会告诉你写错了， 只会给你一条误导性的错误消息。

接着是 need_env。为什么有的内建过程需要环境？看 eval： (eval '(+ 1 2)) 要在当前环境里求值那个被引用的表达式， 所以 Python 侧的 scheme_eval(expr, env) 必须拿到 env。 把 env 加在末尾而不是开头，是因为 scheme_eval 的签名是 (expr, env)—— 第一个参数留给真正的 Scheme 实参。

最后一个坑：except TypeError 必须只抓 TypeError。 ok 里有两个用例专门测 (exit)——scheme_exit 抛的是 EOFError， 它必须原样冒泡上去，REPL 才能正常退出。如果你把 try 的范围写得太大， 或者写成 except Exception，(exit) 就会变成「参数个数不对」，退不出去。 还有一个用例用闭包做了个计数器，要求 py_func 只被调用一次—— 所以不要写「先试着调用一次看会不会出错，再调用一次拿返回值」这种代码。

代码

    if isinstance(procedure, BuiltinProcedure):
        # BEGIN PROBLEM 2
        # Built-ins are plain Python functions, so unpack the Scheme list of
        # arguments into a Python list first.
        python_args = []
        while args is not nil:
            python_args.append(args.first)
            args = args.rest
        if procedure.need_env:
            # Procedures like eval need the calling environment as a last arg.
            python_args.append(env)
        # END PROBLEM 2
        try:
            # BEGIN PROBLEM 2
            return procedure.py_func(*python_args)
            # END PROBLEM 2
        except TypeError as err:
            raise SchemeError('incorrect number of arguments: {0}'.format(procedure))

• 这里只贴出本问要填的 BuiltinProcedure 分支； scheme_apply 三条分支都填满后的完整函数见第 12 节。
• while args is not nil: 用 is not 而不是 !=。 nil 是 Link.empty，也就是空元组 ()；而 Link 定义了 __eq__， 用 != 会触发结构比较，既慢又可能在嵌套结构上产生意外。整个项目里判断链表结束一律用 is nil / is not nil。
• python_args.append(args.first)：只取 first，不做任何求值。 到了 scheme_apply 这一步，实参已经是值了，不是表达式——求值是 scheme_eval 在调用 scheme_apply 之前干的。 这个先后顺序是问题 3 的内容，但现在就要在脑子里分清楚。
• args = args.rest：这里重新绑定的是局部参数名 args， 没有修改任何 Link 对象。题目反复强调「不要修改传入的表达式」， 指的是不能写 args.first = ... 这种；重新绑定名字是安全的。
• if procedure.need_env: 放在 try 外面。 放里面也能过，但语义上它属于「准备参数」而不是「调用」， 而且 try 块越小、except TypeError 误伤的可能性越低。
• return procedure.py_func(*python_args)：这一行必须在 try 里， 因为参数个数不匹配的 TypeError 正是在调用的一刻产生的。

验证

4. 问题 3：scheme_eval 求值调用表达式

题目要什么

补上 scheme_eval 里 else 分支——也就是「这个组合式不是特殊形式，那它就是一个调用表达式」的情况。 三步：

1. 求值算子（operator），结果应该是一个 Procedure 实例；
2. 求值所有算子数（operand），把结果收集成一个 Scheme 列表；
3. 把过程、实参列表、当前环境交给 scheme_apply，返回它的结果。

题面给了两个工具：map_link(f, s) 对 Scheme 列表每个元素应用单参数 Python 函数、 返回新的 Scheme 列表；以及 scheme_apply。 两条硬性约束：不能修改传入的 expr；算子只能求值一次。

怎么想到的

「求值一个调用表达式」这句话，整个学期的环境图课都在讲： 先算算子，再算算子数，然后应用。现在只是把它写下来。真正需要动脑的是三个细节。

细节一：结果要是 Scheme 列表，不是 Python 列表。 为什么？因为 scheme_apply 的第二个参数按约定就是 Link 或 nil—— 问题 2 里你写的 while args is not nil 就是这么假设的。 如果你在这里传 Python 列表，问题 2 的循环会立刻爆炸。 两个函数是一对接口，谁也不能单方面改约定。

那怎么把「对每个元素求值」的结果攒成一个 Link？手写递归当然可以：

# 可以，但没必要
def eval_operands(rest, env):
    if rest is nil:
        return nil
    return Link(scheme_eval(rest.first, env), eval_operands(rest.rest, env))

但 link.py 里已经有 map_link 了，它干的正是这件事。用它就好。

细节二：算子只能求值一次。题面给了一个非常刁钻的测试：

(define x 0)
; expect x
((define x (+ x 1)) 2)
; expect SchemeError
x
; expect 1

这里的算子是 (define x (+ x 1))，一个有副作用的表达式。 求值它一次，x 变成 1，返回符号 'x'；'x' 不是过程， 所以 scheme_apply 里的 validate_procedure 抛 SchemeError。 最终 x 是 1。可如果你写了类似

# 错误写法：算子被求值了两次
if not isinstance(scheme_eval(first, env), Procedure):
    raise SchemeError('not callable')
return scheme_apply(scheme_eval(first, env), args, env)

那 x 就会变成 2，测试失败。解法是把算子求值的结果存进一个局部变量， 之后只用这个变量。

细节三：求值顺序。ok 里有一组 Scheme 级测试用 print-then-return（打印第一个参数、返回第二个）精确地检查顺序：

scm> ((print-then-return 6 print) (print-then-return 1 "a"))
6
1
"a"

先打印 6，说明算子先于算子数被求值；再打印 1，说明算子数随后被求值； 最后 print 打印出 "a"。还有：

scm> (+ (print-then-return 1 1) (print-then-return 2 2))
1
2
3

1 在 2 之前，说明算子数从左到右求值。 这一条是 map_link 白送的——它是 Link(f(s.first), map_link(f, s.rest))， Python 的实参求值顺序是从左到右，所以 f(s.first) 一定先于递归调用发生。 但如果你自作聪明先构造再反转，顺序就反了。

代码

填完之后，scheme_eval_apply.py 里这个函数的完整样子如下（连同脚手架原有的部分， 整段可以直接对照抄进文件）：

def scheme_eval(expr, env, _=None): # Optional third argument is ignored
    """Evaluate Scheme expression EXPR in Frame ENV.

    >>> expr = read_line('(+ 2 2)')
    >>> expr
    Link('+', Link(2, Link(2)))
    >>> scheme_eval(expr, create_global_frame())
    4
    """
    # Evaluate atoms
    if scheme_symbolp(expr):
        return env.lookup(expr)
    elif self_evaluating(expr):
        return expr

    # All non-atomic expressions are lists (combinations)
    if not scheme_listp(expr):
        raise SchemeError('malformed list: {0}'.format(repl_str(expr)))
    first, rest = expr.first, expr.rest

    from scheme_forms import SPECIAL_FORMS # Import here to avoid a cycle when modules are loaded
    if scheme_symbolp(first) and first in SPECIAL_FORMS:
        return SPECIAL_FORMS[first](rest, env)
    else:
        # BEGIN PROBLEM 3
        # A call expression: evaluate the operator once, then every operand.
        procedure = scheme_eval(first, env)
        args = map_link(lambda operand: scheme_eval(operand, env), rest)
        return scheme_apply(procedure, args, env)
        # END PROBLEM 3

• procedure = scheme_eval(first, env)：结果存进局部名字，保证只求值一次。 不做任何类型检查——检查交给 scheme_apply 里的 validate_procedure， 这样错误消息才是官方期望的那条。
• map_link(lambda operand: scheme_eval(operand, env), rest)： map_link 只接受单参数函数，而 scheme_eval 需要两个参数， 所以要用 lambda 把 env 闭包进去。 这是本课「高阶函数 + 闭包」在真实代码里的一次朴素应用。
• 顺序：算子那行在前，map_link 那行在后。 Python 是顺序执行的，这两行的先后就直接决定了 Scheme 的求值顺序。
• rest 全程只读，map_link 返回的是新链表，原 expr 一个字节没动。 这满足了「不要修改传入表达式」的要求——而这个要求不是洁癖： 函数体在 LambdaProcedure.body 里是被反复求值的，改了它下次调用就错了。

验证

再追一个报错用例：(car car)。 算子 car 求值成 BuiltinProcedure，算子数 car 也求值成同一个 BuiltinProcedure， 于是调用 scheme_car(BuiltinProcedure)。scheme_car 内部会 validate_type(x, scheme_pairp, ...)，发现不是 pair，抛 SchemeError。✓ 而 (odd? 1 2 3) 则是 scheme_oddp(1, 2, 3) 参数太多 → TypeError → 被 except 转成 SchemeError('incorrect number of arguments')。✓

5. 问题 4：do_define_form 绑定一个符号

题目要什么

define 有两种用法：(define a (+ 2 3)) 把值绑到符号， (define (foo x) x) 造一个过程再绑上去。这一题只做第一种。

关键是搞清楚 do_define_form 收到的 expressions 到底是什么。 概念题问得很直白：「do_define_form 的 expressions 参数结构是什么？」 答案是 Link(A, Link(B, nil))，其中 A 是被绑定的符号，B 是一个表达式， 它的值要被绑到 A 上。

三个干扰项各错在哪，值得逐个看：

第二道概念题问「Frame 的哪个方法能把值绑到符号」，答案是 define—— 就是你在问题 1 写的那个。

do_define_form 完成后要返回被绑定的符号本身， 所以 REPL 里 (define x 5) 会回显 x。

怎么想到的

这题代码只有两行，思维量在于「先做什么后做什么」。

正确顺序是：先求值表达式，再绑定。 反过来想一下为什么不能先绑定一个占位符再求值——那就是另一种语义了。 考虑 (define x (+ x 1))，x 原来是 0： 如果先求值 (+ x 1)，读到的是旧的 x = 0，结果 1，再绑定，得到 x = 1。 ok 的测试正是这么期望的（那个「算子只求值一次」的用例最后 x 是 1）。

其次，为什么这件事必须是特殊形式，不能是普通过程？ 因为如果 define 是普通过程，scheme_eval 会先把它的两个算子数都求值—— 第一个算子数是符号 x，求值它会去 lookup('x')， 而 x 此刻还没定义，直接 SchemeError。 「有的子表达式不该被求值」正是特殊形式存在的唯一理由。

代码

    validate_form(expressions, 2) # Checks that expressions is a list of length at least 2
    signature = expressions.first
    if scheme_symbolp(signature):
        # assigning a name to a value e.g. (define x (+ 1 2))
        validate_form(expressions, 2, 2) # Checks that expressions is a list of length exactly 2
        # BEGIN PROBLEM 4
        # (define <symbol> <expr>): evaluate the expression, bind, return name.
        env.define(signature, scheme_eval(expressions.rest.first, env))
        return signature
        # END PROBLEM 4

• 这里只贴出本问要填的符号分支；do_define_form 的完整函数 （含问题 10 的过程简写分支）见第 11 节。
• env.define(signature, scheme_eval(...))： Python 先求值实参，所以 scheme_eval 一定在 define 之前发生。顺序天然正确。
• 绑定到 env——当前环境，不是全局帧。 所以在一个过程体里写 (define y 1)，y 是这个调用帧的局部名字， 出了这个过程就没了。ok 问题 9 的用例 (define outer (lambda (x y) (define inner (lambda (z x) ...)) (inner x 10))) 就依赖这一点。
• return signature：返回符号（一个 Python 字符串），不是值。 REPL 打印它，于是你看到 x。 顺带一提，这也是 (eval (define tau 6.28)) 返回 6.28 的原因： 内层 define 返回符号 'tau'，eval 再求值这个符号， 查出刚绑上的 6.28。
• 上面两行 validate_form 是给好的：先保证至少 2 个元素（否则 expressions.first 会崩）， 确认是符号定义后再保证恰好 2 个元素——这样 (define x 2 y 4) 才会报 SchemeError。

验证

scm> (define pi 3.14159)
scm> (define radius 10)
scm> (define area (* pi (* radius radius)))

scm> (define radius 100)
radius
scm> area
314.159

再验一个报错：(define 0 1)。 signature = 0，scheme_symbolp(0) 为假（不是字符串）， 也不是 Link，于是走到最后的 else： raise SchemeError('non-symbol: 0')。✓ (define error (/ 1 0)) 则是在 scheme_eval((/ 1 0), env) 里 被除法内建过程抛出 SchemeError，绑定根本没发生。✓

6. 问题 5：do_quote_form

题目要什么

一行代码，但概念密度很高。(quote x) 返回它的操作数本身，不求值。 读取器会把 'x 这种简写自动转成 (quote x)，所以你只需要处理后者。

概念题问 do_quote_form 的 expressions 结构，答案是 Link(A, nil)，A 是被引用的表达式。 干扰项 Link('quote', Link(A, nil)) 又一次犯了「没剥掉标识符」的错； 干扰项 A（直接就是表达式）忘了它被包在列表里。 起始代码里的 validate_form(expressions, 1, 1) 已经保证了恰好一个元素。

怎么想到的

难点不在写，在于理解「为什么需要 quote」。

Scheme 里，符号 x 求值会去查绑定，列表 (1 2) 求值会被当成调用表达式 （试图调用 1，报错）。可有时候你就是想把一段代码当数据用： 想要那个符号本身，想要那个列表本身。quote 就是「求值系统的逃生舱」。

一旦有了 quote，Lisp 的招牌特性「代码即数据（code as data）」就成立了。 问题 16 的 solution-code 之所以能把一段 Scheme 程序当链表来改写， 全靠 quote 把程序变成了普通数据。

代码

def do_quote_form(expressions, env):
    """Evaluate a quote form.

    >>> env = create_global_frame()
    >>> do_quote_form(read_line("((+ x 2))"), env) # evaluating (quote (+ x 2))
    Link('+', Link('x', Link(2)))
    """
    validate_form(expressions, 1, 1)
    # BEGIN PROBLEM 5
    # quote returns its single operand without evaluating it.
    return expressions.first
    # END PROBLEM 5

return expressions.first：取出唯一的元素，原样返回。 不复制、不遍历、不求值。env 参数完全用不上，但签名必须保留—— SPECIAL_FORMS 字典里所有函数都以 (rest, env) 被调用， 少一个参数会 TypeError。

验证

再看一组更绕的：

scm> (cons 'car '('(4 2)))
(car (quote (4 2)))
scm> (eval (cons 'car '('(4 2))))
4

7. 问题 6：eval_all 与 begin

题目要什么

(begin e1 e2 ... en) 依次求值每个子表达式，整体的值是最后一个子表达式的值。 do_begin_form 已经写好了，它直接转调 eval_all(expressions, env)， 所以真正要实现的是 eval_all。

规格：接收一个 Scheme 列表 expressions 和环境 env， 求值全部表达式，返回最后一个的值。 如果 expressions 是 nil，返回 Python 的 None（代表 Scheme 的 undefined）。 另有一条隐性要求，ok 用一个用例明确检查了：不能修改传入的链表。

为什么这个函数比看上去重要？因为它不只服务于 begin。 后面问题 9（调用 lambda 过程时求值函数体）、问题 13（cond 子句有多个结果表达式）、 EC1（let 体）全都要调它。「一串表达式，取最后一个的值」是 Scheme 里反复出现的模式。

怎么想到的

朴素写法是遍历整条链表，每个都求值，把结果存到变量里，循环结束返回最后存的那个：

# 能用，但有个瑕疵
result = None
while expressions is not nil:
    result = scheme_eval(expressions.first, env)
    expressions = expressions.rest
return result

这个版本连 nil 的情况都顺带处理了（循环不进，返回初始的 None）， 非常紧凑。它能通过问题 6 的所有测试。

那为什么本仓库的实现要写成另一个样子？因为要为 EC2（尾调用优化）留位置。 在尾调用优化的框架下，最后一个表达式的地位和前面那些不同： 前面的表达式只是为了副作用（打印、define），它们的值被丢弃； 最后一个表达式处在尾位置（tail context）——它的值直接就是整个 eval_all 的值， 所以求值它的时候不需要保留当前这个 Python 帧。

要把「最后一个」和「前面的」区别对待，循环条件就得从 「expressions is not nil」改成「expressions.rest is not nil」： 循环处理到倒数第二个为止，剩下最后一个单独处理。 但这样一来，进循环前必须先排除 expressions is nil—— 否则 nil.rest 会报 AttributeError: 'tuple' object has no attribute 'rest' （别忘了 nil 就是空元组）。

代码

def eval_all(expressions, env):
    """Evaluate each expression in the Scheme list EXPRESSIONS in
    Frame ENV (the current environment) and return the value of the last.

    >>> eval_all(read_line("(1)"), Frame(None))
    1
    >>> eval_all(read_line("(1 2)"), Frame(None))
    2
    """
    # BEGIN PROBLEM 6
    if expressions is nil:
        return None  # An empty body has the undefined value
    # Evaluate every expression but the last only for its side effects.
    while expressions.rest is not nil:
        scheme_eval(expressions.first, env)
        expressions = expressions.rest
    # The last expression is in a tail context, so its value is the result.
    return scheme_eval(expressions.first, env, True)
    # END PROBLEM 6

• if expressions is nil: return None：必须放在最前面。 返回 None 而不是 nil——两者在这个解释器里含义不同， None 打印时什么都不显示（undefined），nil 打印成 ()。
• while expressions.rest is not nil:：只要还有下一个，当前这个就不是最后一个。
• 循环体里 scheme_eval(...) 的返回值被丢弃。 这不是浪费——(begin (define x 3) x) 里第一个表达式的意义就是它的副作用。
• expressions = expressions.rest：又一次是重新绑定局部名字。 ok 有个用例存了 s = Link(1, Link(2, Link(3, nil)))， 调用后检查 s 还是 Link(1, Link(2, Link(3)))——这行写法保证了这一点。
• return scheme_eval(expressions.first, env, True)： 第三个参数 True 表示「这是尾调用」。 在你完成 EC2 之前，scheme_eval 的签名是 (expr, env, _=None)，第三个参数被忽略， 写不写都一样；完成 EC2 后它才真正生效。 本仓库两者都实现了，所以这里带着 True。

验证

scm> (define x 0)
x
scm> (begin (define x (+ x 1))
....        (define x (+ x 10))
....        (define x (+ x 100))
....        (define x (+ x 1000)))
x
scm> x
1111

再验 (begin 30 '(+ 2 2))： 第一个表达式 30 自求值成 30，扔掉； 最后一个 '(+ 2 2) 即 (quote (+ 2 2))， 走 do_quote_form 返回未求值的链表，打印成 (+ 2 2)。✓ 干扰选项 4 是把 quote 当成没写；30 是把「取最后一个」记成了「取第一个」。

还有 (begin (print 3) (+ 2 3) (print 6)) 输出 3 换行 6： 三个表达式全被求值（所以 3 和 6 都打印了）， 中间的 (+ 2 3) 算出 5 但没人要； 最后 (print 6) 打印 6 并返回 None，REPL 对 None 不显示任何东西。✓ 如果你写成「只求值最后一个」，3 就不会被打印。

8. 问题 7：do_lambda_form

题目要什么

把 (lambda (x y) (+ x y)) 变成一个 LambdaProcedure 实例。 这个类要三样东西：

• formals：形参名的 Scheme 列表，比如 Link('x', Link('y', nil))；
• body：函数体，是一个嵌套的 Scheme 列表—— 注意是「表达式们的列表」，不是「一个表达式」。 (lambda (x y) (+ x y)) 的 body 是 Link(Link('+', Link('x', Link('y', nil))), nil)， 外面那层 Link 是「只有一个元素的列表」；
• env：lambda 被定义时所处的环境。

函数体至少要有一个表达式（(lambda (x)) 要报错），可以有多个 （(lambda (x) (+ x) (+ x x)) 合法）。起始代码里的 validate_form(expressions, 2) 保证了「形参表 + 至少一个体表达式」， validate_formals(formals) 保证形参是互不相同的符号。

怎么想到的

题目本身只要求你「构造并返回一个对象」，代码一行。 真正要想明白的是body 为什么要多包一层，以及env 为什么存的是定义处的环境。

先说 body。expressions 是 (formals body1 body2 ...)， 所以 expressions.first 是形参表，expressions.rest 就是 「剩下所有体表达式组成的列表」。直接把 expressions.rest 交给 LambdaProcedure 就行——它天然已经是列表形式了。

如果你手贱写成 expressions.rest.first（只取第一个体表达式）， 单表达式的 lambda 还能跑（因为问题 9 里 eval_all 会把它当列表遍历， 而一个 Link('+', Link('x', ...)) 恰好也是个链表，遍历它会求值 '+'、'x'…… 结果诡异地返回最后一个符号的值）。这种「错得不明显」的 bug 最难查。 ok 的 (define (foo x) 1 2 3 4 5) 用例专门验证多表达式函数体。

再说 env。这是词法作用域（lexical scoping）的全部秘密。 一个 lambda 表达式被求值的那一刻，它「记住」了自己所在的环境； 将来无论在哪里被调用，它的函数体都在这个记住的环境的子帧里执行。 这就是闭包（closure）。ok 有个用例把这件事讲得很清楚：

scm> (define x 5)
x
scm> (define outer (lambda (x) (lambda () (print x))))
outer
scm> (define inner (outer 2))
inner
scm> (inner)
2

内层 lambda 是在 outer 的调用帧（x = 2）里被求值的， 所以它的 env 指向那个帧。等到在全局环境里调用 (inner) 时， 打印的仍是 2 而不是 5。这个「2」完全由 do_lambda_form 里存的那个 env 决定。

代码

def do_lambda_form(expressions, env):
    """Evaluate a lambda form.

    >>> env = create_global_frame()
    >>> do_lambda_form(read_line("((x) (+ x 2))"), env) # evaluating (lambda (x) (+ x 2))
    LambdaProcedure(Link('x'), Link(Link('+', Link('x', Link(2)))), <Global Frame>)
    """
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    # BEGIN PROBLEM 7
    # The rest of the form is the (possibly multi-expression) body.
    return LambdaProcedure(formals, expressions.rest, env)
    # END PROBLEM 7

• LambdaProcedure(formals, expressions.rest, env)：三个参数一一对应。 expressions.rest 不加 .first，因为 body 本来就该是「表达式的列表」。
• 没有任何 scheme_eval。lambda 表达式的求值不会执行函数体， 只是把它打包起来。函数体要等到被调用（问题 9）时才执行。
• validate_form(expressions, 2) 在上面已经给好：至少 2 个元素。 所以 (lambda (x)) 会在这里就报 SchemeError—— 「一个 lambda 必须有函数体」这条规则是被 validate 挡住的，不用你写。

验证

现在在 REPL 里输入一个 lambda 表达式，会看到它原样打印出来：

scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))
scm> (lambda (x) (+ x) (+ x x))
(lambda (x) (+ x) (+ x x))
scm> (lambda () 2)
(lambda () 2)
scm> (lambda (x))
SchemeError

为什么能原样打印？看 LambdaProcedure.__str__： return str(Link('lambda', Link(self.formals, self.body)))—— 它把 formals 和 body 重新拼回一个链表再打印。 这也是检验你 body 存对没存对的最快方法： 如果 (lambda (x) (+ x) (+ x x)) 打印成 (lambda (x) (+ x))， 说明你只存了第一个体表达式；如果打印成 (lambda (x) + x)， 说明你多剥了一层。第三个用例 (lambda () 2) 则确认零形参时 formals 是 nil 而不是别的什么，validate_formals(nil) 是通过的。

9. 问题 8：Frame.make_child_frame

题目要什么

这就是「画一个新方框，箭头指向父帧，把形参和实参写进去」这件事的代码版。 方法接收两个 Scheme 列表：formals（符号）和 vals（值），返回一个新的 Frame：

1. 实参个数和形参个数不一致 → 抛 SchemeError；
2. 建一个以 self 为父帧的新 Frame；
3. 按位置一一绑定：formals 的第一个绑到 vals 的第一个，依此类推；
4. 返回新帧。

第 1 步在起始代码里已经写好了（用 len_link 比较长度）。 边界情况：formals 和 vals 都可能是 nil（零参数过程）， 这时应该返回一个空的子帧而不是报错； vals 的元素本身可能是 Link（把列表当参数传）， 不能对它们做任何解包。

怎么想到的

「两个等长链表，按位置配对」——这是链表遍历里最标准的一个模式： 两个指针同步前进。因为长度已经被检查过相等， 所以只需要判断其中一个是不是走到头了。

更值得琢磨的是「为什么是 self 当父帧」。 方法名叫 make_child_frame，调用方式是 某个帧.make_child_frame(...)， 所以 self 是谁，取决于调用者传的是谁。 在问题 9 里你会写 procedure.env.make_child_frame(...)， self 就是定义处的环境 → 词法作用域； 在问题 11 里你会写 env.make_child_frame(...)， self 就是调用处的环境 → 动态作用域。 这个方法本身不决定作用域规则，它只是忠实地「以我为父」建一个帧。 把选择权留给调用者，正是它能同时服务两种作用域的原因。

代码

scheme_classes.py 里 Frame 类的这个方法，完整写出来是这样 （前两行的长度检查是脚手架给好的，缩进是类方法的四格）：

    def make_child_frame(self, formals, vals):
        """Return a new local frame whose parent is SELF, in which the symbols
        in a Scheme list of formal parameters FORMALS are bound to the Scheme
        values in the Scheme list VALS. Both FORMALS and VALS are represented
        as Links. Raise an error if too many or too few vals are given.

        >>> env = Frame(None)
        >>> from scheme_reader import read_line
        >>> formals, expressions = read_line('(a b c)'), read_line('(1 2 3)')
        >>> env.make_child_frame(formals, expressions)
        <{a: 1, b: 2, c: 3} -> <Global Frame>>
        """
        if len_link(formals) != len_link(vals):
            raise SchemeError('Incorrect number of arguments to function call')
        # BEGIN PROBLEM 8
        child = Frame(self)
        # Walk formals and vals in lockstep, binding each name to its value.
        while formals is not nil:
            child.define(formals.first, vals.first)
            formals, vals = formals.rest, vals.rest
        return child
        # END PROBLEM 8

• child = Frame(self)：Frame.__init__ 只做两件事—— self.bindings = {}、self.parent = parent。 传 self 进去就把 parent 箭头连好了。
• while formals is not nil:：只判断 formals，因为长度已确认相等。 判断 vals 也行，但没必要写两个条件。
• formals, vals = formals.rest, vals.rest： 用元组同时赋值，两个指针一起前进。 写成两行也可以，但要注意别写成 formals = formals.rest 然后 vals = formals.rest（打字错误，会错得很难查）。
• 整个过程只读 formals 和 vals。 ok 有专门的用例在调用后检查这两个链表没被改动—— 因为 formals 是从 LambdaProcedure.formals 直接传过来的， 改了它，这个过程下次就废了。
• return child：返回新帧，不返回 self。

验证

<Global Frame>   {+: #[+], -: #[-], ... , car: #[car], ...}   parent = None
      ↑
   child          {a: 1, b: 2, c: 3}                           parent = Global

再验三个边界：

• make_child_frame(nil, nil)：len_link(nil) == len_link(nil) == 0，不报错； 循环一次不进；返回一个空的子帧，frame.parent is global_frame 为 True。✓ 零参数过程 (lambda () 2) 就走这条路。
• make_child_frame(Link('a', nil), Link(1, Link(2, Link(3, nil))))： 1 != 3 → SchemeError。✓ 这就是 ((lambda (x) x) 1 2 3) 报错的地方。
• formals = ('a' 'b')，vals = ((1) (2))（值是两个链表）： frame.lookup('a') → Link(1)。✓ 绑定时对值不做任何处理，是什么就存什么。 然后 frame2 = frame.make_child_frame(nil, nil)， frame2.lookup('a') 仍能拿到 Link(1)—— 说明 parent 链正确地把查找转发上去了（这条依赖你问题 1 写的 lookup）。✓

10. 问题 9：scheme_apply 的 LambdaProcedure 分支

题目要什么

让用户定义的过程真的能被调用。两步：

1. 调用合适的父帧的 make_child_frame，把形参绑到实参值上；
2. 在这个新帧里用 eval_all 求值函数体，返回结果。

题面给了一条极重要的提示：新帧的父帧应该是「lambda 被定义时」的那个帧， 而不是 scheme_apply 收到的 env——后者是「调用发生时」的环境。

怎么想到的

代码只有两行，但这两行是整个项目最容易写错、也最能检验你是否真懂环境图的地方。

手边有两个候选的父帧：procedure.env（问题 7 存进去的定义处环境） 和 env（问题 3 里 scheme_eval 传下来的调用处环境）。选哪个？

用一个具体例子逼自己想清楚：

scm> (define n 5)
n
scm> (define add-n (lambda (x) (+ x n)))
add-n
scm> (add-n 6)
11

add-n 的函数体里有个自由变量 n。求值 (+ x n) 时， x 能在新帧里查到，n 查不到，要沿 parent 链往上找。 这里全局帧无论如何都在链上，所以两种选法结果一样，区分不出来。 换个例子：

scm> (define x 5)
x
scm> (define outer (lambda (x) (lambda () (print x))))
outer
scm> (define inner (outer 2))
inner
scm> (inner)
2

调用 (inner) 是在全局环境里发生的。 如果新帧的父帧取 env（= 全局帧），那查 x 会查到 5； 如果取 procedure.env（= outer 的调用帧，里面 x = 2），查到 2。 ok 期望的是 2，所以答案是 procedure.env。

第二步「用 eval_all 求值函数体」几乎是白送的： procedure.body 已经是「表达式的列表」， eval_all 的语义正好是「依次求值，返回最后一个的值」—— 这也正是 Scheme 过程的返回值规则。两者是为彼此设计的。

代码

    elif isinstance(procedure, LambdaProcedure):
        # BEGIN PROBLEM 9
        # Lexical scoping: the new frame's parent is the frame where the
        # lambda was *defined*, not the one where it is called.
        call_frame = procedure.env.make_child_frame(procedure.formals, args)
        return eval_all(procedure.body, call_frame)
        # END PROBLEM 9

• 这里只贴出本问要填的 LambdaProcedure 分支； scheme_apply 的完整函数见第 12 节。
• procedure.env.make_child_frame(...)：注意接收者是 procedure.env。 这一个属性访问，就是词法作用域的全部实现。
• 参数是 procedure.formals 和 args。 args 是问题 3 里 map_link 算出来的值的列表， 不是表达式——所以这里不需要再求值。
• eval_all(procedure.body, call_frame)：第二个参数是新帧， 不是 env 也不是 procedure.env。 函数体必须在能看见形参的那个帧里执行。
• 参数个数检查在 make_child_frame 里已经做了，这里不用重复。

验证

再看一个更能暴露问题的用例：

scm> (define outer (lambda (x y)
....   (define inner (lambda (z x)
....     (+ x (* y 2) (* z 3))))
....   (inner x 10)))
outer
scm> (outer 1 2)
17

调用 (outer 1 2)：新帧 f1 里 x: 1, y: 2，parent 是 G。 在 f1 里定义 inner，它的 env 是 f1。 然后 (inner x 10)：实参先在 f1 里求值，x → 1，10 → 10。 调用 inner，新帧 f2 里 z: 1, x: 10，parent 是 inner.env = f1。 求值 (+ x (* y 2) (* z 3))： x 在 f2 命中 → 10（f1 里的 x: 1 被遮蔽了）； y 在 f2 没有 → f1 命中 → 2；z 在 f2 命中 → 1。 结果 10 + 4 + 3 = 17。✓

这个用例同时考了「形参遮蔽外层同名变量」和「自由变量沿链上溯」， 一个数字对不上就说明父帧接错了。

11. 问题 10：define 的过程简写形式

题目要什么

让 (define (f x) (* x 2)) 和 (define f (lambda (x) (* x 2))) 等价。 回到 do_define_form，补上第二个分支：signature 是一个 Link 的情况。

此时 expressions 的结构是 Link(签名, 体表达式们)， 其中签名是 Link(过程名, 形参们)。要做四件事：找出名字、形参、函数体； 造一个 LambdaProcedure；绑定；返回名字。

必须支持多表达式函数体：

scm> (define (g y) (print y) (+ y 1))
g
scm> (g 3)
3
4

并且 ok 有一条用例检查不能修改传入的表达式： inp == read_line("(define (f x) x)") 在求值之后仍须为 True。

怎么想到的

题面给了两条路：一是拼出一个 (define _ (lambda ...)) 形式再递归调用自己， 二是直接实现。第二条更直白，但先想清楚数据长什么样。

把 (define (f x) (+ x 2)) 的 expressions（已剥掉 define）画出来：

expressions = Link( Link('f', Link('x', nil)),        <- signature
                    Link( Link('+', Link('x', Link(2, nil))), nil) )   <- body

对照一下 do_lambda_form 需要的输入（(lambda (x) (+ x 2)) 剥掉 lambda 之后）：

Link( Link('x', nil),                                  <- formals
      Link( Link('+', Link('x', Link(2, nil))), nil) )  <- body

两者只差第一个元素：一个是 (f x)，一个是 (x)。 而 (x) 正是 signature.rest！ body 部分（expressions.rest）一模一样，直接复用。

为什么这样做比直接 LambdaProcedure(formals, expressions.rest, env) 好？ 因为 do_lambda_form 里有 validate_form(expressions, 2) 和 validate_formals(formals)。ok 有一条用例 (define (f 1 2 3) 4) 期望 SchemeError—— 形参写成了数字，必须被拦下来。如果你绕过 do_lambda_form， 就得自己记得调 validate_formals。

另外注意 Link(...) 是新建一个结点， 原来的 signature 和 expressions 一个字节没动， 「不许修改输入」的要求自动满足。 如果你写成 signature.first = ... 之类的原地改法， 第二次求值同一段代码就会得到不同结果。

代码

这一问填完，scheme_forms.py 里的 do_define_form 才算完整。 把问题 4 的符号分支和这一问的过程分支放在一起，整个函数是这样：

def do_define_form(expressions, env):
    """Evaluate a define form.
    >>> env = create_global_frame()
    >>> do_define_form(read_line("(x 2)"), env) # evaluating (define x 2)
    'x'
    >>> scheme_eval("x", env)
    2
    >>> do_define_form(read_line("(x (+ 2 8))"), env) # evaluating (define x (+ 2 8))
    'x'
    >>> scheme_eval("x", env)
    10
    >>> # problem 10
    >>> env = create_global_frame()
    >>> do_define_form(read_line("((f x) (+ x 2))"), env) # evaluating (define (f x) (+ x 8))
    'f'
    >>> scheme_eval(read_line("(f 3)"), env)
    5
    """
    validate_form(expressions, 2) # Checks that expressions is a list of length at least 2
    signature = expressions.first
    if scheme_symbolp(signature):
        # assigning a name to a value e.g. (define x (+ 1 2))
        validate_form(expressions, 2, 2) # Checks that expressions is a list of length exactly 2
        # BEGIN PROBLEM 4
        # (define <symbol> <expr>): evaluate the expression, bind, return name.
        env.define(signature, scheme_eval(expressions.rest.first, env))
        return signature
        # END PROBLEM 4
    elif isinstance(signature, Link) and scheme_symbolp(signature.first):
        # defining a named procedure e.g. (define (f x y) (+ x y))
        # BEGIN PROBLEM 10
        # signature is (name . formals) and expressions.rest is the body, so
        # (define (f x) body) means the same as (define f (lambda (x) body)).
        name, formals = signature.first, signature.rest
        procedure = do_lambda_form(Link(formals, expressions.rest), env)
        env.define(name, procedure)
        return name
        # END PROBLEM 10
    else:
        bad_signature = signature.first if isinstance(signature, Link) else signature
        raise SchemeError('non-symbol: {0}'.format(bad_signature))

新增的是中间那个 elif 分支，逐行看：

• name, formals = signature.first, signature.rest： 把签名拆成头和尾。(f x y) 的头是过程名，尾是形参表。 起了名字而不是到处写 signature.first，是为了让下面三行读起来像自然语言。
• Link(formals, expressions.rest)：现造一个链表结点， 把形参表接到函数体列表前面，拼成 do_lambda_form 期待的形状。
• do_lambda_form(..., env)：env 原样传下去， 所以新过程的 env 就是 define 发生的那个环境。词法作用域继续成立。
• env.define(name, procedure)：和问题 4 的分支一样，绑在当前帧。
• return name：返回符号，REPL 打印过程名。
• 外层的 elif 条件 isinstance(signature, Link) and scheme_symbolp(signature.first) 是给好的：签名得是列表，且列表第一个元素得是符号。 (define ((f) x) 1) 这种会落到 else 里报 non-symbol。

验证

另一组 ok 用例是直接检查回显形式：

scm> (define (f x y) (+ x y))
f
scm> f
(lambda (x y) (+ x y))

f 打印成 (lambda (x y) (+ x y)) 而不是 (f (x y) (+ x y))，正说明了「简写形式只是语法糖， 内部存的就是一个普通的 lambda 过程，过程本身不记得自己叫什么名字」。 干扰项 (define f (lambda (x y) (+ x y))) 则是把「求值前的源码」当成了「求值后的值」。

12. 问题 11：mu 与动态作用域

题目要什么

实现一种动态作用域（dynamic scoping）的过程。 mu 不是标准 Scheme 的东西，是这个项目为了讲清作用域概念发明的。

两处要改：

• scheme_forms.py 里的 do_mu_form：返回一个 MuProcedure。 这个类只有 formals 和 body 两个属性，没有 env。
• scheme_eval_apply.py 里 scheme_apply 的 MuProcedure 分支： 调用时，新帧的父帧是调用表达式被求值时所处的环境。

题面给的例子：

scm> (define f (mu () (* a b)))
f
scm> (define g (lambda () (define a 4) (define b 5) (f)))
g
scm> (g)
20

f 的函数体里 a 和 b 都是自由变量， 在全局环境里根本不存在。但因为 (f) 是在 g 的调用帧里被求值的， 而那个帧里恰好有 a = 4、b = 5，所以能算出 20。

怎么想到的

这一题的代码和问题 7、问题 9 几乎逐字相同，只差一个词。 难的不是写，是想清楚「为什么 MuProcedure 不需要存 env」。

顺着推：LambdaProcedure 存 env，是因为调用时要用它当父帧， 而那时候「定义处」早就不在调用栈上了，不存就找不回来。 MuProcedure 呢？它要的父帧是「调用处的环境」， 而调用处的环境正是 scheme_apply 的 env 参数—— 调用发生的那一刻，它就在你手上，不需要提前存。

为什么现实中的语言几乎都选词法作用域？因为动态作用域下， 一个过程的行为取决于「谁调用了它」，你没法只看这个过程的源码就理解它。 把上面例子里的 g 改个形参名，f 就崩了——而 f 的代码一个字没动。 这在大型程序里是灾难。但动态作用域也不是全无用处： 异常处理的 handler 查找、某些语言的「特殊变量 / parameterize」用的就是这个思路。

代码

def do_mu_form(expressions, env):
    """Evaluate a mu form."""
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    # BEGIN PROBLEM 11
    # A mu procedure stores no environment: its caller supplies one.
    return MuProcedure(formals, expressions.rest)
    # END PROBLEM 11

补上这个分支之后，scheme_apply 的三条分支就都填满了。完整的函数是这样：

def scheme_apply(procedure, args, env):
    """Apply Scheme PROCEDURE to argument values ARGS (a Scheme list) in
    Frame ENV, the current environment."""
    validate_procedure(procedure)
    if not isinstance(env, Frame):
       assert False, "Not a Frame: {}".format(env)
    if isinstance(procedure, BuiltinProcedure):
        # BEGIN PROBLEM 2
        # Built-ins are plain Python functions, so unpack the Scheme list of
        # arguments into a Python list first.
        python_args = []
        while args is not nil:
            python_args.append(args.first)
            args = args.rest
        if procedure.need_env:
            # Procedures like eval need the calling environment as a last arg.
            python_args.append(env)
        # END PROBLEM 2
        try:
            # BEGIN PROBLEM 2
            return procedure.py_func(*python_args)
            # END PROBLEM 2
        except TypeError as err:
            raise SchemeError('incorrect number of arguments: {0}'.format(procedure))
    elif isinstance(procedure, LambdaProcedure):
        # BEGIN PROBLEM 9
        # Lexical scoping: the new frame's parent is the frame where the
        # lambda was *defined*, not the one where it is called.
        call_frame = procedure.env.make_child_frame(procedure.formals, args)
        return eval_all(procedure.body, call_frame)
        # END PROBLEM 9
    elif isinstance(procedure, MuProcedure):
        # BEGIN PROBLEM 11
        # Dynamic scoping: the new frame's parent is the calling environment.
        call_frame = env.make_child_frame(procedure.formals, args)
        return eval_all(procedure.body, call_frame)
        # END PROBLEM 11
    else:
        assert False, "Unexpected procedure: {}".format(procedure)

• MuProcedure(formals, expressions.rest)：两个参数，没有第三个。 env 参数在 do_mu_form 里被彻底忽略——这就是「不需要记住定义处」的字面体现。
• env.make_child_frame(...)：接收者是 env， 和问题 9 的 procedure.env.make_child_frame(...) 只差这一处。 把这两行并排放着看，动态作用域和词法作用域的区别就一目了然了。
• eval_all(procedure.body, call_frame)：这一行和问题 9 完全一样。 函数体的求值方式不受作用域规则影响，只是「在哪个帧里求值」变了。

验证

scm> (define y 1)
scm> (define f (mu (x) (+ x y)))
scm> (define g (lambda (x y) (f (+ x x))))
scm> (g 3 7)
13

再看一个把两种作用域混起来的用例：

scm> (define (f x) (mu () (lambda (y) (+ x y))))
f
scm> (define (g x) (((f (+ x 1))) (+ x 2)))
g
scm> (g 3)
8

13. 问题 12：and 与 or 的短路

题目要什么

实现两个逻辑特殊形式。规则：

三个必须记牢的点：

1. Scheme 里只有 #f 是假值。0、nil、空字符串统统是真值。 所以 (or #f (- 1 1) 1) 返回 0——因为 0 是真的。 必须用 is_scheme_true / is_scheme_false（它们就是 val is not False / val is False）， 不能用 Python 的 if value:。
2. 返回的是那个值本身，不是布尔。(and 4 5 6) 是 6，不是 #t。
3. 短路意味着后面的子表达式一次都不能被求值。 (and #t #f 42 (/ 1 0)) 必须返回 #f 而不是报除零错误。

怎么想到的

先问：为什么 and 必须是特殊形式，不能写成普通过程？ 因为普通过程的算子数会被 scheme_eval 全部先求值一遍—— (/ 1 0) 就炸了。短路本身就是「不求值某些子表达式」， 而这正是特殊形式的定义。

然后是控制结构。「从左到右，遇到某种值就提前返回，否则返回最后一个的值」—— 这个模式和问题 6 的 eval_all 高度相似：都要把最后一个特殊对待。 所以直接照搬那个骨架：

if expressions is nil:
    return <单位元>
while expressions.rest is not nil:
    value = scheme_eval(expressions.first, env)
    if <应该短路>:
        return value
    expressions = expressions.rest
return scheme_eval(expressions.first, env, True)

为什么最后一个要拿出循环外？因为它的处理规则不同： 无论真假都直接返回它的值，不需要判断。 (and 3 2 #f) 返回 #f，(and 3 2 1) 返回 1—— 最后一位不管是什么都原样返回。 如果你写成统一处理，(and 3 2 1) 会因为「没触发短路」而不知道返回什么。

代码

def do_and_form(expressions, env):
    # BEGIN PROBLEM 12
    if expressions is nil:
        return True  # (and) is #t
    # Return the first false value; otherwise the value of the last operand.
    while expressions.rest is not nil:
        value = scheme_eval(expressions.first, env)
        if is_scheme_false(value):
            return value  # short-circuit: later operands are never evaluated
        expressions = expressions.rest
    return scheme_eval(expressions.first, env, True)
    # END PROBLEM 12

def do_or_form(expressions, env):
    # BEGIN PROBLEM 12
    if expressions is nil:
        return False  # (or) is #f
    # Return the first true value; otherwise the value of the last operand.
    while expressions.rest is not nil:
        value = scheme_eval(expressions.first, env)
        if is_scheme_true(value):
            return value  # short-circuit: later operands are never evaluated
        expressions = expressions.rest
    return scheme_eval(expressions.first, env, True)
    # END PROBLEM 12

两个函数结构完全对称，只差两处：初始返回值（True vs False） 和短路条件（is_scheme_false vs is_scheme_true）。逐行看：

• return True / return False：返回 Python 的布尔。 题面明确说了「用 Python 的 True 表示 #t」， repl_str 会把它们打印成 #t / #f。
• value = scheme_eval(...) 存进变量再判断： 这样短路时能直接 return value（返回那个值）， 而不是重新求值一遍。有副作用的表达式重新求值会出大问题。
• is_scheme_false(value)：等价于 value is False。 写成 if not value: 的话，(and 0 1 2 3) 会在 0 处短路返回 0， 而正确答案是 3。这是本题最高频的错误。
• expressions = expressions.rest：只重绑名字，不改链表。 ok 有两条用例专门测这个： (define (no-mutation) (and #t #t #t #t)) 调用之后再打印 no-mutation， 函数体必须还是四个 #t。
• 最后一行的第三个参数 True：最后一个子表达式处在尾位置。 (or #f (or #f (or #f f))) 这种深嵌套在 EC2 完成后会变成常数空间。

验证

scm> (and (define x (+ x 1))
....      (define x (+ x 10))
....      #f
....      (define x (+ x 100))
....      (define x (+ x 1000)))
#f
scm> x
11

再逐个核对几条 or 的：

14. 问题 13：cond

题目要什么

cond 是多分支判断。每个子句（clause）形如 (判断式 结果表达式...)， 从上往下找第一个判断式为真的子句，返回它的结果。else 子句的判断式恒真。

特殊情况是这题的全部难点：

• 判断式为真但没有结果表达式 → 返回判断式的值。 (cond ((= 4 4))) 返回 #t；(cond (12)) 返回 12。
• 结果有多个表达式 → 全部求值，返回最后一个的值（用 eval_all）。
• 没有任何真判断式、也没有 else → 返回 None（undefined，REPL 什么都不打印）。
• 只有 else 且它没有结果表达式 → 返回 #t。

起始代码已经写好了外层循环、else 的识别、以及「else 必须是最后一个子句」的检查。 你只需要填「判断式为真之后怎么算结果」这一小块。

怎么想到的

先看起始代码里 else 是怎么处理的：

        if clause.first == 'else':
            test = True
            ...
        else:
            test = scheme_eval(clause.first, env)
        if is_scheme_true(test):
            # 你要填的地方

它把 else 直接当成 test = True。这一手很关键，因为它把 「else 子句」和「普通真子句」统一成了同一条路径， 你只写一份处理逻辑就够了。

那么「只有 else 且没有结果表达式时返回 #t」这条规则怎么来的？ 它不是一条独立规则——它就是「判断式为真但没结果表达式 → 返回判断式的值」 套用在 test = True 上的结果。规则合并之后，你只需要写：

if clause.rest is nil:
    return test
return eval_all(clause.rest, env)

「没有真判断式返回 None」这条也不用你写： 外层 while 循环跑完所有子句都没 return，Python 函数自然返回 None。 不要画蛇添足加一句 return nil。

最后，为什么结果部分要用 eval_all 而不是 scheme_eval(clause.rest.first, env)？ 因为 (cond ((= 4 4) 'here (+ 40 2))) 要返回 42—— 两个结果表达式都要求值，取最后一个。这正是 eval_all 的语义。 又一次，eval_all 被复用了。

代码

def do_cond_form(expressions, env):
    """Evaluate a cond form.

    >>> do_cond_form(read_line("((#f (print 2)) (#t 3))"), create_global_frame())
    3
    """
    while expressions is not nil:
        clause = expressions.first
        validate_form(clause, 1)
        if clause.first == 'else':
            test = True
            if expressions.rest != nil:
                raise SchemeError('else must be last')
        else:
            test = scheme_eval(clause.first, env)
        if is_scheme_true(test):
            # BEGIN PROBLEM 13
            if clause.rest is nil:
                # A clause with no result expressions evaluates to its test.
                return test
            return eval_all(clause.rest, env)
            # END PROBLEM 13
        expressions = expressions.rest

• if clause.rest is nil: return test： 「子句只有判断式，没有结果」。返回 test——已经求过值的那个结果， 不是 clause.first（那是未求值的表达式）。 写成 return clause.first 的话，(cond ((= 4 4))) 会返回链表 (= 4 4)。
• return eval_all(clause.rest, env)： clause.rest 是「结果表达式的列表」，正好是 eval_all 要的形状。 env 是当前环境——cond 不开新帧， 所以 (cond (#t (define x 1))) 定义的 x 会留在外面。 ok 有一条用例正是这么验的。
• 两个 return 都在 if is_scheme_true(test) 里面： 一旦某个子句命中就立刻返回，后面的子句连判断式都不再求值。 这是 cond 的短路语义。
• expressions = expressions.rest 在最外层，只有没命中时才执行。

验证

scm> (cond ((and #f 2) 'whats)
....       ((and 1 #t 2))
....       ((> 2 3) 'going)
....       (else 'on))
2

再看一组用副作用测「判断式求值了几次」的用例：

scm> (define x 0)
x
scm> (cond ((define x (+ x 1)) 'a)
....       ((define x (+ x 100)) 'b))
a
scm> x
1

第一个子句的判断式 (define x (+ x 1)) 只被求值一次： x 变成 1，do_define_form 返回符号 'x'。 is_scheme_true('x') 为真（只有 False 才是假）→ clause.rest 是 Link((quote a), nil)，不是 nil → eval_all 求值它，返回符号 'a'，打印 a。 第二个子句碰都没碰，所以 x 是 1 而不是 101。✓ 如果你在判断真假时又求值了一次判断式，x 会变成 2。

scm> (define x 0)
scm> (define y 0)
scm> (define z 0)
scm> (cond (#t
....        (define x (+ x 1))
....        (define y (+ y 1))
....        (define z (+ z 1)))
....       (else ...))
z
scm> (list x y z)
(1 1 1)

最后确认「什么都没命中」：(cond (#f 1))—— 唯一的子句判断式为假，循环推进到 nil，退出，函数隐式返回 None。 REPL 对 None 不打印任何东西，ok 的期望输出正是一片空白。✓ 而 (cond ((= 1 1) nil)) 返回的是 nil，打印成 ()—— 两者显示不同，这就是 None 和 nil 必须区分的原因。

15. 问题 14：enumerate（用 Scheme 写）

题目要什么

从这里开始换语言：不再是用 Python 写解释器，而是用你刚写好的解释器去跑 Scheme 代码。 如果前面某道题有 bug，这些题会以最莫名其妙的方式失败——所以先确认 1–13 全绿。

(enumerate s) 接收一个列表，返回一个「两元素列表」的列表， 第一个元素是下标（从 0 开始），第二个是原值。

scm> (enumerate '(3 4 5 6))
((0 3) (1 4) (2 5) (3 6))
scm> (enumerate '(c s 6 1 a))
((0 c) (1 s) (2 6) (3 1) (4 a))
scm> (enumerate '())
()

边界情况：空列表返回空列表。

怎么想到的

直觉写法是「递归处理 (cdr s)，然后给结果的每个下标加一」：

; 能用，但是 O(n²)
(define (enumerate s)
  (if (null? s)
      nil
      (cons (list 0 (car s))
            (增量加一 (enumerate (cdr s))))))

这需要再写一个「把所有下标加一」的辅助过程，还要遍历一遍结果， 总复杂度变成平方级。更重要的是，写起来啰嗦。

换个思路：下标是从头往尾递增的，那就让它跟着递归一起往下走。 问题变成「从下标 index 开始给 s 编号」—— 这个问题是递归的：从 index 给 s 编号 = (index (car s)) 接上「从 index+1 给 (cdr s) 编号」。

但 enumerate 的签名只有一个参数，没地方放 index。 解决办法是定义一个带累加参数的内部辅助过程， 外层过程只负责用初始值 0 启动它。

代码

(define (enumerate s)
  ; BEGIN PROBLEM 14
  ;; Walk s while carrying the index of the current element.
  (define (enumerate-from s index)
    (if (null? s)
        nil
        (cons (list index (car s))
              (enumerate-from (cdr s) (+ index 1)))))
  (enumerate-from s 0)
  ; END PROBLEM 14
  )

• (define (enumerate-from s index) ...)： 内部辅助过程，参数里多了个 index。 它的形参 s 遮蔽了外层的 s，这没问题——每层递归用自己那一份。
• (if (null? s) nil ...)：base case。 空列表返回 nil，打印成 ()。 这同时处理了「输入本来就是空表」和「递归到底」两种情况。
• (list index (car s))：造一个两元素列表。 (list a b) 等价于 (cons a (cons b nil))， 用 list 更直观。不能用 (cons index (car s))—— 那会造出点对 (0 . 3) 而不是列表 (0 3)。
• (cons ... (enumerate-from (cdr s) (+ index 1)))： 把当前的两元素列表接到「剩余部分的编号结果」前面。 下标加一随着列表缩短同步发生。
• (enumerate-from s 0)：函数体的最后一个表达式， 用初始下标 0 启动递归。它的值就是 enumerate 的返回值—— 这依赖你在问题 6 写对的 eval_all（多表达式函数体取最后一个的值）。

验证

(enumerate-from (3 4 5) 0)
  s 非空 → (cons (list 0 3) (enumerate-from (4 5) 1))
                              |
                              +→ s 非空 → (cons (list 1 4) (enumerate-from (5) 2))
                                                             |
                                                             +→ s 非空 → (cons (list 2 5) (enumerate-from () 3))
                                                                                            |
                                                                                            +→ (null? ()) 为真 → nil

再验空表：(enumerate '()) → (enumerate-from () 0) → (null? ()) 为真 → 返回 nil → 打印 ()。✓

顺便说一句：这段 Scheme 代码能跑起来，用到了你写的 do_define_form（两个分支都用了）、do_lambda_form、 do_if_form（本来就给好的）、eval_all、 make_child_frame、scheme_apply 的两个分支…… 基本上是对前 13 题的一次集成测试。

16. 问题 15：get 与 set（字典列表）

题目要什么

「字典列表（dictionary list）」是一个形如 ((key value) (key value) ...) 的 Scheme 列表， 每个 key 唯一。要实现两个过程：

• (get dict key)：返回 key 配对的值；找不到返回 #f。
• (set dict key value)：返回一个新的字典列表。 如果 key 已存在，长度不变、把对应的值换成 value； 如果不存在，在末尾追加一个 (key value)。

scm> (define dict-list '((a 1) (b 2) (c 3)))
dict-list
scm> (get dict-list 'b)
2
scm> (get dict-list 'e)
#f
scm> (set dict-list 'b 4)
((a 1) (b 4) (c 3))
scm> (set dict-list 'x 0)
((a 1) (b 2) (c 3) (x 0))

最要紧的一条隐性要求：set 不能改动原字典。 ok 有一条用例先 (set (set schememon 'tree 3) 'fibo 4)， 然后检查 schememon 还是原样。

怎么想到的

先看 questions.scm 顶部给好的几个工具：

(define (caar x) (car (car x)))
(define (cadr x) (car (cdr x)))
(define (cadar x) (car (cdr (car x))))
(define (cdar x) (cdr (car x)))
(define (cddr x) (cdr (cdr x)))

这些名字看着像乱码，其实有规律：从右往左读 a（car）和 d（cdr）。 cadar = car ∘ cdr ∘ car——先取 car，再取 cdr，再取 car。

套到字典上：dict 是 ((a 1) (b 2) ...)， (car dict) 是第一个键值对 (a 1)：

get 于是就是一个三分支递归：空表返回 #f； 第一对的 key 匹配就返回它的 value；否则在 (cdr dict) 里继续找。

set 稍难，难在「返回新列表，不改旧的」。 Scheme 的列表是不可变的（这个项目里没有 set-car!）， 所以「修改」只能靠重新构造： 把不需要改的部分原样 cons 回去，把要改的那个位置换成新的对子。

代码

;; Return the value for a key in a dictionary list
(define (get dict key)
  ; BEGIN PROBLEM 15
  ;; Scan the pairs; caar is a pair's key and cadar is its value.
  (cond ((null? dict) #f)
        ((equal? (caar dict) key) (cadar dict))
        (else (get (cdr dict) key)))
  ; END PROBLEM 15
  )

;; Return a dictionary list with a (key value) pair
(define (set dict key val)
  ; BEGIN PROBLEM 15
  ;; Rebuild the list; replace the matching pair, or append at the end.
  (cond ((null? dict) (list (list key val)))
        ((equal? (caar dict) key) (cons (list key val) (cdr dict)))
        (else (cons (car dict) (set (cdr dict) key val))))
  ; END PROBLEM 15
  )

• (cond ...) 而不是嵌套的 if：三个分支写成三行更清楚。 能这么写，靠的是你在问题 13 刚实现好的 do_cond_form—— Phase 4 的题目会反过来用到 Phase 1–3 的每一项成果。
• (equal? (caar dict) key)：用 equal? 而不是 eq?。 key 是符号时两者都行，但 equal? 对列表也做结构比较，更保险。
• get 的 (cadar dict)：取第一对的第二个元素。 不是 (cdar dict)——那会返回 (1)，一个单元素列表，多了层括号。
• set 第一分支 (list (list key val))：两层 list。 内层造出对子 (key val)，外层把它包成「只有一个元素的字典列表」。 只写一层的话，回代时 cons 会把 key 和 val 摊平进外层列表。
• set 第二分支 (cons (list key val) (cdr dict))： 换掉当前对子，后面原封不动。 这里没有递归——key 唯一，找到就结束。这也保证了「长度不变」。
• set 第三分支 (cons (car dict) (set (cdr dict) key val))： 把当前对子（同一个对象，不是副本）接到递归结果前面。 共享结构是安全的，因为谁都不会去改它。

验证

(set ((squirrel 0) (fibo 1) (oski 2)) tree 3)
  dict 非空；(caar dict) = squirrel ≠ tree → 第三分支
  = (cons (squirrel 0) (set ((fibo 1) (oski 2)) tree 3))
                          (caar) = fibo ≠ tree → 第三分支
                        = (cons (fibo 1) (set ((oski 2)) tree 3))
                                           (caar) = oski ≠ tree → 第三分支
                                         = (cons (oski 2) (set () tree 3))
                                                            (null? dict) → 第一分支
                                                          = ((tree 3))

  squirrel ≠ fibo → (cons (squirrel 0) (set ((fibo 1) (oski 2) (tree 3)) fibo 4))
                                        (caar) = fibo = fibo → 第二分支
                                      = (cons (fibo 4) ((oski 2) (tree 3)))
                                      = ((fibo 4) (oski 2) (tree 3))

schememon ──→ [(squirrel 0)] ──→ [(fibo 1)] ──→ [(oski 2)] ──→ nil
                    ↑                                ↑
                    │（结构共享：新链表复用了同一个对子对象）
                    │                                │
with-tree ──→ [•] ──→ [(fibo 4)] ─────────────────→ [•] ──→ [(tree 3)] ──→ nil

上图说明：with-tree 的第一个和第三个元素与 schememon 是同一个对象， 只是被新的链表结点串了起来。这就是函数式数据结构的「持久化（persistence）」—— 旧版本不受影响，新版本又不用完整复制。

get 的验证简单些：(get with-tree 'tree) 依次比较 squirrel、fibo、oski，都不匹配，最后 (caar ((tree 3))) = tree 匹配， 返回 (cadar ((tree 3))) = 3。✓ (get schememon 'tree) 一路走到 (null? dict)，返回 #f。✓

17. 问题 16：solution-code（把代码当数据改写）

题目要什么

Schémémon 这个卡牌游戏里，玩家可以做一道填空题来加倍伤害。 题目是一段带 _____（五个下划线）的 Scheme 代码，玩家给出填空内容。 (solution-code problem solution) 要把 problem 里每一个 _____ 替换成 solution，返回替换后的表达式。

scm> (define add-problem '(define (add x y) _____))
add-problem
scm> (define add-sol '(+ x y))
add-sol
scm> (solution-code add-problem add-sol)
(define (add x y) (+ x y))

关键点：_____ 可能藏在任意深度的嵌套里 （(* n _____) 就在两层括号内），而且可能出现多次。 ok 的用例还包括「一个 _____ 都没有」的情况（原样返回）。

怎么想到的

这是一道树递归题，但伪装成了列表题。

先想清楚 problem 的数据形状。 '(define (factorial n) (if (= n 0) 1 (* n _____))) 是一棵树： 每个括号是一个内部结点，每个符号/数字是一个叶子。 在 Scheme 里，这棵树用嵌套的 pair 表示。

要「把树里所有的 _____ 换掉」，就得访问每一个结点。 访问一棵用 pair 表示的树，有一个非常经典的写法：同时对 car 和 cdr 递归。

(cons (处理 (car t)) (处理 (cdr t)))

为什么这样能遍历整棵树？因为 (a b c) 就是 (cons a (cons b (cons c nil)))： 对 car 递归 = 往子表达式内部钻； 对 cdr 递归 = 往同层的下一个元素走。 两个方向都走遍，就覆盖了整棵树。

接着定 base case。递归到什么时候停？当参数不再是 pair 的时候。 非 pair 的东西有三类：

1. nil（列表末尾）→ 返回 nil；
2. 符号 _____ → 返回 solution；
3. 其它原子（数字、别的符号）→ 原样返回。

顺序上有个陷阱：pair? 的判断必须在 equal? 之前吗？ 其实这里怎么排都行，因为 _____ 是符号、不是 pair，两个条件互斥。 但 null? 必须在 pair? 之前或与之无关—— nil 不是 pair，所以 (pair? nil) 为假， 它会落到后面的分支，被 else 原样返回 nil。 换句话说第一个分支 (null? problem) 其实可以省掉， 但写出来意图更明确。

代码

(define (solution-code problem solution)
  ; BEGIN PROBLEM 16
  ;; Rebuild the expression tree, swapping every _____ for the solution.
  (cond ((null? problem) nil)
        ((pair? problem) (cons (solution-code (car problem) solution)
                               (solution-code (cdr problem) solution)))
        ((equal? problem '_____) solution)
        (else problem))
  ; END PROBLEM 16
  )

• ((null? problem) nil)：空表原样返回。 它同时是「列表递归到底」的出口。
• ((pair? problem) (cons ... ...))：递归结点。 两个递归调用都传同一个 solution—— solution 在整个替换过程中是不变的。 cons 把两边的结果重新组装成 pair， 所以返回的是一棵结构相同、叶子被替换过的新树。
• ((equal? problem '_____) solution)：命中空格。 注意 '_____ 前面的引号——不加引号的话， Scheme 会试图查找名为 _____ 的变量，报 unknown identifier。 _____ 在 CS 61A 的 Scheme 里是合法符号 （题面说符号可以含 !$%&*/:<=>?@^_~-+. 这些字符，下划线在列）。
• (else problem)：其它原子原样返回。 数字、define、if、n 这些符号都走这一支。
• 整个过程不修改 problem，全靠 cons 造新结构。 这一点和问题 15 的 set 是同一个思路。

验证

solution-code( (+ 1 _____) )
  pair? → cons( solution-code(+) , solution-code((1 _____)) )
           │                        │
           │ 非 pair、非 _____       │ pair? → cons( solution-code(1), solution-code((_____)) )
           │ → else → +             │                │                 │
           │                        │                │ → else → 1      │ pair? → cons( solution-code(_____), solution-code(()) )
           │                        │                │                 │              │                       │
           │                        │                │                 │              │ equal? _____ → (f x)  │ null? → ()

再核对官方 doctest：(solution-code '(define (factorial n) (if (= n 0) 1 (* n _____))) '(factorial (- n 1)))。 递归会一路钻到 (* n _____) 里的 _____， 把它换成 (factorial (- n 1))，其余结点原样重建，得到
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))。✓

还有一条用例是没有空格的： (solution-code '(define (sum s) (if (null? s) 0 (+ (car s) (sum (cdr s))))) '(sum (cdr s))) → 输入里一个 _____ 都没有， 所有叶子都走 else 原样返回，重建出来的树和原树结构完全一样， 打印结果与输入一致。✓ 这条用例在测「不该改的别乱改」。

18. 问题 EC 1：let 特殊形式

题目要什么

(let ((名字 表达式) ...) 体...) 在一个新帧里把名字绑到值， 然后在这个帧里求值函数体。do_let_form 已经给好了， 你要写的是 make_let_frame(bindings, env)： 返回一个 env 的子帧，其中每个绑定的符号被绑到对应表达式的值。

最关键的语义细节，题面用一个例子点了出来：

scm> (define x 5)
x
scm> (define y 'bye)
y
scm> (let ((x 42)
....       (y (* x 10)))  ; 这个 x 指的是全局的 5，不是 42
....   (list x y))
(42 50)
scm> (list x y)
(5 bye)

y 被绑成 50 而不是 420——说明所有绑定表达式都在外层环境里求值， 新帧建好之前谁也看不见谁。这是 let（而非 let*）的定义。

题面还点名了两个工具：validate_form(expr, min, max) 检查列表长度， validate_formals(formals) 检查是一串互不相同的符号。

怎么想到的

先把要做的事拆开：

1. 遍历 bindings，每个元素形如 (名字 表达式)；
2. 对每个元素，校验它长度恰好是 2；
3. 把名字收集成一个 Scheme 列表 names， 把表达式在 env 里求出的值收集成 Scheme 列表 vals；
4. 校验 names 是合法形参表（不重名、都是符号）；
5. return env.make_child_frame(names, vals)——最后一行是给好的。

第 3 步有个技术难点：怎么按原顺序构造一个 Scheme 列表？ Link(x, 已有列表) 只能往前面加，所以如果你边遍历边 cons， 得到的顺序是反的。题面的提示是「从右往左建」，也就是先把所有元素攒起来， 再倒着 cons 回去。

本仓库的实现走的正是这条路：先用两个 Python list 顺序收集， 再用 zip(reversed(...), reversed(...)) 从后往前串成链表。 这样做还有一个好处：求值顺序和链表构造顺序解耦了。 表达式必须从左到右求值（ok 有个用例 (let ((a (define z (+ z 1)))) z) 靠副作用测这个）， 而链表必须从右到左构造。分成两步就不会打架。

还有一个隐藏要求：不能改 bindings。 ok 有一条用例在调用后检查 bindings 还是原样。 因为 let 表达式可能在循环或递归里被反复求值，改坏了就不可逆。

代码

def make_let_frame(bindings, env):
    """Create a child frame of Frame ENV that contains the definitions given in
    BINDINGS. ..."""
    if not scheme_listp(bindings):
        raise SchemeError('bad bindings list in let form')
    names = vals = nil
    # BEGIN OPTIONAL PROBLEM 1
    # Evaluate every binding expression left to right in the *outer* env,
    # collecting names and values so we can build the Scheme lists afterwards.
    collected_names, collected_vals = [], []
    while bindings is not nil:
        binding = bindings.first
        validate_form(binding, 2, 2)  # each binding is exactly (symbol expr)
        collected_names.append(binding.first)
        collected_vals.append(scheme_eval(binding.rest.first, env))
        bindings = bindings.rest
    # Build the linked lists from right to left so the order is preserved.
    for name, val in zip(reversed(collected_names), reversed(collected_vals)):
        names = Link(name, names)
        vals = Link(val, vals)
    validate_formals(names)  # names must be distinct symbols
    # END OPTIONAL PROBLEM 1
    return env.make_child_frame(names, vals)

• collected_names, collected_vals = [], []： 用 Python 列表当中转站。append 是 O(1)，顺序天然正确。
• validate_form(binding, 2, 2)：长度必须恰好 2。 (let ((y 2 3)) ...) 和 (let ((y)) ...) 都在这里被拦下。 放在 binding.first / binding.rest.first 之前， 这样非法结构不会导致 AttributeError。
• scheme_eval(binding.rest.first, env)： 在外层环境求值。这一个参数决定了 let 和 let* 的差别。 ok 的用例 (let ((a 1) (b a)) b) 期望 SchemeError—— 求值 a 时新帧还不存在，外层也没有 a，所以报 unknown identifier。✓
• 循环里求值是顺序发生的，所以副作用按从左到右的顺序累积。
• zip(reversed(...), reversed(...))：两个列表同步倒序遍历。 每轮 names = Link(name, names) 把当前名字接到已有链表前面， 倒着走一遍，最终顺序就正过来了。
• validate_formals(names)：放在链表建好之后、 make_child_frame 之前。它会检查每个元素是符号且互不重复。 (let ((a 1) (2 2)) a) 里的 2 不是符号，在这里被拦下。✓
• names = vals = nil 这行是起始代码给的， 两个名字都指向 nil（同一个空元组）。因为后面是重新绑定不是修改，这没问题。

验证

(let ((x (+ y 2))
      (y (+ x 2)))
  (cons x (cons y nil)))

再验一组嵌套 let：

scm> (let ((x 5))
....    (let ((x 2)
....          (y x))
....        (+ y (* x 2))))
9

外层 let 建帧 f1：{x: 5}，parent = G。 内层 let 的两个绑定表达式都在 f1 里求值： 2 → 2；x → f1 里的 5。 所以内层帧 f2 是 {x: 2, y: 5}，parent = f1。 求值 (+ y (* x 2)) → 5 + 4 = 9。✓ 如果绑定表达式在新帧里求值（即 let* 语义）， y 会绑到 2，结果是 6。

另一条用例 (let ((a (define z (+ z 1)))) z)（起始 z = 0）返回 1： 绑定表达式 (define z (+ z 1)) 在外层求值， 所以 z 是在全局帧上被改成了 1； 函数体里的 z 在新帧查不到，上溯到全局，得 1。✓ 这条同时确认了「绑定表达式在外层环境求值」和「新帧只装绑定的名字」。

19. 问题 EC 2：尾调用优化与 trampolining

题目要什么

让下面这段代码不炸：

scm> (define (sum n total)
....   (if (zero? n)
....       total
....       (sum (- n 1) (+ n total))))
sum
scm> (sum 1001 0)
501501

为什么会炸？因为 (sum 1001 0) 要嵌套 1001 层 Scheme 调用， 而每一层 Scheme 调用在 Python 里对应好几层 scheme_eval / scheme_apply 帧。 Python 默认递归深度上限是 1000 左右，早就爆了：RecursionError。

可 sum 的递归调用是尾调用（tail call）—— 它是函数体里最后要做的事，调用返回之后当前这一层没有任何遗留工作。 既然如此，当前这一层的帧完全没必要留着。 标准 Scheme 要求实现必须做尾调用优化，让这种递归在常数空间里跑。

要做两件事：

1. 补完 optimize_tail_calls，它返回一个「被优化过的 scheme_eval」；
2. 找出解释器里所有处于尾位置的 scheme_eval 调用，给它们传 tail=True。

怎么想到的

Python 不做尾调用优化，所以不能指望语言帮忙。 思路是把「递归」改写成「循环」——但不是手改每个函数， 而是用一个通用机制：thunk + trampoline。

为什么这样能省空间？想象 (sum 3 0)： 不优化时是「eval(sum 3 0) 里面套着 eval(sum 2 3) 里面套着 eval(sum 1 5)…」， 帧一层层叠。优化后变成「while 循环第 1 轮算出一个 thunk『求值 (sum 2 3)』， 第 2 轮算出 thunk『求值 (sum 1 5)』…」， 每一轮开始前，上一轮的所有帧都已经返回了。深度恒定。

代码

def optimize_tail_calls(unoptimized_scheme_eval):
    """Return a properly tail recursive version of an eval function."""
    def optimized_eval(expr, env, tail=False):
        """Evaluate Scheme expression EXPR in Frame ENV. If TAIL,
        return an Unevaluated containing an expression for further evaluation.
        """
        if tail and not scheme_symbolp(expr) and not self_evaluating(expr):
            return Unevaluated(expr, env)

        result = Unevaluated(expr, env)
        # BEGIN OPTIONAL PROBLEM 2
        # Trampoline: keep unwrapping thunks until we reach an actual value.
        # Each iteration performs exactly one step of evaluation, so a chain
        # of tail calls uses constant space in Python.
        while isinstance(result, Unevaluated):
            result = unoptimized_scheme_eval(result.expr, result.env)
        return result
        # END OPTIONAL PROBLEM 2
    return optimized_eval

# ...文件末尾：
scheme_eval = optimize_tail_calls(scheme_eval)

• optimize_tail_calls 是个高阶函数：接收原始的 scheme_eval， 返回一个同名同签名的替代品。最后一行的 scheme_eval = optimize_tail_calls(scheme_eval) 把全局名字换掉， 于是所有对 scheme_eval 的调用都自动走优化版—— 这正是装饰器模式，不用改任何调用点。
• unoptimized_scheme_eval 被闭包捕获。 注意：原版 scheme_eval 内部的递归调用走的是全局名字 scheme_eval， 也就是优化版。所以两者是互相调用的： 优化版的 while 循环调原版走一步，原版在尾位置又调优化版拿到 thunk 返回。
• if tail and not scheme_symbolp(expr) and not self_evaluating(expr)： 这一行是给好的。三个条件：调用方声明这是尾位置、表达式不是符号、不是自求值。 满足就打包成 thunk 返回。
• result = Unevaluated(expr, env)： 用一个 thunk 当循环的初值，这样 while 的条件第一次就成立， 循环体统一处理第一步和后续所有步。比写 do-while 或者重复一次代码干净。
• while isinstance(result, Unevaluated): result = unoptimized_scheme_eval(...)： 蹦床本体。每轮只做「一步」求值。 一步之后如果又碰到尾调用，原版会（通过优化版）返回新的 Unevaluated，循环继续。
• return result：跳出循环时 result 一定是真值。

哪些调用是尾调用

光写 optimize_tail_calls 没用——如果没人传 tail=True， 第一个分支永远不触发，优化等于没做。 所以还要在解释器各处标出尾位置。本仓库标了这些（前面各题的代码里都能看到那个 True）：

反过来，哪些不是尾位置？do_if_form 里求值判断式的那个 scheme_eval(expressions.first, env) 就不是—— 算完还要拿它去判断真假，当前帧还有活干。 and/or 循环里的那些也不是，它们的值要参与短路判断。 scheme_eval 里求值算子和算子数的那两处更不是—— 它们的结果还要交给 scheme_apply。

还有一处配套设施 complete_apply（已给好）：

def complete_apply(procedure, args, env):
    """Apply procedure to args in env; ensure the result is not an Unevaluated."""
    validate_procedure(procedure)
    val = scheme_apply(procedure, args, env)
    if isinstance(val, Unevaluated):
        return scheme_eval(val.expr, val.env)
    else:
        return val

它给「从 Python 侧调用 Scheme 过程」的场合（比如内建的 map、apply）兜底： scheme_apply 现在可能返回一个 thunk，这些调用方不懂怎么处理， complete_apply 替它们展开。

验证

ok 的 EC2 测试用八种写法把同一个 sum 反复考了一遍， 每一种在考一个不同的尾位置：

这些用例合在一起说明：尾位置不是「函数体最后一行」， 而是「求值它之后当前调用就没事可做了」的任何位置—— 它可以穿过 if、cond、and、or、let、begin 一层层往里传。

20. 整份作业回顾

把 18 道题的清单再念一遍没有意义。真正值得带走的是下面几件事。

eval 和 apply 是一对互相咬合的齿轮

整个解释器的骨架只有两个函数：

scheme_eval(expr, env)
   │  expr 是符号        → env.lookup(expr)                    ← 问题 1
   │  expr 自求值        → expr
   │  expr 是特殊形式    → SPECIAL_FORMS[first](rest, env)     ← 问题 4/5/7/10/11/12/13/EC1
   └  expr 是调用表达式  → procedure = scheme_eval(算子)        ← 问题 3
                          args      = map_link(scheme_eval, 算子数)
                          scheme_apply(procedure, args, env)
                                        │
scheme_apply(procedure, args, env) ←────┘
   │  BuiltinProcedure   → py_func(*args)                      ← 问题 2
   │  LambdaProcedure    → procedure.env.make_child_frame(...)  ← 问题 8/9
   │                       eval_all(body, 新帧) ──┐
   └  MuProcedure        → env.make_child_frame() ← 问题 11
                           eval_all(body, 新帧) ──┤
                                                  │
                    eval_all → scheme_eval  ──────┘             ← 问题 6

写完之后你会发现，「一门编程语言」这个听上去很庞大的东西， 核心不过是这两个函数加上一个环境类。 剩下的一切——内建过程库、读取器、REPL——都是围绕它们的配套设施。

四条贯穿全项目的主线

特殊形式速查

动手练习

下面几题的答案都能从上面的代码和推演里推出来，先自己想再看。

验证状态

本仓库在 proj/scheme/ 下运行 python3 ok --local：

---------------------------------------------------------------------
Scheme tests in tests.scm

116 passed; 0 failed
-- OK! --

---------------------------------------------------------------------
Test summary
    235 test cases passed! No cases failed.

235 个测试用例全部通过，无失败项，覆盖问题 1–16 以及两道 Extra Challenge。 上文引用的每一段 Python 和 Scheme 代码都逐字取自 proj/scheme/scheme_classes.py、scheme_eval_apply.py、 scheme_forms.py、questions.scm 这四个文件。