《SICP》｜第一章：构造过程的抽象

作者: 唐鱼的学习探索 | 来源:发表于2017-09-22 09:54 被阅读0次

软件工程大师能够组织好自己的程序，预先发现自己程序的行为方式，即使发生问题也能很快的排出错误，就像一部汽车一样，拥有各个独立的模块，可以分别构造、替换、排出错误。我们这一章正是要了解这种抽象的能力，将对计算过程的认识从实际层面隔离开来，形成更为高阶的抽象认识。

接下来的课程将使用Lisp中的scheme方言，这一语言应用的范围并不广，但是有一个很好的优点是：计算过程的Lisp描述本身又可以作为Lisp的数据来表示和操作。

1.1 程序设计的基本元素（Lisp语言基础知识）

在程序的设计中，我们必须要处理两类：过程和数据。这一章的例子中我们使用的是简单的数值数据，以将我们对注意力放在构造过程对规则中去。

① 表达式

程序设计里面最简单的就是表达式，你最好找到一个lisp的解释器，输入表达式然后得到响应，我使用的是DrRacket和mit-scheme。

你可以尝试输入一些表达式，这里和我们平常的程序设计语言不同的是对于表达式的求值，使用的是前缀的方式，这样也有两个好处：1> 完全适用于任意多个实际参数的过程；2> 允许嵌套可以直接扩充；

我们建议在适用复杂的表达式的时候，保持各运算对象的垂直对齐：

运算对象对齐

② 命名和环境

我们编写复杂的程序，也是一步步由简单的过程构成，如果必须记住并重复每一个细节，这栋大厦是根本无法完工的。好在解释器提供了一个名字和对象的关联功能，也就是lisp中的define，提供了一种由名字到过程的简单抽象。

如此以来，当我们在计算圆周的时候就不需要重复的输入pi和radius的值，直接经由define定义的名字引用就可以了。

解释器提供的这种由符号到具体值的关联过程也就意味着必须要有一种存储能力，这种存储被称为环境，而环境所扮演的角色就是用于确定表达式中各个符号的意义。一个过程可能完全涉及多个不同的环境，这点后面讲。

③ 组合式的求值

组合式求值不难理解，一般来说有以下步骤：

1> 求值各个子表达式的值；

2> 将最左边的运算符应用于第一步求得的各个子表达式的值；

我们来看一个例子：

( * (+ 2 (* 4 6) )

(+ 3 5 7) )

这一求值过程有三个子表达式，共有4个运算符，我们画一张图来理解：

这个树形分支结构的每个节点的最左边是我们的运算符，相应的右边是表达式或者具体的值。用这种结构来看待求值的过程，可以想象子表达式求得的值向上穿行，最终形成计算结果的一个过程（390）。

反复的运用于步骤1，始终能把我们带到一个子节点，他的最左边是运算符，右边是相应的具体的值，我们通常所说的运算符（+ - * /）其实也是指令序列与之关联，也就是环境中的每个符号都有意义。

④ 定义过程

我们这里所说的过程就像我们最开始学习程序设计中的定义函数，这是一种威力更强大的抽象技术，我们可以组合多个操作，然后为其提供一个名字，在lisp中我们如下定义过程：

求一个数的平方

这一过程也就是：

（define (函数名形参）（函数体）)

我们也可以将我们定义好的过程由于其他过程的定义中：

(define (sum-of-squares x y) (+ (square x) (square y)) )

计算两个数的平方和

⑤ 过程求值的代换模型

我们这里要讲解一个代换模型，而后的篇章将发现这个简单模型越来越不适用，直到必须使用更精细的模型取代，这种从简而繁的过程正是建立复制事物的基础。

我们继续定义函数f，使得其有如下行为：

(define (f a) (sum-of-squares (+ a 1) (* a 2)))

我们来看看（f 5）的求值过程：

我们从实际参数5出发，一步一步向上求值，得到最终的结果136，每一步我们都将得到的具体值传递给相应的过程。这样的一个求值过程称为应用序。还有一种被称为正则序的过程，如下：

正则序

完全展开而后求值被就是正则序，这两种方式得到结果是一样的，而应用序剔除了重复计算的过程，效率更高，Lisp采用的是应用序。

⑥ 条件语句和断言

求绝对值

这里使用cond条件的三条语句，将顺序求值，如果1，2，3中有一为真，表达式的结果就是其后的值，如果都为false的话cond的值就没有定义。

变式，else语句：

else语句

变式，if语句：

if语句

备注：复合逻辑运算符and,or,not同于我们学过的程序语言的求值方式，不作讲解。

⑦ 采用牛顿法求平方根

说明性的知识与存在性的知识之间本身存在着巨大的差异，在计算机的世界里我们需要的是更多行动性的知识，我们先来看看平方根的定义：

平方根的定义

有了这个定义以后我们并不能转化成有效的程序，我们没有相应的求解的方式，只能简单的对一个数是否是另一个数的平方根进行判断，来看看牛顿大神的方法（哪里都有他）：（牛顿法详细为什么这么做）

