首页 > 代码库 > SICP读书笔记（一）
SICP读书笔记（一）
第一章 构造过程抽象
计算过程是存在于计算机里的一类抽象事物，它在演化过程中会去操作一些被称为数据的抽象事物。我们通过创建被称为程序的规则模式来指导这类过程的进行。程序由程序设计语言编排而成。
我们将要使用Lisp表达过程性的思想，它是今天还在广泛使用的历史第二悠久的语言，本书将使用Lisp的一个方言，Scheme。我们之所以选择Lisp，是因为它有许多独特的特征，其中最重要的是：计算过程的Lisp描述本身又可以作为Lisp的数据来表示和操作。
1.1 程序设计的基本元素
为了能让我们通过程序语言组织自己有关计算过程的思想，每一种强有力的语言都提供了三种机制，以使我们能够将简单的认识组合起来形成更复杂的认识：
- 基本表达形式，表示语言所关心的最简单的个体
- 组合的方法，通过它们从较简单的元素构造较复合的元素
- 抽象的方法，通过它们可以为复合对象命名，并把它们当作单元操作
过程和数据是我们在程序设计中要处理的两类要素，本章只处理简单的数值数据。
1.1.1 表达式
基本表达式是数，通过表达基本过程的表达形式，我们可以把表示数的表达式组合起来形成复合表达式，例：
(+ 137 349) (- 1000 344) (* 5 99) (/ 10 5)
上面这样的表达式叫做组合式，构成方式为通过一个括号括起一些表达式，构成一个表，用于表示一个过程应用，表中最左边的元素称为运算符，其余均为运算对象。为了得到表达式的值，我们只需要将由运算符刻画的过程应用于有关的实际参数上。
将运算符放在运算对象左边，这种形式被称为前缀表示。前缀表示的优点之一是适用于可能带任意个实参的过程，另一个优点是可以直接扩充，允许组合式的嵌套。例如：
(+ (* 3 5) (- 10 6))
为了使我们的表达式便于阅读，我们习惯于写成下面的形式：
(+ (* 3
( + (* 2 4)
(+ 3 5)))
(+ (- 10 7)
6))
这是遵循一种美观打印的格式规则，按照这种规则，我们写一个很长的表达式时，要令其中的各个运算对象垂直对齐，从而能很好地显示表达式的结构。
1.1.2 命名和环境
我们将名字标识符称为变量，它的值也就是它所对应的对象。
在Scheme中，我们通过define来给事物命名：
(define size 2)
这会导致2和名字size相关联。
define是我们的语言中最简单的抽象方法，它允许我们用一个简单的名字去引用一个组合运算的结果。
我们可以将值与符号相关联，而后又能提取出这些值，这说明解释器需要维护某种存储能力，这种存储被称为环境（更精确地说，是全局环境）。
1.1.3 组合式的求值
要求值一个组合式，我们只需要：
- 求值该组合式的各个子表达式。
- 将作为最左表达式（运算符）的值的那个过程应用于相应的实际参数。
为了实现一个组合式的求值过程，我们要先对组合式里的每个元素执行同样的求值过程。因此，在性质上，这一求值过程是递归的。我们可以采用一棵树的形式，用图形表示组合式的求值结果。
反复地运用步骤1，总可以把我们带到求值中的某一点，这里遇到的是基本表达式。在这里，环境扮演的是确定表达式中各符号意义的角色。注意到，上面的求值规则里并没有处理定义。一般性求值规则的这种例外称为特殊形式，下面还将看到另外一些特殊形式。
1.1.4 复合过程
我们已经看到了Lisp中的一些元素：
- 数和运算是基本的数据和过程。
- 组合式的嵌套让我们可以把多个操作组织到一起。
- 定义是一种受限的抽象手段，它为名字关联相应的值。
现在我们来介绍过程定义，这是一种更强大的抽象技术，它使我们可以为复合操作提供名字，而后就可以将这样的操作作为一个单元使用。
为此，我们来考虑如何定义“平方”这一过程：
(define (square x) (* x x))
这样我们就有了一个复合过程，它的名字为square。被乘的东西也有一个局部名字x，它就好像自然语言中的代词。
过程定义的一般形式如下：
(define (<name> <formal parameters>) <body>)
我们可以用square作为基本构件去定义其他的过程，例如：
(define (sum-of-squares x y)
(+ (square x) (square y)))
现在我们还可以用sum-of-squares作为构件，去进一步构造其他过程：
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
1.1.5 过程应用的代换模型
为了求值一个组合式，解释器将对组合式的各个元素求值，而后将得到的那个过程应用于那些实际参数，我们可以用代换模型来解释这个过程，但是有两点需要注意：
- 代换模型能帮助我们领会过程调用中的情况，但并不是对解释器实际工作方式的具体描述。实际中，它们一般采用提供形式参数的局部环境的方式，产生代换的效果。
- 随着本书讨论的进展，我们将给出一系列有关解释器如何工作的模型，一个比一个更精细，代换模型是这些模型中的第一个。
按照1.1.3中的描述，解释器首先对运算符和各个对象求值，而后将得到的过程应用于得到的实际参数, 但是还有另外一种求值的方法：先不求出运算对象的值，直到实际需要它们时再去求。如果我们使用这种方式，则下面表达式的值应该这样展开来求：
(f 5) (sum-of-square (+ 5 1) (* 5 2)) (+ (square (+ 5 1)) (square (* 5 2)) ) (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
这样，我们会对有些表达式进行更多次数的求值，这种“完全展开而后归约”的求值模型被称为正则序求值，与之对应的是实际使用的“先求参数而后应用”的方式，我们称之为应用序求值。
1.1.6 条件表达式和谓词
Lisp里有一种针对分情况分析的特殊形式，称为cond，其使用形式如下：
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
表达式会按顺序求值谓词，直到得到真，此时就返回相应字句中表达式的值。如果无法找到为真的谓词， cond的值就没有定义。不过如果我们写了else，则在找不到表达式为真的字句时，我们将会执行else后的子句。还有一种特殊形式if，它适用于分情况分析中只有两种情况的需要。
我们还有一些逻辑复合运算符，利用它们可以构造出复合谓词，最常用的三个复合运算符：and, or, not。
练习 1.1
10 12 8 3 6 无 无 19 #f 4 16 6 16
练习 1.2
(/ (+ 5
4
(- 2 (- 3
(+ 6
(/ 4 5))))) (* 3
(- 6 2)
(- 2 7)))
练习 1.3
(define (max-sum a b c)
(cond ((and (< a b) (< a c)) (+ b c))
((and (< b a)(< b c)) (+ a c))
(1 (+ a b))))
练习 1.4
计算a+|b|的值。
练习 1.5
若采取应用序求值，Ben将会看到程序将进入没有响应的状况，因为此时事实上程序将会不断调用过程p，陷入一个死循环。如果采用正则序求值，则会输出0，因为此时我们并不会去求(p)的值。
1.1.7 实例：采用牛顿法求平方根
在数学中，人们通常关心的是说明性的描述（是什么），而在计算机科学里，人们则通常关心行动性的描述（怎么做）。我们可以通过牛顿的逐步逼近法来求平方根，方法是通过对平方根的一个猜测执行一个简单的操作，从而得到一个更好的猜测。
我们可以这样来实现这个过程：
(define (sqrt-it guess x)
(if (good-enough? guess x)
guess
(sqrt-it (improve guess x)
x)))
然后我们需要实现改进操作：
(define (improve guess x)
(average guess (/ x guess)))
其中
(define (average x y)
(/ (+ x y) 2))
我们还需要说明什么叫“足够好”，下面的做法只是为了说明问题，它其实不是一个很好的检测方法：
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
最后，我们需要一种方式来启动整个工作：
(define (sqrt x)
(sqrt-it 1.0 x))
可以看出，在用于写纯粹的数值计算程序时，至今介绍的简单程序设计语言已经足以写出可以在其他语言中写出的任何东西了。
练习 1.6
程序会因陷入无限的递归调用中而崩溃，这是因为当我们计算new-if表达式时，我们会先计算所有的实参，从而将会导致我们无限地调用sqrt-iter。
练习 1.7
如果数过小或过大，我们的方法计算出的平方值也会有相对较大的误差，但如果采用本题所述的方法，就没有这个问题。
练习 1.8
感觉有些无聊，略。
1.1.8 过程作为黑箱抽象
可以看到，对于平方根的计算问题可以自然地分解为若干子问题：怎样说一个猜测是否已经足够好，怎样改进一个猜测，等等。这里的关键在于，分解的每一个过程完成了一件可以清楚标明的工作，这使得它们可以被用于定义其他过程的模块。例如，当我们基于square定义good-enough?时，我们将square看作一个黑箱。此时，我们无需关心这个过程如何计算它的结果，只需要注意它能够计算出平方值的事实。如果只看good-enough?过程，与其说square是一个过程，不如说它是一个过程抽象。
局部名
有关的过程里面的形式参数的名字，是用户无需关注的实现细节之一。这一原则要求过程的形式参数名必须局部于有关的过程体。
形式参数的具体名字是什么，其实完全没有关系，我们把这样的名字称为约束变量，如果一个变量不是被约束的，我们就称它为自由的。名字所被约束的那一集表达式称为名字的作用域。
内部定义和块结构
平方根程序由几个相互分离的过程组成，在这里，事实上只有一个程序对用户是重要的，那就是sqrt程序。其他的过程则只会产生干扰，因为他们再也不能定义另一个不同的good-enough?用于其他程序，因为我们的平方根程序需要它。在许多程序员一起构造大系统时，这个问题会变得非常严重。因此，我们希望将这种子过程局部化，将它们隐藏到sqrt的内部，例如：
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))
这种嵌套定义称为块结构，它是最简单的名字包装问题的一种正确解决方式。实际上，这里还隐藏了一种很好的想法。除了将辅助过程的定义放到内部，我们还可能简化它们。注意到x在sqrt中是受约束的，因此我们没有必要显示地在这些过程之间传来传去。如下所示，当外围的sqrt被调用时，x由实际参数得到自己的值，这种方式称为词法作用域。
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
下面将广泛使用这种结构，以帮助我们将大程序分解为一些容易把握的片段。
SICP读书笔记（一）