The Reasoned Schemer 阅读笔记：从函数式到关系式编程的范式转换

为什么读这本书

读完《The Little Schemer》（TLS）和《The Seasoned Schemer》（TSS）后，你可能以为 Lisp 家族教到头了。TLS 讲递归，TSS 讲状态和 continuation，还有什么？

The Reasoned Schemer（TRS）给你一个完全不同的答案：关系式编程。

这本书不再教你”怎么计算结果”，而是教你”如何定义关系，让系统帮你找所有满足条件的解”。这是从函数式到逻辑编程的范式转换。

---

核心思想：关系 vs 函数

函数式编程的思维模式

在 TLS 中，我们这样定义 append：

(define (append a b)
  (if (null? a) b
      (cons (car a) (append (cdr a) b))))

这是典型的函数式思维：给定输入，计算输出。

逻辑编程的思维模式

在 TRS 中，我们定义一个关系 appendo：

(define appendo
  (lambda (l s out)
    (conde
      ((null? l) (≡ s out))
      (else
       (fresh (d res)
         (cdro l d)
         (appendo d s res)
         (conso (car l) res out))))))

关键区别：

• 不再是”输入 → 输出”
• 而是”l、s、out 三者之间满足什么关系”
• 可以正向、反向、甚至多向查询

---

miniKanren：逻辑编程的核心语言

TRS 使用的核心语言是 miniKanren —— 一个嵌入在 Scheme 中的微型逻辑编程系统。

基础概念

1. 空关系（≡）、成功（#succeed）、失败（#u）

;; ≡ — 等价关系（unify 的基础）
(≡ v v)  ;; 成功，约束 v 等于自身
(≡ v w)  ;; 尝试让 v 和 w 统一

;; #succeed — 空成功（always true）
;; #u — 失败（always false）

2. fresh：创建逻辑变量

