北航OO(2020)第三單元博客作業 [TOC] JML語言總結 理論基礎 JML是用於對Java程式進行規格化設計的一種表示語言,它使用JavaDoc註釋的方式來表示規格。JML以Java語法為基礎併進行了一定的擴充。JML的語法分為幾個層次,下麵對JML Level 0的核心特性進行簡要的總結。 ...
北航OO(2020)第三單元博客作業
目錄
JML語言總結
理論基礎
JML是用於對Java程式進行規格化設計的一種表示語言,它使用JavaDoc註釋的方式來表示規格。JML以Java語法為基礎併進行了一定的擴充。JML的語法分為幾個層次,下麵對JML Level 0的核心特性進行簡要的總結。
規格變數的聲明
規格變數分為靜態規格變數和實例規格變數兩種。以整型數組為例,它們分別可以聲明為//@public static model non_null int []elements
和//@public instance model non_null int []elements
。
常用表達式
表達式 | 含義 |
---|---|
\result | 非void類型的方法的返回值 |
\old(expr ) |
一個表達式expr 在相應方法執行前的取值(遵從引用規則) |
\not_assigned(x, y, ...) | 括弧中的變數是否在方法執行過程中未被賦值 |
\not_modified(x, y, ...) | 限制括弧中的變數在方法執行期間的取值未發生變化 |
(\forall T x; R(x); P(x)) | 全稱量詞,表示滿足R(x)的x都滿足P(x) |
(\exists T x; R(x); P(x)) | 存在量詞,表示存在滿足R(x)的x滿足P(x) |
(\sum T x; R(x); expr ) |
對於滿足R(x)的x,求expr 的和 |
(\max T x; R(x); expr ) |
對於滿足R(x)的x,求expr 的最大值 |
(\min T x; R(x); expr ) |
對於滿足R(x)的x,求expr 的最小值 |
<==> | 等價操作符 |
==> | 蘊含操作符 |
\nothing | 空集 |
方法規格
方法規格分為正常行為規格和異常行為規格兩種,分別對應normal_behavior
和exceptional_behavior
。多個規格之間使用also
連接。每種規格又可分為前置條件、副作用範圍限定和後置條件,分別對應requires
、assignable
和ensures
。多個子句之間為合取關係。
對於純粹訪問性的方法,即不會對對象的狀態進行任何改變,也不需要提供輸入參數,這樣的方法無需描述前置條件,也不會有任何副作用,且執行一定會正常結束。對於這類方法,可以使用簡單的(輕量級)方式來描述其規格,即使用pure
關鍵詞。在方法規格中,前置條件可以引用pure
方法返回的結果。
對於異常行為規格,我們通常會使用signals或signals_only子句來拋出異常。signals子句的結構為signals (***Exception e) expr;
意思是當expr
為true 時,方法會拋出括弧中給出的相應異常e;signals_only子句的結構為signals_only ***Exception;
,意思是一旦進入此子句,就會拋出相應的異常。
類型規格
類型規格指針對Java程式中定義的數據類型所設計的限制規則,一般而言,就是指針對類或介面所設計的約束規則。課程中的重點是不變式invariant和狀態變化約束constraint。不變式invariant是要求在所有可見狀態下都必須滿足的特性,而狀態變化約束constraint對對象狀態的變化進行約束。
應用工具鏈情況
JML的工具鏈較不完善,且大都已很長時間沒有維護。常用的JML工具主要有OpenJML(對JML進行語法檢查、配合Solver進行簡單的靜態驗證、以及運行時驗證)、JMLUnitNG(自動化單元測試生成工具)和JMLUnit(類似前者)等。OpenJML有Eclipse插件版,使用體驗較好。但是沒有可用的IDEA插件是一個遺憾。
在http://www.eecs.ucf.edu/~leavens/JML//download.shtml這個頁面上,有更多JML相關工具的介紹。
OpenJML驗證情況
由於後兩次作業無法通過OpenJML的語法檢查,下麵以第一次作業為例,演示OpenJML的驗證。
Parsing and Type-checking
本功能主要檢查JML規格的語法。
在IDEA的External Tools中,運行如下命令:java -jar openjml.jar -check "$FilePath$" -cp "$Classpath$" -sourcepath "$Sourcepath$" -encoding utf-8
,即可進行JML的靜態語法檢查。-check參數指定檢查類型為Parsing and Type-checking,-cp和-sourcepath命令用於指定Classpath和源文件目錄,-encoding參數用於指定文件編碼。
第一次作業的JML規格成功通過了該檢查,返回值為0。
Extended Static Checking
本功能主要利用Solver對按照JML編寫的程式進行簡單的靜態檢查。
在IDEA的External Tools中,運行如下命令:java -jar openjml.jar -prover z3_4_7 -exec ".\Solvers-windows\z3-4.7.1.exe" -esc "$FilePath$" -cp "$Classpath$" -sourcepath "$Sourcepath$" -encoding utf-8
,即可進行JML的靜態語法檢查。-prover參數用於指定Solver類型,-exec參數用於指定Solver可執行程式,-esc參數指定檢查類型為Extended Static Checking。
在對MyPerson檢查的過程中,觸發了36個警告,其中主要是The prover cannot establish an assertion,但這些警告似乎並不是由於程式的錯誤,而是Solver無法對程式進行充分的解析導致的;在對MyNetwork檢查的過程中,觸發了100個警告,其中主要仍是The prover cannot establish an assertion,且提示靜態檢查不支持對\not_assigned表達式進行檢查。由此可見,該功能對一些較為複雜的程式的支持還十分欠缺。
下麵展示部分MyPerson類的檢查結果:
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:82: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:67: 註: ) in method compareTo
return name.compareTo(p2.getName());
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:67: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:82: 註:
@ ensures \result == name.compareTo(p2.getName());
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:82: 警告: The prover cannot establish an assertion (ExceptionalPostcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:66: 註: ) in method compareTo
return name.compareTo(p2.getName());
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:66: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:82: 註:
@ public normal_behavior
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:53: 警告: The prover cannot establish an assertion (ExceptionalPostcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:29: 註: ) in method equals
return id == person.getId();
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:29: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:53: 註:
@ public normal_behavior
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:53: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:32: 註: ) in method equals
return id == person.getId();
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:32: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:53: 註:
@ ensures \result == (((Person) obj).getId() == id);
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:77: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:62: 註: ) in method getAcquaintanceSum
return acquaintance.size();
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:62: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:77: 註:
//@ ensures \result == acquaintance.length;
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:41: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:25: 註: ) in method getAge
return age;
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:25: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:41: 註:
//@ ensures \result == age;
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:36: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:22: 註: ) in method getCharacter
return character;
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:22: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:36: 註:
//@ ensures \result.equals(character);
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:26: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:16: 註: ) in method getId
return id;
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:16: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:26: 註:
//@ ensures \result == id;
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:31: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:19: 註: ) in method getName
return name;
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:19: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:31: 註:
//@ ensures \result.equals(name);
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:67: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:43: 註: ) in method isLinked
return id == person.getId() || acquaintance.containsKey(person);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:43: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:67: 註:
@ ensures \result == (\exists int i; 0 <= i && i < acquaintance.length;
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:67: 警告: The prover cannot establish an assertion (ExceptionalPostcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:41: 註: ) in method isLinked
return id == person.getId() || acquaintance.containsKey(person);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:41: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:67: 註:
/@ public normal_behavior
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 警告: The prover cannot establish an assertion (ExceptionalPostcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:55: 註: ) in method queryValue
return acquaintance.getOrDefault(person, 0);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:55: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 註:
@ public normal_behavior
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 警告: The prover cannot establish an assertion (ExceptionalPostcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:48: 註: ) in method queryValue
return acquaintance.getOrDefault(person, 0);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:48: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 註:
/@ public normal_behavior
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:58: 註: ) in method queryValue
return acquaintance.getOrDefault(person, 0);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:58: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 註:
@ ensures \result == 0;
^
.\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 警告: The prover cannot establish an assertion (Postcondition: .\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:52: 註: ) in method queryValue
return acquaintance.getOrDefault(person, 0);
^
.\Unit3Homework1\src\com\oocourse\spec1\main\Person.java:52: 警告: Associated declaration: .\Unit3Homework1\src\com\oocourse\implements1\MyPerson.java:72: 註:
@ ensures (\exists int i; 0 <= i && i < acquaintance.length;
^
Runtime Assertion Checking
本功能主要對按照JML編寫的程式進行簡單的運行時檢查。
在IDEA的External Tools中,運行如下命令:java -jar openjml.jar -rac "$FilePath$" -cp "$Classpath$" -sourcepath "$Sourcepath$" -encoding utf-8
,即可進行JML程式的運行時檢查。-rac參數指定檢查類型為Runtime Assertion Checking。
OpenJML在對MyPerson檢查的過程中觸發了Internal JML bug,並拋出了NullPointerException;在對MyNetwork檢查的過程中報錯:An internal JML error occurred。由此可見,該功能還不甚完善。
JMLUnitNG測試(針對MyGroup類)
首先將OpenJML中的jmlruntime.jar複製到環境變數CLASSPATH所在的目錄下,然後,在項目目錄下,運行如下命令:java -jar jmlunitng-1_4.jar -d .\test .\src
即可生成測試類。
對於MyGroup類的測試,可以直接運行MyGroup_JML_Test類中的main方法,得到結果如下:
[TestNG] Running:
Command line suiteFailed: racEnabled()
Passed: constructor MyGroup(-2147483648)
Passed: constructor MyGroup(0)
Passed: constructor MyGroup(2147483647)
Failed: <com.oocourse.implements3.MyGroup@8000001f>.addPerson(null)
Failed: <com.oocourse.implements3.MyGroup@1f>.addPerson(null)
Failed: <com.oocourse.implements3.MyGroup@8000001e>.addPerson(null)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.addRelation(-2147483648)
Passed: <com.oocourse.implements3.MyGroup@1f>.addRelation(-2147483648)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.addRelation(-2147483648)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.addRelation(0)
Passed: <com.oocourse.implements3.MyGroup@1f>.addRelation(0)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.addRelation(0)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.addRelation(2147483647)
Passed: <com.oocourse.implements3.MyGroup@1f>.addRelation(2147483647)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.addRelation(2147483647)
Failed: <com.oocourse.implements3.MyGroup@8000001f>.delPerson(null)
Failed: <com.oocourse.implements3.MyGroup@1f>.delPerson(null)
Failed: <com.oocourse.implements3.MyGroup@8000001e>.delPerson(null)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.equals(null)
Passed: <com.oocourse.implements3.MyGroup@1f>.equals(null)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.equals(null)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.equals(java.lang.Object@61baa894)
Passed: <com.oocourse.implements3.MyGroup@1f>.equals(java.lang.Object@b065c63)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.equals(java.lang.Object@768debd)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getAgeMean()
Passed: <com.oocourse.implements3.MyGroup@1f>.getAgeMean()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getAgeMean()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getAgeVar()
Passed: <com.oocourse.implements3.MyGroup@1f>.getAgeVar()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getAgeVar()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getConflictSum()
Passed: <com.oocourse.implements3.MyGroup@1f>.getConflictSum()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getConflictSum()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getId()
Passed: <com.oocourse.implements3.MyGroup@1f>.getId()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getId()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getPeopleSum()
Passed: <com.oocourse.implements3.MyGroup@1f>.getPeopleSum()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getPeopleSum()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getRelationSum()
Passed: <com.oocourse.implements3.MyGroup@1f>.getRelationSum()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getRelationSum()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.getValueSum()
Passed: <com.oocourse.implements3.MyGroup@1f>.getValueSum()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.getValueSum()
Passed: <com.oocourse.implements3.MyGroup@8000001f>.hasPerson(null)
Passed: <com.oocourse.implements3.MyGroup@1f>.hasPerson(null)
Passed: <com.oocourse.implements3.MyGroup@8000001e>.hasPerson(null)
Passed: <com.oocourse.implements3.MyGroup@8000001f>.hashCode()
Passed: <com.oocourse.implements3.MyGroup@1f>.hashCode()
Passed: <com.oocourse.implements3.MyGroup@8000001e>.hashCode()===============================================
Command line suite
Total tests run: 52, Failures: 7, Skips: 0===============================================
Process finished with exit code 0
可以看出,JMLUnitNG主要針對邊界數據和空引用進行了測試。在上面的測試中,主要由於方法傳入null而失敗。而由於本單元作業中,方法不會傳入null,因此在代碼中未進行處理。
作業架構分析
在本單元的作業中,我主要依據JML進行構建,同時採取一些實現上的優化,如應用容器和演算法等。在本單元,我沒有進行過多的抽象,僅僅是編寫了Pair和SegmentTree工具類,併在MyNetwork類中編寫了Dijkstra和PointBiconnectedComponent內部類進行演算法的封裝。我認為若能將Graph類和Node類抽象出來,並使MyNetwork類和MyPerson類對其分別進行繼承或組合,或許可以收到更好的效果。
下麵是本單元第三次作業的UML類圖(略去了官方包):
作業Bug情況
本單元作業未在公測和互測中出現任何bug。
在第二次作業中,我在本地測試時發現Group中的getAgeVar方法在使用方差公式簡化計算時,若將括弧中的項提取出來,可能會導致誤差,如下:
public int getAgeVar() {
if (people.isEmpty()) {
return 0;
}
return (ageSquaredSum - 2 * getAgeMean() * ageSum) / people.size()
+ getAgeMean() * getAgeMean();
}
需要改成如下寫法:
public int getAgeVar() {
if (people.isEmpty()) {
return 0;
}
return (ageSquaredSum - 2 * getAgeMean() * ageSum
+ getAgeMean() * getAgeMean() * people.size()) / people.size();
}
經驗證,原因是Java整數除法在取整時,採取向0取整的方式,而前面寫法的括弧中可能會出現負數,導致舍入錯誤,而與正確結果差1。
心得體會:規格撰寫與理解
在本單元,我接觸了一種全新的程式設計模式:規格化設計。規格化設計能夠使得設計與實現分離,同時,形式化的規格也便於進行嚴格的形式化驗證。
在撰寫規格時,我們會更多地從需求而非實現的角度去思考程式的設計。此外,規格的前置條件會促使我們考慮各種邊界條件與極端數據,一定程度上緩解了由於前置條件考慮不周而導致程式出現Bug的現象。
在理解規格時,重點是對規格行為的理解。通常情況下,規格描述並不適合直接作為代碼實現。因此,我們需要對規格所描述的行為進行理解,並由此選擇合適的實現。我們甚至還可以在規格的基礎上進一步抽象,設計出更加清晰合理的程式架構。
雖然如此嚴格而繁瑣的形式化規格表述在日常軟體的開發領域並不常見,但我相信,由於其可以進行嚴格的形式化驗證,形式化的規格在高可靠性領域一定大有用武之地。