Lab 10：解释器与尾调用ok 14 项通过

0. 这份作业在练什么

到 Lab 10 为止，这门课一直在教你「读懂求值过程」：看到一个表达式，能在脑子里 按规则一步步算出它的值。Lab 10 把这件事翻了个面——不再是你按规则求值，而是你写一个程序， 让它按规则求值。这个程序就叫解释器（interpreter）。

这个翻面是有代价的：一旦你要写解释器，就必须把此前含混带过的东西全部说死。比如：

• 「一个表达式」在内存里到底长什么样？—— 答：一个 Link 链表对象，第一个元素是算子，其余是算子数。
• 「算子先于算子数求值」是谁保证的？—— 答：是解释器代码里那一行 calc_apply(calc_eval(operator), map_link(calc_eval, operands)) 的书写顺序保证的。
• 「and 会短路」为什么不能靠普通的调用规则实现？—— 答：因为普通调用规则会把所有算子数都求值一遍， 而短路要求「求到一半就停」。所以 and 必须是特殊形式（special form），在解释器里单开一条分支。

作业一共 6 题，分成四组：

做之前该掌握什么

• 链表 Link 类（Lab 7 / Lab 8）：first、rest、Link.empty， 以及「用 while 沿着 rest 往下走」和「用递归处理 rest」这两种遍历方式。
• Scheme 的基本语法（Lecture 18、19）：define、lambda、if、begin、 cons / car / cdr / null? / append、引用 '。
• 递归的两种形态：「先递归再加工」（非尾递归）与「加工完再递归」（尾递归）。Q6 全靠这个。

1. Q1：WWSD 准引用 wwsd-quasiquote

题目要什么

这是一道 What Would Scheme Display（Scheme 会显示什么）概念题，不计分，但它是理解 Q5「宏」的前提。 题目给你一串 Scheme REPL 输入，你要说出每一行的输出。全部输入输出如下 （来自 labs/lab10/tests/wwsd-quasiquote.py，答案已解锁）：

