层次程序结构

III.层次程序设计

O.-J. 达尔与C.A.R. 霍尔

　　　　　　　　　　　　　　　　1.引　　　言

　　本文将探讨程序结构的一些方法，并指出它们与塑造概念的关系。

　　我们将使用程序语言SIMULA 67，尤指它所提供的结构手段。SIMULA 67是一个基于ALGOL 60的语言，而它还包含一个稍加限制和修改的ALGOL 60作为子集。关于它的一些特征我们将在引用时作非形式地介绍和解释。读者应对ALGOL 60有很好地了解，最好还熟悉表格处理技术。

　　我们所引用的是[2]中对于SIMULA 所作的全面解释，也引用了一些[2]中暂未解释过的因素。

　　本文是达尔在(1970)北大西洋公约(NATO)夏季程序设计学校的一系列讲稿的基础上扩充整理而成的。增添的材料大多属于[3,4,5]所提供的例子。

　　　　　　　　　　　　　　　2.预　备　知　识

2.1 基本概念

　　作为程序员，我们主要关心的是一类特殊的动态系统，计算进程或数据进程。一个程序语言为我们提供了构造和分析这样一个进程的基本概念和组成规则。

　　下面是ALGOL的一些基本概念。

　　(1) 一个类型指一类值。每一个类型都有一些有关的运算，适用于它的值。例如，算术运算和关系运算适用于类型integer的值。

　　(2) 一个变量指一给定类型的一类值，这些值是按时间先后排序的。对变量的运算不外乎是“取”或“存”它的现行值。这两者统称为传送。

　　(3) 一个数组指一类依某一空间形状排序的变量，与之有关的是下标运算。
   
    注意，每个这种概念都包含一种数据结构，以及一个或几个有关的运算。

    作为另一个例子，让我们考虑机器语言的情形。这里，二进制位串是基本的数据结构，它自身倒不是很有意义的。但是，当把它同逻辑解释联系起来，它就具有布尔值的意义。若把它同二进位加法器联系起来，它具有一定数值的意义，每一位是以2为基的数字的一位。当把一个输出通道和一个行打印机联系起来，二进位串即能转变为字符串，如此等等。因此，数据结构的意义准确地依赖于与之相联系的运算。

    另一方面，任何计算进程都离不开数据。简言之，数据和运算是不可分离地联系在一起的，任何用于理解计算进程的概念都必须根据这两方面的因素来形成。

2.2 高级概念

    由于大型计算机的出现，我们面临着许多复杂的计算进程，仅用一些最一般的基本概念是很难理解和构造这种进程的。对于人的思维能力而言，若每次面临的因素太多，要作精确思维是不可能的。

    处理复杂系统的唯一有效的办法是按层次的方式构造和分析。一个复杂的动态系统首先可用一些高级概念构造和理解，而这些高级概念又可用一些较低级的概念构造和理解，如此等等。这种层次方式必须反应在定义动态系统的程序结构之中，而每级的一个概念将以某种方式对应于程序的一组成成分。

    塑造满足一定要求的概念是一个创造性的过程，需要对系统的结构有个充分深刻的理解。而这种理解常常只有在系统构造的稍后阶段才能弄明白。因此，如程序员的切身经验所体会到的那样，任何一个软件工程常常是一个复杂的迭代过程，它的每一个阶段常常需要重新构造和修改。

    每一个概念必定涉及整个系统的某一侧面，因而必定对应于整个程序中的某一程序段。在对整个程序进行分解时，就可以看到这种段的存在。如果要使一个程序易于分解，它的每一组成成分应独立编制，并且使得修改起来尽可能不涉及或少涉及系统的其它部分。以此加速整个迭代过程。

    任何一个有用的概念都有着某种程度的一般性，即它是一个由一些具体化的活相构成的类。换言之，人们试图把出现在一个动态系统中的现象分类，并且对每一个类都用一个程序段加以描述。

    作为一个例子，让我们考虑矩阵乘所涉及的算术运算。显然，假定矩阵系数是按二维数组A，B和C的元素分类的，变量i，j和k的值是按一定形式给出的，那末，所有矩阵乘都可按如下单一语句
  
       C[i,j]:=C[i,j]+A[i,k]*B[k,j]

的不同动态实现（执行）进行分类。

    上述语句并未分到足以作为一个“概念”进行思考的地步。但是下面的过程说明，用一种简洁的方式，定义了矩阵乘这个概念。

    重要的是，在一般的语言结构中，一个概念可对应于某个语法范畴（如<分程序>，<过程>）。在一定概念基础上的结构性思维意味这构造句子，概念间具有语法和语义的相互关系。下面的过程经调用序列(过程语句)即可和别的程序成分发生联系。

     procedure matmult(A, B, C, m, n, p);
       array A, B, C; integer m, n, p;
    begin integer i, j, k;
       for i := 1 step 1 until m do
       for j := 1 step 1 until n do
          begin C[i, j] := 0;
             for k := 1 step 1 until p do
                C[i, j] := C[i, j] + A[i, k] * B[k, j]
             end
    end;
    在SIMULA中，过程的参数结构和ALGOL 60的多少有点区别。对于简单<类型>参数，若不标明传送(使用)方式，便理解为用其值。对于其它种类的参数，若不标明传送方式，便理解为用其名。这种区别的引进有种种实际理由。理由之一是，这样一来便和类说明相容了。因此，在上例中，参数i,j,k用以值，而A, B, C则用以地址。