求解2的平方根

假设我们要求出x的平方根，初始的猜测值为y，我们只需要计算(y + (x / y)) / 2，就能改进我们的猜测值，随着多次的迭代我们就将越来越趋近于我们的答案。有了方法以后，我们来看看如何转换成相应的代码：

求解一个数的平方根

1.2 过程与它们所产生的计算

我们在1.1节中已经学习了编写程序的基本规则，但这还远远不够，就像下象棋一样，你只了解基本的走法是不可能战胜对手的，你必须要学会打谱，了解一下经典的开局、战术和策略。我们编写的过程就是这种策略，要想成为编程专家，你必须要了解不同种类的过程所产生的计算过程和结果，所消耗的计算机资源以及计算过程的形状。下面我们从最基本的过程策略讲起：

① 线性的递归和迭代（两种常见模式）

让我们以阶乘函数，其数学定义为：

阶乘函数定义

我们直接将其翻译成递归代码形式：

递归代码和其计算形状

我们还可以使用一种线性的迭代，它的原理就是如果我们准备3个变量，product保存乘积，counter作为计数器，max-count作为我们要计算的数。当我们同样计算6的阶乘的时候，我们首先令product为1，计算器counter为1，通过不断的使用product = counter * product，counter = counter +1的方法，更新counter，将乘积累积在product直到counter的值超越了所要求得的阶乘值时，停止，这一过程可以定义为如下函数：

迭代的代码和计算形状

两种过程虽然都是同一个函数的求解，但是其计算过程的形状完全不同，递归过程有一个完全展开而后计算收缩的链条，这个链条是由解释器负责维护；而迭代过程却不需要有这一的链条，所有的东西都在product、counter、max-count中保存，这种过程有变量更新计数，和函数结束时候的检测。

这里特别要注意一下，我们区分两个概念：过程和计算过程，当我们所某一个过程是递归过程的时候，形如上面两个过程是说其形式上都有调用自身的现象。但这两个递归过程的计算过程却不同，第一个递归调用过程的计算有线性递归，而第二个递归过程的计算过程却是线性迭代。所以说我们看事物的时候不要被起表面形式所迷惑，深究事物的本质有其重大的意义。

② 树形递归

树形递归是我们要介绍的另外一种计算模式，最典型的例子就是斐波拉契数列，数学定义我们就不再重复介绍，直接上代码（递归形式）

斐波拉契数列

其计算形状为典型的树形：

树形计算形状

我们明显看出这一计算过程有太多的重复，特别是对fib3的计算基本上占了大部分的内容。

当然也可以使用迭代的方式，构建两个变量a、b满足如下关系：

带入计算（fib6）的值

完整的代码如下：

迭代法完整代码及演示

两个计算过程比较来看树形递归的确不如迭代高效，但有一个明显的优点是便于理解，几乎是斐波拉契数列的直译版本。如果使用迭代的方法，我们需要重构这个过程，发现其中的奥秘，对大部分人来说可能过于困难。

实例：换零钱的方法统计

我们有5种货币：1美分、5美分、10美分、25美分、50美分，换成1美元换法（美元里面美元角的概念，所以1美元=100美分）描述如下：

1->（树形左侧）用了最大的面额的，减去最大面额的值，继续处理（默认使用最大面额）；

2->（树形右侧）没有用最大面额兑换的，不考虑最大的面额，继续处理（不用最大面额）；

画个图分析一下：

换零钱树形递归结构

我并没有画完，因为这个过程太过庞大了，但大致的结构如上图。

我们用一个简化的图形来说明这个过程：

使用1，3，5凑整10

计算的结果和我列举的一样7种，当amount为0的时候只有一种；当amount＜0或者货币没有的时候为0种。

③ 增长率

我们有时候需要估算不同代码在消耗计算资源上的不同，毕竟如果一个算法耗时太长以至于无法忍受的程度，就算其有解也是毫无意义的。我们引入一种标记方法：Θ（读作theta），R（n）表示一个在参数n的规模下，所消耗的计算资源（resource），记为：

Θ（f（n）） = R（n）

这一计算方法为我们在估算一个计算过程的问题规模改变时，提供了有用的线索，对于某种计算过程：

3种步长有同样的增长率

这三种计算过程的不同步长，有同样的增长率

④ 求幂

我们接下来的内容具体分析一下不同计算过程的资源占用率，看看如何改进我们的计算过程。求幂的数学定义我们就不作讲解了，先来看看第一个版本：

递归计算模型

这一模型基本上是数学函数的直接代码翻译，这一模型需要Θ（n）步和Θ（n）的空间（递归），我们很容易翻译成迭代形式：

迭代计算模型

这一模型需要Θ（n）步和Θ（1）的空间，我们还有方法改进这一模型吗？

观察这一一个事实：

偶数幂

对于指数为2的乘幂都可以使用以上这种方法求解，计算模型变更为：

定义新的计算过程如下：

改进版本

⑤ 最大公约数