scm> '(1 x 3)
(1 x 3)
scm> (define x 2)
x
scm> `(1 x 3)
(1 x 3)
scm> `(1 ,x 3)
(1 2 3)
scm> `(1 x ,3)
(1 x 3)
scm> `(1 (,x) 3)
(1 (2) 3)
scm> `(1 ,(+ x 2) 3)
(1 4 3)
scm> (define y 3)
y
scm> `(x ,(* y x) y)
(x 6 y)
scm> `(1 ,(cons x (list y 4)) 5)
(1 (2 3 4) 5)

怎么想到的

先把三个符号的分工钉死，后面九行全是机械套用：

唯一容易犯迷糊的一点是：解引用之后填回去的是「值」，不是「值的文本」。 所以最后一行 ,(cons x (list y 4)) 求出来是一个列表 (2 3 4)， 它作为一个整体元素被塞进外层列表，于是结果是 (1 (2 3 4) 5)，而不是把三个元素摊平的 (1 2 3 4 5)。 这个「不摊平」的性质在 Q5 里非常关键——那里我们要把 expr 整个塞进 (lambda () ...) 的位置。

逐行推演

2. Q2：用 Link 表示表达式 using_link

题目要什么

同样是概念题（不计分），但它是 Q3、Q4 的地基。题目让你回答关于 Calculator 表达式 (+ (- 2 4) 6 8) 的六个选择题。labs/lab10/tests/using_link.py 里的题目与答案是：

怎么想到的

核心只有一条规则，其余全是它的推论：

拿到 (+ (- 2 4) 6 8)，先数清楚它有几个「顶层元素」。用括号配对来数：

(  +   (- 2 4)   6   8  )
   ↑    ↑        ↑   ↑
  算子  算子数1  数2  数3

是 4 个顶层元素，所以链表有 4 个结点。这一步最容易数错——初学者常把 (- 2 4) 里的 -、2、4 也当成顶层元素，数成 6 个，于是选了错误选项 Link('+', Link('-', Link(2, Link(4, Link(6, Link(8))))))。那个选项表示的是平铺的 (+ - 2 4 6 8)，把嵌套结构彻底压没了。

第二个坑是引号。Calculator 里，算术运算符是用 Python 字符串表示的， 所以必须写 '+' 和 '-'。选项里那两个不带引号的 Link(+, …)、Link(-, …) 在 Python 里根本不是合法表达式（会 SyntaxError）。 而数字用 Python 数字表示，所以 2、4、6、8 不带引号。 一句话记忆：符号带引号，数字不带。

逐层拆开这条链表

把答案写成缩进形式，结构一目了然：

Link('+',                        <- p          first = '+'（算子）
     Link(Link('-',              <- p.rest     first = 嵌套表达式 (- 2 4)
               Link(2, Link(4))),
          Link(6,                <- p.rest.rest      first = 6
               Link(8))))        <- p.rest.rest.rest first = 8, rest = nil

于是六个问题的答案自动落地：

验证：手动追踪 print(p)

Link.__str__ 的写法是：先输出 ( 和 repl_str(self.first)， 然后沿 rest 循环，每次加一个空格和 repl_str(rest.first)，最后补 )。 对我们的 p：

能原样打印回来，说明这条链表确实是那个表达式的忠实表示。

3. Q3：新过程 floor_div（含补全 calc_eval）

题目要什么

给 Calculator 语言加一个整除运算 //。它接受至少两个参数， 多参数时从左往右依次整除：(// a b c d) 等价于 Python 的 ((a // b) // c) // d。

calc> (// 1 1)
1
calc> (// 5 2)
2
calc> (// 28 (+ 1 1) 1)
14

题面明确提示：要同时改 calc_eval 和 floor_div 两处。 这一点很容易漏——起始文件里 calc_eval 处理调用表达式的那一行本来就是空的：

if isinstance(exp, Link):
    operator = ____________
    operands = ____________
    if operator == 'and':
        return eval_and(operands)
    elif operator == 'define':
        return eval_define(operands)
    else:
        return calc_apply(___________, ___________)

也就是说，整个解释器的「调用表达式」这条主干路径要你自己接上， floor_div 只是接上之后顺便加的一个内置过程。floor_div 的 doctest 也分两半： 前五条直接调 floor_div，后三条走 calc_eval，后者只有主干接对了才过。

>>> floor_div(Link(23, Link(2, Link(5, nil))))
2
>>> calc_eval(Link("//", Link(100, Link(Link("+", Link(2, Link(3, nil))), nil))))
20

边界情况：题目说「假设每次调用 // 至少有两个参数」，所以不必处理 (// 5) 这种单参数情况，也不必处理零参数。这句话省掉了一堆判断。

怎么想到的

第一步：先想清楚 floor_div 拿到的是什么

看 doctest：floor_div(Link(23, Link(2, Link(5, nil)))) 返回 2。 传进来的是一条链表 (23 2 5)，里面全是数字，不是表达式。 对比一下 OPERATORS 里已经写好的 addition（在 lab10.py 里以 base64 形式给出， 解码后是一个简单的 while 循环），它们的签名都是「一个参数 expr，是数字链表」。

所以 floor_div 的职责很窄：拿一串已经算好的数，做左折叠（fold left）。 求值这件事不归它管。

第二步：写折叠

「从左往右累积」有两种写法：递归和循环。

递归版大概是这样（示意，未采用）：

def floor_div(args):
    if args.rest is nil:
        return args.first
    return floor_div(Link(args.first // args.rest.first, args.rest.rest))

它能跑，但每一步都要新建一个 Link 对象，纯属浪费；而且读起来绕。 链表本来就适合用 while 走一遍，于是改成循环版：先把 args.first 当初值， 再沿 rest 一路除下去。

第三步：补 calc_eval，这才是真难点

四个空里，前两个不难：由 Q2 已知 operator = exp.first、operands = exp.rest。

难的是 calc_apply(____, ____)。第一反应是直接写 calc_apply(operator, operands)——毕竟名字都对上了。但这样一定会崩：

def calc_apply(op, args):
    return op(args)

calc_apply 第一件事就是把 op 当函数调用。而 operator 是字符串 '//'， 字符串不能调用，报错：

TypeError: 'str' object is not callable

所以第一个空必须是 calc_eval(operator)——让 calc_eval 走到 elif exp in OPERATORS: return OPERATORS[exp] 那条分支，把字符串 '//' 查表换成真正的 Python 函数 floor_div。

第二个空同理：operands 里装的可能是表达式，比如 (// 100 (+ 2 3)) 的第二个算子数是嵌套的 Link('+', …)。 如果原样传给 floor_div，就会执行 100 // Link(...)，报 TypeError: unsupported operand type(s) for //: 'int' and 'Link'。

所以每个算子数都要先 calc_eval 一遍。题面直接给了工具：map_link(f, s) 把函数 f 作用到链表 s 的每个元素上，返回新链表。于是第二个空是 map_link(calc_eval, operands)。注意 calc_eval 不带括号—— 我们传的是函数本身，不是调用它的结果。

代码

calc_eval 的调用表达式分支（labs/lab10/lab10.py）：

def calc_eval(exp):
    if isinstance(exp, Link):
        operator = exp.first  # e.g (+ 1 2), + is the operator
        operands = exp.rest   # e.g (+ 1 2), 1 and 2 are operands
        if operator == 'and': # and expressions
            return eval_and(operands)
        elif operator == 'define': # define expressions
            return eval_define(operands)
        else: # Call expressions
            # The operator is a symbol (a Python string), so evaluate it to get
            # the actual Python function, and evaluate every operand as well.
            return calc_apply(calc_eval(operator), map_link(calc_eval, operands))
    elif exp in OPERATORS:   # Looking up procedures
        return OPERATORS[exp]
    elif isinstance(exp, int) or isinstance(exp, bool):   # Numbers and booleans
        return exp
    elif exp in bindings:   # Looking up variables
        return bindings[exp]

floor_div：

def floor_div(args):
    # args is a Scheme list of already-evaluated numbers.
    # Fold left: keep floor-dividing the running result by each remaining arg.
    result = args.first
    rest = args.rest
    while rest is not nil:
        result = result // rest.first
        rest = rest.rest
    return result

还要把 // 注册进运算符表，否则 calc_eval('//') 查不到：

OPERATORS = { "//": floor_div, "+": addition, "-": subtraction, "*": multiplication, "/": division }

代码逐行讲

验证：手动追踪 calc_eval(Link("//", Link(100, Link(Link("+", Link(2, Link(3, nil))), nil))))

这个输入对应 Calculator 里的 (// 100 (+ 2 3))，doctest 说结果是 20。

再验证多参数的那条：(// 100 2 2 2 2 2)。

返回 3，与 doctest 一致。注意第 3 轮 25 // 2 = 12——每一步都截断， 不是最后才截断。如果先算浮点 \(100/2^5 = 3.125\) 再取整，恰好也是 3， 但换成 (// 23 2 5) 就会露馅：逐步截断是 23//2 = 11、11//5 = 2； 先乘除后截断是 \(23/10 = 2.3 \to 2\)。这条 doctest 结果同为 2，属于巧合； 真正的区别在 (// 7 2 2)：逐步是 7//2=3、3//2=1， 而 \(7/4 = 1.75 \to 1\)——也一样。要制造差异得取更大的数，但无论如何， 按题目定义老老实实逐步整除永远不会错。

4. Q4：新特殊形式 eval_and

题目要什么

给 Calculator 加上 and 表达式，同时引入 Scheme 的布尔值 #t / #f （用 Python 的 True / False 表示）。

calc> (and (= 1 1) 3)
3
calc> (and #f (+ 1 0))
#f
calc> (and 0 1 (+ 5 1))  ; 0 is a true value in Scheme!
6

把 eval_and 的 doctest 翻译成人话，一共考七件事：

另外题面给了一条硬性提醒：判断假值必须用 val is scheme_f， 不能用 val == scheme_f。因为在 Python 里 0 == False 为真， 但 0 is False 为假。用 == 会让 (and 0 1) 错误地短路成 False。

怎么想到的

第一步：为什么 and 不能当普通调用处理

先问一个更根本的问题：为什么 calc_eval 要为 and 单开一条 if 分支， 而不是像 + 那样往 OPERATORS 里塞一个函数？

假设我们真的塞了个 def and_op(args): ...。那么 calc_eval 会走 else 分支， 执行 map_link(calc_eval, operands)——所有算子数在 and_op 被调用之前就已经全部求值完了。 到那时再想「短路」已经晚了，该崩的早崩了。用 doctest 里第二条验证：

calc_eval(Link("and", Link(False, Link("1", nil))))

第二个算子数是 Python 字符串 "1"。若强行求值：不是 Link， "1" in OPERATORS 假，isinstance("1", int) 假，"1" in bindings 假 → 函数走到底返回 None。而期望的行为是「看到第一个 False 就停，压根不碰 "1"」。

第二步：想清楚返回什么值

Scheme 的 and 不返回布尔值，而是返回最后一个被求值的算子数的值。 这和 Python 的 and 行为一致（1 and 3 在 Python 里也是 3）。 把七条 doctest 归纳成规则：

第三步：一个自然但错的写法

最直觉的循环是这样：

# 错误示范
def eval_and(expressions):
    result = scheme_t
    while expressions is not nil:
        result = calc_eval(expressions.first)
        if result is scheme_f:
            return scheme_f
        expressions = expressions.rest
    return result

这一版其实是对的，逻辑完全等价。但它把「求值」和「判断是否最后一个」混在一起， 读的时候要在脑子里维护 result 的状态。仓库里采用的写法把两件事分开了， 意图更直白：对「除最后一个之外」的算子数做「求值 + 检查短路」； 最后一个算子数只求值，直接返回。这样一眼就能看出「最后一个不做短路检查」， 也就自动解释了 (and 0 1) 为什么返回 1——最后一个根本不参与判断。

代码

scheme_t = True   # Scheme's #t
scheme_f = False  # Scheme's #f

def eval_and(expressions):
    # `and` is a special form: evaluate the operands one at a time and stop
    # (short-circuit) as soon as one of them evaluates to a false value.
    if expressions is nil:
        return scheme_t
    while expressions.rest is not nil:
        if calc_eval(expressions.first) is scheme_f:
            return scheme_f
        expressions = expressions.rest
    return calc_eval(expressions.first)

代码逐行讲

验证一：calc_eval(Link("and", Link(0, Link(1, nil)))) → 1

验证二：calc_eval(Link("and", Link(False, Link("1", nil)))) → False

验证三：calc_eval(Link("and", Link(1, Link(Link("//", Link(5, Link(2, nil))), nil)))) → 2

对应 (and 1 (// 5 2))。第一轮：calc_eval(1) 得 1，不是 #f，推进； 循环条件不再满足；最后 calc_eval(Link('//', Link(5, Link(2)))) ——这一步回到 Q3 的路径：calc_eval('//') 得 floor_div， map_link(calc_eval, (5 2)) 得 (5 2)，floor_div 算出 5 // 2 = 2。 返回 2。 ✓ 这条同时证明了 Q3 和 Q4 拼在一起是通的。

5. Q5：宏 repeat

题目要什么

定义一个宏 repeat，接受一个数 n 和一个表达式 expr， 把 expr 求值 n 次，整体的值是最后一次求值的结果。 同时补全辅助过程 repeated-call：它接受数 n 和一个零参数过程 f，调用 f 共 n 次。

题面给了转换目标：(repeat (+ 2 3) (print 1)) 应该等价于

(repeated-call (+ 2 3) (lambda () (print 1)))

并要求 (repeat 2 (repeat 2 (print 'four))) 打印四次 four。骨架是：

(define-macro (repeat n expr)
  `(repeated-call ,n ___))

