十道题：你以为你懂求值

[3, 3, 3] 这题大概率你答对了 —— 它太有名了。但请回答第二个问题：为什么？

常见的解释是「闭包捕获了变量 i，而循环结束时 i 已经是 3 了」。这个解释是对的，但它偷偷跳过了最关键的一环：「捕获」到底捕获了什么？

如果闭包捕获的是值，那三个闭包应该分别记住 0、1、2。可它们没有。所以闭包捕获的不是值，是盒子 —— 是那个叫 i 的存储位置本身。三个闭包记着同一个盒子，循环结束后盒子里躺着 3，于是它们一起看到 3。

那 let 为什么就好了？因为 let 让每一轮迭代拥有一个新的盒子。这不是「let 捕获值、var 捕获引用」—— 两者都捕获盒子，区别在于有几个盒子。

这个「盒子」有个正式的名字，叫环境帧。一旦你能把环境帧画出来，这道题连同它的十几个变种（Kotlin 的 lambda 捕获、Java 的 effectively final、Python 的 late binding）会一起变成常识。→ 第 5 章

ArithmeticException: / by zero 崩溃。

myIf 是一个普通函数。调用一个函数之前，Kotlin 必须先把所有参数算成值 —— 包括 100 / x。所以 x = 0 时，除零发生在 myIf 的第一行代码执行之前。cond 是不是 false 根本不重要，我们压根没走到那一步。

换句话说：你无法用函数实现 if。

这句话值得多读两遍，因为它的推论比它本身更重要 —— if、&&、||、?:、?. 这些东西全都不是函数，它们是语法。它们能「短路」、能「只算一支」，唯一的原因是编译器给了它们特权：不按普通调用规则来。

而你，作为一个用户，拿不到这个特权。你没法给 Kotlin 加一个自己的短路运算符，也没法写一个 unless。你只能等语言设计者发慈悲。

（Kotlin 给了一条缝：inline 函数 + lambda 参数，可以做到接近的效果。为什么是「接近」而不是「等同」，第 7 章会讲。而在 Racket 里，你可以真的加一个 unless，四行，而且它和内置的 if 是同一个等级的公民。→ 第 7 章、第 18 章）

a：5 次b：3 次

a 走的是 List：map 是急切的，它老老实实把 5 个全算了，生成一个新列表 [1,4,9,16,25]，然后 filter 再遍历一遍，最后 first() 拿走第一个（9）。前面四个的计算，有两个是白干的。

b 走的是 Sequence：它一次搬一个元素走完整条链。1 → 算出 1 → 不过 filter；2 → 算出 4 → 不过；3 → 算出 9 → 过了 → first() 满足了，立刻停。4 和 5 从来没被碰过。

你大概率答对了。那么第二个问题：Sequence 凭什么能做到？

它的秘密是：Sequence.map 没有真的做 map。它只是返回了一个「记着我要做 map 这件事」的对象。真正的计算，要等到有人来要元素时才发生。

这个「先记着，别算，等人要了再算」的模式有个名字：惰性求值。Kotlin 用 Sequence 模拟它，Java 用 Stream，JS 用 function*，C# 用 IEnumerable —— 四种语言，四套 API，全是在给同一个缺失的语言特性打补丁。而在 Haskell 里，这是默认行为；在 Racket 里，你用 delay 三行就能自己造一个。→ 第 12 章

这道题没有「输出」，只有理由。而理由有两层，大部分人只知道第一层。

第一层：JVM 不支持尾调用。字节码里没有「复用当前栈帧去调用另一个方法」这条指令。所以 tailrec 不是 JVM 干的活儿 —— 是 Kotlin 编译器把你的递归改写成了 while 循环。反编译一下 sum2，你会看到一个货真价实的 while。

第二层（更有意思的）：为什么要你显式写这个关键字？

因为「这个调用到底在不在尾位置」是一件很容易搞错的事，而搞错的后果是静悄悄的性能悬崖。看这个：

tailrec fun f(n: Int): Int =
    if (n == 0) 0 else 1 + f(n - 1)   // ← 编译器报错！

这里的 f(n-1) 不在尾位置 —— 它返回之后还要做一次加法。Kotlin 会当场报错：「a function is marked as tail-recursive but no tail calls are found」。

这个设计很聪明：你声明意图，编译器验证意图。如果它默默地「能优化就优化」，你就永远不知道自己那个函数到底会不会爆栈 —— 直到线上炸了。

而在 Racket 里，尾调用不是优化，是语言标准的强制要求。任何处在尾位置的调用必须复用栈帧，不允许实现者偷懒。所以 Racket 程序员用递归写循环是天经地义的，根本不需要一个关键字来求编译器开恩。

