The Seasoned Schemer 阅读笔记：状态、Continuation 与控制流

从 TLS 到 TSS

读完《The Little Schemer》（TLS）后，你可能以为：

递归是唯一需要的控制流
没有状态，没有副作用，一切皆纯函数

《The Seasoned Schemer》（TSS）告诉你：现实世界需要状态和控制流。

TSS 引入了 TLS 没有讲的概念：

状态（state）—— 用 set! 修改变量
Continuation —— 用 call/cc 捕获和调用延续
CPS（Continuation-Passing Style）—— 手动转换控制流

状态与 Mutation

TLS 的纯函数式世界

TLS 中，数据是不可变的：

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

;; 每次调用都返回新列表，原列表不变
(define l '(a b c))
(define l2 (rember 'a l))
;; l 仍然是 '(a b c)
;; l2 是 '(b c)

TSS 的可变世界

TSS 引入 set!，允许修改已绑定的变量：

(define x 10)
(set! x (+ x 1))  ;; x 变成 11

Box 模式：模拟可变引用

由于 Scheme 的变量绑定是词法作用域，不能用 set! 修改其他函数的变量。TSS 用 cons cell 模拟可变引用（“Box” 模式）：

(define make-box
  (lambda (initial)
    (cons initial '())))

(define box-get
  (lambda (box)
    (car box)))

(define box-set!
  (lambda (box new-value)
    (set-car! box new-value)))

;; 用法
(define my-box (make-box 42))
(box-get my-box)           ;; => 42
(box-set! my-box 100)
(box-get my-box)           ;; => 100

关键理解：

cons 创建一个包含两个元素的列表
set-car! 修改第一个元素
这个列表就是”可变引用”的容器

词法作用域与绑定

let：并行绑定

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

;; 绑定是并行的，不能引用同一 let 内的其他变量
(let ((x 1)
      (y (+ x 1)))  ;; 错误：x 未定义
  (+ x y))

let*：顺序绑定

(let* ((x 1)
       (y (+ x 1)))  ;; 正确：x 已定义
  (+ x y))  ;; => 3

letrec：递归绑定

(letrec ((even?
           (lambda (n)
             (if (= n 0)
                 #t
                 (odd? (- n 1)))))
         (odd?
           (lambda (n)
             (if (= n 0)
                 #f
                 (even? (- n 1))))))
  (odd? 5))  ;; => #t

关键理解：

letrec 允许互递归
绑定值在所有绑定完成后才求值
这使得 even? 可以引用 odd?，反之亦然

状态与数据结构

队列（Queue）的实现

用状态实现队列，需要维护头尾指针：

(define make-queue
  (lambda ()
    (let ((front (list 'placeholder))
          (rear '()))
      (set! rear front)
      (lambda (msg . args)
        (cond
          ((eq? msg 'enqueue)
           (let ((item (car args)))
             (set-cdr! rear (list item))
             (set! rear (cdr rear))))
          ((eq? msg 'dequeue)
           (if (eq? front rear)
               'empty
               (let ((item (cadr front)))
                 (set! front (cdr front))
                 item)))
          (else (error "Unknown message" msg)))))))

;; 用法
(define q (make-queue))
(q 'enqueue 'a)
(q 'enqueue 'b)
(q 'dequeue)  ;; => 'a
(q 'dequeue)  ;; => 'b

关键理解：

用 set-cdr! 修改列表的尾部
维护头尾指针，实现 O(1) 的入队和出队
这是”消息传递”风格的面向对象编程

Continuation：控制的捕获与调用

什么是 Continuation？

Continuation 是”接下来要做什么”——当前计算的后续。

;; 普通函数调用
(+ 1 (* 2 3))
;; 计算顺序：
;; 1. (* 2 3) => 6
;; 2. (+ 1 6) => 7
;; 3. 返回 7

;; Continuation 的视角：
;; (* 2 3) 的 continuation 是 "(lambda (x) (+ 1 x))"
;; 计算过程：
;; 1. 调用 call/cc，捕获当前 continuation
;; 2. 计算 (* 2 3)
;; 3. 把结果传给 continuation
;; 4. continuation 完成剩余计算

call/cc：捕获 Continuation

(call/cc
  (lambda (k)
    ...))  ;; k 是当前 continuation

例子 1：非局部退出

(define my-break
  (lambda (lst)
    (call/cc
      (lambda (break)
        (map (lambda (x)
               (if (> x 10)
                   (break 'found))
               x)
             lst)))))

(my-break '(1 2 3 11 4))  ;; => 'found

关键理解：

call/cc 捕获当前 continuation
调用 break 相当于”返回到外层”
这比 throw/catch 更强大，可以捕获任意位置的 continuation

例子 2：Coroutine（协程）

(define coroutine-a
  (lambda (k)
    (display "A")
    (newline)
    (call/cc (lambda (k2)
                (set! resume-b k2)
                (k)))))

(define coroutine-b
  (lambda (k)
    (display "B")
    (newline)
    (call/cc (lambda (k2)
                (set! resume-a k2)
                (k)))))

(define resume-a '())
(define resume-b '())

;; 启动
(call/cc (lambda (k) (set! resume-a k)))
(coroutine-a resume-a)  ;; 输出 "A"，切换到 B
(coroutine-b resume-b)  ;; 输出 "B"，切换到 A
(resume-a)               ;; 输出 "A"，切换到 B
(resume-b)               ;; 输出 "B"，...

关键理解：

Continuation 可以保存和恢复执行状态
这就是协程的原理
比 generator 更底层、更强大

CPS（Continuation-Passing Style）

什么是 CPS？

CPS 是一种编程风格，每个函数都显式接收一个 continuation 参数。

从直接递归到 CPS

直接递归：

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (sum (cdr lst))))))

CPS 转换：

(define sum-cps
  (lambda (lst k)
    (if (null? lst)
        (k 0)
        (sum-cps (cdr lst)
          (lambda (rest-sum)
            (k (+ (car lst) rest-sum)))))))

;; 用法
(sum-cps '(1 2 3)
  (lambda (result)
    result))  ;; => 6

CPS 的威力：

显式控制流：continuation 参数代表”下一步要做什么”
无栈尾递归：不需要调用栈，尾调用变成普通函数调用
可组合的中间操作：可以在任意点插入处理逻辑

CPS 转换规则

每次调用都传入 continuation
```
(f x y)  →  (f x y k)
```
普通值传给 continuation
```
42  →  (k 42)
```

函数调用嵌套时，continuation 也嵌套

(+ (f x) (g y))

;; CPS 版本
(f x
  (lambda (fx)
    (g y
      (lambda (gy)
        (k (+ fx gy))))))

回溯与非确定性

用 Continuation 实现回溯

TSS 第 20 章用 continuation 实现类似 Prolog 的搜索：

(define amb
  (lambda (choices)
    (call/cc
      (lambda (k)
        (if (null? choices)
            (fail)
            (k (car choices))
            (amb (cdr choices)))))))

(define fail
  (lambda ()
    (error "No more choices")))

;; 用法：生成 1x1 到 3x3 的乘法表
(define test-amb
  (lambda ()
    (let ((x (amb '(1 2 3)))
          (y (amb '(1 2 3))))
      (* x y))))

;; 调用 call/cc 捕获 continuation，回溯可以"撤销"之前的选择

关键理解：

amb 是”非确定性选择”
如果当前选择导致失败，回溯到上一个 amb
这就是 Prolog 搜索的本质

TLS vs TSS：两种编程范式

维度	TLS	TSS
状态	无状态	有状态（`set!`）
副作用	无副作用	有副作用
控制流	递归	递归 + Continuation
数据结构	不可变	可变（`set-car!`、`set-cdr!`）
思维模式	纯函数式	命令式 + 函数式混合

TSS 的价值

状态管理：理解如何安全地使用状态
控制流抽象：用 continuation 捕获和恢复执行
CPS 转换：手动转换控制流，理解编译器优化
非确定性计算：实现搜索和回溯

Continuation 的哲学

Continuation 是什么？

;; 程序执行是一个"continuation"的链
(call/cc (lambda (k) ...))
;; k = "接下来要做什么"

;; 如果用 continuation 重新表达整个程序
(define run
  (lambda (expr env k)
    (cond
      ((number? expr) (k expr))
      ((symbol? expr) (k (lookup expr env)))
      ...)))

Continuation vs Exception

维度	Continuation	Exception
捕获位置	任意位置	当前调用栈
调用次数	多次	一次
灵活性	高（可以存储、传递、调用）	低（只能抛出和捕获）

TSS 的知识图谱

基础（TLS 复习）
├── 递归思维
├── S-expression / car / cdr / cons
│
绑定与作用域
├── let / let* / letrec
├── 词法作用域
├── 互递归
│
状态与 Mutation
├── set!
├── Box 模式
├── set-car! / set-cdr!
├── 有状态数据结构（队列、栈）
│
Continuation
├── call/cc 基本用法
├── Escape continuation
├── Coroutine
│
CPS
├── CPS 转换
├── 手动转换递归
├── CPS 的威力
│
非确定性
├── amb 操作符
├── 回溯搜索
└── 与逻辑编程的关系

现代编程中的 Continuation

JavaScript 的 Promise

Promise 本质上是 continuation 的简化版本：

// Continuation 风格
fetch(url)
  .then(response => response.json())
  .then(data => console.log(data))
  .catch(error => console.error(error));

// 等价于 CPS
fetch(url, (response) => {
  response.json((data) => {
    console.log(data);
  });
});

Go 的 defer

defer 是一种特殊的 continuation：

func readFile(filename string) {
    f, _ := os.Open(filename)
    defer f.Close()  // 函数退出时执行

    // ... 处理文件
}

React 的 Hooks

React Hooks 捕获了组件的”continuation”（状态和副作用）：

useEffect(() => {
  const subscription = subscribe();
  return () => unsubscribe();  // cleanup 是 continuation
}, []);

阅读建议

谁应该读这本书？

读完 TLS，想深入理解状态和控制流的程序员
对 continuation、CPS、协程感兴趣的人
想理解编程语言实现原理的开发者
Lisp/Scheme 进阶学习者

前置知识

必须先读 TLS：TSS 假设你已经掌握递归思维
熟悉基础 Scheme：car、cdr、cons、递归
理解词法作用域：let、闭包、环境

如何阅读？

在 REPL 中运行代码：TSS 的例子都需要实际运行
手动做 CPS 转换：这是理解 continuation 的关键
实现有状态数据结构：队列、栈、链表
写 coroutine 示例：理解 continuation 如何切换执行流

总结

The Seasoned Schemer 的核心价值：

状态管理：理解如何安全地使用状态和副作用
Continuation：掌握最强大的控制流抽象
CPS 转换：理解编译器如何优化尾递归
非确定性计算：实现搜索和回溯

TLS 教你”纯函数式思维”，TSS 教你”如何在现实世界中使用状态和控制流”。两本书合起来，就是完整的函数式编程谱系。

The Seasoned Schemer 阅读笔记：状态、Continuation 与控制流

从 TLS 到 TSS

状态与 Mutation

TLS 的纯函数式世界

TSS 的可变世界

Box 模式：模拟可变引用

词法作用域与绑定

let：并行绑定

let*：顺序绑定

letrec：递归绑定

状态与数据结构

队列（Queue）的实现

Continuation：控制的捕获与调用

什么是 Continuation？

call/cc：捕获 Continuation

例子 2：Coroutine（协程）

CPS（Continuation-Passing Style）

什么是 CPS？

从直接递归到 CPS

CPS 转换规则

回溯与非确定性

用 Continuation 实现回溯

TLS vs TSS：两种编程范式

TSS 的价值

Continuation 的哲学

Continuation 是什么？

Continuation vs Exception

TSS 的知识图谱

现代编程中的 Continuation

JavaScript 的 Promise

Go 的 defer

React 的 Hooks

阅读建议

谁应该读这本书？

前置知识

如何阅读？

总结

参考资料

📝 文章反馈