2.3 分程序及其活相(Instance)

    ALGOL 60中，关于程序结构的最有效的手段之一是分程序或过程。从塑造概念的观点来看，它有如下有用的性质。

    (1) 二重性。分程序头与分程序尾一起定义了一个实体，它既具有一定的性质又能执行一定的动作。这些性质中可以包含数据结构及有关运算(局部过程)。

    (2) 可分解性。一个只引用局部量的分程序是一个完全自足的程序成分，它将在它所处的任何上下文中起着相同的作用。若配上一个过程头，一个分程序(过程)的动态执行即可和以调用序列相互作用。一个过程若引用或改变了非局部量的值，表示它仅可从整个任务中部分地分解出来。这种过程对于直接同程序环境相互作用是有好处的。

    (3) 活相的类。在ALGOL 60中，作为一段程序文本的静态分程序和作为一个动态执行的分程序(叫做分程序活相——block instance)是由严格区别的，后者是计算进程的一组成成分。从这种区别中可得出一个有用的结果，即一个分程序可用它所可能具有的全部活相的类所标识。

                              3. 对象类

    一个过程，如果它能够产生比调用语句活得更久的分程序活相，我们就称它为一个类；这样的活相称为这个类的一个对象。一个类，不管它是否带有参数，可用定义过程的同样办法予以说明：

    <类说明>::=class<类标识符>
              <形式参数部分>;<区分部分>;<类体>
    <类体>::=<语句>

   局部与类体的任一变量或过程称为该类的特征。类的形式参数，不论是用其值或用其名，也称是该类的特征。如果类体不是一个分程序，可把它看成似乎是由一对分程序括号begin...end所包围。

    调用一个类产生该类的一个新对象。一个调用是一个产生器。相应于形式参数的那些特征的初值必须作为产生器的实在参数部分出现。一个产生器只能象函数命名符那样出现，作为结果值返回的是那个新产生的对象的参引值，即地址：

    <对象产生器>::=new <类标识符><实在参数部分>

    为了能够多次引用一个已产生的对象，需要把它的地址存于某一变量之中。而且，这种变量的说明还必须指出它和哪一个对象类相联系。

     <地址变量说明>::=ref(<类指>)<标识符表>
    <类指>::=<类标识符>

记号ref(<类指>)





                4. 伙伴程序

    在ALGOL中，联合两段程序完成一任务的有效方法是把其中之一作为一个过程，而在另一个的内部调用(或许是反复调用)这个过程。但是在某些情况下，任意两段程序并不明显地具有这种主/副关系；最好是把它们看成是同级的伙伴关系，把这两段程序都作为是伙伴程序。

    例如下棋程序就是伙伴结构的一个简单例子。这种程序思索着自己的走法，并把结果输出给对方，再输入对方的回答，考虑自己的下一步，如此反复，直到分出胜败为止。现在假定由两段不同的程序下一盘棋，要看谁胜谁负。作为一个整体程序来看，把这两段作为伙伴结构是非常自然的，作为主/副关系反而不自然。

   

               5. 表格结构

    使用上述关于类和参引量(地址)的说明，可表示诸如栈和树的递归数据结构，甚至还可表示诸如双向表之类的环形结构。这只需使用参引量作为类特征，而这种参引量所指示的正是该类的某些对象。

5.1 二叉查找树的结构

    一个二叉树可定义为:
             抑(i) none
               或(ii) 一个结点
每个结点含有三个组成成分，
       (i) 一个左分枝，分枝本身是一个树
       (ii) 一个右分枝，分枝本身是一个树
       (iii)一个值val，此值是一个整数。


              6. 程序连接

    在前面几节里我们看到，如何使用对象类这个机构，通过指明数据结构和有关运算，塑造了一些简单概念。在本节里，我们要讨论一种由简单概念构造复杂概念的方法。这需要建立概念的层次，用简单的定义复杂的，把复杂的归结到简单的。我们所使用的构造法称为连接法，这是一种按构成成分组织程序的新方法。

    连接是类与类之间，或者类与分程序之间的运算，旨在形成新的类或分程序。连接运算是指把两个成分的特征合并在一起，把两个成分的动作组合在一块。连接后的对象的形式参数是第一成分的形式参数后随第二成分的形式参数组成的；同样地，区分部分，说明部分和语句部分(如果有的话)也分别是由一，二两成分相继合成的。

    假定A已说明为一个类。所谓把类A连接到另一个类B上，是指把A的名“A”放在类B的说明前面：
    A class B(b1, b2, ...); 诸b的区分;


           7.概念分层

    当开始一项程序设计工程时，人们必须考虑：一，这个工程所要解决的问题；二，解决问题的工具——程序语言。





本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/civili/archive/2007/12/19/1953791.aspx