SICP 笔记 - 0x03

archive time: 2025-02-25

闲了这么久，终于想起来还有两个坑没填

Lecture 3A
Lecture 3B
- 系统健壮性
- 符号微分

Lecture 3A

在 Lecture 2B 介绍了 复合数据 的概念

而这一部分列举了几个复合数据的例子，并展示了抽象的优势，即设计与实现分离，利用统一接口，无需关心具体方法的实现，以此来完成解耦，降低复杂度

除此之外，闭包的概念也被提出，在这里里的闭包更倾向于数学概念，即某个集合在某个运算下封闭：

$\times : A \to A \to A$

这里， $A$ 集合在运算 $\times$ 下就是封闭的，而 LISP 对象这个集合在 CONS 运算下就是封闭的，也就是两个任意 LISP 对象通过 CONS 可以再构造出一个 LISP 对象，这赋予了我们构造更复杂结构的能力

在其他语言中，例如 Rust，这个就类似于使用元组也是可以构造复杂的结构的，但是 Rust 中有更好的选择，即 enum 和 struct

线段

第一个例子就是用 cons 来模拟线段

一条线段可以由两个点来表示，这里举例使用二维平面，所以一个线段可以表示为 $s = {(x_{a}, y_{a}), (x_{b}, y_{b})}$ ，即：

type Point = (f64, f64);
type Seg = (Point, Point);

相应的，我们有如下接口：

fn make_point(x: f64, y: f64) -> Point;
fn make_seg(p1: Point, p2: Point) -> Seg;
fn seg_start(s: Seg) -> Point;
fn seg_end(s: Seg) -> Point;

其中一种可能的实现如下：

fn make_point(x: f64, y: f64) -> Point { (x, y) }
fn make_seg(p1: Point, p2: Point) -> Seg { (p1, p2) }
fn seg_start(s: Seg) -> Point { s.0 }
fn seg_end(s: Seg) -> Point { s.1 }

即便我们将 Point 和 Seg 使用 struct 实现，用户使用这些接口还是能操线段，而无需关系其具体实现

列表

另一个非常实用的例子就是 LIST，即列表

在 Haskell 和 LISP 以及 Scheme 中，列表的实现都可以视作是链表，即：

[1, 2, 3, 4] ~> (1, (2, (3, (4, nil))))

其中这个 nil 可以视作是空列表，或者 NULL

这个在 Rust 中可以表示为：

enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

impl<T> std::fmt::Display for List<T>
where
    T: std::fmt::Display,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[")?;
        let mut current = self;
        loop {
            match current {
                List::Cons(e, next) => {
                    if let List::Cons(_, _) = **next {
                        current = next;
                        write!(f, "{}, ", e)?;
                    } else {
                        writeln!(f, "{}]", e)?;
                        break;
                    }
                }
                List::Nil => {
                    write!(f, "]")?;
                    break;
                }
            }
        }
        Ok(())
    }
}

fn main() {
    let one_to_four = List::Cons(
        1,
        Box::new(List::Cons(
            2,
            Box::new(List::Cons(3, Box::new(List::Cons(4, Box::new(List::Nil))))),
        )),
    );
    println!("{}", one_to_four);
    // => [1, 2, 3, 4]
}

当然，一直使用 CONS 太繁琐了，所以在 LISP 中有一套简化的方法，即 LIST 函数：

(list 1 2 3 4)

我们在 Rust 中也可以使用宏来实现类似方法

macro_rules! list {
    () => {
        List::Nil
    };
    ($($arg:tt)*) => {{
        [$($arg)*].iter().rev().fold(List::Nil, |acc, e| match acc {
            List::Cons(a, inner) => List::Cons(e, Box::new(List::Cons(a, inner))),
            List::Nil => List::Cons(e, Box::new(List::Nil)),
        })
    }}
}

fn main() {
    let one_to_four = list![1, 2, 3, 4];
    println!("{}", one_to_four);
    // => [1, 2, 3, 4]
}

当然，在 Rust 有一个等价的结构叫做 Vector，所以我们不必自己实现这个功能

由于 LISP 中的列表只是 CONS 的等价物，所以我们可以用 CAR 和 CDR 来操作列表：

(define 1-to-4 (list 1 2 3 4))
;; get the second value
(car (cdr 1-to-4))
;; => 2

