SICP——启程

发表于 | 分类于

最近开始看被形容为计算机界的“圣经”的一本 MIT 计算机科学入门课的教材 SICP ，计算机程序的构造和解释（Structue and Interpretation of Computer Programs）。我这次不打算像读《CSAPP》那样整本书看完再进行整理，而是想在阅读这本书的过程中不断地记录读书时的感想，重要的概念，有意思的习题等等……便于给自己查缺补漏，另一方面等到时过境迁，回头看这些记录，必定能有新的思考和总结。（以后再找机会补上算法导论的读书笔记

安利的链接

参考链接

Scheme 语言的解释器环境推荐 Racket

范围

第一章 构造过程抽象

1.1.1 ~ 1.1.5 节，P1-13

keywords: 计算过程、程序设计的基本元素（基本/组合/抽象）、应用序、正则序

笔记

（本书序）每一个计算机程序都是现实中的或者精神中的某个过程的一个模型，通过人的头脑孵化出来……数量上数不胜数，详情琐碎繁杂……我们很少通过自己的程序将这种过程模拟到永远令人满意的程度。正因为如此……就需要去修改程序，直到这一模型最终达到了一种亚稳定状态。而在这时，就又会出现另一个需要我们去为之奋斗的模型……如果说艺术解释了我们的梦想，那么计算机就是在以程序的名义执行它们。

（第一版前言）我们所设计的这门计算机科学导引课程……首先，我们希望建立起一种看法：一个计算机语言并不仅仅是让计算机去执行操作的一种方式，更重要的，它是一种表述有关方法学的思想的新颖的形式化媒介。因此，程序必须写的能够供人们阅读，偶尔地取供计算机执行。……我们的目标是，使完成了这一科目的学生能对程序设计的风格要素和审美观有一种很好的感觉。……这些技能不仅仅适用于计算机程序设计，对于所有的工程设计都是通用的。

开篇就给人一种读这本书会是一种精神上的享受的感觉。确实，里面提到的很多东西是以前的学习中从未接触到的。

第一章的名字叫做，构造过程抽象。准备学习的是有关于计算过程的知识。计算过程是存在于计算机里的一类抽象事物，过程会去操作一些被称为数据的抽象事物。人们创建出程序的规则模式，指导过程的进行。

书中将计算过程比喻成“巫术”，将我们写的程序比作“咒语”。学习程序设计的人们就是“巫师学徒”，我们要去理解和掌握“咒语”的效果。“咒语”中会出现小错误（bug），可能产生复杂的错误结果。这个比喻特别形象生动。我也理解了程序并不是使输入产生输出的最主要的因素，比方说我用编程语言写了一段代码，控制了一些“过程”，是这些“过程”将输入的结果转化成了输出。

一个强有力的程序设计语言，不仅是一种指挥计算机执行任务的方式，还应当成为一种框架，使我们能在其中组织自己有关计算过程的思想。

程序设计的基本要素

第一个重要的知识点，但每一种强有力的语言都有以下三个机制：

  1. 基本表达形式，用于表示语言中最简单的个体。（C语言运算符）
  2. 组合的方法，从较简单的东西出发，构造复合的元素。（结构体）
  3. 抽象的方法，为复合对象命名，将它们当成简单的单元去操作。（函数）

Scheme 相关

  • 1.1.1 讲了 Scheme 的表达式和求值。

  • 1.1.2 讲了 define 的用法。这边提一下 Scheme，它是 Lisp 语言的两种主要方言（方言的意思是拥有 Lisp 主要特性的同时拥有一些自己独有的特性）之一（另一种是 Commom Lisp）。Scheme 是函数式编程语言，这种思想是非常古老的。Lisp 不是一种主流语言，却是今天还在广泛使用的历史第二悠久的语言（比它还老的是 Fortran）。使用学习 Scheme 的原因是这一语言拥有的一些特性，使它成为研究程序设计、构造、数据结构、语言特征的一种极佳媒介。

举例子：下面的表达式就是 Scheme 中最常见的前缀组合式。对 Scheme 解释器输入表达式，解释器就可以返回你结果

1
(+ 137 349)

结果 486

像加减乘除这种一般性的求值规则，就是前面说到的每个强有力的语言都有的三个机制的第一点：基本表达形式。而 define 就是一种例外，是特殊形式。特殊形式就有自己的求值规则。各种不同类型的表达式和与之关联的求值规则组成了程序设计语言的语法形式。语法糖说的是：为完全可以采用统一形式描述的东西给出的另一种表面结构。

  • 1.1.3 讲了表达式的求值。语法树，就是说我们写的语句，在计算机看来，都是一棵棵语法树。

  • 1.1.4 讲了复合过程，介绍了“复合”的做法。

  • 1.1.5 讲了表达式的求值规则，代换模型。其实很简单，就像做函数题一样将参数代入求出结果。不过，代换不是解释器的实际工作方式的具体描述。如何求值的方式有两种

    1. 正则序求值，思路是“完全展开后规约”，就是先不求出值，而是用运算对象表达式去代替形参，直到得到一个只包含基本运算符的表达式后，再求值。
    2. 应用序求值，思路是“先求值参数而后应用”，先把参数的值求了然后带入函数中。
  • 可以证明：对于可以产生合法值的过程应用，两种方法产出的结果将是一样的。

Lisp 采用的是应用序求值，是因为正则序可能多次求同样的算式导致重复计算的工作。但下面就给出了一个反例：

1
2
3
4
5
6
7
(define (p) (p))
(define (test x y) 
    (if (= x 0)
        0
        y))

(test 0 (p))

对于正则序，不断展开，展开成

1
(if(= 0 0) 0 (p))

就停住，并得出结果 0。

但对于应用序，由于参数 (p) 是递归的，会不断地求 (p) 的值，不断调用自身，因此会在这里卡住死循环。每种编程语言的表达式求值，都是这两种中的一个。