2020北航OO第三单元JML

2023-12-05 08:56:58

那么JML(Java Modeling Language)到底是什么呢？“在面向对象编程中，一个重要原则就是尽可能地推迟对于“过程”的思考。”在每次编写程序后，想好了整体架构，搭建好了类和接口，之后面对的就是每一个方法。这个时候，我们思考的是这个方法能给我带来什么预期结果，之后再考虑如何实现。JML在代码中增加了一些符号，这些符号只表述一个方法干什么，并不关系它的实现过程。使用JML，我们就可以描述对于某一个方法的预期功能，却不管实现过程，JML可以把过程性的思考延迟到方法设计中，这点完全符合了“面向对象”。

JML知识梳理

JML(Java Modeling Language)是用于对Java程序进行规格化设计的一种表示语言。一般而言，JML有两种主要的用法：

  • 开展规格化设计。这样交给代码实现人员的将不是可能带有内在模糊性的自然语言描述，而是逻辑严格的规格。

  • 已有的代码实现，书写其对应的规格，从而提高代码的可维护性。这在遗留代码的维护方面具有特别重要的意义。

注释结构

JML以javadoc注释的方式来表示规格，每行都以@起头。有两种注释方式，行注释和块注释。其中行注释的表示方式为//@annotation，块注释的方式为/* @ annotation @*/。按照Javadoc习惯，JML注释一般放在被注释成分的紧邻上部。需要注意的是，规格中的每个子句都必须以分号结尾，否则会导致JML工具无法解析。

package org.jmlspecs.samples.jmlrefman;               // line 1
                                                      // line 2
public abstract class IntHeap {                       // line 3
                                                      // line 4
    //@ public model non_null int [] elements;        // line 5
                                                      // line 6
    /*@ public normal_behavior                        // line 7
      @   requires elements.length >= 1;              // line 8
      @   assignable \nothing;                        // line 9
      @   ensures \result                             // line 10
      @        == (\max int j;                        // line 11
      @               0 <= j && j < elements.length;  // line 12
      @               elements[j]);                   // line 13
      @*/                                             // line 14
    public abstract /*@ pure @*/ int largest();       // line 15
                                                      // line 16
    //@ ensures \result == elements.length;           // line 17
    public abstract /*@ pure @*/ int size();          // line 18
};                                                    // line 19

抽象类IntHeap提供了两个抽象方法，largest()和size()。

第15行和第18行：/*@ pure @ */表示这两个方法都是纯粹查询方法，即方法的执行不会有任何副作用。

第5行：intHeap所管理的数据规格，其中的model表示后面的int[] elements仅仅是规格层次的描述，并不是这个类的声明组成部分，此外也不意味该类的实现人员必须提供这样的属性定义，non_null的意义是elements这个数组对象引用不能为null。

第17行：给出了size方法的后置条件(postcondition)，即任何时候该方法的执行都会返回IntHeap中存储的元素个数(elements.length)，其中的\result是JML的关键词，表示方法的执行返回结果。

第7行到第14行：largest的规格，包括三个部分：

  • requires子句定义该方法的前置条件(precondition)，elements.length>=1，即IntHeap中管理着至少一个元素；
  • 副作用范围限定，assignable列出这个方法能够修改的类成员属性，\nothing是个关键词，表示这个方法不对任何成员属性进行修改，所以是一个pure方法。
  • ensures子句定义了后置条件，即largest方法的返回结果等于elements中存储的所有整数中的最大的那个(\max也是一个关键词)。

JML表达式

原子表达式

\result表达式：表示一个非void类型的方法执行所获得的结果，即方法执行后的返回值。

\old(expr)表达式：表示一个表达式expr在相应方法执行前的取值，该表达式涉及到评估expr中的对象是否发生变化。 如果是引用（如hashmap)，对象没改变，但进行了插入或删除操作。v和odd(v)也有相同的取值。

\not_assigned(x,y,...)表达式：用来表示括号中的变量是否在方法执行过程中被赋值。如果没有被赋值，返回为true，否则返回false。实际上，该表达式主要用于后置条件的约束表示上，即限制一个方法的实现不能对列表中的变量进行赋值。

