程序设计方法学(六)ppt课件

01.05.2020,.,1,第六章程序设计的形式化方法,软件新技术智能化技术扩大软件功能的关键途径自动化技术提高软件生产率的根本途径集成化技术助于提高生产率、提高质量并行化技术提高系统实效的关键技术自然化技术实现社会信息化,01.05.2020,.,2,重要方向攻克的关键教技术网络体系传感器网与因特网的高效融合集成芯片从Systemonchip到Chipondemount虚拟计算资源聚合的有效性和可靠性验证软件工程基于网络环境的需求工程知识处理挖掘从消息到知识到决策的元知识高效系统在高性（效）能计算系统中系列关注信息安全信息教育,01.05.2020,.,3,跨越源之识规律,创新根植辨短长,汪成为院士,01.05.2020,.,4,软件自动化的三个层次,软件自动化（自动程序设计）广义：尽可能地借助计算机系统实现软件开发狭义：从形式化的软件功能规范到可执行程序代码这一过程的自动化从软件需求规范软件功能、性能规范的转换解决从“非形式”“形式”难度很大，寄希望于受限自然语言方面的突破从软件功能、性能规范软件设计从“做什么”“如何做“从软件设计规范高级语言已有相当的进展，出现了许多工具,01.05.2020,.,5,1概述,一、重要意义软件发展中的问题：整体功能不强、缺乏智能、质量欠佳、生产效率低软件自动化是提高软件生产率的根本途径软件自动化的前提是形式化因此将形式化的理论和方法用于需求分析与规格说明是实现软件自动化的前提,01.05.2020,.,6,二、发展状况有30多年历史Dijkstra、Hoare程序验证Scott、Stratchey程序语义形式化方法(FormalMethod)：通过严格的规范化的数学理论来描述软件系统“做什么”的方法。需要形式规范语言的支持。形式规范语言：提供了一个称为语法域的记号系统。一个称为语义域的目标集合，以及一组精确定义的哪些目标系统满足那个规范的规则。,01.05.2020,.,7,因此，形式化方法是在软件系统的开发过程中使用一种形式系统来表示模型的方法。形式系统是二元组（L，Cn）L：语言（形式规范语言）Cn：对应关系，由推理规则构成在软件规范方法方面的代表性成果有：基于异调代数的代数方法特点：用抽象代数中的公理化方法来刻画抽象数据类型中运算的性质，而不涉及数据的具体表示。基本理论：代数语义,01.05.2020,.,8,抽象模型方法特点：基于某些已知的ADT来给出待定义的ADT的抽象模型，用抽象模型来刻画待定义的ADT中运算的功能。基本理论：指称语义状态机方法特点：通过状态的转换来刻画输入与输出间的关系基本理论：操作语义高阶软件方法（HOS）基于控制公理基本理论：公理语义,01.05.2020,.,9,在软件规范语言方面的代表性成果有：一阶谓词演算组成语言80年代：Z语言、Larch语言、VDM语言90年代：面向实时及分布式的LOTOS语言、面向对象的Z+、Object-Z、VDM+等三、分类基于模型的方法给出系统（程序）状态和状态变换与操作的显式的表示但亦是抽象的定义，不涉及并发的行为。如：Z、VDM,01.05.2020,.,10,代数方法通过联系不同的操作间的行为关系给出操作的隐式定义，未给出并发的显式表示。如：OBJ、Larch过程代数方法给出并发过程的一个显式模型，并通过过程间允许的可观察的通信上的限制来约束表示行为。如：CSP（通信顺序进程）和CCS（通信系统计算）基于逻辑的方法采用逻辑来描述系统的特性，包括程序行为的低级规范和系统时间的行为规范。如：时态逻辑、模态逻辑,01.05.2020,.,11,基于网络的方法根据网络中的数据流显式地给出系统的并发模型，包括数据从一个结点流向另一个结点的条件。如：Petri网、谓词变换网,01.05.2020,.,12,四、形式化软件开发方法采用软件生命周期的变换模型，其实质是将现实世界的需求反映成软件的模型化过程。涉及三方面模型：现实世界，模型表示和计算机系统。因此开发的过程就是从三方面对系统进行描述和转换的过程。开发过程中的任务为：模型获取：从现实世界向模型表示的过程，涉及如何提取、表示模型。对应需求分析、设计等活动。模型验证：对得到的模型表示进行检验，判断是否捕获了所有的需求，该模型是否具有所期望的特性。模型变换：是向计算机系统变换的过程，关键的任务是一致性检测。对应实现和测试。,01.05.2020,.,13,三项任务分别对应三方面的活动：1.形式化规范（规格）：软件规范是指对软件系统对象及用来对系统对象进行操作的方法的集合。以及对所开发系统中的各对象在生命周期间的集体行为的描述。对应与软件生命周期的各个阶段，规范应该理解为是一个多阶段的行为。见例图规范可以采用非、半形式化的方法来描述，形式化规范精确地描述了用户的需求、软件系统的功能及各种性质，其描述的是“做什么”，而不考虑“如何做”。因此，在理解、掌握形式规范语言和方法的基础上对所描述的系统的全面、深入的了解，给出恰如其分的描述上至关重要的。,01.05.2020,.,14,包含各规格阶段的生命周期模型例,需求分析,BS,SRD,系统设计1,DS,系统设计2,PS,软件开发,代码实现,软件测试,运行,SRD：软件需求文档BS：行为规范DS：设计规范PS：程序规范,01.05.2020,.,15,软件系统规范的形式化方法,从形式化规范到目标软件系统的可实现和可执行角度，可分为三类：操作类：此类方法基于状态和转移，通过可执行模型来描述系统，模型本身能够采用静态分析和模型执行而得到验证。如：有限状态机、Statecharts、Petri网等。描述类：此类方法基于数学公理和概念，通过逻辑或代数给出系统状态空间，具有高度抽象的特点，便于通过自动工具进行验证。如：基于代数的Z、VDM、Larch等，基于逻辑的命题线性时态逻辑、一阶线性时态逻辑、计算树逻辑等。双重类：此类方法兼具二者的特点，如：扩展状态机/实时时态逻辑等。,01.05.2020,.,16,形式化规范的成功案例,IBM商用信息系统，牛津大学和Hursley实验室使用Z语言。总体成本降低9，获皇家技术成就奖。Praxis公司使用VDM开发的伦敦机场信息显示系统，软件质量大为提高，故障率0.75(220)每K行代码。其他领域：数据库：HP医用仪器实时数据库系统电子仪器：Tektronix系列谐波发生器硬件：INMOS浮点处理器、INMOS中T9000系列虚拟信道处理器运输系统：巴黎地铁自动火车保护系统、以色列机载航空电子软件等等,01.05.2020,.,17,形式化验证软件开发中错误发现的越晚修改的代价越大，与传统方法不同的是形式化方法要求在完成形式规范后就进行形式验证。形式验证主要技术包括模型检验和定理证明。模型验证是一种基于有限状态机模型并检验该模型的期望特性的技术。即对模型的状态空间进行搜索，以确认该系统具有某些性质。终止性依赖于模型的有限性。优点是：完全自动化、速度快，可用于系统的部分规范。缺点是：“状态爆炸问题”因而极大地限制其实际使用范围。有序二叉决策图（OrderedBinaryDecisionDiagrams)是一种表述状态转移系统的高效率的方法。目前可以处理100200个状态变量、状态数达10120的系统。,01.05.2020,.,18,模型检验需要工具的支持，已有的工具有：时态逻辑模型检验工具，如：EMC、CESAR、SMV、Nurphi、SPIN、UV等。行为一致检验工具，如：FRD、Cospan/FormalCheck等复合检验工具，如：HSIS、VIS、STcP等贝尔实验室用FormalCheck对其高级数据链路控制器进行验证，从6个性能的规范中发现一个失败，进而发现一个影响信道流量的Bug。基于SMV输入语言建立了IEEEFuturebus896.11991标准下cache一致协议精确模型，通过SMV的验证，发现了原先未找到和潜在的错误。此工作是第一次从IEEE标准中发现错误。,01.05.2020,.,19,定理证明采用逻辑公式来规范系统及其性质，这儿的逻辑由一个具有公理或推理规则的形式系统给出，进行定理证明的过程就是应用这些公理或推理规则来证明系统具有某些性质。定理证明可以处理无限状态空间问题，粗略地分为自动和交互两种类型，自动定理证明系统是通用搜索过程，在解决各种组合问题中比较成功。交互式定理证明系统需要与用户进行交互，要求用户能提供验证中创造性最强的部分（如断言等），因此效率较低，较难用于大系统的验证。,01.05.2020,.,20,现有的定理证明器有：用户导引自动推理工具，如：ACL2，Eves、LP、Nqthn和RRL等它们由引理或定义序列导引，每一个定理采用已建立的推演、引理驱动重写和简化启发式来自动证明。证明检验器，如：Coq、HOL、LEGO等。复合证明器，如：Analytica中将定理证明和符号代数系统Mathematica复合，PVS和Step将决策过程，模型检验和交互式证明复合在一起。基于符号代数运算的自动证明用于证明Pentium中SRT算法的正确性，查出了一个由故障商数字选择表引起的错误。,01.05.2020,.,21,程序求精（又称程序变换）是将自动推理和形式化方法相结合而形成的一门新技术，研究从抽象的形式规范推演出具体的面向计算机的程序代码的全过程。基本思想是：用一个抽象程度低、过程性强的程序去替代一个抽象程度高、过程性弱的程序，并保持二者功能的一致性。这儿的“程序”是广义的“程序”，是对规范、设计文档、程序代码的统称。按这种观点，程序开发的过程就是从最高层的程序开始，通过一系列的求精变换，每一次都降低一些抽象程度或增加一些可执行性，最终得到能指导计算机明确执行的程序代码。,01.05.2020,.,22,在进行求精的过程中必须要保证程序的正确性，即保证程序是满足最初的形式规范的。程序的这种正确性可以通过求精过程中所遵循的一系列规则来保证，也可以采用验证工具来证明。程序求精技术是形式化方法研究的一个热点，尽管目前真正用于实际软件开发过程中并不多，但是这是一个很重要的方向。典型的方法有：IBMHursley公司和牛津大学PRG程序设计研究组提出的针对Z规范的求精方法，CarrollMorgan的规则求精方案（见ProgrammingfromSpecifications一书）。,01.05.2020,.,23,五、认识形式化方法成长至今争议声不断，应正确地认识形式化方法，在结合到具体的软件开发过程时应考虑：应用的类型，考虑问题领域的特点和模型的复杂性规模和结构，较适应中等规模的系统，大型系统应考虑具有良好的结构类型的选择，应从所确定的目标出发考虑采用的形式化方法的类型形式化的级别，应先确定应用的关键程度、项目规模、可用资源等确定采用非、半或高度形式化的描述,01.05.2020,.,24,使用范围，尽管形式化可以适应所有的开发阶段，但通常应有选择的使用，对那些安全性、可信性要求高的构件应用高度的形式化工具，工具的支持在形式化方法中具有重要的位置，应根据具体项目，综合上述因素选择合适的工具,01.05.2020,.,25,01.05.2020,.,26,结论：形式化的方法不是灵丹妙药，而是一种改进系统可靠性的方法。,01.05.2020,.,27,2.基于代数方法的规范语言OBJ,该方法的理论工作由Guttage提出基本格式：（语法定义、语义定义、限制说明）语法定义指出类型的语法信息和检查信息作用：定义了类型与函数语义定义指出了类型和操作间的公理作用：定义了类型的语义限制说明给出各种限制，防止二义性作用：和语义定义一起给出重写规则基础抽象是整数集，函数定义了它们之间的相互关系，这样规范的值与函数形成一个抽象代数。,01.05.2020,.,28,形式定义：代数规范是三元组（S、E）其中：S、是标记，S是类集，是操作集，E是有限个方程的集合，形式为L=R，其中L、RS，称为项。项的定义S中的变元是项常量是项项经过操作集中的操作后也是项有工具支持的二个代数规范语言是：AFFIRM、OBJ,01.05.2020,.,29,一OBJ简介,一种代数形式规范语言，最基本的概念是ADT（抽象数据类型），每个ADT描述一个客体。具有很强的独立定义和数据抽象的机制。支持层次化设计，即在定义高层ADT时可以使用下层已定义的ADT。用OBJ书写形式规范的过程就是用代数等式（方程）定义ADT的过程。是一种基于代数方程逻辑的代数形式语义，又具有一种基于把代数方程解释为重写规则的操作语义。（可利用这种语义证明程序的正确性）。,01.05.2020,.,30,二、基本形式,一个OBJ的形式规范说明是诸多ADT定义的集合，每个ADT具有如下形式：,其中obj与jbo是必须的，其余部分任选。,01.05.2020,.,31,例1定义ADTNATURALobjNATURALsortsnatops0:nat/*0无定义域，常量*/succ(-):natnat/*nat上的一目运算，-表示运算对象*/jbo在定义ADT时若需要用到低层已定义ADTL中的运算，可在obj处用/L指出，多个时用空格分隔。,例子,01.05.2020,.,32,例2.在NATURAL的基础上定义ADDobjADD/NATURALops-+-:natnatnatvarsx,y:nateqns(0+x=x)(succ(x)+y=succ(x+y)jbo下面将给出一个较大的形式规范定义对整数序列进行分类。在规范中自底向上的顺序分别定义了多个ADT。如：Boolean、Integer、seq_INT、sort_seq_INT等。,01.05.2020,.,33,例3对一个整型数列分类的形式规范1.objBoolean/TRUTH/TRUTH是OBJ内部已varsa:Boolean/定义的ADT，它具有eqns(not(T)=F)/T和F两个常量(not(F)=T)(not(not(a)=a)(Tanda=a)(aandF=F)(Tora=T)(Fora=a)jbo,01.05.2020,.,34,2.整型ADT/对下述十个运算的规则容易给出，故省略了objInteger/BooleansortsINTops-:INTINT-+-:INTINTINT-:INTINTINT-*-:INTINTINT-div-:INTINTINT-mod-:INTINTINT-:INTINTBoolean-=-:INTINTBooleanjbo,01.05.2020,.,35,3.定义整型字符串ADTobjseq_INT/Integersortsseq_INTops:seq_INT/空-:seq_INT/常量-:seq_INTseq_INTseq_INT/链接hd-:seq_INTINT/头元素tl-:seq_INTseq_INT/尾串len-:seq_INTINT/长度varsi:INTs:seq_INT,01.05.2020,.,36,eqns(s=s)(s=s)(hd=0)(hdi=i)(hd(is)=i)(tl=)(tli=)(tl(is)=s)(len=0)(lens=succ(len(tls)ifs)jbo,01.05.2020,.,37,4定义比较ADTobjsort_seq_split/seq_INTIntegerops-=-:seq_INT,INTseq_INTvarss:seq_INTi,x:INTeqns(=x)(i=x)(is)=x=)(i=x=ifi=x=i(s=x)ifi=x)jbo,01.05.2020,.,38,5定义分类ADT的规范objsort_seq_INT/sort_seg_splitseq_INTIntegerBooleanopssort-:seq_INTseq_INTis_sorted-:seq_INTBooleanvarss,s1,s2:seq_INTi,j,x:INTeqns(is_sorted=T)(is_sortedi=T)(is_sortedij=ij)(sort(sij)=sort(sji)ifij)(sort(s1ijs2)=sort(s1jis2ifij)(sort(tls=hds)=sortsifs)(s=x=(tls=x)ifsandhds=x=hds(tls=x)ifsandhds=x)(s=x)(sx=hds(tlsx)ifsandhdsrInv_choicetchoice.lent=4,01.05.2020,.,63,函数及运算,Teacher_Promotion(tsl:Studentdata_list,rsl:Researchdata_list,m：N)P:Teacher_listextwroutput:Teacher_listPrelentsl=(tsli)=name1(rsli)/*教学、科研二个表中名字相同*/PostP=Get_Persons(Teacher_order(Teacher_list_production(ts1,rs1),m)output=outputconjP,01.05.2020,.,64,/*从已排序的教师序列表td中取出总成绩最高的n位教师，从高到低次序放入tt表中*/Get_Persons(td:Teacher_order_list,n:N)tt:Teacher_listPretdlentdni,jindstditotal_score(tdi)total_score(tdj)Postlentt=nelemttelemtdi,jidnsttitotal_score(tti)total_score(ttj)xelemttyelemtd/elemtttotal_score(x)total_score(y),01.05.2020,.,65,/*将输入的tl表中按总成绩从高到低排序后放入另一个表d中*/Teacher_order(tl:Teacher_list)d:Teacher_listPrelentl0Postelemd=elemtli,jindsitotal_score(di)=total_score(dj)/*教学得分+科研得分总成绩*/score_sum(te:Teacher)ts:TeachersumPret_name(te)Postt_name(te)=name2(ts)total_score(ts)=t_score(te)+r_score(te),01.05.2020,.,66,/*一个递归函数，通过引用score_sum和Teacher_Research_Score计算所有教师的总成绩，并将教师的名