1、2022-5-25华东师大计算机科学技术系1程序设计方法学程序设计方法学Programming Methodology 华东师范大学计算机科学技术系华东师范大学计算机科学技术系杨宗源杨宗源2022-5-25华东师大计算机科学技术系2前言前言 从方法论角度讨论、研究程序设计（软件研发）从方法论角度讨论、研究程序设计（软件研发） 重点：程序设计的原理、原则与技术重点：程序设计的原理、原则与技术 目的：提高软件生产率目的：提高软件生产率 研究程序的性质以及程序设计的理论和方法的研究程序的性质以及程序设计的理论和方法的学科。基本内容一般可以包括：学科。基本内容一般可以包括：2022-5-25华东师大计
2、算机科学技术系3程序的性质与特征程序的性质与特征程序的功能描述程序的功能描述程序的正确性验证程序的正确性验证程序的推导与综合程序的推导与综合程序的结构分析程序的结构分析程序语义的描述程序语义的描述程序设计的策略与技术程序设计的策略与技术 程序研制工具、程序研制工具、 环境环境 涉及程序设计理论、规范、研发技术（方法）、涉及程序设计理论、规范、研发技术（方法）、支持环境与自动程序设计等。支持环境与自动程序设计等。2022-5-25华东师大计算机科学技术系4授课内容授课内容 第一章第一章 综述综述 第二章第二章 程序的基本结构程序的基本结构2.1 Prime程序程序 2.2 2.2 复合程序复合程
3、序 2.3 2.3 结构定理结构定理2.4 2.4 递归结构定理递归结构定理 第三章第三章 程序的数据结构程序的数据结构3.1 3.1 类型与类型系统程序类型与类型系统程序 3.2 3.2 程序设计语言中的数据类型程序设计语言中的数据类型 3.3 3.3 数据抽象与抽象数据类型数据抽象与抽象数据类型（ADT）3.4 3.4 面向对象方法面向对象方法3.5 3.5 面向方面编程面向方面编程2022-5-25华东师大计算机科学技术系5 第四章第四章 程序的正确性证明程序的正确性证明 4.1 程序规范与程序的正确性定义程序规范与程序的正确性定义 4.2 部分正确性证明方法部分正确性证明方法 4.3
4、完全正确性证明方法完全正确性证明方法 4.4 最弱前置谓词最弱前置谓词（WP) ) 第五章第五章 程序的形式推导方法程序的形式推导方法5.1 面向目标的程序设计方法面向目标的程序设计方法 5.2 不变式推导方法不变式推导方法 第六章第六章 程序设计的形式化方法程序设计的形式化方法6.1 概述概述6.2 基于代数方法的规范语言基于代数方法的规范语言OBJ6.3基于模型方法的规范语言基于模型方法的规范语言VDM2022-5-25华东师大计算机科学技术系6 第七章第七章 并行程序设计方法并行程序设计方法7.1 7.1 基本概念基本概念 7.2 并行系统并行系统 7.3 并行程序设计语言并行程序设计语
5、言 7.4 通讯顺序进程通讯顺序进程(CSP) 2022-5-25华东师大计算机科学技术系7基本要求基本要求 了解程序设计方法学的地位和重要性；了解程序设计方法学的地位和重要性； 掌握程序控制结构构成的基本原理、基本成份；掌握程序控制结构构成的基本原理、基本成份； 明确数据类型、数据抽象、抽象数据类型对程序明确数据类型、数据抽象、抽象数据类型对程序设计及程序设计语言的影响及重要性并掌握相关设计及程序设计语言的影响及重要性并掌握相关技术；技术； 掌握程序正确性证明的基本方法，具有构造程序掌握程序正确性证明的基本方法，具有构造程序规范的能力；规范的能力； 理解形式化软件开发的基本原理和典型方法；理
6、解形式化软件开发的基本原理和典型方法； 理解并行程序设计基本概念理解并行程序设计基本概念,具有并行程序设计具有并行程序设计的初步能力的初步能力. 2022-5-25华东师大计算机科学技术系8参考书参考书 1. 程序设计方法学基础程序设计方法学基础陈火旺陈火旺 湖南科学技术出版社湖南科学技术出版社 2. 程序设计方法学程序设计方法学 仲萃豪仲萃豪 吉林大学出版社吉林大学出版社 3. 程序设计方法学教程程序设计方法学教程 张幸儿张幸儿 南京大学出版社南京大学出版社 4. 现代软件工程现代软件工程周之英周之英 科学出版社科学出版社5. 形式语义学基础与形式说明形式语义学基础与形式说明 屈延文屈延文
7、科学出版社科学出版社 6. The Science of Programming Gries, D. 7. Communicating Sequential ProcessosHoare,C.A.R8. Programming from Specification Carroll Morgan9. 程序设计方法学程序设计方法学 胡正国胡正国 国防工业出版社国防工业出版社 10. 对象技术导论对象技术导论 冯玉琳冯玉琳 科学出版社科学出版社 2022-5-25华东师大计算机科学技术系9第一章第一章 综述综述 一、发展回顾一、发展回顾1. 四、五十年代四、五十年代机器指令、汇编指令、机器指令、汇编
8、指令、FORTRAN、LISP、ALGOL语言的相继出现，主要用于科学计算。语言的相继出现，主要用于科学计算。成就：冯成就：冯.诺依曼诺依曼提出存储程序提出存储程序 图灵提出自动装置的计算模型图灵提出自动装置的计算模型图灵抽象机图灵抽象机 奠定了现代计算机的理论基础。奠定了现代计算机的理论基础。评价标准：评价标准：指令条数少指令条数少存储单元省存储单元省执行速度快执行速度快2022-5-25华东师大计算机科学技术系102. 六，七十年代六，七十年代高级语言相继出现，高级语言相继出现， 编译技术（语言处理程序）编译技术（语言处理程序）成熟，完善，成熟，完善，Compiler、OS、DBMS 三大
9、系统三大系统软件日趋成熟，解决问题的规模，软件日趋成熟，解决问题的规模， 复杂性大为复杂性大为增加。增加。软件危机出现软件危机出现 缺乏宏观上研究程序设计方法的重要性的认识。缺乏宏观上研究程序设计方法的重要性的认识。“程序设计比人们一般想象的远为复杂得多，其程序设计比人们一般想象的远为复杂得多，其复杂程度超出了人类本身的智力、能力范围。复杂程度超出了人类本身的智力、能力范围。” 成就：成就：a)a) 数据结构和算法理论数据结构和算法理论程序设计程序设计 = 数据结构数据结构 + 算法算法 （Kunth 1971）2022-5-25华东师大计算机科学技术系11b) 形式化方法形式化方法运用推理、
10、逻辑断言等对程序的正确性进行验证运用推理、逻辑断言等对程序的正确性进行验证 Floyd断言法（断言法（1967） 通过断言（谓词公式）证明框图程序的正确性通过断言（谓词公式）证明框图程序的正确性 Hoare公理化法（公理化法（1969） 著名的著名的Hoare逻辑逻辑 PSQ。通过定义一个逻辑系统（含有程序公理及推导通过定义一个逻辑系统（含有程序公理及推导规则）证明程序部分规则）证明程序部分/完全正确性完全正确性 E.D.Dijkstra (1976) 最弱前置谓词最弱前置谓词WP(S,Q)SQ、谓词转换、谓词转换 2022-5-25华东师大计算机科学技术系12 Gries 综合了以谓词演算为
11、基础的证明系统，提出了综合了以谓词演算为基础的证明系统，提出了“程序设计科学程序设计科学”，将程序设计从经验、技术、，将程序设计从经验、技术、技巧升华为科学。技巧升华为科学。 对并行程序对并行程序 提出了时态逻辑、模态逻辑，刻画安全性、提出了时态逻辑、模态逻辑，刻画安全性、事件性、优先性、并发性等程序性质。事件性、优先性、并发性等程序性质。2022-5-25华东师大计算机科学技术系13c)软件工程化方法软件工程化方法软件开发模型软件开发模型 1968年年北大西洋公约组织北大西洋公约组织(NATO)召开软件工召开软件工程会议，首次提出用工程化方法解决软件危机。程会议，首次提出用工程化方法解决软件
12、危机。 Dijkstra（1969） 提出提出”Goto语句语句”有害论。引起了讨论，导有害论。引起了讨论，导致形成致形成“结构程序设计结构程序设计”的概念、原则、方法。的概念、原则、方法。 Pascal语言诞生（语言诞生（Wirth 1971）i) 强调程序结构和风格的良好性强调程序结构和风格的良好性ii) 以良好静态结构，以良好静态结构， 保证程序动态执行的正确性保证程序动态执行的正确性2022-5-25华东师大计算机科学技术系14 Wirth（1971）提出小规模程序设计和大规模程序设计本质的提出小规模程序设计和大规模程序设计本质的不同，提出了不同，提出了“自顶向下、逐步细化自顶向下、逐
13、步细化”，“分分而治之、面向功能、功能分解而治之、面向功能、功能分解”的思想。的思想。 Parnas（1971）提出提出“信息隐藏信息隐藏”，模块化。，模块化。 Modula-2(1979)、C（1972）、）、Ada（1979） Unix OS、SA、SD、JSP等等等等2022-5-25华东师大计算机科学技术系153. 八、八、 九十年代九十年代编程不再是主流，编程不再是主流，构造系统的方法构造系统的方法 （即系统的结（即系统的结构、接口、集成）。构、接口、集成）。网络、分布式共享信息，协同工作。网络、分布式共享信息，协同工作。方法论与工程化方法论与工程化 a) 结构化程序设计方法结构化程
14、序设计方法 80s进入全盛时期，比较完备，称为传统方法。进入全盛时期，比较完备，称为传统方法。关系数据库管理系统（关系数据库管理系统（RDBMS）、）、SQL语言趋语言趋于成熟。于成熟。传统的软件工程方法：传统的软件工程方法： 功能分解法、数据流方法功能分解法、数据流方法 JSD、信息造型法（信息造型法（E-R模型模型） 2022-5-25华东师大计算机科学技术系16b) 面向对象程序设计方法（面向对象程序设计方法（ O-O方法方法 ）1) O-O是程序设计新的规范是程序设计新的规范 从面向过程从面向过程 面向对象面向对象 一系列概念（如：继承、多态、封装一系列概念（如：继承、多态、封装） C
15、/C+、Eiffel、Java、C#（.NET）2) O-O是信息系统设计的方法论是信息系统设计的方法论面向对象分析、设计（面向对象分析、设计（OOAD）Coad/Yourdon面向对象的软件工程面向对象的软件工程 (OOSE)，用例（用例（UseCase)建模建模 对象建模技术（对象建模技术（OMT）G.BOOCH方法方法2022-5-25华东师大计算机科学技术系17责任驱动设计（责任驱动设计（RDD）CRC卡（类责任合作）卡（类责任合作）VMT（可视化建模技术）（可视化建模技术） UML（统一建模语言（统一建模语言 Unified Module Language) RUP（Rational
16、 Unified Process) MDA（模型驱动体系结构（模型驱动体系结构 Model Diven Architechture）UML、XML、CORBA、Java 3 3）O-O是正在兴起的新技术是正在兴起的新技术 支持各类应用、不同种类的开发，支持各类应用、不同种类的开发，重要的突破：软件的复用（重要的突破：软件的复用（Reuse）、应用框架）、应用框架（Application FrameWork)、软件架构（、软件架构（Software Architecture） 2022-5-25华东师大计算机科学技术系18c）面向方面程序设计（面向方面程序设计（Aspect-Oriented P
17、rogramming），简称），简称AOP。是为解决。是为解决OO方方法中的问题而出现的。法中的问题而出现的。 该技术被评为该技术被评为21世纪对经济和人类生活工作方世纪对经济和人类生活工作方式最有影响力十种技术之一。式最有影响力十种技术之一。 AOP的核心思想是将软件系统中的横切关注点的核心思想是将软件系统中的横切关注点和核心关注点分别模块化，各自处理，再通过和核心关注点分别模块化，各自处理，再通过编织器进行无缝的编织实现，以解决代码纠缠编织器进行无缝的编织实现，以解决代码纠缠等问题，降低耦合度，提高可维护、可重用、等问题，降低耦合度，提高可维护、可重用、可扩展性。可扩展性。 目前支持目前支
18、持AOP的语言有的语言有AspectJ、 AspectC、 AspectC+、 AspectC#、 AspectS、 AspectR（Ruby）及）及SpringAOP、JBossAop等等。等等。2022-5-25华东师大计算机科学技术系19 d）工程化的其他方法）工程化的其他方法 i. 计算机辅助软件工程（计算机辅助软件工程（CASE）Unix 工具箱、工具箱、Ada的开发环境、程序综合器、的开发环境、程序综合器、 软件工具软件工具ii. 基于构件（基于构件（Component)的软件工程（的软件工程（CBSE） COM/COM+、CORBA、EJB设计模式设计模式(Gamma) “其重要
19、性可以与其重要性可以与70年年代从编程中分离数据结构和算法作为程序设计代从编程中分离数据结构和算法作为程序设计的规律性成果相媲美的规律性成果相媲美”。2022-5-25华东师大计算机科学技术系20iii. 净室软件工程（净室软件工程（Clean Room SE）集成：建模技术、形式化方法（程序验证等）、集成：建模技术、形式化方法（程序验证等）、 统计质量控制等方法、技术。统计质量控制等方法、技术。 目的：生成极高质量的软件。目的：生成极高质量的软件。iv. 软件过程软件过程CMM体系、体系、CMMiv.轻载软件工程轻载软件工程（Agile开发方法、敏捷软件开开发方法、敏捷软件开发方法）发方法）
20、eXtreme Programming（极值编程）（极值编程）SCRUM开发方法开发方法FDD（特征驱动开发方法）（特征驱动开发方法）DSDM （动态系统开发方法）（动态系统开发方法）2022-5-25华东师大计算机科学技术系21d) 形式化的方法形式化的方法 计算机语言的研究可以分为三部分：计算机语言的研究可以分为三部分： 语法学（语法学（Syntax)：研究程序设计语言的形态结构：研究程序设计语言的形态结构 语义学（语义学（Semantics)：研究程序设计语言和它所指的：研究程序设计语言和它所指的对象间的关系对象间的关系 语用学（语用学（Pragmatics)：研究语言和它使用间的关系：
21、研究语言和它使用间的关系 形式语义学形式语义学 四个研究领域、四种程序计算模型四个研究领域、四种程序计算模型 图灵机模型图灵机模型 谓词演算模型谓词演算模型 代数模型代数模型递归函数论模型递归函数论模型四种语义学四种语义学 指称语义学指称语义学代数语义学代数语义学 公理语义学公理语义学 操作语义学操作语义学2022-5-25华东师大计算机科学技术系22i)i) 指称语义指称语义采用形式系统方法，用相应的数学对象对一个既定形采用形式系统方法，用相应的数学对象对一个既定形式语言的语义进行注释的学科。其基本思想是使语言式语言的语义进行注释的学科。其基本思想是使语言的每一成分对应于一个数学对象，该对象
22、就称为该语的每一成分对应于一个数学对象，该对象就称为该语言成分的指称，程序视为输入域到输出域的映射。言成分的指称，程序视为输入域到输出域的映射。即存在两个域即存在两个域 语法域：定义一个形式语言系统语法域：定义一个形式语言系统 数学域：已知语义的形式系统数学域：已知语义的形式系统方法：用一个语义解释函数，方法：用一个语义解释函数， 以语义域中的对象值来解以语义域中的对象值来解释语法域中定义的语言对象的语义。释语法域中定义的语言对象的语义。基础：论域理论、基础：论域理论、演算演算、不动点理论不动点理论成果：成果：VDMVDM（The Vienna Development Method)The V
23、ienna Development Method)2022-5-25华东师大计算机科学技术系23ii.代数语义代数语义用代数方法对形式语言系统进行语义注释的学科用代数方法对形式语言系统进行语义注释的学科基本思想是把描述语义的逻辑体系和满足这个逻基本思想是把描述语义的逻辑体系和满足这个逻辑系统的各种模型统一在一起，并把模型的集合辑系统的各种模型统一在一起，并把模型的集合视为是一代数机构，研究这些模型间的关系。视为是一代数机构，研究这些模型间的关系。基础：基础：ADT（抽象数据类型）、泛代数、范畴论（抽象数据类型）、泛代数、范畴论方法：寻找合适的模型代数，方法：寻找合适的模型代数， 定义一个抽象数
24、据类型定义一个抽象数据类型（ADT）的不同语义，）的不同语义， 采用代数方法论证规范的采用代数方法论证规范的正确性和实现的正确性正确性和实现的正确性 。成果：成果：OBJ语言（代数形式化规范语言）语言（代数形式化规范语言）2022-5-25华东师大计算机科学技术系24iii. 操作语义操作语义用机器模型语言来解释语言的语义，基本思想是用机器模型语言来解释语言的语义，基本思想是建立一个抽象机器以模拟程序在执行过程中如何建立一个抽象机器以模拟程序在执行过程中如何进行数据处理。进行数据处理。如：属性文法如：属性文法 除定义除定义“做什么做什么”（What），），主要定义主要定义“如何做如何做”（Ho
25、w）iv) 公理语义公理语义把程序设计语言视为一个数据对象把程序设计语言视为一个数据对象,建立它的公理系统建立它的公理系统 ，从而使程序设计语言有了，从而使程序设计语言有了坚实的基础。坚实的基础。 2022-5-25华东师大计算机科学技术系25 这四类方法都可以形成规范语言（这四类方法都可以形成规范语言（Specification Language），形成软件的自动化或半自动化技术。），形成软件的自动化或半自动化技术。 由形成的软件规范（由规范语言描述）由形成的软件规范（由规范语言描述）采用采用演绎综合演绎综合程序转换程序转换归纳综合归纳综合过程实现过程实现机器学习等不同途径机器学习等不同途径
26、实现：从形式规范到程序、实现：从形式规范到程序、从程序到程序的推导从程序到程序的推导 2022-5-25华东师大计算机科学技术系26二、展望二、展望 今后的发展？今后的发展？软件开发对象的变化软件开发对象的变化 数据处理数据处理数据数据无关无关信息技术信息技术信息信息 与一个语境（与一个语境（context）相关联）相关联2022-5-25华东师大计算机科学技术系27知识知识 知识：知识： 与多个语境相关联与多个语境相关联 智慧智慧 智慧：智慧： 基于不同来源的已有知识基于不同来源的已有知识来创造的一般性原理来创造的一般性原理2022-5-25华东师大计算机科学技术系28第二章第二章 程序的控
27、制结构程序的控制结构 2.1 Prime2.1 Prime程序程序一框图程序的基本结点一框图程序的基本结点函数结点：一个入口，一个出口函数结点：一个入口，一个出口 与赋值语句相对应，改变了程序中变量的值。与赋值语句相对应，改变了程序中变量的值。 f 2022-5-25华东师大计算机科学技术系29控制结点（谓词）：一个入口，两个出口控制结点（谓词）：一个入口，两个出口P P是谓词，按是谓词，按P P的值为的值为T T或或F F决定控制流程，不决定控制流程，不改变程序中变量的值改变程序中变量的值 p 2022-5-25华东师大计算机科学技术系30聚合结点：二个入口，一个出口聚合结点：二个入口，一个
28、出口不执行任何运算不执行任何运算 2022-5-25华东师大计算机科学技术系31 在一定条件下，一个程序可由上述结点组合而在一定条件下，一个程序可由上述结点组合而成：成：程序程序 框图框图指令指令 结点结点控制流控制流 有向结点网有向结点网 在框图中将结点名去掉，则该框图可视为一种在框图中将结点名去掉，则该框图可视为一种结构。称为框图结构。结构。称为框图结构。 例例1：框图程序：框图程序： 2022-5-25华东师大计算机科学技术系32p f1q f22022-5-25华东师大计算机科学技术系33二、二、 ProperProper程序程序 一个框图程序，若满足：一个框图程序，若满足： i）一个
29、入口，一个出口（多个出口可由聚合）一个入口，一个出口（多个出口可由聚合结点汇聚成一个）。如：结点汇聚成一个）。如： ii）每个结点总有一条从入口到出口的路径通）每个结点总有一条从入口到出口的路径通过它。过它。 称其为称其为Proper程序。程序。例例1是是Proper程序。程序。例例2：非：非Proper程序的例子：程序的例子：2022-5-25华东师大计算机科学技术系342022-5-25华东师大计算机科学技术系35 定理：一个定理：一个Proper程序，总可以归结成一个函程序，总可以归结成一个函 数结点。数结点。 证：归结方式：找出二个（或二个以上的）结证：归结方式：找出二个（或二个以上的
30、）结点最小的点最小的Proper程序用一个函数结点替代它直程序用一个函数结点替代它直至只有一个结点为止。至只有一个结点为止。 例例3：2022-5-25华东师大计算机科学技术系36三、三、PrimePrime程序程序 Prime程序（程序（ 又称初等程序、基本程序）又称初等程序、基本程序）是是Proper程序且其中不包括由二个以上结点组程序且其中不包括由二个以上结点组成的成的Proper子子程序。程序。 即最小的即最小的Proper程序。程序。 例例4 4：PrimePrime程序有：程序有： 非非PrimePrime程序有：程序有：2022-5-25华东师大计算机科学技术系37 PrimeP
31、rime程序：程序： 非非PrimePrime程序程序: :2022-5-25华东师大计算机科学技术系38 例例5 Prime5 Prime程序的几种重要形式：程序的几种重要形式：函数（函数（funcfunc）序列（；序列（； ）If-thenIf-thenWhile-doWhile-doppf fgf f2022-5-25华东师大计算机科学技术系39Repeat-untilIf-then-elseDo-whilepqf f g f g2022-5-25华东师大计算机科学技术系402.2 复合程序复合程序 一、程序的等价一、程序的等价i.i. ProperProper程序的执行图（程序的执行图
32、（E-chartE-chart） 描述描述ProperProper程序所定义的执行路径。程序所定义的执行路径。E-chartE-chart的构造法：的构造法： （从（从ProperProper程序到程序到E-chartE-chart）a a）对聚合结点编号。）对聚合结点编号。b b）以与）以与ProperProper程序的入口线相连的结点为程序的入口线相连的结点为E-chartE-chart的的根，并沿各路径至出口线。根，并沿各路径至出口线。2022-5-25华东师大计算机科学技术系41c c）对）对E-chartE-chart中每条路径，若当前路径的终止结中每条路径，若当前路径的终止结点是未
33、曾出现在该路径的结点，则把点是未曾出现在该路径的结点，则把ProperProper程程序中与此结点相连的所有出口线及其结点作为序中与此结点相连的所有出口线及其结点作为它的后继。它的后继。d d）执行路径终止在程序的出口或回溯路径中曾）执行路径终止在程序的出口或回溯路径中曾出现的结点。出现的结点。 显然，过程终止（结点有限），得到是一棵有限显然，过程终止（结点有限），得到是一棵有限树。树。2022-5-25华东师大计算机科学技术系42例例6 6：例：例3 3中的框图程序是中的框图程序是ProperProper程序，它的程序，它的E-chartE-chart为：为： 称称 为为repeatrepe
34、at型结点，型结点，可以合并。可以合并。Proper程序中无循环程序中无循环 chart图中无图中无repeat型结型结点。点。ii.程序的执行树（程序的执行树（E-treeE-tree） 是一棵树，描述了程序的所有可能的执行路径。是一棵树，描述了程序的所有可能的执行路径。构造方法：构造方法：在在E-chartE-chart中将所有的中将所有的RepeatRepeat型结点用相应的子型结点用相应的子树替代，抹去所有聚合结点。树替代，抹去所有聚合结点。 2022-5-25华东师大计算机科学技术系43iii. 程序的等价程序的等价 若两个程序有相同的若两个程序有相同的E-tree，则称它们执行等价
35、。，则称它们执行等价。 若两个程序有相同的功能，则称它们功能等价。若两个程序有相同的功能，则称它们功能等价。 例例7 ：程序：程序与程序与程序执行等价执行等价pfffp2022-5-25华东师大计算机科学技术系44 再如：程序再如：程序程序程序不是执行等价，但功能等价不是执行等价，但功能等价 g p q g q p2022-5-25华东师大计算机科学技术系45 结论：结论： 执行等价执行等价=功能等价，功能等价，但功能等价但功能等价执行等价。执行等价。 例例8 8：do-whiledo-while是是PrimePrime程序，但其执行等价的程序，但其执行等价的程序程序不是不是Prime程序程序
36、ffpg2022-5-25华东师大计算机科学技术系46二、复合程序二、复合程序 一个一个PrimePrime程序的函数结点用另一个程序的函数结点用另一个PrimePrime来替代，来替代，产生的一个产生的一个ProperProper程序称为复合程序。程序称为复合程序。 例例9 9：程序：程序是由是由Prime程序程序if-then和和repeat-until复合而成的。复合而成的。pf q2022-5-25华东师大计算机科学技术系47复合程序：一组固定的复合程序：一组固定的PrimePrime程序（称为基础系）程序（称为基础系）经过有限次的替代运算而得到的经过有限次的替代运算而得到的Prope
37、rProper程序。将基程序。将基础系础系P1P1，P2P2PnPn所得到的复合程序全体记为所得到的复合程序全体记为P1P1，P2P2PnPn 。复合程序集的性质、大小由基础系决定。复合程序集的性质、大小由基础系决定。例例1010：1.1. 由由;,If-then;,If-then得到的程序无循环。得到的程序无循环。2. ;，Repeat ;，If-then，While3. ;，If-then-else，While;，If-then-else，Repeat4. ;，If-then与与;，Repeat无法比较无法比较定义：由一组固定的基础系构成的复合程序，称为结定义：由一组固定的基础系构成的复合
38、程序，称为结构化程序。构化程序。 2022-5-25华东师大计算机科学技术系482.3 结构定理结构定理 证明了程序的基本结构是三种证明了程序的基本结构是三种prime程序。程序。 例：只用加法操作计算两个正整数的乘积，即：例：只用加法操作计算两个正整数的乘积，即：x0 y0 S z=x*yz:=0;u:=x;while u0 dobeginz:=z+y;u:=u-1;end2022-5-25华东师大计算机科学技术系49 如还允许加倍、减半等操作，程序为：如还允许加倍、减半等操作，程序为：z:=0; u:=0; v:=0;while u0 do beginif odd(u) then z:=z
39、+v;u:=u div 2;v:=v mul 2; end 2022-5-25华东师大计算机科学技术系50 结构定理：任何一个结构定理：任何一个ProperProper程序功能等价于基程序功能等价于基础系础系;,if-then-else,while;,if-then-else,while所复合的程序。所复合的程序。证：考虑任意的证：考虑任意的ProperProper程序程序P P，设，设P P有有n n个结点个结点（函数、谓词）（函数、谓词）i i）对程序中的谓词、函数结点进行编号（）对程序中的谓词、函数结点进行编号（1 1n n）iiii）引入一个计数器）引入一个计数器L Liiiiii）在
40、编号的基础上为各输入）在编号的基础上为各输入/ /出线进行编号出线进行编号编号规则：编号规则：对结点对结点i i：输入线编号为：输入线编号为i i，输出线为该结点后继，输出线为该结点后继结点的编号；出口线为结点的编号；出口线为0 0。2022-5-25华东师大计算机科学技术系51 注：通过聚合结点至出口线的线编号为注：通过聚合结点至出口线的线编号为0 0。 iv)iv)对每个结点对每个结点i i构造新结点构造新结点g gi i的方法是：的方法是： f i i j p i j k f i i j f i i L:=j 2022-5-25华东师大计算机科学技术系52V）将）将P改造成测试改造成测试
41、L的程序的程序F ： i i j k p i L:=j L:=k 2022-5-25华东师大计算机科学技术系53 程序程序F：L1，while L0 do if L=1 then g1; else if L=2 then g2;else if L=n then gn; else I; FF ;,while,if-then-else;,while,if-then-elseF F与与P P等价。等价。例例1111：2022-5-25华东师大计算机科学技术系54结构化定理的意义结构化定理的意义1. 任一复杂的控制结构可以用三种最基本的结构来任一复杂的控制结构可以用三种最基本的结构来表示。揭露了表示。
42、揭露了Proper程序的构造本质。程序的构造本质。2. 可以从二方面来考察程序：可以从二方面来考察程序：函数结点函数结点 程序段程序段写的过程（逐步细化）写的过程（逐步细化）程序段程序段 函数结点函数结点 读的过程（抽象）读的过程（抽象）3. 给出了如何将一个非结构化的程序转换为结构化给出了如何将一个非结构化的程序转换为结构化程序的方法。程序的方法。2022-5-25华东师大计算机科学技术系552.4 2.4 递归结构程序递归结构程序 问题：问题：结构定理所给出的方法没有考虑程序的清晰性结构定理所给出的方法没有考虑程序的清晰性和有效性，有必要进行改进，可通过消除一些和有效性，有必要进行改进，可
43、通过消除一些多余的计数器多余的计数器L的设置和测试。的设置和测试。 基本思想：对某些基本思想：对某些j0j0，若，若g gj j中不出现中不出现L:=jL:=j的的赋值，可以用程序赋值，可以用程序g gj j来替代所有出现在来替代所有出现在g gi i（ijij）中的赋值）中的赋值L:=jL:=j。如此替代后，由于。如此替代后，由于j j不再赋值给不再赋值给L L，可将，可将L=jL=j从从if-then-elseif-then-else结构中结构中去掉，则语句序列为去掉，则语句序列为g g1 1， g gj-1j-1,g,gj+1j+1 g gn n。这种替代可继续，直至出现如下情形终。这种替代可继续，直至出现如下情形终止。止。i i）除）除L:=0L:=0外所有外所有L L赋值均被消除。赋值均被消除。iiii）每个余下的）每个余下的g gi i中都含有中都含有L:=iL:=i的赋值的赋值2022-5-25华东师大计算机科学技术系56 结论：当程序无循环时，程序中最后只出现结论：当程序无循环时，程序中最后只出现L:=0，所以，所以L可消除，当程序有循环时可消除，当程序有循环时L不可不可消除。消除。 例例12：对例：对例11的改造的改造 例例13：