\not_modified(x,y,...)表达式：与上面的\not_assigned表达式类似，该表达式限制括号中的变量在方法执行期间的取值未发生变化。

\nonnullelements(container)表达式：表示container对象中存储的对象不会有null。

\type(type)表达式：返回类型type对应的类型(Class)，如type(boolean)为Boolean.TYPE。TYPE是JML采用的缩略表示，等同于Java中的java.lang.Class。

\typeof(expr)表达式：该表达式返回expr对应的准确类型。如\typeof(false)为Boolean.TYPE。

量化表达式

\forall表达式：全称量词修饰的表达式，表示对于给定范围内的元素，每个元素都满足相应的约束。(\forall int i,j; 0 <= i && i < j && j < 10; a[i] < a[j])，意思是针对任意0<=i<j<10，a[i]<a[j]。这个表达式如果为真(true)，则表明数组a实际是升序排列的数组。

\exists表达式：存在量词修饰的表达式，表示对于给定范围内的元素，存在某个元素满足相应的约束。

\sum表达式：返回给定范围内的表达式的和。(\sum int i; 0 <= i && i < 5; i)，这个表达式的意思计算[0,5)范围内的整数i的和，即0+1+2+3+4==10。注意中间的0 <= i && i < 5是对i范围的限制，求和表达式为最后面的那个i。

\product表达式：返回给定范围内的表达式的连乘结果。(\product int i; 0 < i && i < 5; i)，这个表达式的意思是针对(0,5)范围的整数的连乘结果，即1* 2* 3 * 4。

\max表达式：返回给定范围内的表达式的最大值。

\min表达式：返回给定范围内的表达式的最小值。

\num_of表达式：返回指定变量中满足相应条件的取值个数。

集合表达式

集合构造表达式：可以在JML规格中构造一个局部的集合（容器），集合构造表达式的一般形式为：new ST {T x|R(x)&&P(x)}，其中的R(x)对应集合中x的范围，通常是来自于某个既有集合中的元素，如s.has(x)，P(x)对应x取值的约束。

操作符

JML表达式中可以正常使用Java语言所定义的操作符，包括算术操作符、逻辑预算操作符等。此外，JML专门又定义了如下四类操作符。

  • 子类型关系操作符：E1<:E2，如果类型E1是类型E2的子类型(sub type)，则该表达式的结果为真，否则为假。如果E1和E2是相同的类型，该表达式的结果也为真.
  • 等价关系操作符：b_expr1<==>b_expr2或者b_expr1<=!=>b_expr2，其中b_expr1和b_expr2都是布尔表达式
  • 推理操作符：b_expr1==>b_expr2或者b_expr2<==b_expr1。对于表达式b_expr1==>b_expr2而言，当b_expr1==false，或者b_expr1==true且b_expr2==true时，整个表达式的值为true。
  • 变量引用操作符：\nothing指示一个空集；\everything指示一个全集，即包括当前作用域下能够访问到的所有变量。变量引用操作符经常在assignable句子中使用，如assignable \nothing表示当前作用域下每个变量都不可以在方法执行过程中被赋值。

方法规格

方法规格的核心内容包括三个方面，前置条件、后置条件和副作用约定

前置条件(pre-condition)

前置条件是对方法输入参数的限制，如果不满足前置条件，方法执行结果不可预测，或者说不保证方法执行结果的正确性。

前置条件通过requires子句来表示：requires P;。其中requires是JML关键词，表达的意思是“要求调用者确保P为真”。注意，方法规格中可以有多个requires子句，是并列关系，即调用者必须同时满足所有的并列子句要求。

后置条件(post-condition)

后置条件是对方法执行结果的限制，如果执行结果满足后置条件，则表示方法执行正确，否则执行错误。

后置条件通过ensures子句来表示：ensures P;。其中ensures是JML关键词，表达的意思是“方法实现者确保方法执行返回结果一定满足谓词P的要求，即确保P为真”。

副作用范围限定(side-effects)

副作用指方法在执行过程中对输入对象或this对象进行了修改（对其成员变量进行了赋值，或者调用其修改方法）。方法在执行过程中会修改对象的属性数据或者类的静态成员数据，从而给后续方法的执行带来影响。

