SICP 第一章(构造过程抽象)

发表于 2025-05-30 分类于编程语言理论阅读次数：

程序设计需要考虑的基本元素

基本的表达形式: 基本的数据表达与基本的过程表达
组合的方法: 将基本表达组合起来构成复合的元素, 如 Lisp 的组合式
抽象的方法: 为复合对象命名, 从一个新的抽象层次操作非基本单元

在 lisp (SICP 使用 scheme 方言) 中有如下体现:

上述概念在 Lisp 的体现

表达式:

基本表达式(如数这样的自求值原子表达式或 + 这样表示基本过程(算术运算)的符号表达式), 或基本表达式组合构成的复合表达式

复合数据: 组合式

形如 (+ 1 2) 用一对括号扩起一些表达式称为组合式来表示一个过程应用, 最左侧称为运算符, 其它称为运算对象. 允许出现组合式嵌套的情况(组合式元素本身还是组合式).

组合式的求值

先求值子表达式, 再将其最左子表达式的值(即一个运算符代表的过程)应用于相应的实际参数(即子表达式运算对象的值), 如 (+ 1 2) 先对 1 和 2 求值, 自求值原子表达式的值分别为 1 和 2, 再将 + 代表的加法过程应用到实际参数 1 和 2 上.

如果有 (define x 1) 或者 let 使名字与一个值相关联后, 求值时就会环境中找这个名字对应的值. 环境维护一个名字与一个值的映射, 具有不同层级 (全局环境和局部环境), 与上下文的概念类似, 在一些常见编程语言中通常用栈帧实现.

有嵌套的组合式就涉及递归求值.
结构化求值:

树形积累 是一种结构化求值的模型, 将表达式作为一个树形结构, 从叶子节点开始逐渐向上组合.
代换模型

通过替换逐步规约表达式, 直到无法继续规约.

应用序: 在任何表达式的计算过程中, 先求值得到实际参数, 再将过程操作应用于实际参数.如 (square_1 (square_2 x)) 的计算过程(这里角标只是方便叙述): 先求 (square_2 x) 得到实际参数 (* x x 的值) 再应用 square_1 过程到这个实际参数上面, 可以看到 square_2 被应用一次.
正则序: 在任何表达式的计算过程中, 先尽可能完全展开树形结构, 而后向上规约. 同样以上一个为例: 先尽可能展开: (* (square_2 x) (square_2 x)) 再展开 (* (* x x) (* x x)), 可以发现 square_2 被应用了两次.

由于正则序的重复计算性质, Lisp 采用应用序. (当然, 正则序也是有意义的)

复合过程:

过程和函数的区别: 函数更注重”是什么”, 过程更注重”怎么做”.

(define (<name> <parameters>) <body>) 是一个过程定义. 注意这(本身)并不是一个组合式, 而是一种特殊形式, 不遵循上述求值的一般规则.
条件表达式: (cond (<p1> <e1>) (<p2> <e2>) ...), 其中 <p> 是一个谓词(Predicate, 值为真或假), <e> 是一个普通表达式. 计算过程是先判断 <p1> 是否为真, 如果为真则 cond 的值就是 <e1>, 否则检查 <p2> , 依次类推. 如果 <p1> 到 <pn> 均为假, 则 cond 无意义; 另一种条件表达式是 (if <predicate> <consequent> <alternative>).
过程封装了内部复杂的逻辑形成了一个黑箱, 这种抽象方式减轻了思维负载, 其依靠的特性之一就是局部名不影响全局的值.

总结

1.1.7 以牛顿法求平方根为例简单展示了使用 Scheme 复合基本数据和复合基本过程来构成代码的实例

1.1 - 1.8习题:
改写为前缀表达式和根据需求写 lisp 比较简单.
比较有意思的是1.5, 如果是应用序, 先规约后展开, 解释器会一直在对 (p) 进行求值 ((define (p) (p))) 时无限递归, 永远无法得到实际参数; 如果是正则序, 先展开后规约: 根据 if 的短路特性, 在 predicate 为真时只对 consequent 求值, alternative 不会被求值, (p) 不会被递归.
1.6 中的 new-if 是一个过程并不是特殊形式, 所以没有 if 的短路特性. (注意区分语义和实现过程, 不要和分支预测混淆)

过程及其产生的计算

递归与迭代过程

通过 (* n (f (- n 1))) 和 (iter (* result n) (- n 1)) 方式计算阶乘

