SICP学习笔记 第一章 构造过程的抽象

这篇文章是SICP一书中第一章的笔记。
文章中用到的图来源MIT.EDU SICP Full text
原书中例子是用scheme写的,这里用JavaScript改写。
例子中的>表示输入,<表示输出。

编程的基本元素

表达式

原始表达式

原始表达式由一个值(字面量)构成,其运算结果也是这个值。

255, 255.0, 0xff, 0377, 0b11111111, true, false, "255"

原始过程

原始过程指常见的内置于语言实现的过程,也叫做运算符,如:

1
2
3
4
5
6
7
8
9
位运算符
& | ^ ~
算术运算符
+ - * /
逻辑运算符
&& || !
赋值运算符
=
等...

组成表达式

表达式由过程和参数组成,也可以说是由运算符和运算数组成。

表达式经运算后会返回一个运算结果。

组合原始过程和原始表达式的表达式如:

1
2
3
4
5
6
7
8
> 255
< 255
> 255+1
< 256
> 1000-334
< 666
> 5*99
< 495

命名与环境

1
2
3
4
5
6
a = 1
inc = function(a) {
return a + 1;
}
b = 1
a = 3

以上表达式执行之后,当前的环境可以表示为:

Symbol 符号 Value 值
a 1 3
inc [Code]
b 1

我们可以说这个Symbol唯一标识了一个值为特定对象的变量。

环境其实也分全局环境和局部环境,而局部环境又是分层级的,当寻找某个Symbol的定义时,程序会先在当前环境查找,如果没找到,则在上层环境中寻找,最终在全局环境中寻找,如果还是没能找到,则可以确定这个Symbol未定义,报错。
当程序执行到块结构结束后,该块结构中的局部环境不再保留。
同层级的环境是没有交集的。

过程

类似的概念有函数,方法,子程序

1
2
3
4
5
6
7
inc = function(a) {
return a+1;
}
dec = function(a) {
return a-1;
}
a = 3

思考一下,以下表达式的值是什么?

1
2
3
inc(a)
inc(dec(a))
a
查看答案
1
2
3
4
5
6
> inc(a)
< 4
> inc(dec(a))
< 3
> a
< 3
这里要注意了,a的值没有被修改过。

得到的值没有和任何符号关联,所以之后是无法被引用的,但在返回时能被引用,这也是能够对a多次调用过程的原因。

复合过程

后面沿用之前的过程定义

1
2
3
add = function(a, b) {
return inc(a)+dec(b);
}

思考一下,以下表达式的值是什么?

1
2
add(3,6)
add(3,-6)
查看答案
1
2
3
4
> add(3,6)
< 9
> add(3,-6)
< -3

条件表达式与谓词

1
2
3
4
abs = function(a) {
if(a<0) return -a;
else return a;
}

思考一下,以下表达式的值是什么?

1
2
3
abs(-1)
abs(0)
abs(1)
查看答案
1
2
3
4
5
6
> abs(-1)
< 1
> abs(0)
< 0
> abs(1)
< 1

这里的abs过程中用到了if <predicate> <consequence> else <alternative>的条件结构,当<predicate>处的表达式的值为true时,执行<consequence>处的代码,否则执行<alternative>处的代码。

preficate即是谓词。

条件表达式使得过程可以根据参数的不同性质来执行不同的代码部分。

过程作为黑盒抽象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function double(x) {
return x+x;
}

//square过程的多种实现
function square(x) {
//Math.exp(x) 返回以e为底x为指数的值
//Math.log(x) 返回以x为底的自然对数
return Math.exp(double(Math.log(x)));
}

function square(x) {
return x*x;
}

可以看出这两种实现都能返回x的平方值(这里暂时不考虑精度)。

这两个过程对外的接口是一样的,过程名为square,接受一个参数,返回参数的平方值,这对于使用者就是一个黑箱的概念,使用者不需要知道其实现细节也能正常使用该过程完成运算。

