智能科学技术导论-周乐昌-第04讲程序编制

第04讲程序编制导语构建了解决问题的算法，要让机器系统能够顺利运行该算法，必须采用机器能够直接处理的某种语言来编制给出算法的程序。当然，一个最为直接的编程语言就是由机器指令构成的机器语言。不过，机器指令过于繁琐且缺乏直观性，不利于描述复杂的算法。因此为了方便编程，人们构建了各种高级编程语言，同时对应构造相应的编译或解释软件，将高级编程语言描述的程序自动转化为机器指令的形式。这样，对于程序编制的一般人员而言，就可以使用高级语言来编制程序了。第4.1节编程语言可以用于程序编制的语言种类繁多，如果包括机器语言在内，通常按照机器系统方便处理的程度分为机器语言、汇编语言与高级语言三类。机器语言就是直接采用机器系统能够直接执行的机器指令来编制程序的一种语言。但显而易见的是，缺乏直观性理解的机器指令非常不方便，给程序的编制、特别是有一定规模的程序编制带来许多困难，明显会加重算法实现的任务复杂性。为了克服机器语言不方便阅读的缺陷，可以为各种操作码、操作数分配各种助记符号，并用这些助记符号取代十六进制数字编码表示，采用这样表示方法形成的语言就称为汇编语言。这样，在编制程序时，程序员就可以使用这些助记符号构成的汇编语言（assembly language）来编制程序，然后再使用一种称为汇编程序（assembler）来自动将汇编语言编制的程序翻译成为机器语言表达的程序，供机器系统执行。由于汇编语言仅仅改变的是操作码、操作数等符号的表示，因此跟机器语言一样，编制这样的程序是深深依赖于机器系统的（所提供的指令系统），于是在一种机器上可以运行的汇编语言编制的程序往往无法在另一种机器上直接运行。这个缺陷就是缺乏可移植性。汇编语言的另一个缺陷是依然没有改变机器语言原有的繁琐性，必须从最基本的机器指令基础上去考虑如何构建算法的实现程序。为了克服汇编语言的上述局限性，开发比汇编语言更加方便编制程序的语言，各种高级程序设计语言应运而生。早期的高级语言有FORTRAN（FORmula TRANslator）应用于科学与工程、COBOL（Common Business-OritentedLanguage）应用于商业、PASCAL（以法国数学家pascal 的名字命名）应用于教学等。一般机器语言称为第一代编程语言，汇编语言称为第二代编程语言，高级语言称为第三代编程语言。与前两代编程语言不同，高级语言（high language）的最大特点就是采用更加高级的操作原语来作为程序构造的基本砌块，非常接近算法设计的伪码。高级语言编译程序 汇编程序汇编语言机器语言汇编语言和高级语言需要经过特定的汇编程序和编译程序进行翻译，使之成为机器能够直接执行的指令，才能为机器所识别。当然它们自身也是程序，也需用某种语言写成。高级语言程序#include void f(int *j);*j = 9;void main() printf(myProgramn);i = 1;printf(“ i=”,i);f(i);printf(“ i=“,i);汇编语言程序MOV DX，OFFSET FILEMOV AL，0MOV AH，3DHINT 21HJC OPERRMOV HANDLE，AXMOV BX，HANDLEMOV DX，OFFSET BUFMOV CX，512MOV AH，3FHINT 21HJC READERRCMP AX，0JE CLOSEMOV BX，AXMOV BUF BX ，$MOV DX，OFFSET BUFMOV AH，9INT 21HJMP READ机器语言程序11011010110001000101100011000010010110110100010101011111011001010111001011101111011000000100111001010110011101010101110010101001010101010001011000110110111011100101100011010111001011010110001101010011111010101010100100100101110100011100101011000110010110001100110010101010101000000111100101101111100101100001011111111001011001011101010101010100010101111110010100100101110010编程语言之间的转化：编译、解释与汇编除了独立于具体的机器，高级语言的主要特点就是面向人类思维特性来进行程序的编制，这也是编程语言不断发展的动力。如果以此动力为标准来考察编程语言的演变历史，那么第一、二代语言主要面向机器运行特性要求的，而从第三代语言开始，越来越体现面向人类思维特性的需要了。目前的高级程序设计语言的范式大致可以分为命令式、说明式、函数式和对象式四种，如下图所示。机器编程语言范型的演变1、过程范式（Procedural paradigm），也称为命令式范式（Imperative paradigm ），是程序设计过程的传统方式，其命令语句与算法设计的伪码最为相像。主要是以程序设计过程为依据、通过控制数据产生所需结果为目的来展现命令序列。其主要特点就是通过寻找解决问题的算法处理过程，并用程序设计语言提供的命令序列描述出来。2、说明范式（Declarative paradigm），也称为逻辑式范式，与过程式语言不同，说明式语言不是给出解决问题的算法过程，而是描述所要解决的问题。具体方法是发现并且实现一个解决问题的通用算法，然后给出与这个算法兼容的形式表达问题，通过形式化通用算法的实现来解决给定的问题。主要的特点是要对问题进行准确的描述，而不是寻找解决问题的算法。3、函数范式（Functional paradigm），也称模块式范式，就是将程序开发过程看作将预先定义“模块”连接起来的过程，这些模块，就是所谓的函数。每个函数都有自己的输入与输出，因此所谓连接不同模块，就是建立不同函数模块输入与输出之间的关系。在函数式程序设计语言中提供有一些基本函数作为原语，程序的编制就是针对具体的问题，去寻找能够将基本函数连接起来的系统方法，从而给出一个联合函数的程序，解决所给定的问题。简言之，这种函数式程序设计的编程过程，就是基于提供的基本函数来构造解决问题的函数嵌套联合体。4、对象范式（Object-oriented paradigm），全称是面向对象的程序设计范式。这是一种目前广泛流行的程序开发方法。在这种设计范式中，将数据单元看作是一种主动的“对象”，而不再是被动由控制命令处理的数据。对象由数据序列及其操作过程共同构成，也就是说任何处理的数据本身就包含了专用的操作数据的过程，因此不再需要外部全局性的算法来处理数据序列本身的操作。对象之间可以通过消息传递机制来建立联系，这些机制也是对象内部操作的有机构成部分。因此，也可以将对象看作是一个小型命令式语言程序单元。面向对象设计的优点就是非常符合模块化软件设计的要求，因此成为目前程序设计语言发展的主流。究其原因，这种程序设计思想，符合人类思维的特点，思维与思维对象捆绑性特点，比如视觉处理与视觉对象相关联，而且不会应用到听觉对象的处理中等。从中不难看出，未来的发展一定智能化、自然化、交互性的趋势。应该说，发展更高层次的语言是人类一直不懈追求的目标。现代人工智能研究的主要领域之一就是自动编制程序，就是要发展一种高层次的语言。这种高级精巧的语言具有这样一些功能：（1）符合人类思维习惯，而不是迎合机器死板规定；（2）自动纠正机器代码中语法错误；（3）能够理解那些含糊其辞的描述；（4）能够运用模型提供预言性的猜测；（5）当遇到不清楚的描述时还能主动提出建议。目前这种语言的实现还在不断努力的过程之中。第4.2节程序结构与自然语言相对应，使用程序设计语言编制的程序类似于自然语言撰写的文章，是由语句构成的。不同的是，程序中的语句一般分为数据描述语句（Declarative statements）与操作命令语句（Imperative statements）两个部分。有时为了方便理解程序句群的含义，也会出现一些注释（Comments）。注释不是程序的必要部分，通常直接用自然语言来说明。第一部分由声明语句组成，描述该程序要操作的数据第二部分由命令语句组成，描述该程序所要实现的动作程序结构示意图对于数据描述语句，其功能主要是定义在程序中使用各种数据类型或数据结构的实体（比如常量、变量以及类型）。数据类型是指数据的种类，其决定着数据的编码方式以及对可执行操作的限制。在程序中处理的常量或变量主要的数据类型包括（data type）整型数据（integer）、实型数据（real或float）、字符型数据（character）、布尔型数据（boolean）。比如，如下图所示就是给出了主要编程语言中的变量类型的说明语句。同样一些实型、整型及字符型变量在不同高级语言Pascal，C类（Java）、FORTRAN中的不同说明方式。除了简单数据变量的说明语句，在程序中还有复杂数据结构（data structure）的说明语句。常见的数据结构通常分为数组、记录与对象三种。数组是一种包含同质数据的集合结构，主要用于表达一维表格、二维表格、多维表格等这样的形式。当然，因为是同质的，数组所有元素具有相同的类型，其说明语句比较简单，如C语言中的int Scores29以及FORTRAN语言中的INTEGER Scores（2 ，9 ）及PASCAL语言中Scores：array34,1220 of integer说明的都是一个二维数组。在程序中一旦说明了一个数组，那么就可以通过引用其名称在程序任何需要的地方引用该数组或数组元素，如果引用的数组元素，要给出其对应的索引标识，此时需要注意不同语言对数组起始索引标识的规定是不同的，比如C语言是从0开始计数，FORTRAN则是从1开始标识的，而PASCAL则从规定的起始位置开始标识的。不同于数组的同质性，记录（异构数组）则是由不同质的数据元素构成的数据结构。比如如图所示给出的是表示职员信息的记录结构：Name (char)Age (integer)SkillRating (Real) 职员记录结构示意图记录中的数据元素通常采用记录名、一个句点和元素名来引用，比如对于上述职员记录，要引用其中的Age，需要写成Employee.Age。不同编程语言中对记录的说明语句至于对象，是指面向对象编成语言中一种复杂数据结构，主要是说明一类对象的模板的，因此严格上通过定义对象类来说明的。对象类除了类名外，内部包括对象数据说明及其各种处理方法两个部分。class LaserClass 数据说明；数据操作方法1；数据操作方法n；一旦定义了一个对象类，就可以用这个对象类来定义具体对象如下：LaserClass Lase1， Laser2， Laser3；现在我们介绍有关常量的说明。在程序中有时要用到一些预先确定的并始终保持不变的量，这些量就称为常量。常量的数据类型同变量一样，可以是整型、实型、字符型、布尔型等。比如Ada语言中说明语句AirportAlt constant Integer :=645;JAVA语言中Final int AirportAlt=645;以及C+语言中Const AirportAlt=645;均定义了一个常量AirportAlt，以后在程序中凡出现AirportAlt的地方，其值均为固定不变的645。当然，你也可以不预先定义常量，而在需要的地方直接写上“645”这个数值，只是这样可能会损害程序的可读性与通用性。比如如果在程序多处出现这个代表机场海拔高度的数值，一旦需要修改该常量的值（比如机场搬家，海拔高度变化了），那么如果预先定义了常量，只需在定义说明处改动就可以完成修改；否则需要在每一处出现的地方均修改数据。这就是常量定义的优点之一，另一个优点则是可读性好。其他常见的类型还可以有枚举型数据、视频类数据、音频类数据、以及超文本类型数据等等，虽然目前大多数编程语言并不支持这样的数据类型的直接说明，但随着智能多媒体技术应用的不断发展，这将是一种不可阻挡的发展趋势。编码的声波振幅 音频数据图像数据 超文本数据最后，需要强调指出的，一些复杂的数据结构，比如表列、堆栈、队列、树图等，均可以通过上述数组、记录与对象及其相关算法来实现。上面是程序的数据说明语句部分，下面介绍程序执行语句部分的具体语句。有了数据变量、常量与复杂数据结构的说明，就可以用程序语句来描述算法步骤了。类似于算法中的伪码，程序执行语句主要包括赋值语句、控制语句（转移、条件与循环）、模块调用三种类别。赋值语句是最基本的执行语句，主要任务就是将某个值（或表达式计算的值）赋给一个变量。不同的语言中赋值语句的表示形式有些微的差别，C、C+、C#、JAVA语言中采用的句式为：Z=X+Y；而Ada和Pascal则采用如下形式：Z ：=X+Y；APL语言则为：ZX+Y如此等等。在赋值语句中，赋值号左边为变量，右边为表达式，表达式中可以含有各种规定的运算符，此时要注意不同运算符之间的优先级。有时候，运算符也可能不是传统意义上的运算操作，比如位移操作、字符串操作、逻辑运算符操作等，一切要按照具体语言的规定来进行运算。控制语句主要是用来控制语句执行次序的，在编程语言中常见的控制语句包括无条件转移语句（如goto语句）、条件类转移语句（如if语句）以及循环类语句（如for语句）。考虑无条件转移语句带来程序结构的非结构性，现在许多编程语言均不提倡使用，以及常见的控制语句包括if-then（-else）语句、case语句、while语句、repeat-until语句、for语句等，除了for 、case语句外，其他均在算法的伪码中有过介绍。因此下面重点说明case语句和for语句。控制语句的结构及在C, C+, C#, and Java中的表示for语句类似于伪码中的while语句，不同之处是循环的控制方式。对于for语句而言，循环过程是由一个计数变量（比如count ）来控制的，而对该变量的初始赋值、修改以及终止条件判断都在一个语句中表达。比如for count：=1 to 3 do （循环体）就是典型的for语句格式，其含义如下面图例所示。For语句的结构以及在不同编程语言中的描述。在执行语句中,第三类重要的语句是模块调用。程序模块主要分为过程与函数两类，而输入输出语句则是一种特定的模块调用，也可以归入模块调用。首先，过程是一个指令的集合，并作为其他程序单元调用的一个模块来完成任务。在其他程序单元调用了某个过程时，程序的控制权就转移给了该过程；在该过程执行之后，控制权又返回到调用该过程的程序单元，如下图所示。其中，将控制权转移给过程的步骤称为调用（calling），而将一个请求过程执行的程序单元称为调用单元（calling unit）。调用程序单元 控制传递到过程请求过程 过程被执行调用程序单元 当过程完成时，控制继续 返回到调用单元程序调用一个过程的控制流程示意图从构成结构上讲，过程就是一个程序的缩影，也包括说明语句与执行语句两个部分构成。在过程说明部分定义的变量称为局部变量（localvariable），其作用范围局限于过程的内部。与此相对，全局变量（global variables）可以作用于整个程序。除了全局变量，过程与调用单元之间的数据传递还可以通过过程参数来实现（parameters）。过程的定义从过程头部（procedures header）语句开始，包括过程名以及形参列表，然后就是类似于程序结构的过程体。过程的调用只需写上调用的过程名以及实参列表，不再需要再现过程体。所谓形参（formalparameters）是指定义过程时在过程中使用的参数变量，而实参（actual parameters）则是指当调用过程中，形参的具体赋值。形参与实参之间的数据传递，不同的语言有不同的实现方式。常见的方式有两种：（1）提供实参的一个副本，此时过程只对副本起作用，而对原实参不起作用；（2）或者提供参数所处的地址，此时过程会对原实参直接作用。定义过程以void开始头部是C语言程序员指定程序单元是过程而不是函数的方法。形参列表。注意，像大多数程序设计语言一样，C 语言要求对每个参数说明数据类型声明一个名为Year的局部变量这些语句描述人口是如何计算并存储在名为Population的全局数组中。实参列表调用过程：ProjectPopulation(0.03);用C语言编写的过程定义与调用定义过程Demo: 调用过程Demo:Procedure Demo(Formal) Actual 5;Formal Formal+1; Demo(Actual);a.当过程被调用时，数据的副本给该过程执行过程Demo，按值传递方式传递参数b.该过程操纵它的副本c.于是，当过程终止时，调用环境没有改变执行过程Demo，按值传递方式传递参数a.当过程被调用时，形参变成对实参的引用b.于是，该过程所做的改变是对实参的c.因此，在过程终止后被保留下来了执行过程Demo，按引用传递方式传递参数现在介绍函数。函数是一种特殊的过程，当其调用结束时会产生一个数值。因此，对函数的调用也与过程不同，其主要出现在表达式中。比如，下图给出的就是用C语言定义的一个函数CylinderVolume（），调用该函数时的形式可为：Cost=3* CylinderVolume（3.45，12.7）；注意，由于函数调用结束后会返回一个值，因此函数可以出现在表达式中来参与计算。函数头部以要返回数据的类型作为开始声明一个名为Volume 的局部变量计算圆柱体的体积终止函数并返回变量Volume的值用C语言编写的函数在一般的编程语言中，均会提供程序的输入输出手段，通常的实现方式是通过系统调用来实现。也就是说由机器系统（操作系统）提供一些标准的过程或函数，称为系统调用，来专门完成各种输入输出任务。对应的，在某种语言中也会提供与这些系统调用相配套的输入、输出标准过程或函数，在编制程序时，不必定义这些过程或函数而可以直接调用。比如，在Pascal语言中，从键盘中输入一个值赋给给定的变量Value，可以直接调用过程Reasln(Value)；并将其输出到屏幕上，则再调用过程：writeln(Value)；如此等等。其他语言也一样，均规定了各自相应的输入输出过程或函数。C语言格式化输出的例子对于编程语言的程序结构，最后需要说明的是，大多数编程语言均提供有注释说明功能，可以称之为解释性语句。主要是帮助人们阅读程序的，而不是提供给机器执行的。因此，在编译器处理程序时，都忽略注释。不同的语言中注释的方式有不同的约定，如下例子：/*This is a comment.*/ This is a comment.均是在C+、C#、JAVA语言中合法的注释。第4.3节软件开发对于十分复杂的智能计算问题，往往需要构造规模庞大的程序，一般称其为智能软件开发，此时就需要有一个软件开发的系统方法。而对于规模较大软件的开发，一般要经过分析、设计、实现与测试这样四个阶段的过程。分析主要是弄清所开发的软件需要解决的是什么问题、实现什么功能、满足什么样的要求等，并以规范化的说明书给出。软件生命周期软件开发周期如果说分析关注的是软件系统应该做什么，那么设计关注的就是应该如何实现软件系统的这些目标或功能等要求。大型软件的开发通常使用模块化方法来设计程序系统，主要思想是将总体任务逐级分解，直到所有最底层的子任务均可以直接进行单独编程为止，然后再建立起来所有分解模块之间的调用关系，形成完整的程序功能设计系统。实现就是将设计的方案具体用某种程序设计语言编制成为软件程序，也常常称为代码。编制好的软件程序需要进行实际运行，检查是否实现了最初的目标，这个过程就叫做测试。因此，测试与实现紧密相关，对于复杂的软件系统开发，系统设计中的每一个模块在其实现过程中均要进行单独的测试，然后才是整体系统的测试。当然，测试一个模块或系统并非是一件容易的事情，需要有系统的测试方法与技术，其中如何选择测试数据就是其中非常具有挑战的课题。常用的测试方法分为白箱测试（glass-box testing）和黑箱测试(black-box testing）。白箱测试是指软件内部结构是透明的，可以采用诸如基本路径测试方法，来测试软件内部每一条可能执行路径的正确性，来完成软件的测试。黑箱测试则刚好相反，软件内部结构是不透明的，只能根据输入数据执行的结构来断言软件系统的正确性。当然，复杂软件的输入往往是不可穷尽的，为了能够有效测试软件，黑箱测试往往只针对一些特殊的数据输入进行测试，比如边界数据分析就是黑箱测试的一种具体方法。通过测试的软件系统就可以投入使用了，不过需要指出的是，即使通过了系统的测试，也很难保证软件程序的正确性，因此在使用中不断发现问题并进行修改完善，是经常性的工作，称为维护。在软件开发的分析、设计、实现与测试四个阶段中，分析是依赖于问题领域的、而实现主要是利用前面介绍的编程语言进行代码就可以完成。因此这里需要进一步深入介绍的就是设计方法问题了，特别是模块化程序设计方法。为了便于分解任务并给出子任务之间的关系，一般采用结构图来刻画软件模块及其之间的关系。如图所示，每一个模块（过程）用一个矩形框来表示，而模块之间的依赖关系用联结矩形框的箭头来表示，可以是构成关系，也可以是调用关系。比如成熟的软件模块描述结构图还有程序流程图，数据流图，以及实体关系图等。任务模块子模块1 子模块2 子模块3子模块21 子模块22任务分解结构图模块的划分原则是模块化程序设计中一个关键问题。显然，模块划分不宜过细，但每个模块也不宜过大，如何做出平衡是提高软件效率的重要课题。划分模块的一个基本原则是，尽可能密切块内联系而降低块间联系。降低块间联系就是使得模块之间的独立性尽可能大，如果将模块之间的联系称为块间耦合（coupling），那么模块之间独立性最大化的目标就变为将块间耦合性最小化。通过分析可知，块间耦合的形式主要有两种，一种是控制耦合，出现在一个模块对另一个模块控制的情形中，比如模块之间的调用关系；另一种是数据耦合，模块之间具有数据共享现象。注意数据耦合常常比较隐秘，容易被忽视，从而导致许多软件错误。我们把那些不是显式的模块耦合现象称为隐式耦合，在软件模块设计中应该尽可能避免。与块间耦合性最小化相对应的另一个问题就是