第章 程序規(guī)范及其正確性證明概述 ppt課件

1、第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述內(nèi)容內(nèi)容Where we are？l程序規(guī)范、規(guī)范的描畫程序規(guī)范、規(guī)范的描畫l斷言與規(guī)范及斷言與規(guī)范及P S Ql程序正確性的概念程序正確性的概念l程序正確性證明的過程程序正確性證明的過程第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序1. 程序規(guī)范：程序規(guī)范：程序設(shè)計(jì)之前，第一步必需明確程序設(shè)計(jì)之前，第一步必需明確“做什么。做什么。所謂所謂“做什么是指對(duì)欲求解的問題的描畫。做什么是指對(duì)欲求解的問題的描畫。程序規(guī)范程

2、序規(guī)范PS-Program Specification:關(guān)于關(guān)于“做什么的描畫。做什么的描畫。這里的這里的PS僅指功能的描畫，不包括諸如處置速度、僅指功能的描畫，不包括諸如處置速度、執(zhí)行時(shí)間、呼應(yīng)周期等與時(shí)間有關(guān)性能目的。執(zhí)行時(shí)間、呼應(yīng)周期等與時(shí)間有關(guān)性能目的。PS是軟件工程的需求分析的結(jié)果。是軟件工程的需求分析的結(jié)果。PS的含義是映射，是輸入到輸出的映射，它反映的含義是映射，是輸入到輸出的映射，它反映了程序?qū)?shù)據(jù)的作用。了程序?qū)?shù)據(jù)的作用。第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))2. 程序程序程序也是映射，是輸入到計(jì)算的映射

3、，即每一輸入都對(duì)程序也是映射，是輸入到計(jì)算的映射，即每一輸入都對(duì)應(yīng)一串計(jì)算步。應(yīng)一串計(jì)算步。3. 程序規(guī)范與程序的關(guān)系程序規(guī)范與程序的關(guān)系給出規(guī)范后，程序開發(fā)就是建立一個(gè)程序，使得計(jì)算剛給出規(guī)范后，程序開發(fā)就是建立一個(gè)程序，使得計(jì)算剛好能實(shí)現(xiàn)規(guī)范的映射；好能實(shí)現(xiàn)規(guī)范的映射；程序驗(yàn)證是證明程序正確地實(shí)現(xiàn)了規(guī)范，即證明規(guī)范和程序驗(yàn)證是證明程序正確地實(shí)現(xiàn)了規(guī)范，即證明規(guī)范和已有程序之間的一致性已有程序之間的一致性規(guī)范規(guī)范程序程序輸入輸入輸出輸出映射映射輸入輸入計(jì)算計(jì)算映射映射第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))4. 程序規(guī)范的描

4、畫程序規(guī)范的描畫-規(guī)范言語規(guī)范言語規(guī)范必需用言語描畫，該言語稱為規(guī)范言語。規(guī)范必需用言語描畫，該言語稱為規(guī)范言語。描畫一個(gè)復(fù)雜問題的輸入和輸出之間的關(guān)系是困難描畫一個(gè)復(fù)雜問題的輸入和輸出之間的關(guān)系是困難的，目前對(duì)規(guī)范言語的方式尚無定論。有三種方的，目前對(duì)規(guī)范言語的方式尚無定論。有三種方式：式：自然言語：不夠準(zhǔn)確，存在二義性，必需輔以數(shù)學(xué)自然言語：不夠準(zhǔn)確，存在二義性，必需輔以數(shù)學(xué)言語。言語。一階謂詞：可以準(zhǔn)確地描畫問題的輸入和輸出的關(guān)一階謂詞：可以準(zhǔn)確地描畫問題的輸入和輸出的關(guān)系，但是規(guī)范文本比較長(zhǎng)。如系，但是規(guī)范文本比較長(zhǎng)。如Hoare系統(tǒng)。系統(tǒng)。數(shù)學(xué)言語：用數(shù)學(xué)言語可以把輸入和輸出的映射描

