The Little Schemer 阅读笔记：用递归思维重新理解编程

为什么这本书很特别

大多数编程书从”变量”和”循环”开始。The Little Schemer（TLS）不这么干。它从 S-expression 开始，用 200 多页的问答对话，教你一件事：递归思维。

TLS 的特点：

没有环境（environment）
没有状态（state）
没有赋值（assignment）
没有副作用（side effects）

只有递归、S-expression 和问不完的问题。

基础：S-expression 与基本操作

S-expression 是什么

Scheme 的所有代码都是 S-expression（Symbolic Expression）：

;; 原子
42
'hello

;; 列表
'(a b c)

;; 嵌套列表
'((a b) (c d))

三个基本操作

(car '(a b c))   ;; => 'a  （第一个元素）
(cdr '(a b c))   ;; => '(b c) （剩余列表）
(cons 'a '(b c)) ;; => '(a b c) （构建列表）

关键理解：列表的递归结构

要么是空列表 '()
要么是 (cons head tail)

这是所有递归模式的基础。

递归的基本模板

模板 1：处理列表

(define process-list
  (lambda (lat)
    (cond
      ((null? lat) ...)        ;; 终止条件：空列表
      (else
       ... (car lat) ...       ;; 处理第一个元素
       (process-list (cdr lat)) ...))))  ;; 递归处理剩余部分

模板 2：处理 S-expression

(define process-sexp
  (lambda (l)
    (cond
      ((atom? l) ...)          ;; 终止条件：原子
      (else
       ... (car l) ...         ;; 处理第一个元素
       (process-sexp (cdr l)) ...))))  ;; 递归处理剩余部分

The Ten Commandments：递归十诫

TLS 总结了 10 条递归定律（“The Ten Commandments”），这是递归编程的黄金法则：

递归处理列表时，先问 (null? lat)

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      (else (or (eq? a (car lat))
                (member? a (cdr lat)))))))

递归处理 S-expression 时，用 atom? 和 (pair? x) 分别处理

(define subst
  (lambda (new old l)
    (cond
      ((null? l) '())
      ((atom? (car l))
       (cond
         ((eq? (car l) old) (cons new (cdr l)))
         (else (cons (car l) (subst new old (cdr l))))))
      (else (cons (subst new old (car l))
                  (subst new old (cdr l)))))))

构建列表时，用 cons 保护元素

(cons (car lat) (rember (car lat) (cdr lat)))

递归时只改变一个参数（至少一个参数趋向终止）
```
(add1 (length (cdr lat)))  ;; (cdr lat) 变短，趋向终止
```

用 (eq? ...) 比较前先确认是原子

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
       (and (eq? (car l1) (car l2))
            (eqlist? (cdr l1) (cdr l2))))
      ((or (atom? (car l1)) (atom? (car l2))) #f)
      (else (and (eqlist? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

简化只在合法时进行
对子列表的属性，用辅助函数

用 collector 累积结果

(define rember-f
  (lambda (test? a l col)
    (cond
      ((null? l) (col '() '()))
      ((test? a (car l))
       (col (cdr l) (cdr l)))
      (else
       (rember-f test? a (cdr l)
         (lambda (newlat seen)
           (col (cons (car l) newlat)
                (cons (car l) seen))))))))

用 letrec 定义辅助函数来抽象重复模式
用 collect 一次构建多个值

高阶函数与 Lambda

Lambda：匿名函数

((lambda (x) (* x x)) 5)  ;; => 25

高阶函数：函数作为参数

(define rember-f
  (lambda (test? a l)
    (cond
      ((null? l) '())
      ((test? a (car l)) (cdr l))
      (else (cons (car l) (rember-f test? a (cdr l)))))))

;; 用法
(rember-f eq? 'a '(a b c))  ;; => '(b c)
(rember-f number? 1 '(a 1 b 2))  ;; => '(a b 2)

Currying：柯里化

(define rember-f
  (lambda (test?)
    (lambda (a l)
      (cond
        ((null? l) '())
        ((test? a (car l)) (cdr l))
        (else (cons (car l)
                     ((rember-f test?) a (cdr l))))))))

;; 用法
((rember-f eq?) 'a '(a b c))  ;; => '(b c)

Y Combinator：不用 define 的递归

TLS 第 9 章的核心：如何在不使用 define 的情况下实现递归？

从自引用到不动点

;; 不能这样做（需要 define）
(define length
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l)))))))

;; 问题：length 如何引用自己？

Y Combinator 的构造

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

;; 用法
((Y (lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l))))))))
 '(a b c))