从语法上来看，副作用约束子句共有两种形态，一种不指明具体的变量，而是用JML关键词来概括；另一种则是指明具体的变量列表。

正常行为规格和异常行为规格

为了有效的区分方法的正常功能行为和异常行为，JML提供了这两类行为的区分机制，可以明确按照这两类行为来分别描述方法的规格，如下所示：

/*@ public normal_behavior
@ requires z <= 99;
@ assignable \nothing;
@ ensures \result > z;
@ also
@ public exceptional_behavior
@ requires z < 0;
@ assignable \nothing;
@ signals (IllegalArgumentException e) true;
@*/
public abstract int cantBeSatisfied(int z) throws IllegalArgumentException；

signals子句

signals子句的结构为signals (Exception e) b_expr;，意思是当b_expr为true时，方法会抛出括号中给出的相应异常e。

还有一个简化的signals子句，即signals_only子句，后面跟着一个异常类型。signals子句强调在对象状态满足某个条件时会抛出符合相应类型的异常；而signals_only则不强调对象状态条件，强调满足前置条件时抛出相应的异常。有时候，为了更加明确的区分异常，会针对输入参数的取值范围抛出不同的异常，从而提醒调用者进行不同的处理。这时可以使用多个exceptional_behavior。

类型规格

不变式invariant

不变式（invariant）是要求在所有可见状态下都必须满足的特性，语法上定义invariant P，其中invariant为关键词，P为谓词。

对应类成员变量有静态和非静态之分，JML区分两类不变式，静态不变式(static invariant)和实例不变式(instance invariant)。其中静态不变式只针对类中的静态成员变量取值进行约束，而实例不变式则可以针对静态成员变量和非静态成员变量的取值进行约束。可以在不变式定义中明确使用instance invariant或static invariant来表示不变式的类别。

状态变化约束constraint

对象的状态在变化时往往也许满足一些约束，这种约束本质上也是一种不变式。JML为了简化使用规则，规定invariant只针对可见状态(即当下可见状态)的取值进行约束，而是用constraint来对前序可见状态和当前可见状态的关系进行约束。如下面的例子：

public class ServiceCounter{
    private /*@spec_public@*/ long counter;
    //@ invariant counter >= 0;
    //@ constraint counter == \old(counter)+1;
}

类型层次设计（继承）

  • 子类继承了父类的规格
  • 子类可以重写父类的方法规格
  • 子类可以扩充父类的方法规格和数据规格
    • 子类的数据抽象：父类数据抽象+新增的数据抽象
    • 子类的数据规格：父类的数据规格+扩展的数据规格+新增的数据规格
    • 子类的方法规格：父类方法规格+重写的方法规格+新增的方法规格
  • 以上描述需满足LSP原则
    • 子类重写父类方法时不能与父类的方法规格相冲突
    • 子类新增和扩展的数据规格不能与父类数据规格相冲突

JML工具链

  • OpenJML可以静态检查JML语法的正确性，同时也可以作为编译时的依赖包，生成可以运行时检查程序是否符合JML规格的class文件。OpenJML将检查实现和规范是否一致。
  • JMLUnitNG可以通过编写单元测试类和方法，来实现对类和方法实现正确性的快速检查和测试。
  • SMT Solver用来证明程序逻辑等价的，也就是可以用来从形式上证明两个函数的效果是等价的。

JMLUnit

使用JMLUnit对MyGroup生成测试用例：

java -jar jmlunitng.jar MyGroup.java
javac -cp jmlunitng.jar *.java
java -cp jmlunitng.jar MyGroup_JML_Test

结果：

[TestNG] Running:
  Command line suite