在 Rust 中表示为：

fn car<T>(lst: &List<T>) -> Option<&T> {
    match lst {
        List::Cons(e, _) => Some(e),
        List::Nil => None,
    }
}

fn cdr<T>(lst: &List<T>) -> Option<&List<T>> {
    match lst {
        List::Cons(_, p) => Some(&*p),
        List::Nil => None,
    }
}

fn main() {
    let one_to_four = list![1, 2, 3, 4];
    let second = car(cdr(&one_to_four).unwrap()).unwrap();
    println!("{}", second);
    // => 2
}

如果我想要对这个列表中的每一个元素都应用某个操作，例如都加上 $10$ ，或者都乘以 $2$

我们可以有如下操作¹：

fn trans_list<A, B>(lst: &List<A>, f: impl Fn(A) -> B) -> List<B>
where
    A: Clone,
{
    match lst {
        List::Cons(e, p) => List::Cons(f(e.clone()), Box::new(trans_list(&*p, f))),
        List::Nil => List::Nil,
    }
}

fn main() {
    let one_to_four = list![1, 2, 3, 4];
    let eleven_to_fourteen = trans_list(&one_to_four, |x| x + 10);
    println!("{}", eleven_to_fourteen);
}

这种操作在现在有了一个统一的称呼，即 MAP，将某个容器中的每一个元素都应用上某种变换，然后得到新的容器

当然，有时候我们只是想要在容器上执行某些东西，例如逐行打印容器内的元素，那么就可以使用另一种方法 FOR-EACH

在 Rust 中，这些可以通过为容器实现 Iter 来实现：

struct ListIter<'a, T> {
    curr: &'a List<T>,
}

impl<'a, T> std::iter::Iterator for ListIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.curr {
            List::Cons(e, inner) => {
                self.curr = &*inner;
                Some(e)
            }
            List::Nil => None,
        }
    }
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> ListIter<'a, T> {
        ListIter { curr: self }
    }
}

impl<'a, A> FromIterator<A> for List<A>
where
    A: Clone,
{
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
        iter.into_iter()
            .collect::<Vec<_>>()
            .iter()
            .rev()
            .fold(List::Nil, |acc, e| match acc {
                List::Cons(a, inner) => List::Cons(e.clone(), Box::new(List::Cons(a, inner))),
                List::Nil => List::Cons(e.clone(), Box::new(List::Nil)),
            })
    }
}

fn main() {
    let one_to_four = list![1, 2, 3, 4];
    let eleven_to_fourteen = one_to_four.iter().map(|&&e| e + 10).collect::<List<i32>>();
    println!("{}", eleven_to_fourteen);
    // => [11, 12, 13, 14]
    eleven_to_fourteen.iter().for_each(|e| print!("{} ~ ", e));
    // => 11 ~ 12 ~ 13 ~ 14 ~
    println!()
}

元语言抽象

在工程上，解决复杂度问题的一种方法，就是构造一门新的语言，这种语言被统称为 特定领域语言（DSL）

我们可以在前端看到这种方法被大规模应用，即每过一段时间都会有一个新的前端框架被发明，用于解决某些痛点，而这些前端框架就可以看成是用 JavaScript 编写的 DSL，当然，这同时也会引入一定的复杂度，因为大家需要学习新的东西了，即便新的东西比原来要解决的问题要更简单

我们学习一门新的语言，需要注意的有三点：

原始类型，即基本数据类型
复合类型，如何模拟更复杂的数据
数据抽象，即如何操作数据

其中第二点和第三点就是我们控制复杂度的关键，因为我们可以通过复合类型和数据抽象，来将要解决的问题进行抽象

例如我们需要构造一种图片，那么我们可以将图片这种数据抽象出来，作为新语言的原始类型，然后，对于图片的操作，我们可以简化为缩放、旋转、翻转和拼接这四种操作，通过这种方式，就可以解决我们的复杂需求

我们对于数据和方法的封装过程实际上就可以看成是构建 DSL 的过程， DSL 不过是原语言的一个库

一个比较出名的 DSL 的例子就是 Ruby 与 HomeBrew²

Lecture 3B

系统健壮性

