SICP 笔记 - 0x01

archive time: 2024-11-02

Rust 也算 LISP！

• 缘起
• Lecture 1A
  • 牛顿法求平方根
  • 二分法求平方根
• Lecture 1B
  • Peano 加法
  • Fibonacci 数列
  • Hanoi 塔

缘起

我为什么要开始写这个笔记呢？

其实 SICP 的视频和书我已经看了很多次了，虽然每次都没有看完，但是常看常新，所以还是有很多收获

写这个笔记主要是为了整理思路，同时也是为了练习 Rust¹， 笔记顺序大致按照 SICP 1986 年教学视频 的顺序， 部分地方我可能会额外穿插一些我自己的想法和说明

Lecture 1A

这一部分主要是介绍什么是计算机科学以及为什么学习 LISP 语言²

计算机科学（Computer Science）实际上既不计算机也不科学， 正如几何（Geometry）不是测量的学科，而是用数学语言公理化地描述空间和物体的学科， 计算机科学则是公理化地描述计算过程的学科，这个公理化的描述称为 算法， 而计算机科学所关心的是如何控制过程的 复杂度

这段话对于现在所有的学科都是有用的，很多学科现代的发展已经偏离了这门学科刚刚发展的方向， 大体上，理论学科的发展趋势都可以用一个词概括，那就是 公理化

哪怕是现在的 Machine Learning，也在朝着公理化的方向发展， 因为对于目前的科学来说，只有公理化，能够用数学符号和语言表述，才能去证明其正确性， 不过 Machine Learning 对于大多数人而言只要能跑就行，很少人会去真正关心这个“黑盒子”的内部结构

牛顿法求平方根

求平方根是一个非常经典的算法例子，可以很好的展现求根的过程以及迭代的使用，我们需要关心的是：

• 为什么会收敛
• 迭代过程是什么样的
• 能否更快收敛

大部分的求根问题，都可以被抽象成一个求 不动点³ 的迭代过程，其中最常用的方法就是牛顿法

对于求平方根，我们可以将问题变成求 $f(x)=x^2-P$ 的根，其中 $P$ 是我们要求平方根的数，即：

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$

我们要进行的迭代就是：

$$x_{n+1}=\frac{1}{2}(x_n+\frac{P}{x_n})$$

例如对于 $P=5$，可以假设 $x_0=P/2$，则有如下过程：

x_0: 2.5
x_1: 2.25
x_2: 2.2361112
x_3: 2.236068

仅用了 $3$ 次迭代就得到了不动点，验证可以知道 $2.236068^2\approx 5.000000100624$

对应 Rust 代码为：

fn sqrt_f32(n: f32) -> f32 {
    fn sqrt_f32_i(n: f32, guess: f32) -> f32 {
        if (guess.powi(2i32) - n).abs() < f32::EPSILON {
            guess
        } else {
            sqrt_f32_i(n, (guess + n / guess) / 2.0f32)
        }
    }
    sqrt_f32_i(n, n / 2.0f32)
}

现在来尝试回答那三个问题：

• 为什么会收敛：牛顿法利用切线在某一点的局部去近似函数，而 $f(x)/f^{\prime }(x)$ 就是误差
• 迭代过程是什么样的：大部分情况下根据根和函数的不同会呈现线性收敛和二次收敛
• 能否更快收敛：可以，我们可以尝试给误差加上一个倍数 $m$，也就是 $$x_{n+1}=x_n-m\frac{f(x_n)}{f^{\prime }(x_n)}$$

二分法求平方根

如果我们不知道牛顿法，我们该怎么去求解呢？

思路是相近的，大概可以分成三步：

1. 判断我们的猜测是否满足条件
2. 如果满足，那么就返回结果
3. 否则就进行“优化”，将优化的结果作为猜测返回第一步

而这个迭代的效果就要取决于这个“优化”方法了，而最容易想到的方法就是二分法，也就是：

$$x_{n+1}=\frac{1}{2}(\frac{P}{x_n}+x_n)$$

通过让 $x_n$ 和 $P/x_n$ 不断接近来求解 $\sqrt{P}$，因为 $P/\sqrt{P}=\sqrt{P}$

而这个式子却和牛顿法惊奇地一致，这也算是某种“趋同”吧

Lecture 1B

这一部分主要介绍计算过程和递归，包括复杂度的计算

大体上来说，我们可以认为计算，或者说函数实际上就是在不断的做替换，例如：

fn square_of_sum(a: u8, b: u8) -> u8 {
    square(a) + square(b)
}

fn square(a: u8) -> u8 {
    a * a
}

如果我们要计算 square_of_sum(3, 4)，我们可以认为这个式子会被替换成 square_of_sum 的内部实现，在这里就是 square(3) + square(4)

然后会尝试使用 + 求和，但是要得到结果，我们需要先知道 square(3) 和 square(4) 的结果，所以又发生替换 (3 * 3) + (4 * 4)