Failed: racEnabled()
Passed: constructor MyGroup(-2147483648)
Passed: constructor MyGroup(0)
Passed: constructor MyGroup(2147483647)
Passed: <<MyGroup@6842775d>>.addRelation()
Passed: <<MyGroup@574caa3f>>.addRelation()
Passed: <<MyGroup@1761e840>>.addRelation()
Passed: <<MyGroup@1517365b>>.addPerson(null)
Passed: <<MyGroup@4fccd51b>>.addPerson(null)
Passed: <<MyGroup@44e81672>>.addPerson(null)
Passed: <<MyGroup@60215eee>>.addPerson(java.lang.Object@4ca8195f)
Passed: <<MyGroup@65e579dc>>.addPerson(java.lang.Object@61baa894)
Passed: <<MyGroup@768debd>>.addPerson(java.lang.Object@490d6c15)
Passed: <<MyGroup@7d4793a8>>.delPerson(null)
Passed: <<MyGroup@449b2d27>>.delPerson(null)
Passed: <<MyGroup@27082746>>.delPerson(null)
Passed: <<MyGroup@66133adc>>.delPerson(java.lang.Object@7bfcd12c)
Passed: <<MyGroup@42f30e0a>>.delPerson(java.lang.Object@24273305)
Passed: <<MyGroup@5b1d2887>>.delPerson(java.lang.Object@46f5f779)
Passed: <<MyGroup@1c2c22f3>>.equals(null)
Passed: <<MyGroup@18e8568>>.equals(null)
Passed: <<MyGroup@33e5ccce>>.equals(null)
Passed: <<MyGroup@5a42bbf4>>.equals(java.lang.Object@270421f5)
Passed: <<MyGroup@52d455b8>>.equals(java.lang.Object@4f4a7090)
Passed: <<MyGroup@18ef96>>.equals(java.lang.Object@6956de9)
Passed: <<MyGroup@6aceb1a5>>.getAgeMean()
Passed: <<MyGroup@2d6d8735>>.getAgeMean()
Passed: <<MyGroup@ba4d54>>.getAgeMean()
Passed: <<MyGroup@12bc6874>>.getAgeVar()
Passed: <<MyGroup@de0a01f>>.getAgeVar()
Passed: <<MyGroup@4c75cab9>>.getAgeVar()
Passed: <<MyGroup@1ef7fe8e>>.getConflictSum()
Passed: <<MyGroup@6f79caec>>.getConflictSum()
Passed: <<MyGroup@67117f44>>.getConflictSum()
Passed: <<MyGroup@5d3411d>>.getId()
Passed: <<MyGroup@2471cca7>>.getId()
Passed: <<MyGroup@5fe5c6f>>.getId()
Passed: <<MyGroup@6979e8cb>>.getRelationSum()
Passed: <<MyGroup@763d9750>>.getRelationSum()
Passed: <<MyGroup@5c0369c4>>.getRelationSum()
Passed: <<MyGroup@2be94b0f>>.getValueSum()
Passed: <<MyGroup@d70c109>>.getValueSum()
Passed: <<MyGroup@17ed40e0>>.getValueSum()
Passed: <<MyGroup@50675690>>.hasPerson(null)
Passed: <<MyGroup@31b7dea0>>.hasPerson(null)
Passed: <<MyGroup@3ac42916>>.hasPerson(null)
Passed: <<MyGroup@47d384ee>>.hasPerson(java.lang.Object@2d6a9952)
Passed: <<MyGroup@22a71081>>.hasPerson(java.lang.Object@3930015a)
Passed: <<MyGroup@629f0666>>.hasPerson(java.lang.Object@1bc6a36e)
Passed: <<MyGroup@1ff8b8f>>.size()
Passed: <<MyGroup@387c703b>>.size()
Passed: <<MyGroup@224aed64>>.size()

===============================================
Command line suite
Total tests run: 52, Failures: 1, Skips: 0
===============================================

但是观察后发现，只是对边界值（null，INT_MAX, INT_MIN, 0）进行了代入，实际的测试意义好像不大？

作业设计

第一次作业

  • 容器选择：为使得访问方便，多使用HashMap作为容器，例如，在MyPerson中，使用HashMap<Person, Integer> acquaintance保存熟人与value
  • isCircle的实现：采用bfs判断两点是否连通。