上面介绍了如何构建系统和解决问题，但是在解决系统复杂度问题上，还有一点非常重要，那就是维护

一个稳健的系统，应当对小的变化不敏感，问题中的小变化应该只导致解决方案中的小变化，为了做到这点，我们在解决问题时不应该只解决问题本身，应该还需要解决问题的一些临近的相关问题

一种方案就是构建一门可以描述对应问题的语言，通过这门特定语言来解决问题，这样在问题出现变化的时候，我们同样可以用这门语言去描述这种变化，只需要较小的修改就可以覆盖变化产生的新问题

符号微分

有了上述的思想以及方法，我们就可以着手解决一个问题，那便是函数求导，并且与使用 dx 来进行数值模拟不同，这次要做的是对多项式进行符号微分，其基本原理就是函数求导的法则：

$\frac{d c}{d x} = 0, \frac{d x}{d x} = 1, \frac{d c u}{d x} = c \frac{d u}{d x} \frac{d ( u + w )}{d x} = \frac{d u}{d x} + \frac{d w}{d x}, \frac{d ( u w )}{d x} = \frac{d u}{d x} w + u \frac{d w}{d x} \frac{d ( u / w )}{d x} = \frac{\frac{d u}{d x} w - u \frac{d w}{d x}}{w ^{2}} \frac{d u ^{n}}{d x} = n u^{n - 1} \frac{d u}{d x}$

其中 $c$ 是任意常数

具体的 Rust 实现和分析如下

这里是一个直接的实现，没有考虑各种优化，只是对于微分结果有一定的简化：

#[derive(Clone, Debug)]
enum DiffElement {
    Constant(f64),
    Variable,
    Add(Box<DiffElement>, Box<DiffElement>),
    Mul(Box<DiffElement>, Box<DiffElement>),
    Div(Box<DiffElement>, Box<DiffElement>),
    Pow(Box<DiffElement>, f64),
}

fn is_zero(x: &f64) -> bool {
    x.abs() <= core::f64::EPSILON.sqrt()
}

impl DiffElement {
    pub fn make_add(e1: DiffElement, e2: DiffElement) -> DiffElement {
        match (&e1, &e2) {
            (DiffElement::Constant(a), DiffElement::Constant(b)) => DiffElement::Constant(a + b),
            (DiffElement::Constant(a), _) if is_zero(a) => e2,
            (_, DiffElement::Constant(a)) if is_zero(a) => e1,
            _ => DiffElement::Add(Box::new(e1), Box::new(e2)),
        }
    }

    pub fn make_mul(e1: DiffElement, e2: DiffElement) -> DiffElement {
        match (&e1, &e2) {
            (DiffElement::Constant(a), DiffElement::Constant(b)) => DiffElement::Constant(a * b),
            (DiffElement::Constant(a), _) if is_zero(&(a - 1.0)) => e2,
            (DiffElement::Constant(a), _) if is_zero(a) => DiffElement::Constant(0.0),
            (_, DiffElement::Constant(a)) if is_zero(&(a - 1.0)) => e1,
            (_, DiffElement::Constant(a)) if is_zero(a) => DiffElement::Constant(0.0),
            _ => DiffElement::Mul(Box::new(e1), Box::new(e2)),
        }
    }

    pub fn make_div(e1: DiffElement, e2: DiffElement) -> DiffElement {
        match (&e1, &e2) {
            (DiffElement::Constant(a), DiffElement::Constant(b)) if !is_zero(b) => {
                DiffElement::Constant(a / b)
            }
            (DiffElement::Constant(a), _) if is_zero(a) => DiffElement::Constant(0.0),
            (_, DiffElement::Constant(a)) if is_zero(&(a - 1.0)) => e1,
            _ => DiffElement::Div(Box::new(e1), Box::new(e2)),
        }
    }

    pub fn make_pow(e: DiffElement, n: f64) -> DiffElement {
        match (&e, n) {
            (DiffElement::Constant(a), _) if !is_zero(a) => DiffElement::Constant(a.powf(n)),
            (DiffElement::Pow(u, p), _) => DiffElement::make_pow(*u.clone(), p + n),
            (_, _) if is_zero(&(n - 1.0)) => e,
            _ => DiffElement::Pow(Box::new(e), n),
        }
    }

