SICP——构造过程抽象（一）

0."三机制"和"两要素"

一个强有力的程序设计语言为了能够将简单认识组合起来成更复杂认识，为此，提供了三种机制：

• 基本表达形式 (用于表示语言所关心的最简单的个体)
• 组合的方法 (通过它们可以从较简单的东西出发构造出复合的元素)
• 抽象的方法 (通过它们可以为复合对象命名，并将它们当作单元去操作)

在程序设计中，我们需要处理两类要素：过程和数据
非形式地说，
数据是一种我们希望去操作的"东西"
过程是有关操作这些数据的规则的描述

这样，任何强有力的程序设计语言都必须能表述基本的数据和基本的过程，还需要对过程和数据进行组合和抽象的方法

Lisp描述(即过程)本身又可以作为Lisp的数据来表示和操作，具备将过程作为数据进行处理的灵活性

1.表达式

组合式的构成方式：用一对括号括起一些表达式形成一个表，用于表示一个过程应用：

(+ 123 345)

最左的元素(+)称为运算符，它所刻画的过程应用于运算对象，它在左边的形式称为前缀表示

前缀的优点:

1. 它完全适用于可能带有任意个实参的过程
2. 可以扩充，允许出现组合式嵌套的情况

其它元素称为运算对象(可以是实际参数、其它过程定义等)

2.命名与环境

变量: 提供一个名字标识符，能够通过该名去使用计算对象的方式

定义变量的方法define：

• 最简单的抽象方法，作用是用一个简单的名字去引用一个组合运算的结果
• 语法：(define <name> <value>)

构造一个复杂的程序，也就是为了去一步步地创建出越来越复杂的计算性对象，一个Lisp程序通常总是由一大批相对简单的过程组成的

环境(全局环境):存放着值与符号(保持名字-值对偶的轨迹，例如+)关联的地方，在求值时提供上下文

3.组合式的求值

• 如何求值：
  1. 求值该组合式的各个子表达式
  2. 将运算符的值的那个过程应用于相应的实际参数(运算对象)

在性质上，这一求值过程是递归的，即它在自己的工作步骤中包含着调用这个规则本身的需要

我们应该把递归看作一种处理层次性结构(例如树)的极强有力的技术

"值向上穿行"形式的求值形式是树形积累的一个例子

• 求值规则：
  1. 数的值就是他们所表示的数值
  2. 内部运算符的值就是能完成相应操作的机器指令序列
  3. 其它名字的值就是在环境中关联于这一名字的那个对象

特殊形式：有其自身的求值规则，不同种类的表达式形式语法，例如define

Lisp的语法很简单，可以描述为：

• 一个简单的通用规则
• 一组针对不多的特殊形式的专门规则

4.复合过程

• 过程定义：可以为复合操作提供名字，作为一个单元使用
  • 一般形式：(define (<名字> <形式参数>) <内容体>)
  • 以平方为例：( define (square x) (* x x ) )

可以把一个过程作为基本构件去定义其他过程，如在其他过程中使用square

5.过程应用的代换模型

基本流程：先对运算符求值(求过程) -> 运算对象求值 (得实参)-> 把运算符的值应用于实际参数(应用)

这种计算过程称为过程应用的代换模型，是确定过程应用的"意义"的一种模型

代换的作用只是为了领会过程调用中的情况，在实际中他们一般采用提供形式参数的局部环境的方式产生代换效果

有两种求值模型：

• 正则序求值：完全展开而后归约
• 应用序求值：先求值参数而后应用

Lisp采用应用序求值，原因有下：

1. 避免对于表达式的重复求值，提高效率
2. 正则序在超出可采用替换方式模拟的过程范围之后，会变得复杂

6.条件表达式和谓词

• cond：分情况分析，形式：(cond (<p1><e1>) … (else x)) ，p是判断用的谓词，当p为真，执行e
  常见谓词： > < =
  复合运算符(用谓词构造的)： and、or、not(and和or都是特殊形式，因为子表达式不一定都求值，not则是普通的过程)
• if：只两种情况，形式：(if <c1><v><c2>)，若c1真，返回v，否则返回c2

每个cond子句的<e>部分可以是一个表达式的序列，如果对应的<p>为真，<e>中的表达式就会顺序地求值，并将其中最后一个表达式的值作为整个cond的值返回，而在if中<v>和<c2>都只能是单个表达式