SICP 笔记 - 0x02

archive time: 2024-11-05

Rust 还是不够纯，但是也够用了

Lecture 2A
Lecture 2B
- 有理数系统
  - CONS, CAR, CDR

Lecture 2A

这一部分介绍了什么是高阶过程

所谓高阶过程就是以过程为参数的某种过程，最典型的就是求和函数 $\sum_{i}^{n} f (i)$

求和函数

如果比较有经验，应该可以立刻写出求和函数的实现：

fn sum<A, N, F>(from: A, next: N, to: A, f: F) -> A
where
    A: std::clone::Clone + std::default::Default + std::cmp::PartialOrd + std::ops::Add<Output = A>,
    N: Fn(A) -> A + std::clone::Clone,
    F: Fn(A) -> A + std::clone::Clone,
{
    fn sum_i<A, N, F>(from: A, next: N, to: A, acc: A, f: F) -> A
    where
        A: std::clone::Clone
            + std::default::Default
            + std::cmp::PartialOrd
            + std::ops::Add<Output = A>,
        N: Fn(A) -> A + std::clone::Clone,
        F: Fn(A) -> A + std::clone::Clone,
    {
        if from > to {
            acc
        } else {
            sum_i(next(from.clone()), next, to, f(from) + acc, f)
        }
    }
    sum_i(from, next, to, A::default(), f)
}

看起来 N 和 F 是重复的类型，但这里是为了表明 next 和 f 是不同的函数，因为在 Rust 中不同的闭包的类型是不同的，哪怕是实现完全相同的两个 Closure 对象也是不一样的，这点和 Java 的 Lambda 对象是一样的，所以对于不同的函数，哪怕函数签名一致，也需要标注不同的类型名

使用方法如下：

fn main() {
    let res = sum(1, |x| x + 1, 10, |x: i64| x.pow(2));
    println!("sum of i^2 from 1 to 10 is {}", res);
}

我们为什么会需要高阶过程呢？

高阶过程显然不是必须的，但是这给了我们一种解耦的能力，我们只需要知道 sum 需要 next 和 f，而我们也只需要实现 next 和 f，至于 sum 的实现就不是我们关心的问题了

不动点

之前提到过，对于求根问题，我们大部分情况下都可以转为求不动点问题，那么是什么不动点呢？

不动点就是对于一个函数 $f$ 和参数 $x$ 使得 $x = f (x)$ ，那么 $x$ 就是 $f (x)$ 的不动点

对于简单函数，不动点可以通过求 $f (x)$ 与 $y = x$ 解得，但是通常情况下，这个 $f$ 是不显然的，此时就需要我们使用迭代的方式求解不动点

fn fix<F, P>(f: F, init: f64, is_equal: P) -> f64
where
    F: Fn(f64) -> f64 + std::clone::Clone,
    P: Fn(f64, f64) -> bool + std::clone::Clone,
{
    fn fix_i<F, P>(current: f64, next: f64, f: F, is_equal: P) -> f64
    where
        F: Fn(f64) -> f64 + std::clone::Clone,
        P: Fn(f64, f64) -> bool + std::clone::Clone,
    {
        if is_equal(current, next) {
            next
        } else {
            fix_i(next, f(next), f, is_equal)
        }
    }
    fix_i(init, f(init), f, is_equal)
}

使用方法如下：

fn main() {
    let is_equal = |x: f64, y: f64| (x - y).abs() < std::f64::EPSILON.sqrt();
    let fix_cos = fix(|x| x.cos(), 1.0, is_equal);
    println!("fix point of cos is {}", fix_cos);
}

我们可以通过这个 fix 方法来实现之前的求平方根的过程：

let sqrtf = |y: f64| fix(|x| (y / x + x) / 2.0, y / 2.0, is_equal);
println!(
    "sqrtf(5) = {}, 5.0f64.sqrt() = {}",
    sqrtf(5.0),
    5.0f64.sqrt()
);

牛顿法

有了 fix 函数后，我们可以非常方便的求解一个函数的不动点，但是不动点的概念还是有些复杂了，但是求根就非常容易理解

类似的，我们可以将求根问题变成求不动点问题，我们同样可以将求不动点问题变成求根问题，所以我们可以实现一个高阶的牛顿法来求根

但是实现牛顿法有一个难点，那就是怎么求函数的导函数

在这里，我们并不需要关心这个求导过程的实现，我们可以先假设已经实现来一个求导函数，然后在这个基础上实现牛顿法，这种思考方式也被称为 “wishful thinking”，或者说自顶向下¹，这就是高阶过程的意义，可以从一个更高层次的抽象来解决问题

fn newton<F, P>(f: F, init: f64, is_equal: P) -> f64
where
    F: Fn(f64) -> f64 + std::clone::Clone,
    P: Fn(f64, f64) -> bool + std::clone::Clone,
{
    let df = derivative(f.clone());
    fix(|x| x - f(x) / df(x), init, is_equal)
}

然后我们再来具体看怎么求导，导数的定义是：

$\frac{d f ( x )}{d x} = h \to 0 lim \frac{f ( x + h ) - f ( x )}{h}$

我们大可以模仿这个定义写出如下函数：

fn derivative<F>(f: F) -> impl Fn(f64) -> f64 + std::clone::Clone
where
    F: Fn(f64) -> f64 + std::clone::Clone,
{
    let h = std::f64::EPSILON.sqrt();
    move |x: f64| (f(x + h) - f(x)) / h
}

使用方法：