;; => 3

Y Combinator 的魔力：

(f f) 创建自引用
(lambda (x) ((f f) x)) 延迟求值，避免无限循环
它是”递归的不动点”

元循环解释器：用 Scheme 写 Scheme

TLS 第 10 章的压轴戏：用 Scheme 写一个 Scheme 解释器。

(define value
  (lambda (e)
    (cond
      ((atom? e) e)
      ((eq? (car e) 'quote) (cadr e))
      ((eq? (car e) 'lambda) e)
      ((eq? (car e) 'cond)
       (evcon (cdr e) aenv))
      (else (apply (meaning (car e) aenv)
                   (elist (cdr e) aenv))))))

(define evcon
  (lambda (lines aenv)
    (cond
      ((value (caar lines) aenv)
       (meaning (cadar lines) aenv))
      (else (evcon (cdr lines) aenv)))))

元循环的含义：

解释器和被解释的语言是同一个（Scheme）
不需要外部语言，语言自举
体现了 Lisp homoiconicity（代码即数据）

TLS 的知识图谱

基础
├── S-expression / car / cdr / cons        (Ch1-3)
├── 递归思维与递归模板                       (Ch2-3)
├── 数字运算（递归定义）                     (Ch4)
│
高阶抽象
├── 高阶函数 / map / filter / fold          (Ch5-8)
├── lambda / 闭包                           (Ch8)
├── Collector / continuation 雏形           (Ch8)
│
元编程
├── Y Combinator                           (Ch9)
├── 元循环解释器                             (Ch10)

TLS 的独特教学法

1. 问答驱动

每个概念先用问题引发思考，再给出答案：

Q: What is the value of (rember 'a '(a b c))?
A: (b c)

Q: How did you get it?
A: By consing 'b and 'c.

2. 渐进复杂度

每个例子只比上一个多一个难点：

rember：移除一个元素
multirember：移除所有匹配的元素
multirember-f：用高阶函数抽象
multirember&co：用 collector 累积结果

3. 不用数学记号

全部用代码表达概念，没有复杂的数学符号。

4. The Commandments

总结的 10 条定律，可以作为”口诀”记住。

TLS 对现代编程的启发

1. 递归是基础

即使你用 for 循环，理解递归思维也很重要：

树形结构（JSON、AST）
分治算法
深度优先搜索

2. 不可变数据

TLS 没有 set!，所有数据不可变：

函数式编程的基础
并发安全
易于测试和调试

3. 代码即数据

S-expression 是代码，也是数据：

宏的威力
元编程
解释器和编译器

4. 最小化语言

TLS 用极少的概念构建一切：

quote、if、lambda、cond
其余都是可构建的

阅读建议

谁应该读这本书？

想理解递归思维的程序员
对函数式编程感兴趣的人
想深入理解编程语言基础的开发者
Lisp/Scheme 爱好者

如何阅读？

跟着对话思考：不要只看答案，自己先思考
写代码验证：在 REPL 中运行每个例子
做练习题：每章的练习是关键
多次重读：第一遍可能理解不深，第二遍会有新收获

顺序建议

推荐阅读顺序：

The Little Schemer —— 递归思维
The Seasoned Schemer —— 状态和控制流
The Reasoned Schemer —— 逻辑编程

总结

The Little Schemer 的核心价值：

递归思维：从零开始构建递归的直觉
极简语言：用最少的语法表达最复杂的概念
对话式教学：通过问答引导思考，而非灌输
元编程基础：理解代码即数据，理解解释器

这本书不教你”写代码”，而是教你”像语言设计者一样思考”。