然后分别计算 3 * 3 和 4 * 4 后得到结果 9 和 16，再回溯到 +，即 9 + 16，最后得到结果 25 并返回

当然，计算机或者说编译器要做的工作不止这些，但是对于计算过程，我们只需要关注到这种程度即可

Peano 加法

在数学公理化中，有一个公理非常重要，那就是 Peano 公理⁴， 这个公理中，自然数可以表示为两种状态 $0$ 以及 $Sn$，其中 $S$ 表示后继

enum Peano {
    Zero,
    Succ(Box<Peano>),
}

那么对于 Peano 数的加法，我们可以有两种定义方式

fn peano_add_one(a: Peano) -> Peano {
    Peano::Succ(Box::new(a))
}

fn peano_add_l(a: Peano, b: Peano) -> Peano {
    match a {
        Peano::Zero => b,
        Peano::Succ(n) => peano_add_l(*n, peano_add_one(b)),
    }
}

fn peano_add_r(a: Peano, b: Peano) -> Peano {
    match a {
        Peano::Zero => b,
        Peano::Succ(n) => peano_add_one(peano_add_r(*n, b)),
    }
}

这两种方式乍一看非常相似，但是这两种方式的复杂却截然不同，我们可以用替换来尝试计算 2 + 3

第一种方式：

peano_add_l(2, 3)
=> peano_add_l(1, 3 + 1) ~> peano_add_l(1, 4)
=> peano_add_l(0, 4 + 1) ~> peano_add_l(0, 5)
=> 5

=> 表示一次替换，~> 表示会立刻计算成对应形式，而第二种方式

peano_add_r(2, 3)
=> peano_add_r(1, 3) + 1
=> peano_add_l(0, 3) + 1 + 1
=> 3 + 1 + 1
=> 4 + 1
=> 5

某种意义上来说，一个计算过程的复杂度我们可以通过替换来呈现， 其中时间复杂度就是这个过程的深度， 而空间复杂度就是这个计算过程变量个数以及变量的大小

第一种方式的时间复杂度和空间复杂度分别为 $\mathcal{O}(N)$ 和 $\mathcal{O}(1)$， 而第二种方式的时间复杂度和空间复杂度分别为 $\mathcal{O}(N)$ 和 $\mathcal{O}(N)$

Fibonacci 数列

另外一个经典的递归案例就是 Fibonacci 数列，我们同样有两种（及以上）实现方式：

fn fib_l(n: u8) -> usize {
    fn fib_l_i(n: u8, a: usize, b: usize) -> usize {
        match n {
            0 => a,
            1 => b,
            _ => fib_l_i(n - 1, b, a + b),
        }
    }
    fib_l_i(n, 0, 1)
}

fn fib_r(n: u8) -> usize {
    match n {
        0 => 0,
        1 => 1,
        _ => fib_r(n - 1) + fib_r(n - 2),
    }
}

通过替换，我们可以发现 fib_r 的调用可以组成一个树，其空间复杂度就是这个树的深度，也就是 $N$， 其时间复杂度就是树的叶子个数，和 Fibnacci 数列成比例

使用大 O 表示法，fib_l 的时间复杂度和空间复杂度为 $\mathcal{O}(N)$ 和 $\mathcal{O}(1)$， 而 fib_r 的时间复杂度和空间复杂度约⁵为 $\mathcal{O}(2^N)$ 和 $\mathcal{O}(N)$，

Hanoi 塔

还有一个经典例子用于展示时间复杂度，那就是 Hanoi 塔

假设有 $n$ 个物体堆在 $A$ 处，要将这些物体通过 $B$ 移动到 $C$ 处， 并且这些物体有大小，必须小的放在大的上面，一次只能移动一个物体

我们可以分解一下要求：

• 要将 $n$ 个物体从 $A$ 通过 $B$ 移动到 $C$
• 可以先将上面 $n-1$ 个物体从 $A$ 通过 $C$ 移动到 $B$
• 然后将最下面的那个物体移动到 $C$
• 最后再将其他物体从 $B$ 通过 $A$ 移动到 $C$
• 不断重复上述过程直到完成移动

可以看到上面主要的有三个部分，第一就是起点，其次就是终点，剩下的就是中继点

按照这个思路可以有如下方法：

fn hanoi(n: u8, from: char, bypass: char, to: char) -> usize {
    fn hanoi_i(n: u8, from: char, bypass: char, to: char, cnt: usize) -> usize {
        if n == 0 {
            cnt
        } else {
            // move n - 1 from A by C to B
            let p = hanoi_i(n - 1, from, to, bypass, cnt);
            // move 1 from A to C
            println!("{}: {} -> {}", p, from, to);
            // move n - 1 from B by A to C
            hanoi_i(n - 1, bypass, from, to, p + 1)
        }
    }
    hanoi_i(n, from, bypass, to, 0)
}

总共的移动步数是 $2^n-1$ 步

前两节课主要是构建一个对于计算过程和递归的印象，之后的课程会详细讲解如何去优化某些过程