Scheme 语言精要：从递归到 Continuation

两本经典对话体教材，用最少的篇幅讲透递归、高阶函数、Y 组合子、元循环解释器、Continuation。本文系统整理了其核心知识点。

---

S-expression：一切皆表达式

Scheme 的世界只有一种数据结构：S-expression。它要么是一个原子（atom），要么是一对（pair）。

;; 原子
42
'hello
#t

;; 列表就是嵌套的 pair
'(1 2 3)  ;; 等价于 (cons 1 (cons 2 (cons 3 '())))

三个基本操作，你只需要这三个就能拆解和构建一切：

;; car — 取第一个元素
(car '(1 2 3))    ;; => 1

;; cdr — 取剩余部分
(cdr '(1 2 3))    ;; => (2 3)

;; cons — 在前面拼接
(cons 1 '(2 3))   ;; => (1 2 3)

判断条件：

(null? '())        ;; #t — 空列表
(atom? 'hello)     ;; #t — 是原子（某些实现没有内置 atom?）
(pair? '(1 2))     ;; #t — 是 pair
(eq? 'a 'a)        ;; #t — 同一个原子

这就是全部的基本数据操作。没有循环，没有下标索引，只有 car、cdr、cons 和递归。

---

递归思维：第一诫

在 Scheme 中，递归是唯一的循环。所有列表操作都遵循同一个模式：

问：列表是否为空？
  是 → 返回基础值
  否 → 处理第一个元素，递归处理剩余部分

例子：判断元素是否在列表中

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)                    ;; 空列表 → 找不到
      ((eq? a (car lat)) #t)              ;; 第一个就是 → 找到了
      (else (member? a (cdr lat))))))     ;; 否则 → 在剩余部分里找

(member? 'tea '(coffee tea milk))   ;; => #t
(member? 'beer '(coffee tea milk))  ;; => #f

例子：移除列表中第一个匹配的元素

(define rember
  (lambda (a lat)
    (cond
      ((null? lat) '())
      ((eq? a (car lat)) (cdr lat))
      (else (cons (car lat)
                  (rember a (cdr lat)))))))

(rember 'mint '(lamb chops and mint jelly))
;; => (lamb chops and jelly)

例子：移除所有匹配的元素

(define multirember
  (lambda (a lat)
    (cond
      ((null? lat) '())
      ((eq? a (car lat))
       (multirember a (cdr lat)))
      (else
       (cons (car lat)
             (multirember a (cdr lat)))))))

(multirember 'cup '(coffee cup tea cup and hick cup))
;; => (coffee tea and hick)

注意规律：把 rember 改成 multirember，只需要把”找到就停”改成”找到也继续递归”。

---

用递归定义算术

Scheme 的数字也可以纯递归定义（不用 +、-）：

;; 定义加法：一个一个数
(define o+
  (lambda (n m)
    (cond
      ((zero? m) n)
      (else (o+ (add1 n) (sub1 m))))))

(o+ 3 4)  ;; => 7

;; 定义乘法：连续加
(define o×
  (lambda (n m)
    (cond
      ((zero? m) 0)
      (else (o+ n (o× n (sub1 m)))))))

(o× 3 4)  ;; => 12

这不只是数学游戏——它展示了所有计算都可以归结为递归。

---

高阶函数：Lambda the Ultimate

函数是一等公民。你可以把函数当参数传，当返回值返。

map — 对每个元素做变换

(define my-map
  (lambda (f lst)
    (cond
      ((null? lst) '())
      (else (cons (f (car lst))
                  (my-map f (cdr lst)))))))

(my-map add1 '(1 2 3))        ;; => (2 3 4)
(my-map (lambda (x) (* x x)) '(1 2 3 4))  ;; => (1 4 9 16)

filter — 过滤元素

(define my-filter
  (lambda (pred lst)
    (cond
      ((null? lst) '())
      ((pred (car lst))
       (cons (car lst) (my-filter pred (cdr lst))))
      (else (my-filter pred (cdr lst))))))

(my-filter even? '(1 2 3 4 5 6))  ;; => (2 4 6)

fold — 归约（TLS 中叫 collector 模式）

foldr（右折叠）：

(define foldr
  (lambda (f init lst)
    (cond
      ((null? lst) init)
      (else (f (car lst)
               (foldr f init (cdr lst)))))))

;; 用 foldr 重写 sum
(foldr + 0 '(1 2 3 4 5))  ;; => 15

;; 用 foldr 重写 map
(define map-via-fold
  (lambda (f lst)
    (foldr (lambda (x acc) (cons (f x) acc)) '() lst)))

foldl（左折叠）：

(define foldl
  (lambda (f init lst)
    (cond
      ((null? lst) init)
      (else (foldl f (f (car lst) init) (cdr lst))))))

(foldl cons '() '(1 2 3))  ;; => (3 2 1) — 注意方向反转

Collector 模式：continuation 的雏形

TLS 第 8 章最关键的概念。把”怎么处理结果”作为参数传进去：

;; 不返回列表，而是把结果"倒进"一个 collector
(define multirember&co
  (lambda (a lat col)
    (cond
      ((null? lat) (col '() '()))
      ((eq? a (car lat))
       (multirember&co a (cdr lat)
         (lambda (newlat seen)
           (col newlat (cons (car lat) seen)))))
      (else
       (multirember&co a (cdr lat)
         (lambda (newlat seen)
           (col (cons (car lat) newlat) seen)))))))

;; 用法：收集匹配和不匹配的两个列表
(multirember&co 'cup
  '(coffee cup tea cup and hick cup)
  (lambda (not-matched matched)
    (list not-matched matched)))
;; => ((coffee tea and hick) (cup cup cup))

为什么重要：这个模式是 CPS（Continuation-Passing Style）的前身。理解了 collector，后面理解 continuation 就顺理成章。

---

Y 组合子：不用 define 实现递归

这是 TLS 第 9 章的高潮。问题是：如果没有 define，怎么写递归函数？

推导过程

第一步：正常写法（用了 define）

(define length
  (lambda (lst)
    (cond
      ((null? lst) 0)
      (else (add1 (length (cdr lst)))))))

第二步：把函数自身作为参数传给自己

;; 把 length 绑定变成参数
(lambda (self)
  (lambda (lst)
    (cond
      ((null? lst) 0)
      (else (add1 (self (cdr lst)))))))

第三步：问题来了——self 调用时传什么？需要把自己再传一次：

;; 不完全解法：只能手动嵌套
((lambda (self)
   (lambda (lst)
     (cond
       ((null? lst) 0)
       (else (add1 ((self self) (cdr lst)))))))
 (lambda (self)
   (lambda (lst)
     (cond
       ((null? lst) 0)
       (else (add1 ((self self) (cdr lst))))))))

第四步：提取重复 → Y 组合子

(define Y
  (lambda (f)
    ((lambda (x) (f (lambda (v) ((x x) v))))
     (lambda (x) (f (lambda (v) ((x x) v)))))))

;; 使用：不需要 define 就能递归
((Y (lambda (self)
      (lambda (lst)
        (cond
          ((null? lst) 0)
          (else (add1 (self (cdr lst))))))))
 '(a b c d))  ;; => 4

Y 组合子本质上是一个不动点组合器：f(Y(f)) = Y(f)。它让任何函数都能引用自身，而不需要命名。

---

元循环解释器：用 Scheme 写 Scheme

TLS 第 10 章用大约一页代码实现了 Scheme 的核心求值器：

(define value
  (lambda (e)
    (cond
      ((atom? e) e)                          ;; 原子 → 自求值 / 查环境
      ((eq? (car e) 'quote) (cadr e))        ;; (quote x) → x
      ((eq? (car e) 'lambda) e)              ;; lambda → 返回自身（闭包）
      ((eq? (car e) 'cond) (eval-cond (cdr e))) ;; cond → 逐条判断
      (else (apply (value (car e))           ;; 函数调用
                   (evlis (cdr e)))))))

;; apply — 调用函数
(define apply
  (lambda (f args)
    (cond
      ((atom? f) ...)              ;; 基本操作符
      ((eq? (car f) 'lambda)       ;; 用户定义函数
       (value (caddr f)            ;; 函数体
              ...)))))             ;; 绑定参数到环境

;; evlis — 求值参数列表
(define evlis
  (lambda (lst)
    (cond
      ((null? lst) '())
      (else (cons (value (car lst))
                  (evlis (cdr lst)))))))

这揭示了 Lisp 家族的一个深刻特性：语言的核心极其简单，整个语言可以用自身来定义。

---

作用域与绑定：let / let* / letrec

TSS 第 12-13 章引入了局部绑定。

let — 并行绑定

(let ((x 1)
      (y 2))
  (+ x y))  ;; => 3

;; 注意：x 的值在绑定 y 时还看不到
(let ((x 1)
      (y (+ x 1)))  ;; 错误！x 还未绑定
  y)

let* — 顺序绑定

(let* ((x 1)
       (y (+ x 1)))  ;; 正确，x 已经绑定了
  y)  ;; => 2

letrec — 递归绑定

;; letrec 允许绑定的函数互相引用（包括引用自身）
(letrec ((even? (lambda (n)
                  (if (zero? n) #t (odd? (sub1 n)))))
         (odd? (lambda (n)
                 (if (zero? n) #f (even? (sub1 n))))))
  (even? 10))  ;; => #t

三者的区别：

let    → 所有绑定同时生效（互相看不到）
let*   → 绑定从左到右依次生效
letrec → 所有绑定互相可见（用于递归/互递归）

---

状态与 Mutation：set!

TSS 第 14-15 章引入了可变状态。纯函数式世界被打破。

set! — 赋值

(define counter 0)

(define count!
  (lambda ()
    (set! counter (+ counter 1))
    counter))

(count!)  ;; => 1
(count!)  ;; => 2
(count!)  ;; => 3

用 cons cell 做可变引用（Box）

;; 用一个单元素列表模拟可变引用
(define (box val) (list val))
(define (unbox b) (car b))
(define (set-box! b val) (set-car! b val))

(define b (box 42))
(unbox b)         ;; => 42
(set-box! b 100)
(unbox b)         ;; => 100

用 mutation 实现队列

(define (make-queue)
  (let ((front '()) (rear '()))
    (lambda (msg . args)
      (cond
        ((eq? msg 'enqueue)
         (let ((new-pair (list (car args))))
           (if (null? front)
               (begin (set! front new-pair)
                      (set! rear new-pair))
               (begin (set-cdr! rear new-pair)
                      (set! rear new-pair)))))
        ((eq? msg 'dequeue)
         (let ((val (car front)))
           (set! front (cdr front))
           val))
        ((eq? msg 'empty?)
         (null? front))))))

(define q (make-queue))
(q 'enqueue 1)
(q 'enqueue 2)
(q 'enqueue 3)
(q 'dequeue)  ;; => 1
(q 'dequeue)  ;; => 2

重要提醒：mutation 打破了引用透明性，是 bug 的温床。能用纯函数解决的，不要用 mutation。

---

Continuation：程序的未来

TSS 第 17-20 章的核心。Continuation 是”程序剩余要做的所有事情”的抽象。

call/cc — 捕获当前 continuation

;; Escape continuation：提前退出
(define (find-first pred lst)
  (call/cc
    (lambda (return)
      (for-each
        (lambda (x)
          (when (pred x)
            (return x)))     ;; 直接跳出，返回找到的值
        lst)
      #f)))

(find-first even? '(1 3 5 4 7))   ;; => 4
(find-first even? '(1 3 5 7))     ;; => #f

Coroutine：用 continuation 实现协程

(define resume #f)

(define (producer)
  (let loop ((n 1))
    (display (format "生产: ~a\n" n))
    (call/cc (lambda (k)
               (set! resume k)     ;; 保存自己的 continuation
               (consumer-continuation n))))
    (loop (+ n 1))))

(define consumer-continuation #f)

(define (consumer val)
  (display (format "消费: ~a\n" val))
  (call/cc (lambda (k)
             (set! consumer-continuation k)
             (resume 'continue))))  ;; 跳回 producer

CPS（Continuation-Passing Style）手写转换

把所有函数改成”接收一个 continuation 参数，把结果传给它”：

;; 直接风格
(define (fact n)
  (if (zero? n) 1
      (* n (fact (sub1 n)))))

;; CPS 风格
(define (fact/k n k)
  (if (zero? n)
      (k 1)
      (fact/k (sub1 n)
              (lambda (r)
                (k (* n r))))))

(fact/k 5 (lambda (x) x))  ;; => 120

CPS 的意义：

1. 所有函数调用都是尾调用 — 不会爆栈
2. 控制流显式化 — continuation 就是”接下来做什么”
3. 编译器的基础 — 很多编译器内部会把代码转成 CPS

用 continuation 实现回溯搜索

(define fail-stack '())

(define (amb choices)
  (if (null? choices)
      (if (null? fail-stack)
          (error "no more choices")
          ((car fail-stack)))      ;; 回溯
      (call/cc
        (lambda (k)
          (set! fail-stack
                (cons (lambda () (k (amb (cdr choices))))
                      fail-stack))
          (car choices)))))

(define (assert condition)
  (unless condition
    (if (null? fail-stack)
        (error "assertion failed")
        ((car fail-stack)))))      ;; 条件不满足 → 回溯

;; 使用：自动搜索满足条件的解
(let ((x (amb '(1 2 3 4 5)))
      (y (amb '(1 2 3 4 5))))
  (assert (= (+ x y) 7))
  (assert (> x y))
  (list x y))  ;; => (4 3) 或 (5 2)

---

知识图谱总览

基础
├── S-expression / car / cdr / cons
├── 递归思维与递归模板
├── 数字运算（递归定义）
│
高阶抽象
├── 高阶函数 / map / filter / fold
├── lambda / 闭包
├── Collector 模式（continuation 雏形）
│
元编程
├── Y 组合子（不用 define 的递归）
├── 元循环解释器（Scheme 写 Scheme）
│
状态与控制
├── let / let* / letrec / 作用域
├── set! / mutation / 可变数据结构
├── call/cc / continuation
├── CPS 转换
├── 回溯 / 非确定性计算

递归十诫（The Ten Commandments）

这些是 TLS 总结的递归编写准则，堪称 Scheme 编程的”武功心法”：

1. 处理列表先问 null?
2. 处理 S-expr 先问 atom? 和 pair?
3. 用 cons 构建列表时保护元素
4. 递归时至少一个参数趋向终止
5. 用 eq? 比较前先确认是原子
6. 简化只在合法时进行
7. 对子列表的属性用辅助函数
8. 用 collector 累积结果
9. 用 letrec 抽象重复模式
10. 用 collect 一次构建多个值

---

参考书籍

• The Little Schemer — Daniel P. Friedman & Matthias Felleisen
• The Seasoned Schemer — Daniel P. Friedman & Matthias Felleisen
• 后续：The Reasoned Schemer（逻辑编程）、The Little Typer（依赖类型）