第二次作业

  • MyGroup中的方法实现：如果各种查询方法直接按照伪代码描述，复杂度较高，故在MyGroup中设置成员变量relationSum，valueSum，conflictSum，ageSum。

        private int relationSum;
    private int valueSum;
    private BigInteger conflictSum;
    private int ageSum;

  • 在addPerson、addRelation时对这些变量进行改变。

        public void addPerson(Person person) {
        int relationNum = 0;
        int valueNum = 0;
        for (Person groupMember : people) {
            if (person.isLinked(groupMember)) {
                relationNum += 2;
                valueNum += person.queryValue(groupMember) * 2;
            }
        }
        people.add(person);
        relationSum += relationNum + 1;
        valueSum += valueNum;
        conflictSum = conflictSum.xor(person.getCharacter());
        ageSum += person.getAge();
    }

        public void addRelation(int value) {
        relationSum += 2;
        valueSum += value * 2;
    }

第三次作业

  • delPerson需要进行变量relationSum，valueSum，conflictSum，ageSum的维护。

  • 最短路径算法：采用堆优化迪杰斯特拉算法。java提供了容器PriorityQueue，并且PriorityQueue采取堆实现，只需要重写Edge的compareTo方法。

    public class Edge implements Comparable<Edge> {
    private Person from;
    private Person to;
    private int value;

	/* ……………………………… */
    
    @Override
    public int compareTo(Edge o) {
        return value - o.getValue();
    }
}

    PriorityQueue<Edge> cands = new PriorityQueue<>();

  • 点双连通分量的判断：

    • 如果id1与id2之间直接连接，采用dfs判断是否能寻找到一条路径；
    • 如果id1与id2之间不直接连接，采用dfs寻找id1到id2之间的一条路径，对于路径上的每一个中间点，如果将其mask后判断id1与id2之间依然连通，则id1与id2之间满足Stronglinked.

并查集

由于第三次作业中涉及连通分支数，现在看来，采取并查集实现isCirlcle与queryBlockSum应该是更好的做法。收藏一篇超赞的并查集博客，写得无敌有意思。

https://blog.csdn.net/qq_41593380/article/details/81146850

Tarjan

https://www.cnblogs.com/nullzx/p/7968110.html

bug分析

第一次作业

第一次作业比较简单，但我没有进行全面的测试，侥幸认为通过中测应该没有太大问题，但是结果无疑是piapia打脸……我因为一处变量名书写错误导致isCircle方法出现错误，甚至没有进强测。

第二次作业

尽管和同学进行了对拍，但是还是出现了边界的错误，边界条件的检查还是得靠自己鸭。

对规格理解的错误，没有检查addToGroup时Group的人数是否小于1111，强测中WA了4个测试点，同组中有同学出现了相同的错误。同组也有同学方法复杂度过高出现CTLE。

第三次作业

一开始对于点双连通的判断，我mask了第一条路径上的所有中间点，后来发现这种方法的错误进行改正。但是我的实现还是复杂度过高，强测与互测出现了CTLE。同Room的同学有delPerson没有更新相关变量的问题，也有和我一样的qsl实现不佳导致的CTLE。

心得体会

我对这一单元还是觉得比较遗憾的，期待第四单元能够做得更好~

相比于前两个单元从设计架构到编码上的难度，这一单元的架构设计似乎看起来难度并不大，我第一次做作业的时候甚至感觉，伪代码都给我了，这好愉悦啊。感谢第一单元作业的成绩让我意识到了我思想的错误。┭┮﹏┭┮ 首先规格化描述写的不是“方法流程”，另外规格给出的数据结构也并不能保证高效实现。

这一单元对于理解规格，思考并选择合适的数据结构来高效实现规格等方面的要求是比较高的，另一方面，为了保证自己正确地实现了规格，这一单元几乎宣告着手动测试党的冬天，而且对于一个粗心大意、粗枝大叶的同学而言，保证规格的正确实现真的真的不是一件容易的事情，最可怕的不是你理解了规格写出了bug，而是明明没有理解规格却以为自己理解了规格，还不按照规格编写测试！！

这一单元还让我意识到了我的基础课数据结构和离散数学怕是学个了寂寞，可以重学了……

如果说有什么建议的话，建议在第一单元或者第二单元就引入Junit教学，简直太好用了。

上一篇：CF922A Cloning Toys--题解报告


下一篇：HDU 1716排列2