构造数据抽象

1、数据抽象引导

2、层次性数据和闭包性质

3、符号数据

4、抽象数据的多重表示

5、带有通用型操作的系统

过程与它们所产生的计算

程序设计中的一些要素:使用过许多基本的算术操作,对这种操作进行组合,通过定义各种复合过程,对复合操作进行抽象。

一个过程也就是一种模式,它描述了一个计算过程的局部演化方式,描述了这一计算过程中的每个步骤是怎样基于前面的步骤建立起来的。

我们将考察由一些简单过程所产生的计算过程的“形状”,还将研究这些计算过程消耗各种重要计算资源(时间和空间)的速率。

1、线性的递归和迭代

2、树形递归

3、增长的阶

4、求幂

5、最大公约数

6、(实例)素数检测

程序设计的基本元素

一个强有力的程序设计语言,不仅是一种指挥计算机执行任务的方式,还应该成为一种框架,使我们能够在其中组织自己有关计算过程的思想。。这样,当我们描述一个语言时,就需要将注意力特别放在这一语言所提供的,能够将简单的认识组合起来形成更复杂的方法方面。每一种强有力的语言都为此提供了三种机制:

1、基本表达式,用于表示语言所关心的最简单的个体

2、组合的方法,通过它们可以从较简单的东西出发构造出复杂的元素

3、抽象的方法,通过它们可以为复合对象命名,并将它们当作单元去操作

在程序设计中,我们需要处理两类要素:

1、过程

2、数据

(实际并不是这样严格分类的)。

数据是一种我们希望去操作的“东西”,而过程就是有关操作这些数据的规则的描述。

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

1、表达式

运算符+运算对象

2、命名和环境

         变量:名字标识符+对应 有值

3、组合式求值

对各种表达式的求值规则可以描述为一个简单的通用规则和一组针对不多的特殊形式的专门规则

4、复合过程

1、数和算术运算是基本的数据和过程

2、组合式的嵌套提供了一种组合起多个操作的方法

3、定义是一种受限的抽象手段,它为名字关联相应的值

4、过程定义。通过它可以为复合操作提供名字,而后就可以将这样的操作作为一个单元使用了

5、过程应用的代换模型

解释器将对组合式的各个元素求值,而后将得到的那个过程应用于那些实际参数

 

正则序求值:完全展开而后归约的求值模型

应用序求值:先求值参数而后应用

6、条件表达式和谓词

7、(实例)采用牛顿法求平方根

8、过程作为黑箱抽象

计算机的构造和解释

1、构造抽象过程

计算过程是存在于计算机内的一类抽象事物,在其演化进程中,这些过程会去操作一些被称为数据的抽象事物。人们创建出一些成为程序的规则模式,以指导这类过程的进行

2、构造数据抽象

3、模块化、对象和状态

4、元语言抽象

5、寄存器机器里的计算