5、數(shù)學(xué)言語：用數(shù)學(xué)言語可以把輸入和輸出的映射描畫為函數(shù)。這些函數(shù)的準(zhǔn)確的泛函定義就構(gòu)成了畫為函數(shù)。這些函數(shù)的準(zhǔn)確的泛函定義就構(gòu)成了問題的規(guī)范。但存在過于規(guī)范的問題。問題的規(guī)范。但存在過于規(guī)范的問題。第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))5. 一個(gè)適宜的程序規(guī)范言語應(yīng)滿足的根本條件一個(gè)適宜的程序規(guī)范言語應(yīng)滿足的根本條件:該當(dāng)為描畫者和運(yùn)用者所直接了解；該當(dāng)為描畫者和運(yùn)用者所直接了解；該當(dāng)有嚴(yán)厲的數(shù)學(xué)語義該當(dāng)有嚴(yán)厲的數(shù)學(xué)語義該當(dāng)與方式方法的構(gòu)造實(shí)際和程序設(shè)計(jì)言語協(xié)調(diào)該當(dāng)與方式方法的構(gòu)造實(shí)際和程序設(shè)計(jì)言語協(xié)調(diào)該當(dāng)有較強(qiáng)的表達(dá)才干和通

6、用性該當(dāng)有較強(qiáng)的表達(dá)才干和通用性第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))lZ言語言語lVDMlB方法方法l三者的比較三者的比較6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))lZ言語是一種基于集合論和一階謂詞邏輯的方式化言語；言語是一種基于集合論和一階謂詞邏輯的方式化言語；lZ言語支持軟件的方式化規(guī)范描畫，規(guī)范的推理和求精；言語支持軟件的方式化規(guī)范描畫，規(guī)范的推理和求精；l是迄今為止運(yùn)用最廣泛的方式言語之一；是

7、迄今為止運(yùn)用最廣泛的方式言語之一；lZ是在是在Jean Raymond Abrial等的開創(chuàng)性任務(wù)下，由英國(guó)等的開創(chuàng)性任務(wù)下，由英國(guó)牛津大學(xué)的程序設(shè)計(jì)研討小組牛津大學(xué)的程序設(shè)計(jì)研討小組PRG，Programming Research Group，于，于20世紀(jì)世紀(jì)80年代初開發(fā)；年代初開發(fā)；lPRG與與IBM的的Hursley實(shí)驗(yàn)室協(xié)作，將實(shí)驗(yàn)室協(xié)作，將Z言語用于言語用于IBM的客的客戶信息控制系統(tǒng)的開發(fā)，使得最終的產(chǎn)質(zhì)量量得到了全面戶信息控制系統(tǒng)的開發(fā)，使得最終的產(chǎn)質(zhì)量量得到了全面的的提高，所測(cè)出的錯(cuò)誤數(shù)量大大減少，并且整體開發(fā)費(fèi)的的提高，所測(cè)出的錯(cuò)誤數(shù)量大大減少，并且整體開發(fā)費(fèi)用降低了用降

8、低了9；l在在ISO指點(diǎn)下的國(guó)際規(guī)范化指點(diǎn)下的國(guó)際規(guī)范化Z任務(wù)于任務(wù)于2019年完成年完成6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介1第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l提供了一種稱為方式提供了一種稱為方式Schema的構(gòu)造，它是的構(gòu)造，它是Z的根本描畫單位，以此來描畫一個(gè)規(guī)范闡明的的根本描畫單位，以此來描畫一個(gè)規(guī)范闡明的形狀空間靜態(tài)性質(zhì)和操作動(dòng)態(tài)行為。形狀空間靜態(tài)性質(zhì)和操作動(dòng)態(tài)行為。l言語的方式和方式演算：言語的方式和方式演算：l形狀方式對(duì)目的軟件系統(tǒng)的構(gòu)造特征進(jìn)展籠統(tǒng)描形狀方式對(duì)目的