对前者来说, 其代换模型展现出一个先构造其一个推迟执行的长链(先求 $(n-1)!$ 获得返回值再推迟乘 $n$ )后再收缩(对每个得到的返回值乘当前 $n$), 这个计算过程是一个递归, 且因为其执行次数与 $n$ 成正比, 称为 线性递归. 总结一下: 递归过程的特点: 信息由返回值获得, 推迟执行, 计算状态隐含在代换模型长链的构造与收缩中
对后者来说, 由第一个形式参数 result 保存信息, 不推迟, 直接执行乘 $n$, 然后再用乘法所得结果替换下一次执行的形式参数实现了用参数而不是返回值保存信息. 由于执行次数与 $n$ 成正比, 称为 线性迭代. 迭代过程的特点: 由几个变量保存迭代状态, 不推迟执行, 计算状态单纯由迭代状态量表示
注意不要混淆计算过程的与实现的区别, 从这个实现上来讲这两者都是递归; 迭代的实现也不一定是要用递归和参数保存信息, 部分语言中也有循环语法实现迭代$^{[1]}$.

${[1]}: $ 任何循环都能由递归表示和实现, 反之亦然
但由于递归的实际实现方式开销较大(保存上下文等), 所以编译器往往是将递归优化成循环. 编译器通常只优化尾递归 (称为尾调用优化), 尾递归 是”递归调用在过程的最后一步”的递归, 这样的递归转换为循环是很方便的. 但通用递归到循环的转换非常复杂, 需要模拟调用栈等, 反而开销会更大一些.

练习 1.9:

(define (+ a b) 
    (if (= b 0) a
        (inc (+ a (dec b)) ) 
    )
)
; 代换模型类似 (inc (inc (inc (+ 0 res)))), 在达到递归边界之前一直在推迟计算

(define (+ a b) 
  (if (= b 0) a
      (+ (inc a) (dec b))
  )
)
; 代换模型类似 (+ 0 res), 没有推迟计算

~~话说我第一次老老实实展开看代换模型写对了, 写这个博客的时候算第二次试图直接看结果看错了~~

练习 1.10: 直接展开模拟然后归纳, 但是我之前写的时候墨迹太乱了, 依稀只能看出有一个是 $^{n-1}2$ (即 $2^{2^{2^{2^{...}}}}$)

树形递归

像斐波那契的递归求法这样的 DFS 过程称为树形递归, 其代换模型不是一长链, 而是一棵树.

递归如何简化逻辑

以书中对任意数量 $n$ 现金求拆分成 $c$ 种价值的零钱的方法数 (称为 $f(n, c)$ ) 为例.
递归可以将其简化为单纯的分类过程: 数量为 $n$ 的现金可以 “使用第一种硬币” 和 “不使用第一种硬币”, 因此拆分种数也就是 “拆分 $n$ 为除第一种硬币之外的其他 $c-1$ 币种的拆分数” 加上 “仅使用一次第一种硬币, 递归拆分 $n - d$ 为 $c$ 币种的拆分书”, 即递归为 $f(n, c-1)+f(n-d, c)$ . 再确认相关递归边界即可.

(define (f n c) (cond 
                 ((= c 0) 1) 
                 ((or (< c 0) (= n 0)) 0)
                 (else (+ (f n (- c 1)) 
                          (f (- n (coins c)) c) 
                          ))
                 ))
; coins 是一个根据 c 币种编号返回对应币种价值的过程, 类似承担数组/map的职责
; 这 scheme 写起来匹配括号看眼花了, 我懒得写了()

练习 1.11: 看起来是个非常直观的树形递归, 所以用递归很好写; 迭代过程需要反着算(因为不能推迟计算), 从 f(0), f(1), f(2) 往上加算出 f(n) 来

复杂度分析

给了标准的大 $\Theta$ 记法的定义: $k_1g(n) \leq f(n) \leq k_2g(n)$ 称为 $f(n) = \Theta(g(n))$.
(btw, 大 $O$ 记法就是把下界换成0, 仅代表上界, 即最坏情况)

练习 1.19 很有意思, 总之就是按他说的去推, 最后是: $T^2_{pq} = T_{p'q'}$, 其中 $p' = p^2+q^2, q' = 2pq + q^2$.

高阶函数做抽象

过程作为参数

lisp 中过程可以直接作为其他过程的参数.
如果需要临时的匿名过程, 可以使用 lambda: lambda (<parameters>) <body>
如果需要建立临时变量约束, 可以用 lambda 的一种语法糖 let:

(let ((<var1> <exp1>)
  (<var2> <exp2>)
	...
  )
  <body>
)

// TODO

过程作为一般性方法

折半法找函数的根, 找函数不动点

过程作为返回值

牛顿法

练习: