无数的事实证明,人脑的能力是非常有限的,尤其是应对海量的、毫无关联的信息以及十分复杂的过程之时,我们很容易便迷失于其中,难以理出一丁点头绪。与人类相反,计算机却是特别擅长于处理海量信息,他们先天比人类更适合于进行严密的逻辑演绎推理,处理复杂而又精细的事物。所以,作为提升生产力的手段,我们常常使用计算机代替我们从事这一类的工作,从而避免麻烦,也避免犯错。

可是,问题是,作为一名和计算机打交道的软件工程师,我们却不得不混迹于复杂诡谲的逻辑之中,绞尽脑汁寻求答案。只因为计算机只是一个严谨的实践者,需要我们提供解决问题的步骤。

如何解决困难的问题,构建复杂的系统?我们采用的方式便是控制复杂度,其重要手段便是抽象。这种策略是非常Brain-Friendly的,它使得我们在任何时候都只关注问题的某一部分,而忽略其他细节。

抽象是在诸多工程领域都有所应用。硬件工程师造出视频的编码解码芯片,对于其他的工程师来说,他们无须知道具体原理,对于需要执行编码或者解码的工作,只需要述诸解码芯片这个抽象的黑盒便可完成;软件工程师使用高级语言书写程序,于是我们不需要知道应该用怎样的机器指令实现这些逻辑,只需要通过高级语言告之计算机,我们需要做算术运算,逻辑运算,条件判断或者循环等等即可。即使是在非工程领域,抽象(复杂度控制)这种手段也常被应用,比如公司或者国家的层级化管理,就是一种体现。

我们所做的一切,都是在其他人,或者我们自己之前建立起来的城池之上继续搭建亭台楼阁。而因为有了之前刀耕火种修建城池的基础,我们不再需要从头做起,只需要用现成的零件即可。当然,在计算机领域,这种零件往往指的是一种思想,或者抽象物件而非实体。

SICP全书便是讲的“抽象”这个强大的工具,是如何在计算机领域,在整个计算机体系上上下下所体现的。

SICP一开始两章便是以数据抽象和过程抽象这两个最基本的概念引入的,不过这两个概念基本上是任何一个学过编程的人都能掌握的,其内容乏善可陈。不过鉴于SICP只不过是MIT的本科生入门教程,倒也无可厚非。

和传统的编程教程不同,SCIP一开始便选取了LISP作为全书使用的编程语言。稍微了解一点历史的人都知道,LISP是函数式编程语言,脱胎于Church著名的lambda Calculus模型,而我们平常使用的Java,C++等语言的理论模型则是图灵的图灵机。这两者在计算能力上虽然是完全等价的,不过作为语言的使用者,我们还是能够深深地感受到这两种不同思想所带来的别样的乐趣。

因为LISP继承了lambda Calculus的思想,有较为浓重的学术气息,我想这也是为什么作者Albeson和Sussman选择使用LISP来教学的原因之一(作者提到的另一点原因是LISP的语法的简洁性适合于教学)。

第三章则是讲述了如何对状态进行建模。如果说之前章节使用的LISP能够算是纯函数式语言(pure functional programming language)的话,那么这一章对变量的引入,则使得我们开始接触了混合的函数式语言。

虽然变量对于当今的程序员来说犹如家常便饭,但它引入却给LISP的编程模型带来了巨大的改变。现在我们考虑一个非常普通的求阶乘的函数:

1 (define (factorial n)
2   (if (= n 1)
3       1
4       (* n (factorial (- n 1)))))
5 
6 (factorial 4)

作为一名合格的程序员,我们看到这段代码后,脑子里会立马模拟出其执行时的状态。首先我们用参数4调用了factorial函数,这表示我们要求的是4!。于是我们程序进入factorial函数,然后函数判断参数的值…… 但是,等等,在我们用一个动态执行的、机械式的角度审视这段代码之前,我们可以尝试从一个新的角度去理解这段代码。而LISP能给我这个看待程序的新思路:

 1 ;generate sequence(list)
 2 (factorial 4)
 3 (* 4 (factorial (- 4 1)))
 4 (* 4 (* (- 4 1) (factorial (- (- 4 1) 1))))
 5 (* 4 (* (- 4 1) (* (- (- 4 1) 1) (factorial (- (- (- 4 1) 1) 1)))))
 6 
 7 ;resolving value for list
 8 (* 4 (* (- 4 1) (* (- (- 4 1) 1) (factorial (- (- 3 1) 1)))))
 9 (* 4 (* (- 4 1) (* (- (- 4 1) 1) (factorial (- 2 1)))))
10 (* 4 (* (- 4 1) (* (- (- 4 1) 1) (factorial 1))))
11 (* 4 (* (- 4 1) (* (- (- 4 1) 1) 1)))
12 (* 4 (* (- 4 1) (* (- (- 4 1) 1) 1)))
13 (* 4 (* (- 4 1) (* (- 3 1) 1)))
14 (* 4 (* (- 4 1) (* 2 1)))
15 (* 4 (* (- 4 1) 2))
16 (* 4 (* 3 2))
17 (* 4 6)
18 24