顺便说个反直觉的：上面那个非尾递归的 1 + f(n-1)，在 Racket 里递归十万层也不会崩。为什么？因为 Racket 的栈在堆上，能一直长。它只是费内存（O(n)），不会 StackOverflowError。会当场崩的是 JVM 和 V8 —— 它们的栈是一块固定大小的内存。→ 第 8 章

{value: 1, done: false} 然后打印 x = 42，再 {value: 84, done: true}

如果你答对了，恭喜 —— 你比大多数 JS 程序员更懂生成器。但真正的问题在这里：

第一次 next() 时，函数停在了 yield 1 这个位置。它停下来的时候，「函数体里还没跑完的那一半」去哪了？它显然没有消失 —— 因为第二次 next(42) 时它又从那里接着跑了，而且 42 变成了 yield 表达式的返回值，赋给了 x。

所以：JS 引擎把「函数剩下的部分」保存成了一个东西，存在了某个地方。这个「函数剩下的部分」——「拿到一个值之后接下来要做的全部事情」——就是续延（continuation）。

yield 做的事一共三件：① 把「函数剩下的部分」打包存起来；② 跳回调用者（把 1 交给它）；③ 下次 next(42) 时，把 42 塞进那个包，让它接着跑。

这不是 JS 的发明。1975 年 Scheme 就把这个能力直接交给用户了，而且是不加任何限制的完全体，叫 call/cc。你在第 14 章会亲手用它造出生成器 —— 大约二十行。→ 第 13、14、15 章

它变成了：

// 反编译后（示意）
fun loadUser(id: String, cont: Continuation<User>): Any

Continuation<T> —— 「续延」。

这不是巧合，也不是 JetBrains 随手起的名字。它就是上一题里那个东西。

每一个 suspend 函数，编译器都会偷偷加一个参数：Continuation，它代表「这个函数返回之后，接下来要做的一切」。函数走到挂起点时，把这个续延交给调度器，然后自己 return 走人，把线程还回去。等结果到了，调度器再拿着这个续延，让计算从当初停下的地方接着跑。

这套把戏有个名字：CPS 变换（Continuation-Passing Style，续延传递风格）。它是 Scheme 社区在 1970 年代发明并用烂了的技术。Kotlin 的协程不是什么新东西 —— 它是编译器替你做了一遍 Racket 程序员手写了四十年的事。

知道这一点有什么用？用处大了。一旦你明白 suspend 的本质是「多传一个『接下来要做什么』的参数」，那么下面这些原本要死记的规则，会全部变成推论：

• 为什么 suspend 函数只能在 suspend 函数里调用？因为它需要一个续延，而只有 suspend 上下文里才有。
• 为什么普通的 lambda 里不能调 suspend？因为普通 lambda 的签名里没有那个参数。
• 为什么 suspend 函数的「返回」可能发生在另一个线程上？因为恢复它的是调度器，调度器爱在哪儿跑就在哪儿跑。

→ 第 15 章（那一章你会看到左边 Racket 手写、右边 Kotlin 编译器生成，两栏并排）

1 2 —— 没换成。而且编译器一句警告都不给。

展开之后是这样：

{
    int tmp = tmp;   // ← 宏的 tmp 遮住了我的 tmp
    tmp = y;         // ← 改的是宏的那个
    y = tmp;
}

宏作者用了一个叫 tmp 的临时变量。调用者碰巧也有一个叫 tmp 的变量。于是宏里那个 int tmp 把外面的遮住了，整段代码在一个错误的变量上忙活了半天。

这个现象叫变量捕获（variable capture）。它是「宏 = 邪恶」这个流传了几十年的偏见的直接来源。

C 程序员的解法是命名约定：把它叫 __swap_tmp_x9z_，然后祈祷没人重名。这不是解法，这是希望。

而 Racket 的宏在语言层面上不可能发生这件事。宏里引入的每一个绑定都会自动改名成一个宇宙中独一无二的名字 —— 你想撞都撞不上（真要撞得显式请求，见第 20 章）。这个性质叫卫生（hygiene），它不是一个补丁，它是宏系统设计的起点。

顺带一提：Rust 的 macro_rules! 直接抄的 Racket 的 syntax-rules —— 连名字、连省略号语法、连卫生规则都抄了。你如果写过 Rust 宏，第 18 章会让你有一种回家的感觉。→ 第 19 章

因为在这些语言里，「代码」和「数据」是两种东西。

