Structure and Interpretation of Computer Programs

《计算机程序的构造和解释》题解，使用标准Racket 实现（开发环境是Emacs）

If art interprets our dreams, the computer executes them in the guise of programs!

如果说艺术解释了我们的梦想，那么计算机就是以程序的名义执行着它们

We toast the Lisp programmer who pens his thoughts within nests of parentheses.

向以括号为画笔的Lisp程序员举杯，干杯！

安装依赖

raco pkg install --auto --batch # 类似 JavaScript 的 npm install

习题

习题完成情况:

• 章节一: 43/46
• 章节二: 88/97
• 章节三: 22/82
• 章节四: TODO
• 章节五: TODO

运行

运行所有的习题

raco test -t .

运行指定的习题:

raco test chapter1/exercise1-10.scm 

笔记

chapter2

图形语言

racket的 sicp package 包含了一个画图工具，可以画出类似书中的效果

#lang racket
(require sicp-pict)
(define (flipped-pairs painter)
  (let ((painter2 (beside painter (flip-vert painter))))
    (below painter2 painter2)))

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

(define (corner-split painter n)
  (if (= n 0)
      painter
      (let ((up (up-split painter (- n 1)))
            (right (right-split painter (- n 1))))
        (let ((top-left (beside up up))
              (bottom-right (below right right))
              (corner (corner-split painter (- n 1))))
          (beside (below painter top-left)
                  (below bottom-right corner))))))

(define (square-limit painter n)
  (let ((quarter (corner-split painter n)))
    (let ((half (beside (flip-horiz quarter) quarter)))
      (below (flip-vert half) half))))

(paint (square-limit einstein 6))

在 DrRacket 的运行效果（只能在DrRacket 运行，在终端无法展示图片）：

配合 wave的实现，画出来的效果：

chapter3

蒙特卡罗模拟步骤来计算 π

3.1 赋值与局部变量, 155 页

举例来说，6/π^2 是随机选取的两个整数之间没有公因子（也就是说，它们的最大公因子是1）的概率。我们可以利用这一事实做出π的近似值。

完全读不懂这段话，没理解是怎么可以算出π的近似值的。

查阅完资料都知道:

随机选取两个正整数，它们互质（即最大公约数GCD为1）的概率是 $\frac{6}{π^2}$ , 所谓的 互质指两个数没有公共因子（如8和15互质，但8和12不互质，因为公约数为4）。

而这一结论是源自数论中关于 互质数的密度 的研究，与黎曼ζ函数相关（难怪我看不懂了）。

而用蒙特卡罗模拟步骤来计算 ${π}$:

随机实验：重复多次随机选取两个整数，检查它们的GCD是否为1。

例如：

• (3, 5) → GCD=1（计数+1）
• (4, 6) → GCD=2（不计数）

统计概率：

若总实验次数为 N，其中 k 次GCD=1，则互质概率的估计值为 $\frac{k}{N}$

关联π：

根据数论结论 $\frac{k}{N} ≈ \frac{6}{π^2}$，解得 $π ≈ \sqrt{\frac{6N}{k}}$。

当直接计算π困难时，可通过概率实验间接逼近。

这里利用了数论中的概率规律，将π与随机事件联系起来。(对于高数也只是低分飘过的我来说，不知道数论的东西也太正常了)

#lang racket

(define (estimate-pi trials)
  (sqrt (/ 6 (monte-carlo trials cesaro-test))))

(define (cesaro-test)
  (= (gcd (rand) (rand)) 1))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trial-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1) (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1) trials-passed))))
  (iter trials 0))

这里的蒙特卡罗实现真的是优雅