9、軟件系統(tǒng)的構(gòu)造特征進(jìn)展籠統(tǒng)描畫；畫；l操作方式對(duì)目的軟件系統(tǒng)的行為特征進(jìn)展籠統(tǒng)描操作方式對(duì)目的軟件系統(tǒng)的行為特征進(jìn)展籠統(tǒng)描畫；畫；l經(jīng)過方式演算，無論多么大型系統(tǒng)的規(guī)格闡明都經(jīng)過方式演算，無論多么大型系統(tǒng)的規(guī)格闡明都可以經(jīng)過一個(gè)個(gè)小的部分來構(gòu)成；可以經(jīng)過一個(gè)個(gè)小的部分來構(gòu)成；6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介2第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l方式闡明可以組合成新的方式，新的方式闡明可以組合成新的方式，新的方式承繼其成分方式的一切屬性和約束。軟方式承繼其成分方式的一切屬性和約束

10、。軟件系統(tǒng)的方式規(guī)格闡明可以按一定的層次件系統(tǒng)的方式規(guī)格闡明可以按一定的層次構(gòu)造給出。構(gòu)造給出。l規(guī)格闡明由一系列方式組成，每個(gè)方式定規(guī)格闡明由一系列方式組成，每個(gè)方式定義一個(gè)籠統(tǒng)對(duì)象或操作，并用謂詞斷定描畫義一個(gè)籠統(tǒng)對(duì)象或操作，并用謂詞斷定描畫給出新的對(duì)象或操作的語義約束。給出新的對(duì)象或操作的語義約束。l方式例方式例:6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介3第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l方式例方式例1:lStudent / 引入根本類型引入根本類型studentl Stude

11、ntSys /方式名方式名lEnrolled,tested: P Student / 聲明部分聲明部分, 學(xué)生的密集類型學(xué)生的密集類型l#enrolled size / 斷言部分，合斷言部分，合取關(guān)系取關(guān)系ltested enrolledl等價(jià)于：等價(jià)于：/程度方式程度方式lStudentSys=enrolled,tested: P Student | #enrolled size tested enrolled 6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介4第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)

12、續(xù))l方式例方式例2:lEnrollStudentl StudentSys / = Studentsys StudentSys的簡(jiǎn)寫的簡(jiǎn)寫 lname?: Student / 在輸入變量后加？在輸入變量后加？lname? enrolled / 在輸出變量后加！在輸出變量后加！lenrolled size / 帶有后綴帶有后綴的變量表示的變量表示操作后的變量操作后的變量lenrolled = enrolled name?ltested= tested 6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介5第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.

13、1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l缺陷缺陷:l 言語對(duì)大型系統(tǒng)的模塊化才干缺乏。言語對(duì)大型系統(tǒng)的模塊化才干缺乏。l 難以識(shí)別影響某一形狀方式的一切操作方式。難以識(shí)別影響某一形狀方式的一切操作方式。l 不能支持規(guī)格闡明的重用。不能支持規(guī)格闡明的重用。l 言語難以由計(jì)算機(jī)直接處置。言語難以由計(jì)算機(jī)直接處置。l短少商品化的工具支持等到諸多緣由短少商品化的工具支持等到諸多緣由6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介Z言語簡(jiǎn)介言語簡(jiǎn)介6第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l VDMVienna Develo

14、pment Method是在1969年為開發(fā)PL/1言語時(shí)，由IBM公司維也納實(shí)驗(yàn)室的研討小組提出的。初衷是為了描畫PL/1言語的語義。lVDM是一種功能構(gòu)造性規(guī)格闡明技術(shù)，它經(jīng)過一階謂詞邏輯和已建立的籠統(tǒng)數(shù)據(jù)類型來描畫每個(gè)運(yùn)算或函數(shù)的功能。l這種方法在90年代初在歐美許多研討機(jī)構(gòu)或大學(xué)得到了廣泛的運(yùn)用。如曼徹斯特大學(xué)將其作為CS的必修課。 l2019年ISO制定了VDM的國(guó)際規(guī)范化版本VDM-SL6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介VDM簡(jiǎn)介簡(jiǎn)介1第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))lVDM技術(shù)的根