let root1 = newton(|x| (x - 3.0) * (x + 6.0), 1.0, is_equal);
let root2 = newton(|x| (x - 3.0) * (x + 6.0), -4.0, is_equal);
println!("root is {} and {}", root1, root2);
// => root is 3 and -6

一等公民

函数式编程中总能听到这样一个概念：“函数是一等公民”，那么什么是一等公民呢？

一等公民（first-class citizen）² 是一种对象，这个对象可以：

使用变量命名
可以作为参数传给某个过程
可以作为过程的返回值
可以作为数据结构的一部分

现在大部分语言都已经将函数作为一等公民了，包括 C 语言，不过 C 语言的函数使用的是函数指针，本质上是一个指针对象，这点和其他语言是不太一样的

Lecture 2B

这一部分主要介绍复合类型，也被称为 和类型（sum type）

复合类型在其他语言中常以结构体或者数据类的方式出现，不过在 LISP 中，复合类型通常使用元组来表示

有理数系统

一个非常典型的复合类型就是二维向量类型，不过在这里介绍的则是有理数系统

有理数定义为两个互质³ 整数的除法， $q = \frac{m}{n}, m ⊥ n$ ，若 $n = 1$ ， $q$ 就是整数， $n \neq = 0$

(define (make-rat n d) (cons n d))
(define (num q) (car q))
(define (den q) (cdr q))

对应 Rust 中的实现如下：

type Rational = (i64, i64);

fn make_rat(n: i64, d: i64) -> Rational {
    (n, d)
}

fn numer(q: &Rational) -> i64 {
    q.0
}

fn denom(q: &Rational) -> i64 {
    q.1
}

这是面向对象中的封装思想，但是在非面向对象编程中也有非常多的应用，通过这种封装，我们赋予了基本的元组类型一个意义，这种特殊的元组被称为有理数

并且我们可以将类型的具体实现抽象出来，也就是对外提供 make_rat 构造器⁴，以及 numer 和 denom 访问方法⁵，对于外部调用者，不用管 Rational 是怎么实现的，即便我将元组改成了 struct，例如：

struct Rational {
    pub numer: i64,
    pub denom: i64,
}

fn make_rat(numer: i64, denom: i64) -> Rational {
    Rational { numer, denom }
}

fn numer(q: &Rational) -> i64 {
    q.numer
}

fn denom(q: &Rational) -> i64 {
    q.denom
}

通过这三个函数，我们也可以正常去使用 Rational 类型：

fn rat_add(a: Rational, b: Rational) -> Rational {
    let na = numer(&a);
    let da = denom(&a);
    let nb = numer(&b);
    let db = denom(&b);
    make_rat(na * db + nb * da, da * db)
}

fn main() {
    let res = rat_add(make_rat(1, 2), make_rat(1, 4));
    println!("{}", numer(&res));
    // => 6
    println!("{}", denom(&res));
    // => 8
}

CONS, CAR, CDR

这个是作为补充部分，看看 scheme 的 cons 是怎么实现的，作为理论，cons 实际上是在 $λ$ -演算⁶ 中提到的

$CONS CAR CDR NIL TRUE FALSE := λ x . λ y . λ p . p x y := λ p . p TRUE := λ p . p FALSE := λ x . TRUE := λ x . λ y . x := λ x . λ y . y$

$NIL$ 也可以定义为 $NIL := λ x . FALSE$

在 scheme 中，可以表示为：

(define (cons' a b) (lambda (p) (if p a b)))
(define (car' x) (x #t))
(define (cdr' x) (x #f))

在 Rust 中，这些可以表示为：

enum Pair<A, B> {
    Left(A),
    Right(B),
}

fn cons<A: std::clone::Clone, B: std::clone::Clone>(
    x: A,
    y: B,
) -> impl Fn(bool) -> Pair<A, B> + std::clone::Clone {
    move |p: bool| {
        if p {
            Pair::Left(x.clone())
        } else {
            Pair::Right(y.clone())
        }
    }
}

fn car<A: std::clone::Clone, B: std::clone::Clone>(p: impl Fn(bool) -> Pair<A, B>) -> A {
    match p(true) {
        Pair::Left(a) => a,
        Pair::Right(_) => unreachable!(),
    }
}

fn cdr<A: std::clone::Clone, B: std::clone::Clone>(p: impl Fn(bool) -> Pair<A, B>) -> B {
    match p(false) {
        Pair::Left(_) => unreachable!(),
        Pair::Right(b) => b,
    }
}

这两节课主要建立了“函数是第一公民”的印象，并且引入了 cons，这样就可以建立更加复杂的结构，之后的课程会从语言本身的性质转为研究一些复杂性的处理

自顶向下.Wikipedia [DB/OL].(2024-10-28)[2024-11-05]. https://en.wikipedia.org/wiki/Bottom-up_and_top-down_design

一等公民.Wikipedia [DB/OL].(2024-06-25)[2024-11-05]. https://en.wikipedia.org/wiki/First-class_citizen

互质.Wikipedia [DB/OL].(2024-10-22)[2024-11-05]. https://en.wikipedia.org/wiki/Coprime_integers

⁴

构造器.Wikipedia [DB/OL].(2024-08-09)[2024-11-05]. https://en.wikipedia.org/wiki/Constructor_(object-oriented_programming)

⁵

访问方法.Wikipedia [DB/OL].(2024-10-06)[2024-11-05]. https://en.wikipedia.org/wiki/Mutator_method

⁶

$λ$ -演算.Wikipedia [DB/OL].(2024-10-25)[2024-11-05]. https://en.wikipedia.org/wiki/Lambda_calculus#Pairs

Kevin Stephen's Blogs