(define (repeated-call n f)
  (if (= n 1) ___ (begin ___ ___)))

ok 的两条测试用例（labs/lab10/tests/repeat-lambda.py）：

scm> (repeat (+ 2 3) (print 1))
1
1
1
1
1
scm> (repeat 2 (repeat 2 (print 'four)))
four
four
four
four

边界：repeated-call 的 base case 是 n = 1，不是 n = 0。 题目没要求处理 n 为 0 或负数的情况。

怎么想到的

第一步：为什么必须是宏，普通函数不行？

先试着不用宏。写一个普通过程：

; 错误示范
(define (repeat n expr) ...)

Scheme 是先求值算子数再调用的。所以 (repeat 5 (print 1)) 会先把 (print 1) 求值——打印一次，得到值 undefined——然后把这个已经用过的值传进去。 函数体里再怎么折腾，也只是在反复摆弄一个死值，永远不会再打印第二次。

第二步：宏该生成什么代码？

题面直接说了目标形状：(repeated-call ,n (lambda () ,expr))。 但要理解为什么是这个形状。

repeated-call 是个普通过程，它的参数会被求值。如果我们生成 (repeated-call 5 (print 1))，那 (print 1) 又会在传参时被求值一次，前功尽弃。 解决办法是把它裹进一个零参数 lambda：(lambda () (print 1))。 这个 lambda 表达式求值的结果是一个过程对象，创建过程不会执行函数体。 之后每写一次 (f)，函数体 (print 1) 才被求值一次。

第三步：逗号加在哪里？

这是全题最需要想清楚的地方。宏体是准引用的 ` (repeated-call ,n (lambda () ,expr))， 四个位置里两个带逗号、两个不带：

Q1 的第 9 行 `(x ,(* y x) y) → (x 6 y) 讲的就是这件事： 同一份准引用里，带逗号的位置放「求出来的东西」，不带逗号的位置放「字面符号」。 宏体就是靠这个混搭来拼装代码的。

第四步：repeated-call 的三个空

(if (= n 1) ___ (begin ___ ___))。题面的 Hint 说得很直白： 零参数过程的调用写作 (f)；n 为 1 时调一次就完事；n 大于 1 时先调一次，再递归处理 n-1 次。

• base case：(f)。注意不能写成 f——那样返回的是过程对象本身，而不是调用它的结果， 也不会产生 print 的副作用。
• begin 第一个子表达式：(f)，产生第一次副作用，返回值被丢弃。
• begin 第二个子表达式：(repeated-call (- n 1) f)，它的值就是 begin 的值， 也就是整个 if 的值，也就是「最后一次求值的结果」。

顺便注意：这个递归调用正好是尾调用——begin 的最后一个子表达式处在尾位置。 所以 (repeat 100000 ...) 不会爆栈。Q6 会把这个概念讲透。

代码

labs/lab10/lab10.scm：

; Evaluate expr n times. The macro wraps expr in a zero-argument lambda so
; that repeated-call can re-evaluate it on every call instead of just once.
(define-macro (repeat n expr)
  `(repeated-call ,n (lambda () ,expr)))

; Call zero-argument procedure f n times and return the final result.
(define (repeated-call n f)
  (if (= n 1)
      (f)
      (begin (f) (repeated-call (- n 1) f))))

验证一：(repeat (+ 2 3) (print 1))

(repeated-call (+ 2 3) (lambda () (print 1)))

验证二：(repeat 2 (repeat 2 (print 'four))) 为什么打印四次

这条用例专门验证「expr 真的被重新求值了，而不是只算一次然后重复用它的值」。

(repeated-call 2 (lambda () (repeat 2 (print 'four))))

6. Q6：尾递归 concatenate

题目要什么

写一个尾递归的 concatenate，接受 s（一个「由列表组成的列表」）， 把里面所有元素拼成一个列表。提示是用内置的 append。

scm> (concatenate (list (list 1 2) (list 5 1)))
(1 2 5 1)
scm> (concatenate (list (list 1 2) (list)))
(1 2)

关键在第三条 ok 测试，它不检查返回值，只检查能不能跑完：

scm> (define (tail-list n so-far)
....   (if (= n 0)
....       so-far
....       (tail-list (- n 1) (cons 1 so-far))))
tail-list
scm> (define big-list (tail-list 100000 '()))
big-list
scm> (define result (concatenate (list big-list (list 1 2 3 4)))) ; Test for tail recursion
result

它先造一个十万元素的列表，再拿去 concatenate。如果你的实现不是尾递归， 这一步会因为递归深度太大而报错。所以「尾递归」不是可选的风格要求，是硬性通过条件。

边界情况：内层可以是空列表（(list)）；s 本身也可能是空列表，这时应返回 ()。

怎么想到的

第一步：先写出最自然的（非尾递归）版本

「把 s 里所有列表接起来」的直觉递归是：

; 能出正确答案，但不是尾递归
(define (concatenate s)
  (if (null? s)
      '()
      (append (car s) (concatenate (cdr s)))))

逻辑没问题：第一个子列表接在「其余部分拼好的结果」前面。但它不是尾调用—— (concatenate (cdr s)) 返回之后，还得再做一次 append。 按题面的判据「递归调用返回后还有活要干吗？有 → 不是尾调用」，这里明摆着还有活。

结果就是：每一层递归的帧都必须留着，等里层返回才能干自己的 append。 空间是 \(\Theta(n)\)，n 是子列表个数。测试里 s 只有两个元素， 这个版本其实也过得去……但 append 本身可能不是尾递归的， 真正让第三条测试爆掉的是十万长的列表被反复 append。所以我们要老老实实按题目要求写尾递归。

第二步：尾递归的通用改法——加一个累积器

把非尾递归改成尾递归，标准手法只有一个：把「返回之后还要做的那件事」提前做掉， 把中间结果用一个额外参数带着走。这个额外参数通常叫 accumulator，这里叫 so-far。

但 concatenate 的签名是固定的，只能收一个参数。所以需要一个内部辅助过程 helper，带两个参数：remaining（还没处理的子列表）和 so-far（已经拼好的部分）。 外层 concatenate 只负责用初值 '() 启动它。

第三步：确认 append 的参数顺序

(append so-far (car remaining)) 还是 (append (car remaining) so-far)？ 这决定了结果是正序还是乱序。so-far 装的是已经处理过的、靠前的元素， 新来的 (car remaining) 应该接在后面，所以是 (append so-far (car remaining))。

写反的话，(concatenate (list (list 1 2) (list 5 1))) 会得到 (5 1 1 2)—— 子列表的顺序被整体倒过来了（每个子列表内部还是正序）。这是一个很容易犯、 但一跑测试就立刻暴露的错。

第四步：base case

(null? remaining) 为真时，说明所有子列表都已经拼进 so-far 了，直接返回 so-far。 这也顺带处理了「s 是空列表」：helper 第一次调用就命中 base case，返回初值 '()。

代码

labs/lab10/lab10.scm：

; Concatenate a list of lists into a single list, tail recursively:
; the recursive call to helper is the last thing helper does.
(define (concatenate s)
  (define (helper remaining so-far)
    (if (null? remaining)
        so-far
        (helper (cdr remaining) (append so-far (car remaining)))))
  (helper s '()))

代码逐行讲

验证：(concatenate (list (list 1 2) (list 5 1)))

输入是 ((1 2) (5 1))。逐帧展开：

f1: concatenate    s = ((1 2) (5 1))
    调用 (helper ((1 2) (5 1)) ())      <- 尾调用，f1 可以关闭

f2: helper   remaining = ((1 2) (5 1))   so-far = ()
    (null? remaining) -> #f
    (car remaining) = (1 2)
    (append () (1 2)) = (1 2)
    (cdr remaining)  = ((5 1))
    调用 (helper ((5 1)) (1 2))          <- 尾调用，f2 可以关闭

f3: helper   remaining = ((5 1))         so-far = (1 2)
    (null? remaining) -> #f
    (car remaining) = (5 1)
    (append (1 2) (5 1)) = (1 2 5 1)
    (cdr remaining)  = ()
    调用 (helper () (1 2 5 1))           <- 尾调用，f3 可以关闭

f4: helper   remaining = ()              so-far = (1 2 5 1)
    (null? remaining) -> #t
    返回 (1 2 5 1)

输出 (1 2 5 1)。 ✓

注意 f2、f3 右边那句「可以关闭」。 这就是尾递归的全部意义： 在发起下一次调用的瞬间，当前帧里再没有任何将来还要用到的信息 （remaining 和 so-far 的新值都已经算好并交出去了）， 所以解释器可以直接复用这个帧，而不是压一个新的上去。 任意时刻只存在一个 helper 帧，空间 \(\Theta(1)\)。

对比非尾递归版本处理同样输入：

f1: concatenate  s = ((1 2) (5 1))
    要算 (append (1 2) <待定>)   <- f1 必须留着，等里层结果
  f2: concatenate  s = ((5 1))
      要算 (append (5 1) <待定>) <- f2 必须留着
    f3: concatenate  s = ()
        返回 ()
      f2 恢复: (append (5 1) ()) = (5 1)，返回
    f1 恢复: (append (1 2) (5 1)) = (1 2 5 1)，返回

三个帧同时存在，空间 \(\Theta(n)\)。子列表一多就爆栈。

验证：为什么 (concatenate (list (list 1 2) (list))) 得 (1 2)

第二轮时 (car remaining) 是 ()，(append '(1 2) '()) 仍是 (1 2)—— append 遇到空列表什么也不加。所以空子列表被自然地跳过，不需要特判。

为什么十万元素那条测试能过

(concatenate (list big-list (list 1 2 3 4))) 中 s 只有两个元素， 所以 helper 只递归 3 层——就算不尾递归，栈深度也才 3。真正的压力在 append： 它要遍历十万长的 so-far。61A 的 Scheme 解释器实现了尾调用优化， 且 append 是内置过程（用 Python 实现，不吃 Scheme 的栈），因此没有问题。

7. 整份作业回顾

Lab 10 的六道题看起来分属三个话题，其实全在回答同一个问题： 「求值」这件事，可以被推迟、被绕过、被重新安排到什么程度？

三条值得带走的结论

动手自测

def eval_or(expressions):
    while expressions is not nil:
        value = calc_eval(expressions.first)
        if value is not scheme_f:
            return value
        expressions = expressions.rest
    return scheme_f

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