15、本思想：技術(shù)的根本思想：l運(yùn)用籠統(tǒng)數(shù)據(jù)類型、數(shù)學(xué)概念和符號(hào)來規(guī)定運(yùn)運(yùn)用籠統(tǒng)數(shù)據(jù)類型、數(shù)學(xué)概念和符號(hào)來規(guī)定運(yùn)算或函數(shù)的功能；算或函數(shù)的功能；l可使軟件系統(tǒng)的功能描畫在籠統(tǒng)級(jí)上進(jìn)展，完可使軟件系統(tǒng)的功能描畫在籠統(tǒng)級(jí)上進(jìn)展，完全擺脫了實(shí)現(xiàn)細(xì)節(jié)，這樣為軟件實(shí)現(xiàn)者提供了全擺脫了實(shí)現(xiàn)細(xì)節(jié)，這樣為軟件實(shí)現(xiàn)者提供了很大的靈敏性；很大的靈敏性；l這種方式化規(guī)格闡明還為程序正確性證明提供這種方式化規(guī)格闡明還為程序正確性證明提供了根據(jù)。了根據(jù)。6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介VDM簡(jiǎn)介簡(jiǎn)介2第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序

16、(續(xù)續(xù))lVDM支持兩種籠統(tǒng)：數(shù)據(jù)籠統(tǒng)和操作籠統(tǒng)。支持兩種籠統(tǒng)：數(shù)據(jù)籠統(tǒng)和操作籠統(tǒng)。l一個(gè)一個(gè)VDM規(guī)范有以下不同的塊組成：規(guī)范有以下不同的塊組成：ltypesllvaluesllfunctionslloperationsllstate ofllend6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介VDM簡(jiǎn)介簡(jiǎn)介3第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l缺陷：缺陷：l 由于由于VDM對(duì)籠統(tǒng)數(shù)據(jù)類型預(yù)先定對(duì)籠統(tǒng)數(shù)據(jù)類型預(yù)先定義了運(yùn)算，而某些用戶定義的類型義了運(yùn)算，而某些用戶定義的類型在規(guī)格闡明描畫中無需這么多運(yùn)算，在

17、規(guī)格闡明描畫中無需這么多運(yùn)算，因此產(chǎn)生了運(yùn)算冗余。因此產(chǎn)生了運(yùn)算冗余。l VDM目前還未能建立一整套描畫目前還未能建立一整套描畫機(jī)制，將一個(gè)大型系統(tǒng)分解為許多機(jī)制，將一個(gè)大型系統(tǒng)分解為許多運(yùn)算而描畫出這些運(yùn)算之間的關(guān)系運(yùn)算而描畫出這些運(yùn)算之間的關(guān)系l VDM方式規(guī)格闡明過于方式化不方式規(guī)格闡明過于方式化不容易了解容易了解6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介VDM簡(jiǎn)介簡(jiǎn)介4第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))lB方法是方法是20世紀(jì)世紀(jì)80年代初中期由年代初中期由J.R.Abrial以及以及BP研研討中

18、心的討中心的MATRA和和GE Alsthom研討小組開發(fā)的。研討小組開發(fā)的。l言語是計(jì)算機(jī)輔助軟件工程中技術(shù)、方法和工具言語是計(jì)算機(jī)輔助軟件工程中技術(shù)、方法和工具集的簡(jiǎn)稱集的簡(jiǎn)稱;l言語是一種健全的面向?qū)嵺`軟件過程的基于數(shù)學(xué)實(shí)言語是一種健全的面向?qū)嵺`軟件過程的基于數(shù)學(xué)實(shí)際的技術(shù)際的技術(shù);l方法所用的符號(hào)和方法支持大部分的軟件過程：需方法所用的符號(hào)和方法支持大部分的軟件過程：需求分析、規(guī)格闡明、軟件設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)求分析、規(guī)格闡明、軟件設(shè)計(jì)、實(shí)現(xiàn)和維護(hù);l方法的指點(diǎn)性原那么：分層軟件的逐漸構(gòu)造伴隨著方法的指點(diǎn)性原那么：分層軟件的逐漸構(gòu)造伴隨著逐漸的驗(yàn)證和校驗(yàn)；逐漸的驗(yàn)證和校驗(yàn)；6. 方式化程序