局部名称

1
2
3
function isGoodEnough(guess, x) {
return abs(square(guess)-x) < 0.001;
}

过程实现的细节之一就是过程内部使用的形参名字,过程的意义不应该依赖于其作者为形式参数所选用的名字。

对于语言的实现者来说,他们得保证过程的形式参数必须局部于有关的过程体,也就是过程调用时必须为形参分配一个新的环境,确保过程中使用的形参的值确实属于过程自身,从而使得square能够成为一个黑箱。

过程的形参名称不影响该过程的定义,这样的名称叫做约束变量,我们也说这个过程的定义约束了它的形参。如果在一个完整的过程定义里将某个约束变量统一重命名,这一过程定义的意义将不会有任何改变。

如果一个变量不是被约束的,我们就称它为自由的

一个名字的定义被约束于定义这个约束的一系列表达式中,这些表达式所在的地方就叫做这个名字的作用域

在过程定义中,定义为过程中形参的约束变量,其作用域为整个过程体。

在上面的isGoodEnough的定义中,guessx是约束变量,但是<,-,abssquare是自由的。只要guessx不同于<,-,abssquareisGoodEnough的意义就不应该依赖于guessx的名字。(考虑一下,如果我们将guess重命名为abs,那么我们通过捕获变量abs引入了一个bug。捕获变量abs意味着其从自由的转为约束的。)

isGoodEnough不依赖于其自由变量的名字,但它确实依赖于这些自由变量的定义,如它希望abs是返回一个数的绝对值。如果abs的定义不是这样,那么isGoodEnough的含义也就不同了。

内部定义与块结构

1
2
3
4
5
6
function square(x) {
function double(x) {
return x+x;
}
return Math.exp(double(Math.log(x)));
}

这样在square过程内部定义了一个double过程,叫做嵌套定义,{}形成一个块结构。

这里的double是局部的过程定义,在square的块结构外是无法使用这个double过程的。

这样做的好处是形成了一个命名空间,将所有需要的新过程定义在内部,这样就不会依赖于外层环境中的double定义,因此也使得使用者能够在外层环境中自由地使用double这个名字。

过程和它们所产生的运算

线性递归与迭代

1
2
3
4
function factorial(n) {
if(n==1) return 1;
return n*factorial(n-1);
}

factorial(6)产生的计算过程如下图:

A linear recursive process for computing 6!

这个过程利用n的阶乘等于n乘以(n-1)的阶乘来实现求n阶乘的功能。

可以看到这是一个线性递归的计算过程,先展开再收缩最后得到结果。

不要把递归过程和产生线性递归计算过程的过程这两个表述混淆了,一个描述过程调用,一个描述过程调用所产生的计算过程。

考虑另一种实现方式,n的阶乘可以写成1*2*...*n的形式,那么用代码实现就是:

