计算机程序的构造与解释

计算机程序的构造与解释

构造过程抽象

程序设计的基本元素

一个强有力的程序设计语言:

  1. 指挥计算机执行任务
  2. 一种使我们能在其中组织自己有关计算过程的思想的框架

因此每一种强有力的程序设计语言都为此提供了三种机制:

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

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

  1. 过程(有关操作数据的规则的描述)
  2. 数据(我们希望操作的单元)

表达式

前缀表示:将运算符放在所有运算对象的左边,优点:

  1. 完全适用于可能带有任意个实参的过程
  2. 可以直接扩充,允许出现组合式嵌套的情况,即:允许组合式的元素本身又是组合式

命名和环境

程序设计语言中一个必不可少的方面:需要提供一种通过名字去使用计算对象的方式。

实际上,构造一个复杂的程序,也就是为了去一步步地创建出越来越复杂的计算性对象。解释器使这种逐步的程序构造国产变得非常方便,因为我们可以通过一系列交互式动作,逐步创建器所需要的名字-对象关联。这种特征鼓励人们采用递增的方式去开发和调试程序。

组合式的求值

解释器按照以下过程求值一个组合式:

  1. 求值该组合式的各个子表达式
  2. 将作为最左子表达式(运算符)的值的那个过程应用于相应的实际参数(其他子表达式/运算对象的值)

因此,在性质上,求值过程是递归的,也就是说,它在自己的工作步骤中,包含着调用这个规则本身的需要。一般而言,我们应该把递归看作一种处理层次性结构的(如:树)极强有力的技术。

复合过程

任何一种强有力的程序设计语言必然包括:

  1. 数和算术运算是最基本的数据和过程
  2. 组合式的嵌套提供了一种组织起多个操作的方法
  3. 定义是一种受限的抽象手段,它为名字关联相应的值

过程定义可以为复合操作提供名称,使它可以作为一个单元使用。

过程应用的代换模型

为了求值一个组合式(其运算符是一个复合过程的名字),解释器将采用以运算符为基本过程的组合式一样的计算过程。即:解释器将对组合式的各个元素求值,而后将得到的那个过程(即组合式里运算符的值)应用于那些实际参数(组合式里那些运算对象的值)。

复合过程采用的计算过程是:将复合过程应用于实际参数,就是在将过程体中的每个形参用相应的实参取代之后,对这一过程体求值。而这种计算过程,可以成为过程应用的代换模型,它可以被看作确定过程应用“意义”的一种模型,但还需要强调两点:

  1. 代换是为了理解过程调用中的情况,而不是对解释器实际工作方式的具体描述
  2. 代换模型只是解释器工作的其中一个简单模型

正则序求值:完全展开而后规约

过程与它们所产生的计算

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

线性的递归和迭代

递归计算过程:代换模型揭示出一种先逐步展开而后收缩的形状,收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画。

迭代计算过程:与递归计算过程对应,迭代计算过程中没有任何增长或收缩。即状态可以用固定数目的状态变量描述的计算过程,而与此同时,又存在着一套固定的规则,描述了计算过程在从一个状态刀下一状态转换时,这些变量的更新方式;还有一个(可能有)结束检测,它描述这一计算过程应该终止的条件。

还可以从另一个角度看两个过程的对比:在迭代的情况里,在计算过程中的任何一点,那几个程序变量都提供了有关计算状态的一个完整描述。如果我们令上述计算在某两个步骤之间停下来,要想重新唤醒这一计算,只需要为解释器提供有关这三个变量的值。而对于递归计算过程而言,这里还存在着另外一些“隐含”信息,它们并未保存在程序变量里,而是由解释器维持着,指明了在所推迟的运算所形成的链条里的漫游中“这一计算过程处在何处”。这个链条越长,需要保存的信息也就越多。

构造数据抽象

发表评论

电子邮件地址不会被公开。 必填项已用*标注

跳至工具栏