OO Unit3 总结

OO课Unit3人际关系网JML应用技术回顾

BUAA.1823.邓新宇

2020/5/23

方法规格

JML中，同一个方法在不同的条件下会产生不同的行为，这种行为分为正常行为和异常行为，分别用单成一行的public normal_behavior和public exceptional_behavior作为该行为的描述的声明放在行为描述的最开始，不同的行为之间用also连接。一个方法的描述中可以有多个不同的行为类，而不同的行为类的前置条件应当互斥，并且子类的行为描述不应当与父类有冲突。

在每一个行为类中，有该行为类的前置条件、后置条件、副作用，分别用行前的requires、ensures、assignable/modifiable表示，分别表示传入参数的要求、方法完成后应当满足的条件、方法可能对其它部分产生的影响。每一个行为类中可以有多个前置条件、后置条件、副作用。

在行为的形式化描述的时候，通常需要进行全部、存在、求和的描述，分别用\forall、\exists、\sum语句来完成，它们的格式分别为：

\forall 类型 临时变量; 前提的条件（通常为取值范围）; 约束条件

这表示每一个该符合前提条件的变量都需要满足指定的约束条件，即

\[\forall i, i满足前提条件 \rarr i满足约束条件
\]

\exists 类型 临时变量; 前提的条件（通常为取值范围）; 约束条件

这表示存在一个该符合前提条件的变量可以需要满足指定的约束条件，即

\[\exists i, i满足前提条件 \rarr i满足约束条件
\]

\exists 类型 临时变量; 前提的条件（通常为取值范围）; 加和数值

这表示每一个该符合前提条件的变量，按照加和数值规则进行求和，即

count = 0
for value in 前提条件:
    count += 加和数值
return count

在异常行为描述的过程中，通常需要描述异常的抛出，这需要通过signals语句来完成，其格式为：

signals (异常名称 e) 抛出条件

这表示在抛出条件成立时，抛出异常名称指定的异常

类型规格

类规格主要有不变式和状态变化约束，分别用行前的invariant、constraint表示，它们都可以加上static修饰符来表示针对静态属性的约束。

不变式是该类始终满足的条件，而状态变化约束更像是每一个方法的后置条件的提取，后者相当于在每个方法的后置条件增加该语句。

一堆莫名其妙的bug，后面再补。

由于作业主要是按照给定的Interface中的JML约束进行完成即可，所以整体架构并没有太多的设计过程。

Person功能添加

Person的接口定义中，字段acquaintance是没有访问器的，而NetWork又需要大量的与此相关的查询工作和修改工作。为了保持Person的封装性，我没有选择为Person添加访问器，因为针对acquaintance其实只有几种工作，一是为某个Person添加一个新的acquaintance，其它的都是各种查询，其实没必要直接让外部自由修改acquaintance，只需要Person提供这些查询即可。所以在设计时，为Person添加了isCircle、queryStrongLinked、queryMinPath三个查询方法，来实际执行NetWork的同名查询，为Person添加了link方法来添加一个新的acquaintance。

查询方案

查询有两种简单方案：

1. 在每次查询的时候都重新计算结果；
2. 在每次可能导致查询结果发生变化的时候重新计算结果；

前者会降低查询的效率，而后者会降低每次更改的效率。前者在状态改变少、查询次数多的时候效率低下，后者在状态改变多、查询次数少的时候效率低下。

为了使二者互补，我才用了如下较复杂的方案：

        在状态发生改变的时候进行标记，每次查询的时候检查标记，如果标记有效则重新计算、保存并返回查询结果，然后复位标记，否则直接返回保存的结果

这样在面对各种情况下都有比较好的效率。

本次作业的bug主要分两类：

1. 在上文查询方案优化中，对于“状态发生改变”的情况考虑不全，比如Group只在添加新的成员时才置位标记，但实际上对Group成员进行新的acquaintance添加时，Group的部分查询结果也会发生改变，所以后来为每个Person记录了其所在的Group，每次添加acquaintance后通知那些Group进行相应的标记置位；
2. 图的查询算法实现出现bug，主要原因就是菜，对于复杂算法了解不够，自己瞎想的算法一方面有漏洞一方面效率低下。

按照JML进行实现，先把握住会导致不同行为的前置条件，先利用这些前置条件把各个行为分开，然后再在各类行为之中进行实现。

虽然这次算法的复杂度并没有要求很低，但是要求算法的正确性要求很高，在现有理论十分丰富的当下，实在没必要自己去瞎发明轮子，这是一个教训，应该好好学习别人已经分享的解决方案，复用已经被证明过的轮子。