19、規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介B言語簡(jiǎn)介言語簡(jiǎn)介1第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))l工具盒包括有大量的工具，一切的工具集成在一個(gè)基工具盒包括有大量的工具，一切的工具集成在一個(gè)基于窗口的軟件開發(fā)環(huán)境中，因此支持運(yùn)用方法開發(fā)軟于窗口的軟件開發(fā)環(huán)境中，因此支持運(yùn)用方法開發(fā)軟件的整個(gè)軟件過程；件的整個(gè)軟件過程；l工具支持軟件的逐漸構(gòu)造，其中的驗(yàn)證過程可用靜態(tài)工具支持軟件的逐漸構(gòu)造，其中的驗(yàn)證過程可用靜態(tài)分析，動(dòng)態(tài)分析采用模擬技術(shù)，正確性證明那么運(yùn)用集分析，動(dòng)態(tài)分析采用模擬技術(shù)，正確性證明那么運(yùn)用集成的定理證明器。成

20、的定理證明器。l方法用一種簡(jiǎn)單的偽程序文語來描畫需求模型、闡明方法用一種簡(jiǎn)單的偽程序文語來描畫需求模型、闡明接口，并進(jìn)展中間設(shè)計(jì)和實(shí)現(xiàn)；接口，并進(jìn)展中間設(shè)計(jì)和實(shí)現(xiàn)；lB言語就是言語就是AMN籠統(tǒng)機(jī)器符號(hào)，籠統(tǒng)機(jī)器符號(hào)，AMN支持規(guī)格闡明支持規(guī)格闡明的類型檢測(cè)、動(dòng)態(tài)驗(yàn)證、數(shù)學(xué)證明等來確保設(shè)計(jì)過程的的類型檢測(cè)、動(dòng)態(tài)驗(yàn)證、數(shù)學(xué)證明等來確保設(shè)計(jì)過程的正確。正確。6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介B言語簡(jiǎn)介言語簡(jiǎn)介2第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))lB方法的特點(diǎn)方法的特點(diǎn)l簡(jiǎn)單熟習(xí)的符號(hào)表示法：這種符號(hào)表

21、示法用來表達(dá)形狀轉(zhuǎn)簡(jiǎn)單熟習(xí)的符號(hào)表示法：這種符號(hào)表示法用來表達(dá)形狀轉(zhuǎn)換，從規(guī)格闡明到編碼，這種一致的方式減少了學(xué)習(xí)的難換，從規(guī)格闡明到編碼，這種一致的方式減少了學(xué)習(xí)的難度和轉(zhuǎn)換中的語法錯(cuò)誤。度和轉(zhuǎn)換中的語法錯(cuò)誤。l模塊化構(gòu)造：從規(guī)格闡明到實(shí)現(xiàn)的模塊化構(gòu)造允許將規(guī)格模塊化構(gòu)造：從規(guī)格闡明到實(shí)現(xiàn)的模塊化構(gòu)造允許將規(guī)格闡明和驗(yàn)證過程分解為多個(gè)子義務(wù)來進(jìn)展。闡明和驗(yàn)證過程分解為多個(gè)子義務(wù)來進(jìn)展。l大量適用的工具支持：現(xiàn)有大量的適用工具支持了大量適用的工具支持：現(xiàn)有大量的適用工具支持了B方法方法軟件開發(fā)周期的一切階段，包括動(dòng)畫和文檔生成。軟件開發(fā)周期的一切階段，包括動(dòng)畫和文檔生成。l勝利的工業(yè)運(yùn)用：勝利