你的程序在运行时能操作的，是 String、List、User 这些数据。而你写的那些 if、class、fun ——那些是代码，它们在编译后就蒸发了，运行时根本不存在。

所以，当你想「写一个程序去生成另一个程序」时，你面对的第一个问题是：我拿什么来表示那个被生成的程序？

Java 的答案是：我们再造一套数据类型来模拟代码。于是有了 Element、TypeMirror、MethodSpec…… 这是一整个平行宇宙，一套「代码的影子」。你要先把它学会，才能开始干活。KotlinPoet 的 FunSpec.builder("foo").addStatement(...) 就是在用字符串拼一个函数。

而在 Lisp 里，这个问题从一开始就不存在。

因为 Lisp 的代码本来就是数据。(+ 1 2) 是一段代码，同时它字面上就是一个三元素的表：第一个元素是符号 +，后面两个是数字。你想操作它？用 car、cdr、map —— 就是你操作任何列表的那些函数。你想生成代码？造一个表就行了。

这个性质叫同像性（homoiconicity）。它是 Lisp 最核心、也是最难向别人解释清楚的那个优势 —— 因为它不是「多了一个特性」，而是少了一堵墙。

KSP 之所以难写，Babel plugin 之所以难写，不是因为写它们的人笨。是因为他们在跟一堵不该存在的墙搏斗。→ 第 4 章、第 20 章

不是拍脑袋。这个参数顺序，忠实地反映了两种折叠在结构上的区别 —— 而这个区别在 Lisp 里是肉眼可见的。

foldRight（Racket 里叫 foldr）是这样展开的：

(foldr f init '(1 2 3))
= (f 1 (f 2 (f 3 init)))
;    ↑  ↑
;   元素 「右边折完的结果」 ← 所以元素在前

fold（Racket 里叫 foldl）是这样的：

(foldl f init '(1 2 3))
= (f 3 (f 2 (f 1 init)))
;  它带着一个累加器从左往右走，边走边算

参数顺序反映的是「谁在里面、谁在外面」。一旦你把这两个展开式写出来，参数顺序就不再需要记了 —— 它是推导出来的。

而「为什么一个是 123 一个是 321」，答案同样在展开式里：foldRight 从最右边的元素开始拼，fold 从最左边开始拼，而字符串拼接不满足交换律，所以顺序反了。

顺便，一个能让你终身受用的调试技巧：搞不清 fold 方向的时候，把函数换成 cons 跑一遍。

(foldr cons '() '(1 2 3))   ; ⇒ '(1 2 3)   原样复制 —— foldr 保形
(foldl cons '() '(1 2 3))   ; ⇒ '(3 2 1)   顺手反转 —— foldl 反向

答案立刻自己现形。还有一件事：map、filter、reverse、length 全都是 fold 的特例，第 10 章会一个一个造给你看。→ 第 10 章

大约一百行，一个下午。

而且核心只有两个互相调用的函数：

(define (my-eval expr env)      ; 把表达式变成值
  (cond
    [(number? expr) expr]
    [(symbol? expr) (lookup expr env)]
    [(eq? (car expr) 'lambda) (make-closure expr env)]
    [(eq? (car expr) 'if) ...]
    [else (my-apply (my-eval (car expr) env)
                    (map (lambda (e) (my-eval e env)) (cdr expr)))]))

(define (my-apply f args)       ; 把函数用在值上
  (if (primitive? f)
      (apply-primitive f args)
      (my-eval (closure-body f)
               (extend-env (closure-params f) args (closure-env f)))))

就这些。这两个函数互相咬着尾巴 —— eval 遇到函数调用就叫 apply，apply 为了算函数体又回头叫 eval —— 一路把整棵语法树吃完。

这个东西叫元循环求值器（metacircular evaluator）：用一门语言，写出这门语言自己的解释器。它是 SICP 第四章的高潮，也是这本书的高潮。

为什么它在 Racket 里只要一百行，而在 Java 里要几千行？因为前面九道题的答案在这里全部汇合了：

• 不用写词法/语法分析器 —— 因为 read 已经把代码读成表了（题 8）
• 不用设计 AST 的类型体系 —— 因为表就是 AST（题 8）
• 闭包只是一个「代码 + 环境」的结构体 —— 因为你已经知道闭包捕获的是环境（题 1）
• 递归函数不用特殊处理 —— 因为环境链天然支持（题 1）
• if 必须单独判 —— 因为它不能按普通调用来做（题 2）

而一旦你写出了这台机器，一件事会永久地改变：你会开始把所有语言都看成「某台机器上的配置」，而不是「必须背下来的规则」。这就是这本书要卖给你的东西。→ 第 21、22 章