2014年12月, 我在知乎上发现一本被大家广为推荐的书, 叫做《计算机机程序的构造和解释》(SICP)。当时的我决定还是要正儿八经地学习一些编程知识,于是搜索了许多程序领域的入门书籍, 发现SICP和UC Berkeley的课程CS61A好评较高,且思想相近,一个选用较为“古老的”scheme语言,一个注使用较为工程化的python语言,我想正好可以学习这些经典思想怎么在现代化语言上运用,于是便断断续续地开始学习。

SICP

以下的内容都是我在断断续续学习SICP,python,和其它编程语言时慢慢总结的一些想法,这里进行一个大概的总结,作为笔记放于此处。

SICP是一本内容不深但是覆盖面很广的书籍,前三章花了很少的篇幅就讲了从函数式编程,计算模型,环境模型,基本的数据结构,到抽象数据类型,面向对象,并发,流式计算等概念,极大程度开阔了我的眼界。全书的思想,虽然涉及面广泛,但都是统一在“软件工程”的框架下进行叙述的,所谓的编程活动,其实就是清晰地给现实世界或者人的头脑中的某个过程进行建模的活动,我们看到的无论是命令行程序,GUI软件,还是游戏,抑或数值计算,其实都逃不开这个很大的概念。

前三章我读了大部分的内容,其中有一些部分是通过观看CS61A的讲课完成的,我觉得和SICP重复,就没有读SICP的对应部分,习题也选做了不少。这本书的习题安排的方式很有趣,习题和正文穿插进行,大部分习题其实都是读了正文的介绍后,自己想要进一步思考或者实现的部分,习题就给进一步提出来了。不过读这本书和做习题真不是一件轻松的事,不仅要花费大量的时间,头脑也要清醒,有时候一节的习题一做就是一下午,真不愧为“时间黑洞”。让人感慨,编程不易!

statement (语句)& expression(表达式)

第一章定义了许多编程语言中十分重要的术语,这些术语都是可以跨语言使用的。第一个概念就是statement和expression.

statement(语句) 任何用来被执行的代码,包括了表达式。 # python: x = 1 pass return None

expression(表达式) 用来被规约到一个值 # python 3 + 5 ;; scheme (+ 5 2) (+) 1 (define a 2) a

scheme中没有statement的概念,而所有的语句其实都可以看作表达式,因为scheme中所有的表达式都有对应的值。这就体现了scheme函数式编程的本质。

表达式

scheme中的表达式分为如下几种: - 自求值 - 变量(identifier) - 组合式 - 特殊形式

每一种都有不同的求值方式。

组合式

组合式:用括号括起来,第一个元素叫做operator(运算符),剩余的元素都叫做operand(运算对象). 对组合式求值,只需要将operator和operand进行求值,得到过程和实际参数,然后将过程应用到实际参数上,这个过程是递归进行的。规约到最后,就会只剩下3种最基础的求值元素:

  1. 内部operator的名字,例如+, *, cons等过程名,对应着机器序列,如果对+求值只会返回一段字符串,目的是告诉你这是一个过程。
  2. 其它名字,对应的是在环境中所关联的对象。例如#f, 等等.

在其它语言里,采用类似求值方法的语句叫做函数调用式(call expression).

特殊形式

scheme中有许多和组合式长得一样的表达式,也是用括号括起来的,不过它们的求值规则和组合式求值可不一样,因此也不是组合式。例如(define a 2)并不是将2a应用到过程define上。这种表达式在scheme中称为“特殊形式”(special form). 需要说明的是,每一种特殊形式都有自己的求值规则,或是会对环境造成影响。

定义表达式 (define a 2)

变量? a

条件表达式 (if (= a 2) #t #f)

lambda表达式 (lambda (x) (* x x))

let表达式 …

等等。scheme里的特殊形式屈指可数,但其它语言的特殊形式相当多。就拿python这种易学的语言来说,特殊形式竟然多达110种。我个人认为特殊形式多一点是有好处的,多出来的特殊形式往往是语言内建的语法糖,基本都是被语言设计者千锤百炼挑出来的, 能很大程度上提高编程的效率。

给计算对象命名

scheme允许给对象命名,这是构造抽象的最基本的方式。 然而,你还能给一个复杂的过程命名,这样只需要一个简单的名字就能代表一个相当复杂的过程。

(define a 2)
x = 2

给函数命名,对比一下和python, javascript的命名方式:

scheme:

(define sqrt (lambda (x) (* x x)))

python:

def sqrt(x):
	return x * x

javascript:

var sqrt = function(x){
	return x * x;

可发现javascript实际上最能体现和scheme一样的概念:过程是一个计算对象,通过命名的方式把它和一个变量绑定起来。python就不大容易看得出来这种感觉。

first-class function

事实上,第一章的核心的要点是:将过程(函数)当成一种抽象单元进行编程。所以选用了scheme这种语言来进行讲解。概括地说,scheme将过程提到了很重要的地位(叫做first-class function),特权包括:

  1. 可以用变量命名一个过程;
  2. 可以作为另一个过程的参数;
  3. 可以返回一个过程, 而不是一个值;
  4. 可以包含在数据结构中。

这使得这门语言的描述能力极其惊人。

1.3节讲了好多例子,现实从一开始的折半区间法求方程的根来讲解如何分解计算为一系列子过程,然后讲到求函数的不动点,然后利用不动点来求数的平方根,又中途引入了“平滑阻尼”技术加快收敛速度,后面又讲了一个牛顿法求方程的根;无论是“平滑阻尼的不动点程序”,还是“牛顿法”求根的程序,其本质还是是从一个函数出发,找出这个函数在某种变换(从f(x)变换为(x+f(x)/2,或者f(x)变换为Df(x))下的不动点,所以又可以把这种普遍性的思想表述为这一节最后的过程:即fixed-point-of-transform

高阶函数是一种威力强大的表达方式,SICP第二章用它构造数据结构;第三章实现了面向对象的“对象”,实现了“按需计算”的数据对象,此外高阶函数还广泛运用于其它方面,例如软件工程常用的“回调函数”。以后有时间再写吧。