22、的工業(yè)運(yùn)用：B言語和方法已在很多的工業(yè)領(lǐng)域得到言語和方法已在很多的工業(yè)領(lǐng)域得到勝利運(yùn)用，包括實(shí)時(shí)、仿真、信息處置和工程等。勝利運(yùn)用，包括實(shí)時(shí)、仿真、信息處置和工程等。6. 方式化程序規(guī)范描畫言語簡(jiǎn)介方式化程序規(guī)范描畫言語簡(jiǎn)介B言語簡(jiǎn)介言語簡(jiǎn)介3第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.1 程序規(guī)范與程序程序規(guī)范與程序(續(xù)續(xù))6. Z言語、言語、VDM、B方式化方法的比較方式化方法的比較屬性屬性ZVDMB基礎(chǔ)基礎(chǔ)謂詞演算謂詞演算, 集集合論合論, 模式模式偏函數(shù)偏函數(shù), 集集合論合論最弱前置條件最弱前置條件, 集合集合論論開發(fā)階段開發(fā)階段規(guī)范說明規(guī)范說明規(guī)范說明規(guī)范說明

23、, 設(shè)計(jì)設(shè)計(jì)規(guī)范說明規(guī)范說明, 設(shè)計(jì)設(shè)計(jì), 實(shí)現(xiàn)實(shí)現(xiàn)形式形式模式的符號(hào)模式的符號(hào)表示表示, 關(guān)系關(guān)系前前/后置條后置條件件, 函數(shù)函數(shù)嚴(yán)格的編程語言嚴(yán)格的編程語言工具支持工具支持在規(guī)格說明在規(guī)格說明級(jí)級(jí)在規(guī)格說在規(guī)格說明級(jí)明級(jí)B-Toolkit,AtchierB,所有開發(fā)階段所有開發(fā)階段培訓(xùn)支持培訓(xùn)支持圖書、課程圖書、課程圖書圖書, 課程課程實(shí)例研究、課程實(shí)例研究、課程第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述內(nèi)容內(nèi)容Where we are？l程序規(guī)范、規(guī)范的描畫程序規(guī)范、規(guī)范的描畫l斷言與規(guī)范及斷言與規(guī)范及P S Ql程序正確性的概念程序正確性的概念l程序正確性證明的

24、過程程序正確性證明的過程第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.2 斷言與規(guī)范斷言與規(guī)范1. 斷言斷言斷言就是關(guān)于事物性質(zhì)的陳說。這個(gè)陳說可真可假。斷言就是關(guān)于事物性質(zhì)的陳說。這個(gè)陳說可真可假。如如“三是個(gè)質(zhì)數(shù)三是個(gè)質(zhì)數(shù)用斷言作為程序的注解或作為正確性命題的一部分用斷言作為程序的注解或作為正確性命題的一部分時(shí)，常用大括號(hào)括起來。時(shí)，常用大括號(hào)括起來。例例1：寫一個(gè)計(jì)算商和余數(shù)的程序：寫一個(gè)計(jì)算商和余數(shù)的程序程序規(guī)范：程序規(guī)范：“設(shè)被除數(shù)設(shè)被除數(shù)x1是個(gè)非負(fù)整數(shù)，除數(shù)是個(gè)非負(fù)整數(shù)，除數(shù)x2是是個(gè)正整數(shù)，計(jì)算個(gè)正整數(shù)，計(jì)算x1除以除以x2的商的商y1和余數(shù)和余數(shù)y2又描