可以看到,和按照指令“执行”一段程序不同。LISP给了我们一种静态的感觉,我们似乎不是在执行一段代码,而仅仅是根据各种条件生成了一段列表(LISP语言的全称是LISt Processing),然后再对这个列表求值。这正是Church的lambda calculus思想的体现,我们以一种静态的定义性的语言来描述计算过程,而不是通过命令式的方式来说明每个步骤的内容。

于是在计算过程当中,我们脑子里呈现的模型是这样的:

而不是这样的:

1 int factorial(int n){
2 	int result = 1;
3 	for (int i = 1; i <= n; i++) {
4 		result *= i;
5 	}
6 	return result;
7 }

然而,LISP这种静态的美却轻易被变量的引入打破了。在未引入变量之前,LISP是referential transparency的,这意味着对于程序中的任意一个表单式、函数,都能被替换成其值,而不影响程序的行为。例如:

1 (+ (factorial 4) (factorial 6))

我们能轻易地把(factorial 4)替换成24, 把(factorial 6)替换成720。基于这一点,在编译器优化技术中,我们常常对具有referential transparency性质的函数进行优化,将其运行时的计算开销挪到编译时,从而提升程序效率。

实际上,所有数学意义上的函数都是referential transparency的。而LISP作为纯粹的函数式编程语言来使用时也具有这种特性,不得不说它作为和数学有的很大的渊源。但是如果我们引入变量(状态),情况便大有不同了:

1 (david-withdraw 50)  ;=> 200
2 (david-withdraw 50)  ;=> 150
3 (+ (david-withdraw 50) (david-withdraw 50))

很容易看到,referential transparency在这里完全失效了。我们失去了数学公式静态的、定义式的代码,因为这里每一个语句都包含了一个隐藏在台面下的状态:David的账户余额。于是调用两次函数(david-withdraw 50),函数名和参数完全一致,却返回了不同的结果,这和数学上定义的函数便有了分歧。

相对于于理论的纯粹精巧之美,现实总是充满了各种妥协。我们在建模客观世界时,状态、时序是一个很重要的东西,我们不能放弃它,于是我们只能放弃LISP纯粹的理论之美。(于是substitution模型被Environment模型所替代,这种思路的影子仍可见于许多现代语言之中:例如Ruby和Javascript)

于是构建于变量这一抽象物件至上,我们实现了对客观事件状态的建模。这之后,两位作者笔锋一转,开始讲述起了语言的抽象。我们在高级语言这个抽象之上实现了数据和代码的高级抽象。那么,我们又是怎样建立高级语言这种抽象的呢?Albeson和Sussman在这里做了一个精巧的阐述,为了说明如何实现这个抽象,他们首先用LISP语言本身去实现了一个LISP。

这个思路其实不新奇。比如第一个C语言编译器被创造之后,到目前为止,大部分的c编译器都会使用C语言来实现自己。这不就是用C语言实现C语言的例证么。

书到这里,使用LISP的优势就体现出来了。由于LISP语法十分简单,做parsing几乎不费吹灰之力。甚至可以说,我们直接使用LISP自己的功能,就能得到一串LISP代码所对应的抽象语法树。而这个工作要是放到C语言环境下,恐怕就得拿出lex&yacc这类工具了。

整个LISP语言的实现非常简单,就是在这棵语法树上做解释执行。这里我们可以说,我们造出来的类LISP语言,是构建于我们使用的LISP编程语言之上的。

但这个模拟仍不够精确,因为真正的LISP语言是运行在计算机上面的,是由CPU直接执行的,而不是由另外一层LISP的抽象执行的。为了更加精确的表述这一点,两位作者又继续往下走了一层,开始用LISP模拟一个CPU出来。这样就造出一个能够执行某个指令集的抽象,然后我们在这个抽象上实现LISP语言,继而让读者了解到LISP是如何在机器层面上执行的。

Simulator的实现实际上不算困难,用几个变量便能模拟出寄存器。于是我们的机器便有了状态,在此基础上再引入一些逻辑运算指令,算术运算指令,一个可以用的CPU抽象便完成了。

不止如此,在造出一台模拟的机器之后,为了展示如何实现LISP这个抽象,两位作者又实现一个编译器,将LISP语言编译成之前实现的抽象机器能够理解的指令集…… 所以,为什么SICP这么一本LISP教程,一本讲“抽象”这一思路的书,能够被奉为经典?原因就在于两位作者为了阐明这些观点,实现了一个编译器,一个类x86的模拟机器,一个解释器。这也是为什么大部分书评都建议读者一定要看看最后两章的原因。

总之,无论作为一本计算机科学思想导论,还是作为一本LISP教程,还是作为一本“抽象”教学工具,亦或是作为编译器,解释器实现原理教程,SICP都是一本值得一读的好书。