程序设计方法学第一章程序设计方法概述(新).ppt

1,程序设计方法学,2,课程的主要研究问题,程序设计的基本特征结构化 模块化对象化（OOP，Object Oriented Programming）智能化（AOP，Agent Oriented Programming）程序设计标准化问题 形式语义 代数规范 程序正确性的代数证明 程序的形式推导 程序变换技术程序设计标准实施问题设计风格 设计方法 设计工具 设计技巧,课程目标,本课程主要介绍程序设计方法学的科学理论、方法 和实现技术。主要介绍程序设计方法学这一新兴学科的主要内容，即结构化程序、程序正确性证明、结构化程序 的正确性证明、递归程序及其正确性证明、程序的 形式推导技术、程序变换技术、面向对象的设计方 法和大型程序设计方法学基础等。培养学生运用这些理论和方法，从认识规律出发训 练各种良好的程序设计习惯，掌握到目前为止公认 为成熟的有实用价值的具有完整科学理论和与之相 关的技术方法作指导的软件设计和开发技术。,3,4,程序设计方法学,基本内容,结构化程序设计方法,模块化程序设计方法,面向对象程序设计方法,函数型程序设计方法,逻辑程序设计方法,程序设计方法发展趋势,程序正确性证明技术,程序形式推导技术,程序变换技术,程序调试技术,抽象数据类型,代数规范理论,类型系统理论,复杂性分析技术,基本方法,基本理论,5,程程序设计方法学与其他相关学科的关系,软件工程（管理、软件产业）数据结构与算法（编程及实现）程序设计语言学（编程及实现）程序设计技巧学（技术与技巧，具有特殊性）程序设计方法学（方法学，指导性理论及基本方法，具有普遍性）,6,“优秀”和“不优秀”程序的要素,正确性；结构化；模块化；可重用可维护；可变化；可管理；可测试性能均衡,错误的；非结构化；难以维护；不能适应变化；不可管理性能与条件失衡,参 考 资 料,1、程序设计方法学，冯树椿、徐流通编著，浙江大学出版社；2、程序设计方法学，胡正国、吴健、邓正宏编著，国防工业出版社，2003年1月；3、新编程序设计方法学，王申康，浙江大学出版社，2004年5月；4、程序验证和规范的形式方法H.K.Berg等著，宋国新等译；5、Design Patterns 或者设计模式6、软件工程Java语言实现StophenR.Schach著袁兆山等译机械工业出版社；7、计算机图灵奖ACM获得者；8、计算机科学导论赵致琢编著，科学出版社；9、文章：浅谈程序设计方法的演进、模块化与计算机软件设计、抽象数据类型及其实现、递归递推与算法设计、递归算 法的非递归实现、面向对象语言与过程语言比较之不足等。,7,8,第一章 程序设计方法概论,学习重点：了解程序设计语言、程序设计方法之间的关系了解程序设计方法形成和发展的过程掌握常见程序设计方法的概况,程序设计就是用计算机语言把对数据进行处理的算法表达出来程序的表达手段就是程序设计语言,9,10,1.1 程序设计语言和程序设计方法,1.1.1 程序设计语言概述 一、定义：程序设计语言是一种用于书写计算机程序的语言。语言的基础是一组记号和一组规则。程序设计语言是人机交互的一种表达方法，是使用计算机的一种工具。程序设计语言是建立计算机精确处理模型与人类智能处理模型之间的某种形式化的桥梁。,11,二、怎样理解和使用程序设计语言？（1）语法：规定程序的结构或形式，记号串的组成规则；（2）语义：程序的含义，记号的特定意义；（3）语用：程序和使用者之间的关系，人机交互的表达方式；（4）语境：理解、执行和实现程序的环境，预定义成分、与系统实现有关的成分，输入输出。,12,程序设计语言发展,13,三、程序设计语言的发展,1、第一代语言：机器语言。机器语言是最早的计算机语言；运行效率高。它用二进制代码表示数据和指令，这些代码不用翻译即可在计算机上直接执行；指令难记，程序难读。编写机器语言程序是一件枯燥而繁杂的工作，存储空间的安排、寄存器变址的使用都由程序员自己计划，且所有的地址分配都是以绝对地址的形式处理；要把为一种机器编制的程序搬到另一种机器上去运行根本行不通。因为不同的机器有不同的指令系统。,14,2、第二代语言：汇编语言。汇编语言是一种比机器语言更接近于自然语言和数学语言的低级程序设计语言。指令采用助记符表示容易记忆，程序也更容易阅读。由于汇编语言一般都是为特定计算机或计算机系统设计的，因此它虽然比机器语言好学，好记，程序也好写些，但仍然没有解决机器语言存在的问题，其生产效率也很低。汇编语言也是面向机器的。它能直接操作计算机的寄存器、内存单元和输入/输出端口，能够设计出执行效率很高的程序，因而汇编语言在某些领域仍有应用。用汇编语言编写的程序需经汇编程序翻译成机器语言程序后才能在计算机上运行。汇编语言指令与机器指令基本上是一对一的关系，但有的汇编语言中可以有宏指令，它对应于一串机器指令。,15,机器语言和汇编语言,原始的冯.诺依曼机器（1946年）代码00000010101111001010 00000010111111001000 00000011001110101000 机器语言是晦涩难懂的，因此需要设计另外一种语言来写程序，它应该是符号式的或者说助记性的。高级语言的优越性：可扩展性；可读性；可移植性,16,3、第三代语言：高级语言。是指人容易理解和有利于人对解题过程进行描述的程序语言，通常所讲的程序设计语言往往指的是高级语言。,从1952年第一个高级语言Short Code诞生到现在，程序设计语言先后出现了不同类型、不同版本不下数 百种语言。,17,18,一、命令式语言,科学计算的语言 Backus1957为Fortran的成功预备了两个成分：记法和效率 APL是唯一使用带有专用符号的交互式键盘来编写程序的语言。商用语言第一个商用语言是COBOL(面向商业的公用语言的缩写)。它是一种功能很强而又极为冗长的语言BASIC设计者的最意图体现在该语言的名字上-初学者通用的符号指令码多用途语言Alogol60主导20世纪60年代程序设计语言的发展。Pascal作为教学语言扩展了AlgolDennis Ritchie1972年创建C语言,19,二、函数式语言,1958年MCarthy设计了LISP用作符号演算，具有严格的理论基础Standard ML、Miranda、Haskell对语言发展的推动作用1984年CLOS是LISP的面向对象扩展，全名是Common Lisp Object System,20,三、面向对象语言,Simula:Kristen Nygaard和Ole-Jodan Dahl在1961年设计了这个语言，目的是想同时作为一种描述语言和程序设计语言Smalltalk是第一个严格意义的全面向对象的程序设计语言，它的设计受到了LISP的影响C+设计的是为了把面向对象的优点带进C的命令式程序设计中JAVA是面向对象程序设计语言的成熟标志你需要知道的一些面向对象程序设计语言和相关语言Algol Ada Smalltalk C C+JAVA,21,4、第四代语言：第四代语言是抽象层次更高的程序设计语言，它把程序员从繁杂的过程性设计中解放出来，用自己的语法形式表示控制和数据结构，不再涉及太多的算法细节。使用最广的第四代语言是数据库语言，它支持用户以复杂的方式操作数据库，用户只需关心做什么，而不用关心怎么做，可以用类自然语言的形式提问。程序生成器是更为复杂的一类4GL，它输入由甚高级语言书写的语句，自动产生完整的第三代语言程序。,22,四、程序设计语言的实现 实现系统:任何一个程序设计语言都有一个实现系统(如编译系统或解释系统)与之匹配。用户使用程序语言编制出的源程序必须通过实现系统的加工处理。1 转换机制:源语言目标语言 a、纵向转换：源语言机器语言（汇编语言）翻译程序:它是这样一个计算机程序,能把用高级语言书写的程序翻译为等价的机器语言或汇编语言.翻译程序主要有编译程序和解释程序。,23,编译程序：是一种把用高级语言编写的源程序作为输入，经过翻译变换产生出面向目标计算机的目标代码程序作为输出的翻译程序。编译程序比较重视目标代码的效率。FORTRAN语言采用这种方式。解释程序：是一种一边解释用高级语言编写的源程序的语句，一边根据解释的结果直接执行。解释程序花费的机器时间要多些，但所占的内存要少些。,源程序,执行机,可执行程序,连接程序,目标程序,编译程序,结果,数据,编译阶段,运行阶段,解释程序,源程序,结果,数据,24,编译程序设计概述 1、词法分析：区别、分离出源程序行文中一个一个的单词，如标识符、保留字、常量、运算符、定界符等。2、语法分析：识别出源程序的基本结构，如模块、子程序、分程序、程序包、数据说明、语句等，并生成有关表格（含语义分析的有关工作）。3、中间代码生成：根据语法分析阶段识别出的语法范畴产生相应的中间代码。中间代码有多种形式，如逆波兰表示法，三元式、四元式等。4、优化处理：主要任务是对前一阶段所产生的代码进行时间与空间的优化。5、目标代码生成：根据中间代码及有关表格生成可在裸机上执行的目标代码，其中包括内存与寄存器的分配等工作。,25,26,b、横向转换：以描述语言Li 表示的源程序SLi以描述语言Lj 表示的源程序SLj,Li,Lj,Fi,Gj,LijP,SLj,SLi,实现系统,27,2 中间语言 在语言的实现过程中产生的非目标语言。中间语言的作用：（1）如中间语言是汇编语言，可实现混合编程。可方便地调用库过程、库函数、外部过程和函数，实现链接功能的扩充和统一。（2）作为两种语言的翻译语言，实现翻译功能。Fi（Li）=M Gj（M）=Lj,28,（3）形成中间语言是编译过程中必不可少的过程。在编译过程中的每一趟均存在着不同形式的中间语言。（4）中间语言提供了不依赖于机器的语言实现机制；Java的编译器把Java的源程序转换成字节码，它不依赖机器，可以看作中间语言，字节码由Java的运行系统解释执行。（5）在函数式语言中，中间语言（计算模型）是描述对象和控制策略的工具。,29,4 语言的等价性理解:重在功能等价。a、源程序级的功能等价：编译过程中产生的中间语言程序和目标程序，它们的功能是相同的。相同的输入产生相同的输出。,从操作语义上理解：meaning(SL)=meaning(SML1)=meaning(SML2)=meaning(SOL),30,b、不同语言之间的功能等价：定义1：对于算法A，采用两个程序设计语言PL1和PL2，所编出源程序SPL1（A）和SPL2（A），如果则对于算法A，PL1和PL2是等价的。定义2：如果对于任何算法，定义1都满足，则称PL1和PL2是语言功能等价的。,31,c、不同语言的语法单位的功能等价（横向软件工程中经常用到）：例1：数据类型定义：PASCAL语言：var x:real;C语言：float x;ADA语言：x:float;,32,例2：循环语句：PASCAL语言：REPEAT S1；UNTIL B；C语言：DO S1；while（!B）；注意：C语言是条件为假时退出循环。,B,S1,T,F,33,d、同一种语言中，相同功能的不同实现。例1：while B do S 与if语句的等价：,L1：if B then begin S；goto L1；end else goto L2;L2:,34,例2：循环语句之间的等价：PASCAL语言：REPEAT S1；UNTIL B；等价为：S1；while（!B）do S1,35,例3：if语句与case语句之间的等价：PASCAL语言：if B then s1 else s2等价为：,i:=BoolIntTran(B);CASE i of 1:S1;2:S2;end CASE;,36,例4：case 语句与if语句之间的等价：PASCAL语言：等价为：,CASE i of 1:S1;2:S2;3:S3;4:S4;end CASE;,if i=1 then S1;else if i=2 then S2;else if i=3 then S3;else S4;,37,1.2 程序设计语言和程序设计方法随着计算机技术发展，程序设计从技巧上升为科学；语言和程序设计方法之间关系密切；新型方法导至新语言的产生；语言是方法的体现，是程序设计的工具；程序设计的关键是算法设计，即方法是第一位的；学习程序设计方法就是设计与规划的能力；程序的正确性是追求的首要目标，而科学的程序设计方法是程序质量的保证。,程序设计方法,功能分解法 计算任务结构化程序设计 以数据为中心面向对象程序设计 以对象为中心组件程序设计 以组件为中心,38,39,程序设计方法的作用,首先，从哲学的角度来看，任何实践活动都需要理论指导。程序设计作为人类在计算机领域的实践活动同样需要科学的理论和方法作为指导。其次，通过对程序设计方法的学习，不仅可以提高对相应语言的运用能力，而且可以从全局的角度对整个软件系统进行规划。最后，科学的程序设计方法是程序质量的可靠保证。,40,美国IBM公司在1963年至1966年开发的IBM360机的操作系统。这一项目花了5000人一年的工作量，最多时有1000人投入开发工作，写出了近100万行源程序。据统计，这个操作系统每次发行的新版本都是从前一版本中找出1000个程序错误而修正的结果。,1995年SEI统计，美国共取消了810亿美元的商业软件项目，其中31的项目未做完就被取消，53的软件项目进度通常要延长50%的时间，只有9的软件项目能够及时交付并且费用也控制在预算之内。,1962年7月22日美国一个计划飞往金星的飞船水手1号在升空290秒之后坠毁。经调查发现，地面控制计算机中一段运行程序执行了类似这样的代码：If not 雷达发现火箭 then 不调整火箭的飞行路线。然而程序员一个不小心漏掉了not，导致了这些事故的发生,程序设计方法的形成-软件危机的产生,41,程序设计方法的形成-软件危机的产生,2000年TechRepublic公司发表了有关IT项目的调查结果。该调查是以北美的1375个IT专家为对象实施问卷调查进行的。根据此调查，IT项目中有40%失败，这些项目的平均成本每年花费100万美元。,程序设计思想的进步,在1968年，荷兰教授E.W.Dijkstra提出了“GOTO语句是有害的”观点，指出程序的质量与程序中所包含的GOTO语句的数量成反比，认为应该在一切高级语言中取消GOTO语句。这一观点在计算机学术界激起了强烈的反 响，引发了一场长达数年的广泛的论战，其 直接结果是结构化程序设计方法的产生，并推动了适应该种方法的语言的产生。,42,程序设计思想的进步,由瑞士计算机科学家Niklaus Wirth开发的Pascal，一经推出，它的简洁明了以及丰富的数据结构和控制结构，为程序员提 供了极大的方便性与灵活性，同时它特别适合微计算机系 统，因此大受欢迎。结构化程序设计思想采用了模块分解与功能抽象和自顶向下、分而治之的方法，从而有效地将一个 较复杂的程序系统设计任务分解成许多易于控制和处理的子 程序，便于开发和维护。因此，结构化方法迅速走红，并在整个20世纪70年代的软件开发中占绝对统治地位。,43,程序设计思想的进步,到了70年代末期，随着计算机科学的发展和应用领域的不断扩大，对计算机技术的要求越来越高。结构化程序设计语言 和结构化分析与设计已无法满足用户需求的变化，于是面向 对象技术开始浮出水面。面向对象程序设计方法起源于Simula 67语言。在程序设计语言的发展史上，20世纪60年代后期是承上启下的重要时期。这一时期有三种重要的语言问世，即Simula 67、由一批顶尖计算机科学家共同设计的Algol 68、以及为iBM 360系列机配套开发的PL/i。这三种语言虽均有所创新，但Simula 67的面向对象概念的影响是最巨大而深远的。它本身虽因为比较难学、难用而未能广泛流行，但在它的影响下所产生的面向对象技 术却迅速传播开来，并在全世界掀起了一股OO热潮，至今盛行不衰。面向对象程序设计在软件开发领域引起了大的变 革，极大地提高了软件开发的效率，为解决软件危机带来了 一线光明。,44,程序设计思想的进步,事实表明，面向对象程序设计方法虽然比结构化方 法能更自然地表现现实世界，但它不是灵丹妙药，并不能解决所有问题，它本身存在固有的内在的局 限性。最近兴起的面向方面编程（AOP）正是为了改进上述程序设计方法学的不足。AOP被视为是“后”面向对象时代的一种新的重要的程序设计技术。而从更广义的范畴看，在过去的40年里，软件体系结构试图处理日益增长的软件复杂性，但复杂性却仍 继续增加，传统的体系结构好像已经达到了其处理 此类问题的极限。新兴的Web 服务通过允许应用程序以对象模型中立的方式实现互连，从而提供了一 个更强大、更灵活的编程模型，并将对软件开发方法产生巨大影响。,45,程序设计方法产生与发展,一、背景程序设计的发展过程 手工艺式的设计方法-工程化的设计方法（50年代后60年代初）（本世纪60年代以来）软件危机 对成本、进度的估算难以准确 用户对已完成的软件系统常常不满意 软件产品质量不可靠 软件常常难以维护 软件成本的上升 缺少文档资料 软件生产速度跟不上实际需要,46,47,程序设计方法的形成-软件危机如何解决,管理学和工程学角度软件工程 划分阶段；加强审计；质量控制；过程改进；结构化；方法学和语言学角度程序设计方法 标准的程序设计；设计模式；设计风格；设计技巧,发 展 过 程,不同程序设计语言的出现带来不同的程序设计方法 1）五十年代：机器指令代码、手工艺劳动，少、快、省 2）六十七十年代初期：第一个高级语言FORTRAN语言出现，简化程序设计，摆脱机器特性限制，集精力于算法本身。,48,问题：1966年，Bohm,Jacopini证明：只要三种控制结构就能表达用一个入口、一个出口的框图（流程图）所能表达的任何程序逻辑1968年Dijkstra Communication of ACM“GOTO有害论”打响了第一炮NATO 在德国软件工程会议建议：GOTO语句太易把程序弄乱，应从一切高级语言中去掉；只用三种基本控制结构就可以写各种程序，而这样的程序可以自顶向下阅读而不会返回。具有历史意义的引起激烈讨论，提出一种新的程序设计思想、方法和风格结构化程序设计思想与概念，以期提高软件生产率和降低软件维护代价 七十年代初期，大型系统软件，操作系统，数据库出现，给程序设计带来新的问题：“软件危机”,49,程序设计方法学的产生和发展（续）,七十年代现在：结构化程序设计程序正确性证明的研究1972年，Mills进一步提出程序应该只有一个入口和出口，补充了结构程序的规则。1974年，D.E.Knuth 对GOTO争论进行了总结：“有些情形，主张废除；另一些情况，主张引进”。1980年，Gries综合了以谓词演算为基础的证明系统，称为“程序设计科学”。首次把程序设计从经验、技术上升为“科学”。今天：方法学的研究获得了不少成果，除结构化程序设计日益完善 外，模块化程序设计、递归程序设计、逐步求精方法等均成 为有效的方法，抽象数据的代数规范，程序的形式化推导技 术正在发展，特别是程序变换技术和自动化方面虽不成熟，但已取得可喜进展。,50,51,1.3 程序设计方法的形成和发展1、程序设计技巧阶段面向机器编程数字计算机之所以能进行程序设计，是因为它有一有穷指令集。50年代编程是使用机器指令代码进行的。随后的汇编语言程序虽然用符号代替代码，但在程序设计本质上没有改变。这个时代的编程者要对机器代码和符号代码非常熟悉。面向机器所编程，程序运行效率一般较高，但维护性、可读性、移植性、通用性都很差。,52,高级语言编程高级语言的出现，大大简化程序设计。高级语言编程基本上与机器无关，而主要集中解决算法、数据结构问题。程序设计=算法+数据结构+程序设计语言各种领域的计算机程序的开发促进程序设计的发展。出现多种高级程序设计语言。但新出现的复杂的操作系统、数据库等软件对程序设计在可靠性、维护、修改、和移植性等方面提出更高要求。此时，传统的程序设计方法出现“软件危机”。,53,2、程序设计从技巧上升为科学结构化程序设计方法1969年，Dijkstra提出结构化程序设计思想：从程序结构上改变传统的程序设计方法。经实践，结构化程序设计方法解决“软件危机”，使程序设计走向系统化、工程化。另外，递归程序设计、自上而下逐步求精设计进一步完善了结构化程序设计方法。一个好的按结构化要求设计程序，一般要求：结构清晰，易读易改易验证，可靠性好，运行效率也高。当运行效率与结构化发化矛盾时，我们宁可牺牲效率，确保好的结构。,54,面向过程的程序设计方法程序由若干个过程（函数）组成，采用自顶向下逐步求精的手段，实现模块分解和功能抽象。程序按功能被划分成若干个模块，各模块在功能上相对独立。每个模块可以用过程（函数）来实现。模块之间要求高内聚、低耦合。过程式程序设计也称为模块化程序设计。数据和过程是相互独立的两个实体。主要设计语言有FORTRAN、BASIC、C、Pascal,55,面向对象的程序设计方法结构化程序设计解决了“软件危机”。但庞大、复杂的程序维护成为整个软件开发过程中非常繁杂的工作，也面临新的考验。面向对象程序设计方法直接将“解”映射到人们对问题的认识上，努力取得对象和操作之间的协调。面向对象方法有目的地把系统分解为模块策略，并将设计决策与客观世界的认识相匹配。在人工智能、数据库领域的研究表明，面向对象不只是有效的程序设计技术，还应成为软件开发的基本方法，成为开发技术是今后软件发展的主流之一。现在的“B、C、D、F”等编程语言都使用了该技术。,56,其它程序设计方法函数式程序设计方法 程序被看作是描述输入与输出之间关系的一个数学函数主要语言有LISP。C也常被称为函数式程序设计语言。逻辑程序设计语言 逻辑被看作是知识推理的工具。程序被看作描述输入与输出之间各种关系的一组方程。程序设计可归结为事实列举、定义逻辑关系、逻辑公式演绎，以提问方式求解。代表语言是Prolog。,57,1.4 程序设计的一般途径,程序设计中最为关心的是程序的效率与程序的正确性。程序的效率常由算法的效率来决定；程序的正确性要保证程序的易读性、可靠 性、可维护性等。在程序设计中十全十美的方法是不存在的。所谓好的程序设计方法只能是针对某些特定的情况而言，所以我们平时应注重在程序设计方法本质的理解和灵活的运用。,58,程序设计的基本步骤,对一个实际问题进行程序设计时通常按照以下步骤进行：问题分析 即弄清待解决问题的功能需求建立数学模型算法设计 即确定面向计算机的解决问题的方法和步骤选用合适的算法描述工具进行算法描述选用合适的计算机语言进行编码在给定的计算机环境中编辑、测试、调试、运行程序，以得到预期的结果,