SICP_scheme_笔记

2026年1月3日 · 1201 字 · 6 分钟

摘要

本文为《计算机程序的构造和解释》（SICP，CS61A 南大引进版）scheme部分课程核心笔记，聚焦程序设计的底层逻辑与核心思想，旨在帮助学习者搭建“知其然更知其所以然”的编程认知框架。适合正在学习 CS61A 课程的学习者梳理知识体系，也可作为编程入门者夯实基础、理解程序设计本质的参考资料。

SICP Note -> Scheme

主题一：Scheme 基础与求值 (Scheme Basics and Evaluation)

主题概述

Scheme 是一种 Lisp 方言，其核心特点是程序由表达式 (Expressions) 构成，并且代码与数据结构高度统一。理解 Scheme 的求值规则，尤其是调用表达式 (Call Expressions) 和特殊形式 (Special Forms) 的区别，是关键。

核心概念

1. 表达式的分类 (Types of Expressions)

Scheme 程序由两种表达式构成：

原子表达式 (Atomic Expressions / Atoms) ：不可再分割的基本值。
- 自求值 (Self-evaluating): 数字 (3, -10)、布尔值 (#t, #f) 。
- 符号 (Symbols): 绑定到值的名称 (+, modulo, x) 。
组合 (Combinations) ：形如 (<operator> <operand1> <operand2> ...) 。它们是调用表达式或特殊形式表达式 。

2. 调用表达式求值 (Call Expression Evaluation)

调用表达式将一个过程 (Procedure) 应用于一组参数 (Arguments) 。

求值三步法:

对 运算符 (Operator) 求值，得到一个过程。

从左到右对所有 操作数 (Operands) 求值，得到参数。

将过程应用于参数。

例：

scm> (- (+ 7 (* 4 6)) (* 3 5))
; 1. (* 4 6) -> 24
; 2. (+ 7 24) -> 31
; 3. (* 3 5) -> 15
; 4. (- 31 15) -> 16
16

3. 特殊形式 (Special Forms)

特殊形式的求值规则不同于标准的调用表达式，它们的运算符（如 define, if, lambda）不一定先求值，且操作数不一定全部求值。

特殊形式	英文标注	语法	求值规则
定义	define	`(define <name> <expr>)`	1. 求值 `<expr>` 。 2. 将结果值绑定到当前框架的 `<name>` 上。
条件	if	`(if <predicate> <if-true> <if-false>)`	1. 求值 `<predicate>` 。 2. 如果结果不是 `#f` (唯一 Falsy 值) ，求值并返回 `<if-true>` ；否则求值并返回 `<if-false>` 。
过程	lambda	`(lambda (<params>) <body>)`	创建并返回一个 lambda 过程 (Procedure) 。不求值函数体 `<body>`，函数体在过程被调用时才求值。

define 简化形式 (Function Shorthand): (define (square x) (* x x)) 等同于 (define square (lambda (x) (* x x))) 。

主题二：数据抽象：Pairs 与 Lists (Data Abstraction: Pairs and Lists)

主题概述

Scheme 中唯一的序列类型是链表 (Linked List) 。链表是通过基本的构建块对 (Pairs) 构成的。

核心概念 (Core Concepts)

1. 对 (Pairs)

对是使用 cons 表达式创建的基本结构。

cons: 构造一个对。
- (cons <first> <second>)
car: 选择对中的第一个元素 (Head) 。
cdr: 选择对中的第二个元素 (Tail) 。

2. 链表 (Linked Lists)

链表是通过递归地使用 cons 构造对，并以特殊符号 nil (空列表) 终止而形成的序列结构。

nil: 表示空列表 (Empty List) 。
链表结构：第二个元素 (cdr) 必须是另一个对或 nil 。

例题：链表构造

scm> (cons 1 (cons 2 nil))
(1 2) ; 列表的表示形式

scm> (define x (cons 1 (cons 2 nil)))
scm> (car x)
1
scm> (cdr x)
(2) ; 结果仍然是一个列表 (一个对，其 car 是 2，cdr 是 nil)

主题三：符号编程与引用 (Symbolic Programming and Quotation)

主题概述

在 Scheme 中，符号 (Symbols) 通常求值为其绑定的值。引用 (Quotation) 允许我们直接引用符号本身，而不是它的值。这对于将 Scheme 代码结构作为数据处理（符号编程）至关重要。

核心概念 (Core Concepts)

1. 引用 (`quote` 或 `'`)

作用: 阻止表达式被求值，而是将表达式本身作为值返回。
使用方式:
- 长形式: (quote <expr>)
- 短形式: '<expr>

例题：引用符号

scm> (define a 1)
scm> (list a 2)
(1 2) ; a 被求值为 1

scm> (list 'a 2)
(a 2) ; 'a 被引用，求值为符号 a 本身

2. 引用组合 (Quoting Combinations)

引用也可以应用于组合表达式，使其成为一个列表数据结构。

例题：引用列表

scm> '(a b c)
(a b c) ; 返回列表 (a b c)
scm> (car '(a b c))
a       ; car 选择列表的第一个元素
scm> (cdr '(a b c))
(b c)   ; cdr 选择列表的剩余部分

主题四：尾递归 (Tail Recursion)

主题概述

Scheme 语言不内置迭代 (Iteration) 结构，循环通常通过递归 (Recursion) 实现。尾递归 (Tail Recursion) 是一种特殊的递归形式，支持尾调用优化 (Tail Call Optimization)，能像迭代一样高效运行，使用常数 (Constant) 数量的帧 (Frames) 。

核心概念

1. 尾上下文与尾调用 (Tail Context and Tail Call)

尾上下文 (Tail Context): 表达式在尾上下文中，意味着它是在函数调用中求值的最后一步。在它求值/应用之后，没有其他操作会进行。
尾调用 (Tail Call): 发生在尾上下文中的函数调用。
尾递归 (Tail Recursion): 尾调用调用了函数自身 。

2. 尾调用优化 (Tail Call Optimization, TCO)

如果 Scheme 语言支持 TCO，一个尾递归函数只会开启常数数量的帧，从而避免栈溢出，效率等同于迭代。

3. 识别尾上下文 (Identifying Tail Contexts)

是尾上下文 (Tail Contexts):
- lambda（函数）的最后一个 body 子表达式。
- if 中的 <if-true> 和 <if-false> (前提是 if 表达式本身在尾上下文中)。
- and, or, begin, let 中的最后一个子表达式。
不是尾上下文 (Non-Tail Contexts):
- 在 *, +, - 等操作符下作为操作数 (Operand) 的递归调用。因为操作数求值后，还需要进行操作符的运算。

例题：非尾递归阶乘 (Non-Tail Recursive Factorial)

(define (fact n)
  (if (= n 0)
      1
      # 递归调用 (fact (- n 1)) 的结果必须和 n 相乘
      # 因此 (fact ...) 不在尾上下文，需要保留帧 f1, f2, ...
      (* n (fact (- n 1)))))

4. 编写尾递归函数 (Writing Tail Recursive Functions)

要将非尾递归函数转换为尾递归，通常需要引入一个辅助函数 (Helper Function) 和一个累加器 (Accumulator) 参数。

目标: 将所有等待的计算（例如上面的 * n）作为参数，传递给下一次递归调用。
累加器 (Accumulator): 存储到目前为止的计算结果。

例题：尾递归阶乘 (Tail Recursive Factorial)

(define (fact n)
  # 引入辅助函数 fact-tail
  (define (fact-tail n result) ; result 就是累加器
    (if (<= n 1)
        result
        # 最后一步操作是 (fact-tail ...)，
        # 这是一个尾调用，无需保留当前帧。
        (fact-tail (- n 1) (* n result)))) 
  (fact-tail n 1)) # 初始调用，累加器从 1 开始

主题五：表达式作为数据 (Expressions As Data)

主题概述

Scheme 的核心理念是代码即数据 (Code as Data)。由于 Scheme 表达式（组合）本身就是列表，我们可以将代码结构当作普通数据来操作。

核心概念

1. 表达式的表示与求值 (Representation and Evaluation)

表达式的类型: 在 Scheme 中，表达式要么是原始表达式 (primitive expressions)，要么是列表 (lists)。
引用 (Quoting): ‘<expr> 或 (quote <expr>) 阻止表达式求值，返回表达式本身（即一个数据结构）。
eval 函数: 接收一个未求值 (unevaluated) 的表达式（数据），并对其进行求值。
例题:

scm> '(+ 1 2) ; 引用，返回列表数据
(+ 1 2)
scm> (eval '(+ 1 2)) ; 对该列表进行求值
3

表达式的操作: 我们可以将表达式赋值给变量、作为参数传递给函数、甚至在函数内创建并返回新的表达式。

主题六：辅助特殊形式 (Auxiliary Special Forms)

主题概述

begin 和 let 是 Scheme 中常用的特殊形式，用于控制求值顺序和局部变量的创建。

核心概念

1. `begin` (顺序执行)

作用: begin 接收任意数量的子表达式。它会按顺序 (in order) 求值这些子表达式，并以最后一个子表达式的值作为整个 begin 表达式的值。
用途: 当你需要在一个预期只有一个表达式的位置（如函数体）执行多个带有副作用的操作时，begin 非常有用。
例题:

scm> (begin (define x 2) (define x (+ x 1)) x)
3 ; 返回最后一个表达式 x 的值

2. `let` (局部绑定)

作用: let 用于创建临时的局部变量绑定，仅在 let 的主体 (body) 中有效。
绑定规则: 所有的 symbol 都与其对应的 expr 的值并行 (in parallel) 绑定。这意味着一个绑定不能引用同一 let 表达式中定义的其他绑定。
语法:

(let ((symbol1 expr1)
      (symbol2 expr2)
      ...)
  <body>)

主题七：宏原理 (Macro Principles)

主题概述

宏 (Macros) 是一种元编程 (Metaprogramming) 工具，它允许用户在程序求值之前转换程序的代码结构，从而扩展语言的语法。

核心概念

1. 定义宏 (`define-macro`)

语法: (define-macro (<name> <params>) <body>)。
宏与过程的区别:
过程 (Procedure): 接收值 (values) 作为参数，返回值。
宏 (Macro): 接收表达式 (expressions) 作为参数，返回表达式（代码）。

2. 宏的求值流程 (Macro Evaluation) 【核心考点】

宏调用的求值流程有别于普通函数调用：

不求值操作数 (Operands Not Evaluated): 宏的操作数不会像普通函数调用那样被求值。
传递表达式: 操作数（表达式本身）作为参数传递给宏过程。
宏转换: 宏过程执行，返回一个新的表达式 (a new expression)。
再次求值: 解释器会立即对宏返回的新表达式进行求值 (evaluated)。

3. 宏的用途 (Writing Macros)

编写宏时，关键是思考具有等效行为的表达式是什么。宏的目的是将自定义的语法转换为等效的 Scheme 基本语法。

例题：for 宏: 转换 (for x in '(1 2 3 4) do (* x x)) 为 (map (lambda (x) (* x x)) '(1 2 3 4))。

(define-macro (for sym in vals do expr)
  (list 'map (list 'lambda (list sym) expr) vals))

主题八：准引用 (Quasi-Quotation)

主题概述

在宏中，我们经常需要构造新的列表（表达式）。准引用 (Quasi-Quotation) 允许在引用 (Quoting) 表达式的同时，有选择地对其中的部分子表达式进行求值，大大简化了代码生成。

核心概念

符号	英文标注	名称	作用
```	Quasiquote	准引用	允许列表中的大部分内容被视为字面值（像 `quote` 一样）。
`,`	Unquote	取消引用	必须出现在准引用 ```` 内部。紧跟其后的表达式会被求值，然后将其值插入到构造的列表中。

例题：使用准引用重写 for 宏

(define-macro (for sym vals expr)
  ; 整个结构是准引用的 (`)，大部分是字面值
  ; ,sym, ,expr, ,vals 在宏应用时会被求值并替换到相应位置
  `(map (lambda (,sym) ,expr) ,vals))

( 和 map 是字面符号。
,sym 求值结果是符号 x，被插入到 lambda 的参数列表中。
,expr 求值结果是表达式 (* x x)，被插入到 lambda 的函数体中。
,vals 求值结果是表达式 '(1 2 3 4)，被插入到 map 的第二个参数位置。

函数1:twice
方式1:正常函数
scm> (define (twice exp) (list 'begin exp exp))
twice
scm> (eval (twice '(print 2)))
2
2
方式2:macro
scm> (define-macro (twice exp) (list 'begin exp exp))
twice
scm> (twice (print 2))
2
2
即macro只是相当于省略了调用时需要的eval 和'
方式3:准引用(suger)
scm> (define-macro (twice exp) `(begin ,exp ,exp))
twice
scm> (twice (print 2))
2
2

函数2
scm> (define-macro (add-to sym exp) (list 'define sym (list '+ sym exp)))
add-to
scm> (add-to 'x (+ x 2))
x
scm> x
30

scm> (define-macro (add-to sym exp) `(define ,sym (+ ,sym ,exp)))
add-to
scm> (add-to x (+ x 2))
x
scm> x
62

函数3
scm> (define-macro (for sym in val do exp) `(map (lambda (,sym) ,exp) ,val))
for
scm> (for i in (list 1 2 3) do (print i))
1
2
3
(undefined undefined undefined)
(上面这行是map的返回值,即None,None,None)

主题九：惰性求值与流基础 (Lazy Evaluation & Stream Basics)

主题概述

流 (Streams) 是 Scheme 中处理序列的一种方式。它与链表（List）非常相似，但核心区别在于：流的“剩余部分”（tail）只有在被显式要求时才会进行计算。这种机制被称为惰性求值 (Lazy Evaluation)。

核心概念

1. 为什么需要流？

Python 对比: Python 使用迭代器（Iterators）和生成器（Generators）来实现惰性求值，可以表示无限序列。
Scheme 链表的局限: 在标准链表中，cons 的第二个参数总是会被立即求值。如果尝试递归定义无限链表，会导致 maximum recursion depth exceeded（达到最大递归深度）。
流的优势: 流允许我们表示巨大的甚至无限长 (infinitely long) 的列表，因为它只在需要时计算下一个元素。

2. 流的构造与基本操作

cons-stream: 构造一个流。其第二个参数是一个承诺 (Promise)，不会立即求值。
car: 获取流的第一个元素（与 List 相同）。
cdr-stream: 获取流的剩余部分。这是关键操作：它会强制 (Force) 履行承诺，计算并返回流的下一个部分。
例题：流的表示

scm> (define s (cons-stream 1 (cons-stream 2 nil)))
s
scm> s
(1 . #[promise (not forced)])  ; 第二部分显示为尚未强制的承诺
scm> (car s)
1
scm> (cdr-stream s)
(2 . #[promise (not forced)])

主题十一：无限流 (Infinite Streams)

主题概述

由于流是惰性求值的，我们可以定义一个在逻辑上永远不会结束的序列。

核心概念

1. 定义无限流

通过在 cons-stream 的第二个参数中进行递归调用，可以创建一个无限序列。

例题：整数流 (Integer Stream)

(define (ints first)
  (cons-stream first (ints (+ first 1))))

scm> (define s (ints 1))
scm> (car s)
1
scm> (car (cdr-stream s))
2

2. 使用高阶函数操作流

我们可以像操作 List 一样编写流的操作函数，只需将 cons 替换为 cons-stream，将 cdr 替换为 cdr-stream。

map-stream (流映射):

(define (map-stream fn s)
  (if (null? s)
      nil
      (cons-stream (fn (car s))
                   (map-stream fn (cdr-stream s)))))

filter-stream (流过滤): 只有当满足条件的元素被找到时，才会构造流的下一个 car。

主题十二：流的高级应用 (Advanced Stream Applications)

核心概念 (Core Concepts)

1. 递归定义的流 (Self-referencing Streams)

流可以引用自身来定义复杂的序列。

全 1 流 (Ones): (define ones (cons-stream 1 ones))
整数流 (Integers): 通过将“全 1 流”与“当前整数流”相加得到下一个整数。

(define ones (cons-stream 1 ones))
(define ints (cons-stream 1 (add-stream ones ints)))

2. 流与列表的转换

stream-to-list: 为了查看流的内容，通常需要将其转换为列表，并指定获取元素的数量（避免死循环）。

SICP Note -> Scheme

主题一：Scheme 基础与求值 (Scheme Basics and Evaluation)

主题概述

核心概念

1. 表达式的分类 (Types of Expressions)

2. 调用表达式求值 (Call Expression Evaluation)

3. 特殊形式 (Special Forms)

主题二：数据抽象：Pairs 与 Lists (Data Abstraction: Pairs and Lists)

主题概述

核心概念 (Core Concepts)

1. 对 (Pairs)

2. 链表 (Linked Lists)

主题三：符号编程与引用 (Symbolic Programming and Quotation)

主题概述

核心概念 (Core Concepts)

1. 引用 (quote 或 ')

2. 引用组合 (Quoting Combinations)

主题四：尾递归 (Tail Recursion)

主题概述

核心概念

1. 尾上下文与尾调用 (Tail Context and Tail Call)

2. 尾调用优化 (Tail Call Optimization, TCO)

3. 识别尾上下文 (Identifying Tail Contexts)

4. 编写尾递归函数 (Writing Tail Recursive Functions)

主题五：表达式作为数据 (Expressions As Data)

主题概述

核心概念

1. 表达式的表示与求值 (Representation and Evaluation)

主题六：辅助特殊形式 (Auxiliary Special Forms)

主题概述

核心概念

1. begin (顺序执行)

2. let (局部绑定)

主题七：宏原理 (Macro Principles)

主题概述

核心概念

1. 定义宏 (define-macro)

2. 宏的求值流程 (Macro Evaluation) 【核心考点】

3. 宏的用途 (Writing Macros)

主题八：准引用 (Quasi-Quotation)

主题概述

核心概念

主题九：惰性求值与流基础 (Lazy Evaluation & Stream Basics)

主题概述

核心概念

1. 为什么需要流？

2. 流的构造与基本操作

主题十一：无限流 (Infinite Streams)

主题概述

核心概念

1. 定义无限流

2. 使用高阶函数操作流

主题十二：流的高级应用 (Advanced Stream Applications)

核心概念 (Core Concepts)

1. 递归定义的流 (Self-referencing Streams)

2. 流与列表的转换

1. 引用 (`quote` 或 `'`)

1. `begin` (顺序执行)

2. `let` (局部绑定)

1. 定义宏 (`define-macro`)