SICP 解题集
更新日期：2026-03-10
1 目录
其余部分正在编写中。
2 说明
SICP，全名为《计算机程序的构造和解释》（Structure and Interpretation of Computer Programs），作者为 Harold Abelson、Gerald Jay Sussman 和 Julie Sussman。
这里使用本书第二版。
书中使用 Scheme 编程语言 。本项目使用 Racket 编程语言 。后者是前者的超集。
本项目使用了：
Racket 文档工具 Scribble ，用于生成网页，便于浏览。
Racket 包 scribble-math ，用于在代码中写出数学公式。
3 学习资源
麻省理工学院官网提供了 SICP 电子版资源：
要运行 Scheme 代码，可以选择：
4 其他链接
5 补充的 Lisp 知识
SICP 书中刻意避开了一些在实际使用 Lisp 时需要了解的知识，这里进行补充。
5.1 数值精度问题
Racket 和 Chez Scheme 都支持大整数类型，所以不必担心整数溢出等问题。例如，可以轻易计算出 2^{256} 的值：
> (expt 2 256) 115792089237316195423570985008687907853269984665640564039457584007913129639936
在 Racket 中，整数除法 (/ a b) 的结果类型为有理数（或整数，如果分母为 1），不会进行浮点除法或整除。
> (/ 6 10) 3/5
> (/ 6 2) 3
（根据 Scheme 标准 IEEE 1178-1990，符合标准的 Scheme 实现并不一定要支持大整数和有理数类型。）
5.2 不适当表
在书中，我们知道解释器会将 (cons 1 (cons 2 (cons 3 '()))) 打印成 (1 2 3) ，如下：
> (cons 1 (cons 2 (cons 3 '()))) '(1 2 3)
但书中没有提到， (cons 1 (cons 2 3)) 会打印成什么样。事实上，会像这样打印：
> (cons 1 (cons 2 3)) '(1 2 . 3)
像这样，对于一个序对，如果递归应用 cdr ，最后得到的却不是空表 '() ，这样的结构称为“不适当表”（improper list）。注意到普通的序对也是不适当表，所以我们可以知道解释器是怎样打印一个普通序对了。
> (cons 1 2) '(1 . 2)
（SICP 竟然在全书都避免了打印不适当表。）
5.3 方括号
SICP 全书都使用圆括号写代码，但 Lisp 代码中有时会使用方括号，例如：
> (define (fib n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fib (- n 1)) (fib (- n 2)))])) > (map fib '(0 1 2 3 4 5 6)) '(0 1 1 2 3 5 8)
事实上，方括号和圆括号是等价的，可以随意互换。（但至于 ([)] 这种诡异的结构还是算了吧。）
方括号标记着 cond 和 let 中，根据语法规定必须成对出现的东西。例如， cond 中的每一个子句（条件-结果），或者 let 中的每一对绑定（名字-值），就用方括号来标记：形如 (a b) 的代码将会写成 [a b] 。
在其他一些地方也会用，例如 基于模式匹配的宏 中的每一个子句（模式-模板）。
Racket 官方文档对 cond 的讲解 中提到，这是一种惯例写法，这样做有助于提高可读性。
5.4 宏
SICP 中没有涉及 Lisp 宏，只在脚注 217（位于 4.1.2 节）里提了一句。
应当指出，Lisp 最精髓的地方不是发明了 REPL，甚至也不是发明了 GC（垃圾回收），而是成为了一个“手写语法树”的语言，让代码和数据共享同一个表示方式。这样一来，就能够轻易编写出宏，使用代码对代码作出变换。这是其他语言绝不可能做到的，除非其他语言也将自己变成手写语法树的样子。
自然，学习 SICP 并不需要理解宏，因为全书都没有使用过它。但在学习之余，也可以试着了解一下有关 Lisp 宏的知识。
第三章中，延迟求值的语法就可以使用宏实现。