Scheme 解释器、尾递归与声明式 SQL

前七篇都在 Python 里打转。最后一篇，CS61A 故意把你拽进另一种语言——Scheme（Lisp 方言），再让你亲手写一个"能运行 Scheme 的解释器"。
为什么？因为跳出一种语言，你才真正看清"编程"这件事的边界：原来函数可以没有名字、原来递归可以不用占栈、原来"我要什么"和"我怎么做"可以彻底分开。
这一篇是 CS61A 的高潮，也是把全课程串起来的那根线。

一、Scheme 基础：括号即一切

是什么：Scheme 里一切都是 S-表达式（S-expression）——要么是一个原子（数字、符号），要么是括号包裹的组合 (操作符操作数 ...)。所有语法都是这一种形式的变体。

(define (square x) (* x x))      ; 定义过程 square
(square 5)                       ; => 25
(define x 10)
(if (> x 0) "正" "负")           ; => "正"

调用形式是全前缀的 (操作符操作数 ...)，和 Python 的 操作符(操作数) 一一对应，只是把操作符挪到了最前、用空格分隔。一开始别扭，习惯后反而觉得"统一得干净"。

坑：Scheme 里所有东西都是表达式——连 if、define 都有返回值（不像 Python 的 if 是语句）。而且括号必须成对、位置严格，少一个括号解释器就一路报错到文件尾。写 Scheme 的第一课是"数对括号"。

本质一句话：Scheme = 统一的前缀 S-表达式；一切皆表达式，括号即语法。

二、过程也是值（和 Python 一致，但是原生）

是什么：篇二讲的"高阶函数 + 闭包"，在 Scheme 里不是特例，而是原生范式。过程可以当参数、当返回值、用 lambda 当场造：

(define (make-adder n)
  (lambda (x) (+ x n)))          ; 返回匿名过程，且闭包记住了 n
(define add5 (make-adder 5))
(add5 3)                         ; => 8

这正是篇二"函数工厂"的 Scheme 版。make-adder 返回的过程带着定义时的 n，call 它时 n 还在——和 Python 闭包同构。

本质一句话：在 Scheme 里，过程和数字一样是一等公民；闭包不是技巧，是默认设定。

三、尾递归：让递归不爆栈

是什么：普通递归调用之后往往"还要做点什么"——比如 fib 的 +：(fib n) 算完两个子调用后还得把它们相加，所以调用栈一直挂着等结果。这种叫递归过程（recursive process），空间 O(n)。

若递归调用是函数体的最后一步、它的返回值直接作为整体结果，就是尾递归（tail recursion）。此时"后面没事可干了"，解释器可以复用当前栈帧（尾调用优化，TCO），空间压到 O(1)。

; 尾递归版阶乘：用累加器 acc 带着中间结果一路传下去
(define (fact n)
  (define (iter i acc)
    (if (= i 0)
        acc
        (iter (- i 1) (* i acc))))   ; ← 最后一步就是递归调用本身
  (iter n 1))

调用栈对比：

递归过程（普通阶乘，空间 O(n)）：
fact(3)
  └ 等 3 * fact(2)
            └ 等 2 * fact(1)
                      └ 等 1 * fact(0) = 1   ← 栈一层层挂着

迭代过程（尾递归 factorial，空间 O(1)）：
iter(3, 1)
iter(2, 3)        ← 直接复用同一个帧，旧状态被覆盖
iter(1, 6)
iter(0, 6) = 6    ← 栈深度始终为 1

坑（Python 程序员特别注意）：Python 不做尾调用优化！哪怕你写成尾递归，n 一大照样 RecursionError。所以"尾递归"在 Scheme 里能把递归当循环用，在 Python 里只是个好看但救不了栈的写法。语言特性差异，别想当然套用。

本质一句话：尾递归 = 递归调用是最后一步 → 可复用栈帧、空间 O(1)；但 Python 不优化，别迷信。

四、eval / apply：解释器怎么跑起来的

是什么：CS61A 的高潮是亲手写一个 Scheme 解释器。核心只有两个互相调用的函数：

eval(expr, env)：在当前环境里求值一个表达式；
apply(proc, args)：把一个过程作用于实参。

┌───────────┐
│   eval    │── 遇到调用 ──▶ apply
└───────────┘◀── 返回结果 ──┘
      ▲                        │
      │ 查名字、求值子表达式     │ 调用过程体
      └────── 环境 env ◀────────┘  (名字→值的映射)

二者互相调用，形成"求值—应用"的循环。理解了它，你就懂了**"编程语言本身也是个程序"**——这也完美呼应篇一的环境模型：env 就是那张"名字→值"的表，eval 沿表查找名字，apply 开新帧执行过程体。

坑：手写解释器最容易在"环境链"上出错——eval 求值时必须带着正确的环境去找名字，否则闭包就会"记错老家"。环境模型不是空话，它是解释器正确性的命根子。

本质一句话：解释器 = eval 与 apply 互调的循环，建立在"环境=名字→值映射"之上。

五、声明式编程与 SQL：说要什么，不说怎么做

是什么：前七篇的 Python 都是命令式（imperative）——你告诉计算机一步步怎么做。而 声明式（declarative） 只说要什么，具体怎么执行交给系统。SQL 是最典型的声明式语言。

SELECT name, age
FROM   students
WHERE  age > 20
ORDER  BY age DESC;

这段只声明了"选出年龄>20 的姓名年龄、按年龄降序"，至于数据库是扫描全表还是走索引、先过滤还是先排序，你一概不管。对比命令式 Python：

1	[(s.name, s.age) for s in students if s.age > 20][::-1] # 自己管遍历和排序方向

核心区别：声明式把"逻辑"和"执行"解耦，系统拿到"要什么"后能自由优化（换索引、改连接顺序都不影响你的查询）。命令式把步骤写死，优化空间也写死了。

范式	你写的是	代表	优势
命令式	怎么做（步骤）	Python、C	控制精细、直觉
函数式	映射/组合（Scheme）	Lisp、Haskell	无副作用、易推理
声明式	要什么（约束）	SQL	系统可优化、简洁

本质一句话：声明式 = 说要什么、不说怎么做；逻辑与执行解耦，系统方能自由优化。

收官小结

Scheme：前缀 S-表达式、一切皆表达式、过程原生是一等公民。
尾递归 = 递归调用是最后一步 → 可尾调用优化、空间 O(1)；但 Python 不优化。
解释器 = eval 与 apply 互调，根植于篇一的环境模型。
SQL 是声明式：描述"要什么"，执行交给系统优化。

至此，一个月、8 篇，CS61A 的核心骨架已铺完：

函数 / 环境模型  →  高阶函数 / lambda  →  递归（线性→树形）
        ↓
数据抽象 / 序列  →  可变性与 Link/Tree  →  面向对象（类/继承/MRO）
        ↓
效率 / 迭代器 / 生成器  →  Scheme / 解释器 / 尾递归 / 声明式 SQL

从"名字怎么绑定"到"语言怎么被解释"，你看到的不再是零散语法，而是一套自洽的计算世界观。后续往 数据结构与算法（CS61B）、计算机系统（CS61C） 深入时，这套世界观会一直给你兜底。🐾