    pub fn diff(self) -> DiffElement {
        match self {
            DiffElement::Constant(_) => DiffElement::Constant(0.0),
            DiffElement::Variable => DiffElement::Constant(1.0),
            DiffElement::Add(e1, e2) => DiffElement::make_add(e1.diff(), e2.diff()),
            DiffElement::Mul(e1, e2) => DiffElement::make_mul(e1.diff(), e2.diff()),
            DiffElement::Div(e1, e2) => DiffElement::make_div(
                DiffElement::make_add(
                    DiffElement::make_mul(e1.clone().diff(), *e2.clone()),
                    DiffElement::make_mul(
                        DiffElement::Constant(-1.0),
                        DiffElement::make_mul(*e1, e2.clone().diff()),
                    ),
                ),
                DiffElement::make_pow(*e2, 2.0),
            ),
            DiffElement::Pow(e, n) => DiffElement::make_mul(
                DiffElement::Constant(n),
                DiffElement::make_mul(DiffElement::make_pow(*e.clone(), n - 1.0), e.diff()),
            ),
        }
    }
}

fn main() {
    // (x^2 + 3) / (x^3 - 8 x^2 + 3)
    let eq = DiffElement::make_div(
        DiffElement::make_add(
            DiffElement::make_pow(DiffElement::Variable, 2.0),
            DiffElement::Constant(3.0),
        ),
        DiffElement::make_add(
            DiffElement::make_pow(DiffElement::Variable, 3.0),
            DiffElement::make_add(
                DiffElement::make_mul(
                    DiffElement::Constant(-8.0),
                    DiffElement::make_pow(DiffElement::Variable, 2.0),
                ),
                DiffElement::Constant(3.0),
            ),
        ),
    );
    println!("{:?}", eq.diff());
}

手动格式化后的输出如下：

Div(
|   Add(
|   |   Mul(
|   |   |   Mul(Constant(2.0), Variable),
|   |   |   Add(
|   |   |   |   Pow(Variable, 3.0),
|   |   |   |   Add(
|   |   |   |   |   Mul(Constant(-8.0), Pow(Variable, 2.0)),
|   |   |   |   |   Constant(3.0)
|   |   |   |   )
|   |   |   )
|   |   ),
|   |   Mul(
|   |   |   Constant(-1.0),
|   |   |   Mul(
|   |   |   |   Add(Pow(Variable, 2.0), Constant(3.0)),
|   |   |   |   Mul(Constant(3.0), Pow(Variable, 2.0))
|   |   |   )
|   |   )
|   ),
|   Pow(
|   |   Add(
|   |   |   Pow(Variable, 3.0),
|   |   |   Add(
|   |   |   |   Mul(Constant(-8.0), Pow(Variable, 2.0)),
|   |   |   |   Constant(3.0)
|   |   |   )
|   |   ),
|   |    2.0
|   )
)

即：

$\frac{2 x ( x ^{3} + ( - 8 x ^{2} + 3 )) + ( - ( x ^{2} + 3 ) ( 3 x ^{2} ))}{( x ^{3} + ( - 8 x ^{2} ) + 3 ) ^{2}}$

可以看到，还是有很多优化空间的，我们再手动优化一下可以得到：

$\frac{2 x}{x ^{3} - 8 x ^{2} + 3} - \frac{3 x ^{2} ( x ^{2} + 3 )}{( x ^{3} - 8 x ^{2} + 3 ) ^{2}}$

可以发现这个答案就是我们想要的答案

在早期的 Maxima³，符号微分的实现就是用类似的 LISP 代码来实现的，这种实现引出了下一部分所要讲的内容，即 模式匹配

好久没写博客了，重新开始写一下子有些不适应，特别是一些措辞和格式上还是有些不习惯，例如要使用斜体还是粗体

嘛，不过最近我会慢慢恢复更新，最起码一周一更，到时候应该就会好很多了

这里可以使用尾递归优化，但是为了直观，故采用直接的方式

Cask::DSL.HomeBrew [DB/OL].(2025-01-13)[2025-02-25]. https://rubydoc.brew.sh/Cask/DSL.html

Maxima: v5.47 [CP/OL].(2023-05-31)[2025-02-25].https://maxima.sourceforge.io/zh/index.html

Kevin Stephen's Blogs