25、畫為：又描畫為：“初始條件：初始條件：x1=0 AND x20, 計(jì)算滿計(jì)算滿足足x1=x2*y1+y2 and 0=y2=0 and x20lY2:=x1; y1:=0;l0=y2 and 0=x2 dol begin 0=y2 and 0 x2y2 and x1=x2*y1+y2l y2 :=y2-x2; y1:=y1+1;l 0=y2 and 0 x2 and x1=x2*y1+y2l end;lx1=x2*y1+y2 and 0=y2x2第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.2 斷言與規(guī)范斷言與規(guī)范(續(xù)續(xù))l問題：?jiǎn)栴}：l如何構(gòu)造斷言使他們能準(zhǔn)確地反映不同

26、位如何構(gòu)造斷言使他們能準(zhǔn)確地反映不同位置上程序的性質(zhì)？置上程序的性質(zhì)？l有了斷言，如何證明他們的正確性？有了斷言，如何證明他們的正確性？l能否有準(zhǔn)那么，可以從規(guī)范能否有準(zhǔn)那么，可以從規(guī)范P，Q構(gòu)構(gòu)造出程序造出程序S，使，使P S Q為真。為真。第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.2 斷言與規(guī)范斷言與規(guī)范(續(xù)續(xù))2. 程序斷言的進(jìn)一步闡明程序斷言的進(jìn)一步闡明闡明：在給出規(guī)范描畫闡明：在給出規(guī)范描畫P，Q時(shí)，必需指明哪時(shí)，必需指明哪些量是可變的，哪些是不可變的。假設(shè)是可變的，些量是可變的，哪些是不可變的。假設(shè)是可變的，必要時(shí)對(duì)前者還需指明其變化方式。必要時(shí)對(duì)前者還需

27、指明其變化方式。輸入?yún)?shù)：在程序執(zhí)行前從外部獲得值，但在程序輸入?yún)?shù)：在程序執(zhí)行前從外部獲得值，但在程序執(zhí)行中，其值一直堅(jiān)持不變的變量。普通用以執(zhí)行中，其值一直堅(jiān)持不變的變量。普通用以x開頭的標(biāo)識(shí)符表示。開頭的標(biāo)識(shí)符表示。輸出變量：其值隨程序的執(zhí)行而不斷變化的變量。輸出變量：其值隨程序的執(zhí)行而不斷變化的變量。普通以普通以y開頭的變量，或不以開頭的變量，或不以x和和u開頭的變量標(biāo)開頭的變量標(biāo)識(shí)。識(shí)。輔助變量：為了描畫程序變量取值變化方式而因入輔助變量：為了描畫程序變量取值變化方式而因入的變量。這些變量不得在程序中出現(xiàn)，用以的變量。這些變量不得在程序中出現(xiàn)，用以u(píng)開開頭的變量表示。頭的變量表示。第

28、第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.2 斷言與規(guī)范斷言與規(guī)范(續(xù)續(xù))l例例1. 編寫一個(gè)程序編寫一個(gè)程序Swapy1，y2，功能，功能是把是把y1，y2兩變量的值互換。兩變量的值互換。l其規(guī)范其規(guī)范:l (y1=u1 y2=u2，y1=u2y2=u1)第第3章章 程序規(guī)范及其正確性證明概述程序規(guī)范及其正確性證明概述3.2 斷言與規(guī)范斷言與規(guī)范(續(xù)續(xù))例例2：對(duì)數(shù)組：對(duì)數(shù)組bm：n進(jìn)展排序的程序。功能是把數(shù)組進(jìn)展排序的程序。功能是把數(shù)組bm：n各元素的值從小到大陳列起來，使得最后的數(shù)組滿各元素的值從小到大陳列起來，使得最后的數(shù)組滿足足bi bi+1，i=m，,n-1。規(guī)范：規(guī)范：P：m n bm:n=um:n Q：m n perm(bm:n,um:n) (i: m i 0 s=b0+bil 令令S為：為： i := i+1 ; s :=s+bil 簡(jiǎn)單證明如下：簡(jiǎn)單證明如下：l P：i0s=b0+bil P1： i+10s=b0+bi+1-1l i := i+1 ;l Q1: i0s=