最大公约数的数学定义我们不做解释，将一个著名的算法说一下，欧几里得算法：

GCD（a，b） = GCD（b，r）其中r是a除以b的余数

多次相除以后r必定为0，剩下的b就是最大公约数，看一个例子：

欧几里得算法范例

我们很容易将其翻译成代码计算过程：

迭代过程

分析其资源消耗率，我们发现一个定理，Lame定理：欧几里得算法所需要的k步计算出一对整数的gcd，那个这两个整数中较小的那个数必然大于或者等于第k个斐波拉契数。这样，算法的增长率也就是Θ（log n）。

⑥ 实例：素数检测

素数定义为在大于1的自然数中，除了1和它自身外不能再有其他因子。最直接的方法就是从2开始直接计算被测验数n是否能被整除，请看下面的代码：

直除检测法

其中核心的函数是find-divisor，它有两个参数，被测验数n和测试因子（从2开始计算）。这一函数的结束判断有两种，cond的第一个条件是被测验数大于了n的开方，停止检查（求值的范围只能在1至n的开方之间）；第二个条件就是找到了能被整除的数test-divisor，结束检查不是素数。else执行我们的递归调用，更新测试数，继续查验。这也就意味着这一计算过程拥有the-tan的开方的增长率。

费马检测法：

第二种方法使用的是，对于给定的整数n，随机选取一个数a＜n，计算出a的n次方除以n的余数，如果得到的结果不等于a，那么n就肯定不是素数；如果得到的结果等于a，那么n是素数的概率就要大些。多次测验以后我们的信心就会不断的增强。我们来看看代码：

费马检测法

先来看看主要函数fast-prime？，输入两个值被检测数n和测验次数times，当测验次数递减为0任然没有检测出不是素数的话，输出true；否则调用fermat-test函数测验n在随机生成数a的情况下是否满足费马检测条件，如果满足素数的条件继续下一次调用fast-prime？，并将次数times更新减去1；

再来看看fermat-test函数，主要使用的是random生成了1到n-1之间的随机数a，放入try-it封装的expmod函数进行处理，返回的结果与a比较看是否满足费马条件；

最后来看看expmod函数，它有三个参数随机数base（随机数），exp（幂），和m（被测验数），主要用于计算一个数的幂对另外一个数取模的结果，用到了1.2.4中的奇偶分形判别法，并将结果与被测验数n取模的结果返回给调用函数。

总结一下，费马检测这种方法不同于我们已经学到的其他算法，通过费马检测的数只能说是概率上很有可能是素数，如果我们测验的次数足够多，我们能够将这种概率调至任意我们满意的程度。这一类算法叫做概率算法。

1.3 使用高阶过程构造抽象

如果我们将过程限制为只能接受以数为参数，就会严重的限制我们构建抽象的能力，在这一小节中我们需要了解高阶过程的抽象原理，所谓的高阶过程就是以过程为参数，或者以过程作为返回值的过程。

① 以过程作为参数

我们首先观察三个过程：

虽然表面上看是三个不同的计算过程，但是其模型几乎是一样的，我们替换出来就是：

有了这个模型以后，我们尝试写出通用的求和算法：

同计算模型不同的地方是，这里有term和next两个过程作为参数，只需要一些简单的定义，就可以用作计算a到b的立方和了：

同样的原理，上面的三个例子都可以使用这种方法稍加改变就能开始计算。

② 用lambda构造过程

lambda表达式提供了一个更加简练的函数式语法来写匿名方法，不需要定义过多的辅助过程。

使用的方法上和define相同，只是不提供相应的函数名：

lambda表达式

使用let创建局部变量：

假设我们有如下函数

为了便于理解，我们令：

我们使用两种方法定义这一计算过程（普通和lambda）：

这种结构非常清晰和好用，以至于专门发明了一种叫做let的表达式：

使得var1具有exp1的值，var2具有exp2的值，依次类推。我们使用新的let表达式重写上面的lambda结构：

let表达式的第一部分维持的是一个变量名-表达式的对偶表，每个变量名关联于对应的表达式的值，这些变量名都为let的局部变量，再来求值let的body中的内容。我们观察到这一表达式仅仅是lambda表达式的一个变种，不需要解释器再提供其他的新的机制就可以依靠lambda来实现。有两点需要注意的地方：

1> let使得人们能在尽可能接近其使用的地方建立起局部变量约束；

2> 变量的值是在let之外计算的。（说明：

注：如果x的值是2，那么在let内的x=3，y=4，y的值是在let之外计算的，不同于其局部性变量x的值，这一点要特别的注意）

③ 找出函数零点（求根）和不动点的一般方法

区间折半法寻找方程的根：

这种方法的基本思路是如果有f(a)< 0 < f(b)也就是说f(a)和f(b)中必然有一个零点，我们可以通过求得a和b的平均值来计算出相应的f(value)如果为正，就同f(a)继续计算中间点，如果为负，就同f(b)计算中间点，函数逐渐逼近到我们想要的任何精度即可求出f(x) = 0。直接上代码：