1
2
3
4
5
6
function factorial(n) {
function factIter(product, counter, maxCount) {
if(counter>maxCount) return product;
return factIter(counter*product, counter+1, maxCount);
}
return factIter(1, 1, n);

这时factorial(6)产生的计算过程如下图:

A linear iterative process for computing 6!

可以看出counter存的是计数器的值,而product存的是总的乘积。

相比之前的实现方式,这是一个线性迭代的计算过程,其没有展开再收缩的过程。

对于线性递归的计算过程,解释器需要保存过程调用中的信息随着乘积的链的长度的增加而线性增加。

相反,对于线性迭代的计算过程,解释器只需要保存当前调用的过程的信息即可,无论乘积的链有多长,所需要的空间是一定数量的(在本例中就是product, counter, maxCount)。

在一些编程语言中,针对后者的编译器优化叫做“尾递归优化”,编译器发现这种形式后,在递归调用过程时只会保存当前过程的信息。

练习1.10

下面过程计算一个称为Ackermann函数的数学函数:

1
2
3
4
5
6
function A(x, y) {
if(y==0) return 0;
else if(x==0) return 2*y;
else if(y==1) return 2;
else return A(x-1, A(x, y-1));
}

下面各表达式的值是什么:

1
2
3
A(1,10)
A(2,4)
A(3,3)

请考虑下面的过程,其中的A就是上面定义的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function f(n) {
return A(0, n);
}

function g(n) {
return A(1, n);
}

function h(n) {
return A(2, n);
}

function k(n) {
return 5*n*n;
}

请给出过程f,g和h对给定整数值n所计算的函数的数学定义。例如,k(n)计算的是5n的平方。

树形递归

Fibonacci数列有以下形式:

Fibonacci numbers

一般来说,可以通过以下规则来定义Fibonacci数列:

Fib(n) rule

写成代码:

1
2
3
4
5
function fib(n) {
if(n==0) return 0;
if(n==1) return 1;
else return fib(n-1)+fib(n-2);
}

fib(5)产生的计算过程如下图:

The tree-recursive process generated in computing (fib 5)

从这个计算过程中我们可以发现,其中有许多冗余的计算,如在本例中:

fib(n) 计算次数
5 1
4 1
3 2
2 3
1 4
0 3

结合之前的例子,思考一下,怎么把这个过程优化一下?

查看答案
1
2
3
4
5
6
function fib(n) {
function fibIter(a, b, count) {
if(count==0) return b;
return fibIter(a+b, a, count-1);
}
return fibIter(1, 0, n);
想出来了吗? 此时`fib(5)`产生的计算过程如下:
1
2
3
4
5
6
7
8
fib(5)
fibIter(1, 0, 5)
fibIter(1, 1, 4)
fibIter(2, 1, 3)
fibIter(3, 2, 2)
fibIter(5, 3, 1)
fibIter(8, 5, 0)
5

练习1.11

函数f由以下的规则定义:如果n<3,那么f(n)=n;如果n>=3,那么f(n)=f(n-1)+2f(n-2)+3f(n-3)。请写一个采用递归计算过程计算f的过程。再写一个采用迭代计算过程计算f的过程。

还记得递归计算过程和迭代计算过程有什么区别吗?如果忘记了就回顾一下前面所学的内容吧。

增长的阶

之前的例子说明了不同的过程消耗计算资源的比率上有很大的不同。

有一种便利的方式可以用来描述这一不同,那就是使用“增长的阶”这一概念来获取当输入变大时,一个过程所需要的资源的总体估计。

若n为描述问题的大小的量,则R(n)则代表过程解决这一问题所需要的资源的量。

在先前的例子中,我们把n选取为给定函数计算的数字,但也存在其他可能。

举例来说,如果我们的目标是计算一个数的平方根的近似值,我们可以把n选取为需要的数的精度。

而对于矩阵乘法,我们可以把n选取为矩阵中的行数。

总的来说,有许多问题的属性可以用来分析给定的过程。

类似的,R(n)可以估算内部存储寄存器使用的数量,基本的机器操作执行的数量等等。

在只能一段时间执行固定数量的操作的计算机中,花费的时间将与执行的基本的机器操作的数量成比例。

求幂

稍后补上。

用高阶函数做抽象

过程作为参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sumIntegers(a, b) {
if(a>b) return 0;
return a+sumIntegers(a+1, b);
}

function sumCubes(a, b) {
function cube(x) {
return x*x*x;
}
if(a>b) return 0;
return cube(a)+sumCubes(a+1, b);
}

function piSum(a, b) {
if(a>b) return 0;
return 1.0/(a*(a+2)) + piSum(a+4, b);
}

piSum计算的数列如下图:

piSum

其会非常缓慢地收缩到PI/8。

观察上面三个过程,你可以看出有什么共同点吗?

将a,b比作数轴上的一条直线的两个端点的话,上面的过程都是将从a到b的值加起来的过程,至于加多少和每次越过多少距离则各有差异。

用代码来描述的话,可以写成:

1
2
3
4
function sum(term, a, next, b) {
if(a>b) return 0;
return term(a) + sum(term, next(a), next, b);
}

sum过程和我们之前描述的过程有个很大的不同,它接受了两个过程作为参数,在递归调用过程之时,通过传入的过程对a的值进行处理,并且更新了下一次过程调用中a的值。

两个过程都是接受一个值并返回一个新的值,其中term是对”端点a“的值操作后加入总和,next则向b的方向“移动端点a”。

既然我们抽象出了以上过程的共同模式,让我们应用sum过程来修改sumIntegers,sumCubes和piSum三个过程吧。

还记得inc过程的定义吗?下面就不再单独定义了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function sumIntegers(a, b) {
function identity(x) {
return x;
}
return sum(identity, a, inc, b);
}

function sumCubes(a, b) {
function cube(x) {
return x*x*x;
}
return sum(cube, a, inc, b);
}

function piSum(a, b) {
function piTerm(x) {
return 1.0/(x*(x+2));
}
function piNext(x) {
return x+4;
}
return sum(piTerm, a, piNext, b);
}

是不是觉得没什么大的变化,代码量也没减少?接下来我们就学习一下lambda,之后就能看到这三个过程的显著变化了。

练习1.30

上面的过程sum将产生出一个线性递归。我们可以重写该过程,使之能够迭代地执行。请说明应该怎样通过填充下面定义中缺少的表达式,完成这一工作。

1
2
3
4
5
6
7
function sum(term, a, next, b) {
function iter(a, result) {
if(??) ??
else return iter(??, ??);
}
return iter(??, ??);
}

用lambda构造过程

之前过程中内部定义的过程其实只被引用过一次,单独赋个名字似乎有点多余,有什么办法简化一下吗?

我们可以定义一个匿名函数:

1
2
3
4
5
6
7
function piSum(a, b) {
return sum(function(x) {
return 1.0/(x*(x+2));
}, a, function(x) {
return x+4;
}, b);
}

好像还是没短多少?

考虑一种匿名函数的形式,它的定义形式为

1
2
3
(<formal-parameters>) => {
<body>
}

这就是lambda,那么应用lambda到piSum中:

1
2
3
function piSum(a, b) {
return sum(x => 1/(x*(x+2)), a, x => x+4, b);
}

因为函数体中只有一条语句,所以可以省略{}

现在piSum是不是非常简洁?提取公有模式后,借此写出的过程更加凸显了实际的代码逻辑。


考虑下面一种函数形式:

f(x,y)

我们换种写法:

f(x,y) with local variables

用代码表述出来:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function square(x) {
return x*x;
}

//最通俗的写法
function f(x,y) {
function fHelper(a,b) {
return x*square(a) + y*b + a*b;
}
return fHelper(1+x*y, 1-y);
}

//使用lambda
function f(x,y) {
return ((a,b) => x*square(a) + y*b + a*b)(1+x*y, y-1);
}

//使用let声明局部变量
function f(x,y) {
let a = 1+x*y;
let b = 1-y;
return x*square(a) + y*b + a*b;
}

相比之下,是不是最后一种更加直观?

这里我们就用let声明了a,b两个局部变量。

在Scheme中,let表达式被解释成对应的lambda表达式。也就是说let只是一个语法糖,所以解释器不需要新的机制就可以提供对局部变量的支持。

过程作为一般性的方法

见前面sum的例子。

过程作为返回值

过程可以作为过程的参数,有没有可能让一个过程的返回值也是一个过程?

答案是肯定的。

1
2
3
4
5
6
7
function average(a, b) {
return (a+b)/2;
}

function averageDamp(f) {
return x => average(x, f(x));
}

能看懂吗?想一下averageDamp(square)(10)的值是什么?