SICP-1.1程序设计的基本元素 | LiJun's Blog
每一种强有力的语言都为此提供三种机制：
- 基本的表达形式，用于表示语言所关心的最简单的个体。
- 组合的方式，通过它们可以从较简单的东西出发构造出复合的元素。
- 抽象的方法，通过它们可以为复合对象命名，并将它们当作单元去操作。
在程序设计中，我们需要处理两类要素：过程和数据。而这两者并不是严格分离的，数据是一种我们希望去操作的东西，而过程是有关操作这些数据的规则的描述。这样，任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要提供对过程和数据进行组合和抽象的过程。
1.1.1 表达式
Scheme中的基本表达式就是数：456、3、8…，解释器则会输出你键入的数的值：456、3、8…。
组合式：用表示过程的表达形式，将表示数的表达式组合起来，形成复合表达式。构成方式就是用一对括号括起一些表达式，形成一个表，表里最左边的元素是运算符，其它元素为运算对象。比如：
1 2 3 | (+ 137 349) (* 3 5 8) (- 4 9 8 76) |
这种将运算符放在所有运算对象左边的形式称为前缀表示。这种形式的一大好处就是适用于带有任意个实参的过程，表里右边的运算对象可以是任意个。
前缀表示的另一个有点就是可以直接扩充，允许出现组合式嵌套的情况，而且嵌套深度没有限制：
1 | (/ (* (+ 4 6) (- 97 32)) (+ 98 78)) |
1.1.2 命名和环境
变量：名字标识符，它的值就是它所对应的那个对象。
Scheme中通过define命名变量：
1 2 3 4 5 6 7 8 9 10 11 | (define time 30) age 30 (* age 2) 60 (define distance 100) distance 100 (define speed (/ distance time)) speed 10/3 |
任何一个复杂的程序都是由一个个简单的过程组成的，通过创建一个程序所需要的名字-对象关联，就可以一步步创建越来越复杂的计算性对象或过程，进而构造一个复杂的程序。
而解释器为了保持名字 – 对象关联，需要维护某种存储能力，这就被称为环境，更准确的说叫做全局环境，而在一个计算过程中，完全可能涉及不同的环境。
1.1.3 组合式的求值
解释器是按照下面的过程求值一个组合式的：
- 求值该组合式的各个子表达式。
- 将作为最左子表达式（运算符）的值的那个过程应用于相应的实际参数，也就是其它子表达式（运算对象）的值
而一个深度嵌套的组合式的求值过程，就是在各个子表达式中不断的重复上面的两个过程。这种在自己的计算步骤中，包含了调用这个计算规则本身的需要，这一求值过程就是递归。
1 2 | (* (+ 2 (* 4 6)) (+ 3 5 7)) |
可以用树形来表示上面这一组合式的求值过程，这种“值向上穿行”形式的求值过程被称为树形积累。
1.1.4 复合过程
过程定义：可以给某一复合操作过程提供名字，而后可以通过这个名字将这一复合操作作为一个单元使用了。比如定义一个“平方”操作过程：
1 | (define (square x) (* x x)) |
过程定义的一般形式是：
1 | (define (<name> <formal parameters>) <body>) |
name是关联的过程名字，formal parameters是形式参数，可以有多个，body是具体的操作过程。
也可以将定义好的过程作为基本构件去定义其它过程：
1 2 | (define (sum-of-square x y) (+ (square x) (square y))) |
1.1.5 过程应用的代换模型
对于复合过程，过程应用的计算过程是：将复合过程应用于实际参数，就是在将过程体重的每个形参用相应的实参取代之后，对这一过程体求值。
这种计算过程称为过程应用的代换模型。
解释器首先对运算符和各个运算对象求值，而后将得到的过程运用于得到的实际参数，这种先求值参数而后应用的方式称为应用序求值。
先不求出运算对象的值，而是用运算对象表达式去代换形式参数，直到得到一个只包含基本运算符的表达式，然后再去求值。这种“完全展开而后归约”的求值模型称为正则序求值。
Scheme解释器里用的是应用序求值，部分原因在于能避免对于表达式的重复求值，但某些时候，正则序求值也会非常有用，后面的章节会讲到。
1.1.6 条件表达式和谓词
条件表达式的一般性形式为：
1 2 3 4 5 6 | (cond (<p1> <e1>) (<p2> <e2>) (<p3> <e3>) . . (<pn> <en>)) |
其中
是谓词，是一个表达式，它的值会被解释为真或假（Scheme中#t为真，#f为假）。
上述形式中，会按顺序求值谓词p，直到求出的值为真，然后计算序列表达式e的值，并返回该值。如果没有找到值为真的p，cond的值则没有定义。
另外可以通过else返回一个绝对值：
1 2 3 | (cond (<p1> <e1>) (<p2> <e2>) (else x)) |
另外也可以使用if：
1 2 | (if <predicate> <consequent> <alternative>) ;if 可以省略else |
Scheme采用的特殊形式的if，在求值时，解释器会先求值predicate，如果为真，再去求值consequent，否则就是求值alternative。而不是采用应用序求值方式，先对所有参数求值，再进行计算。这一点需要特别注意。
基本的谓词有>、<和=，逻辑运算符有：
- 逻辑与：(and \…\)
- 逻辑或：(or \…\)
- 逻辑非：(not \)
具体的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | (define (abs x) (cond ((> x 0) (- x)) ((= x 0) 0) ((< x 0) x))) (define (abs x) (cond ((> x 0) (- x)) (else x)) ;两个abs等价的 (define (compare x) (if (< x 0) (- x) x)) |
1.1.8 过程作为黑箱抽象
1.1.7中的求平方根的问题，我们分为了若干个子问题，每一个子问题的解决过程都进行了定义，并将这些子过程的定义用作定义其它过程的模块。这样在使用一个过程定义时，这个定义内部的计算细节就被隐藏，也无需关注，我们只需要知道它能做的事即可。比如square，我们只需要知道它能计算一个数的平方，而不需要知道它是如何计算的。这就是一个过程的抽象，在这一抽象层次上，任何能计算出平方的过程都可以用。
在这些过程抽象中，我们使用到了一些参数，比如x、guess，这些都是形式参数，这些形式参数只在这一抽象的过程中有效，它们被称为约束变量，整个过程体就是这些形参的作用域。
如果一个变量不是被约束，我们就称它为自由的。比如square、improve guess、abs这些就是自由的，在任何过程体中都是有效的。
之前我们已经定义了improve guess, good-enough?等过程抽象，但其实我们目前定义的这些只是用来辅助计算sqrt的，但因为它们都是自由的，如果其它的计算过程也需要这样的辅助，但计算过程不一样，就得定义不一样的名字。这样就很容易在定义过程时造成命名混乱，而且这些过程都是辅助特定的计算过程的，现在这样独立定义出来，也会影响代码的可读性。因此我们可以把这些定义放入sqrt过程内部，变成一个约束变量、内部定义。
1 2 3 4 5 6 7 8 9 10 | (define (sqrt x) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.0001)) (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过程体中都是有效的，没有必要再在内部传递，可以直接用作实际参数，因此这个过程定义又可以简化为：
1 2 3 4 5 6 7 8 9 10 | (define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.0001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0)) |