;; fresh 创建新变量，在 body 内作用域
(fresh (x)
  (≡ 'pea x))  ;; 约束 x 等于 'pea

3. unify：统一（unification）

基本规则：

1. 原子 vs 原子：相同则成功，否则失败
2. 变量 vs 值：绑定变量
3. 列表 vs 列表：递归 unify 每个元素
4. 两个变量：共享（以后其中一个绑定，另一个也生效）

;; 统一两个原子
(≡ 'pea 'pea)   ;; 成功
(≡ 'pea 'bean)  ;; 失败

;; 统一嵌套列表
(fresh (x y z)
  (≡ '((a b) c) '((x y) z)))  ;; x='a, y='b, z='c

---

多向查询的威力

appendo 的三种用法

;; 1. 正向：和函数一样
(run* (q) (appendo '(a b) '(c d) q))
;; => ((a b c d))

;; 2. 反向：已知结果和一部分输入，求另一部分
(run* (q) (appendo q '(c d) '(a b c d)))
;; => ((a b))

(run* (q) (appendo '(a b) q '(a b c d)))
;; => ((c d))

;; 3. 双向未知：求解所有可能的划分
(run* (q)
  (fresh (a b)
    (≡ q (cons a b))
    (appendo a b '(a b c d))))
;; => ((() (a b c d))
;;     ((a) (b c d))
;;     ((a b) (c d))
;;     ((a b c) (d))
;;     ((a b c d) ()))

这就是逻辑编程的魅力：一次定义，多向使用。

memberto：成员关系的威力

(define memberto
  (lambda (x l)
    (conde
      ((conso x _ l))
      (else
       (fresh (d)
         (cdro l d)
         (memberto x d))))))

;; 1. 标准用法：x 是否在列表中？
(run* (q) (memberto 'pea '(pea bean soup)))
;; => (_0)

;; 2. 反向：列表中有什么？
(run* (x) (memberto x '(pea bean soup)))
;; => (pea bean soup)

;; 3. 找所有包含 pea 的列表
(run* (l)
  (fresh (a b c d)
    (≡ l (cons a (cons b (cons c (cons d '())))))
    (memberto 'pea l)))
;; => ((pea _0 _1 _2) ...)

---

conde：多分支关系

conde 是 cond 的关系式版本，但语义完全不同：

;; 普通函数式 cond
(cond
  (test1 result1)
  (test2 result2)
  (else result3))
;; 只执行第一个成功的分支

;; 关系式 conde
(conde
  (goal1)
  (goal2)
  (goal3))
;; 尝试所有分支，收集所有成功的解

例子：找列表的前缀：

(define prefixo
  (lambda (l s)
    (conde
      ((null? s) (≡ l '()))            ;; 任意列表的前缀都是空列表
      ((null? l) (≡ s '()))            ;; 空列表的前缀是空列表
      (else
       (fresh (a d a2 d2)
         (conso a d l)
         (conso a2 d2 s)
         (≡ a a2)
         (prefixo d d2))))))

---

切割（cut）：控制搜索空间

逻辑编程的 “cut” 用于修剪搜索树，避免不必要的回溯。

conda（软切）vs condu（硬切）

• conda：如果一个分支失败，回溯到 conda 之前；如果分支成功，后续分支被”切割掉”
• condu：更强的切割，阻止更外层的回溯

例子：查找列表中第一个匹配的元素：

(define find-firsto
  (lambda (pred l out)
    (conda
      ((conso out _ l) (pred out))     ;; 找到第一个满足的，就停
      (else
       (fresh (d)
         (cdro l d)
         (find-firsto pred d out))))))

---

evalo：关系式求值器

这是全书的压轴章节：用关系式编程写一个解释器。

(define evalo
  (lambda (expr val)
    (conde
      ;; 1. 数字求值为自身
      ((numbero expr) (≡ expr val))

      ;; 2. 符号求值为绑定的值
      ((symbolo expr) (lookupo expr env val))

      ;; 3. (if test then else)
      ((fresh (test then else tval)
         (conso 'if (cons test (cons then (cons else '()))))
         (evalo env test tval)
         (conde
           ((true? tval) (evalo env then val))
           (else (evalo env else val)))))

      ;; 4. (lambda (x) body)
      ((fresh (args body)
         (conso 'lambda (cons args (cons body '())))
         ...))

      ;; 5. (func arg)
      ((fresh (func arg fval aval)
         (conso func (cons arg '()))
         (evalo env func fval)
         (evalo env arg aval)
         (applyo fval aval val))))))

evalo 的魔力：可以正向执行（求值）、反向执行（已知结果求输入）、甚至生成满足条件的程序。

;; 正向：执行程序
(run* (q) (evalo '(+ 1 2) q))
;; => (3)

;; 反向：生成能输出 3 的程序
(run* (p) (evalo p 3))
;; => (3 (+ 1 2) (+ 2 1) (+ 3 0) ...)

---

Quine：自输出程序

关系式编程可以生成自复制的程序：

(define quine
  (lambda ()
    (run 1 (p)
      (evalo p p))))  ;; p 求值后等于自身

这在传统编程中很难做到，但在逻辑编程中很自然——把程序本身当作数据。

---

三本书的完整谱系

The Little Schemer
    ↓ 函数式编程：递归、高阶函数、Y 组合子
The Seasoned Schemer
    ↓ 状态和控制流：set!、continuation、CPS
The Reasoned Schemer
    ↓ 关系式编程：unify、miniKanren、非确定性

三本书形成一个完整的编程范式谱系：

1. 纯函数式
2. 带状态的控制流
3. 关系式/声明式

---

与 Prolog 的对比

特性	Prolog	miniKanren (TRS)
语法	专门语法	Scheme 子集
Cut	! 操作符	conda / condu
查询	?- query	(run* (x) goal)
惰性求值	否	可以手动控制
嵌入语言	独立语言	嵌入 Scheme

miniKanren 的优势：

• 可以与 Scheme/函数式代码无缝集成
• 更好的调试和元编程能力
• 更清晰的语义（避免 Prolog 的 negation-as-failure 问题）

---

核心编程模式

1. 关系式定义

不要想”怎么计算结果”，要想”什么关系满足条件”：

;; 函数式思维：append 返回拼接结果
(define (append a b) ...)

;; 逻辑编程思维：appendo 是拼接关系
(define appendo (lambda (a b out) ...))

2. 多向查询

定义一次，多种用法：

(appendo '(a b) '(c d) q)    ;; q = (a b c d)
(appendo q '(c d) '(a b c d)) ;; q = (a b)
(appendo '(a b) q '(a b c d)) ;; q = (c d)

3. 递归关系 + conde

递归 + 多分支 = 强大的非确定性搜索：

(define any-patho
  (lambda (start end path)
    (conde
      ((≡ start end) (≡ path (list start)))
      (else
       (fresh (next rest)
         (edgeo start next)
         (any-patho next end rest)
         (≡ path (cons start rest)))))))

---

常见陷阱

1. 避免无限递归

;; 危险：没有终止条件
(define bad-lookupo
  (lambda (x env val)
    (fresh (y v rest)
      (conso (cons y v) rest env)
      (conde
        ((≡ x y) (≡ val v))
        (else (bad-lookupo x rest val))))))  ;; 可能永远搜索

2. 滥用 cut

• cut 会破坏关系式编程的语义
• 只在性能优化时使用，且理解清楚语义

3. 混淆值和变量

;; 错误：试图 unify 一个非变量
(≡ 'pea (≡ 'bean x))  ;; 不合法

;; 正确
(fresh (x) (≡ 'pea x) (≡ x 'pea))

---

适用场景

The Reasoned Schemer 的核心价值：

1. 关系式思维：不是”计算”，而是”约束和搜索”
2. 多向查询：一次定义，多个方向使用
3. 非确定性：自动处理搜索空间和回溯
4. meta-circular：用关系式编程写关系式解释器

适用场景：

• 需要多向求解的问题（配置生成、逆向工程）
• 复杂约束满足问题
• 需要内省和元编程的解释器
• 自动推理和规则引擎

这本书比 TLS/TSS 更抽象，但一旦理解，会彻底改变你对编程的看法。

---

参考资料

• The Reasoned Schemer - MIT Press
• miniKanren 官方网站
• The Reasoned Schemer 的在线实现
• Logic Programming in miniKanren