Home

SC_Lab2和Chapter3

软件构造笔记
字数统计: 2.5k阅读时长: 11 min
2019/03/19 Share

阅读材料来自于MIT的Software Construction课程 Reading 11: Abstraction Functions & Rep Invariants.

要点如下:

·invariant

·representation exposure

·abstraction functions

·representation invariants

The rep invariant will make it easier to catch bugs caused by a corrupted data structure.

Invariants

 一个好的抽象数据型(ADT)的关键：能否preserves its own invariants

Immutability

 看下面的例子


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Tweet {
 
public String author;
public String text;
public Date timestamp;

/**
 * Make a Tweet.
 * @param author    Twitter user who wrote the tweet
 * @param text      text of the tweet
 * @param timestamp date/time when the tweet was sent
 */
public Tweet(String author, String text, Date timestamp) {
    this.author = author;
    this.text = text;
    this.timestamp = timestamp;
  }
}

  如何确保Tweet类是不可变的呢？即一旦建立，相关属性不改变。

 威胁之一是客户端能够直接修改这个域。Representation exposure ：code outside the class can modify the representation directly.

 
不过辛亏有private和final，官方给出如下解释

The private and public keywords indicate which fields and methods are accessible only within the class and which can be accessed from outside the class. The final keyword also helps by guaranteeing that the fields of this immutable type won’t be reassigned after the object is constructed.


 一种策略就是防御式拷贝(defensive copying)。
例如：

1
2
3
public Date getTimestamp() {
    return new Date(timestamp.getTime());
}

 值得注意的是，另一种copy a mutable object is clone(),但是有些问题，暂且不谈。


1
2
3
4
5
6
7
8
9
10
/** @return a list of 24 inspiring tweets, one per hour today */
public static List<Tweet> tweetEveryHourToday () {
   List<Tweet> list = new ArrayList<Tweet>(); 
   Date date = new Date();
   for (int i = 0; i < 24; i++) {
       date.setHours(i);
       list.add(new Tweet("rbmllr", "keep it up! you can do it", date));
   } 
return list;
}



 所以不变性又被破坏了，采用一下策略：

1
2
3
4
5
public Tweet(String author, String text, Date timestamp) {
    this.author = author;
    this.text = text;
    this.timestamp = new Date(timestamp.getTime());
}

Immutable wrappers around mutable data types

 此时，轮到我们的Collections.unmodifiableList()亮相。但是一个downside就是得到的所谓的immutability只是在runtime，but not at compile time. Java也不会在你试着sort()这个unmodifiable list的时候警告你，反而抛给你一个冷冰冰的异常。

 注意阅读练习里面的array相关的problem

Rep invariant and abstraction function

 关键不仅仅在于选取两个集合Space，而且在于选取什么的元素为合法，并且怎样将它们对应成抽象的值。

not only choosing the two spaces… but also deciding which rep values are legal, and how to interpret them as abstract values.

比如根据此图，我们得到下面的映射：
以下要点：

 ·每一个抽象类都对应有原象

 ·一些抽象类映射前的原象不止一个

 ·而在集合R中并非所有元素都有映射的象

 和实验相关一点，AF就是某个成员变量代表的抽象概念，RI就是对这个成员变量的限制。然而我这个傻子恍然大悟，AF就是”Abstraction functioin”,RI即为” Representation invariant”啊！！！

抽象函数AF：R和A之间映射关系的函数，即如何去解 释R中的每一个值为A中的每一个值。

表示不变性RI：某个具体的“表示”是否是“合法的”

 可将RI看作：所有表示值的一个子集，包含了所有合法的表示值

 也可将RI看作：一个条件，描述了什么是“合法”的表示


 从rep values到其所表示的抽象值之间的映射表示如下

AF: R -> A

同时也可以用R → Boolean的映射表示是否rep value和一个abstract values之间存在着对应关系。如下图所示

 对于表达值（rep value）而言， RI(r) 为真当且仅当r被AF映射。RI(“a”) = true, RI(“ac”) = true, 并且 RI(“acb”) = true, 但 RI(“aa”) = false and RI(“abbc”) = false.

 尽管有着不相同类型的rep value space 和相同的rep invariant，我们可以构建出不同的映射。例如“acgg”表示字符串之间的范围，[a-c]和[g-g]，所以代表的元素是集合set{a,b,c,g}.

 对于client of an abstract data type而言，visible and documented的应该为：abstract value space, creators, observes. 而不可见：abstraction function, rep 和 rep invariant.

Rep invariant is a function from rep values to boolean.

Checkint the rep invariant

check的特点：

 It’s good for an implementer to call checkRep() just before returning from a public method of an ADT class.

 checkRep() asserts the rep invariant.

No null values in the rep

Beneficnet mutation

Documenting the AF,RI, and safety from rep exposure

注意，在描述rep invariant and abstraction function的时候，必须注意：

 不能仅仅用“域内全员合法”来简简单单概括RI，重要的是explain是如何区分“合法”和“非法”的。

 同样的，对于AF而言，仅仅声明“represents a set of charaters”也是不够的。而应该define precisely how the concrete field values are interpreted
而根据同学的解释

Rep exposure：

 java中数据类型分为mutable和immutable的，对前者进行的操作可能会改变其内部数据；而对后者的操作不改变其内部值，而是构造新的对象。因此，对于mutable的数据，如果没有良好的保护，意味着client对其的调用可以直接修改内部数据。

What an ADT specification may talk about



ADT invariants replace preconditions

An invariant is a property of a program that is always true, for every possible runtime state of the program.

 为什么需要不变量？ 因为爱情。保持程序的“正确性”，容易发现错误。

补充

SPEC

 SPEC is the abbreviation of the word-specification，规约。client能干什么，不能干什么，输入输出满足的条件将在spec中罗列得清清楚楚。
大致要点

  1. Function / method in programming language
  2. Specification: Programming for communication
  3. Designing specifications

    Spec Structure

  • 前置条件 precondition(对客户端的约束，在使用方法时必须满足的条件）

    The precondition is an obligation on the client (i.e., the caller of the method). It’s a condition over the state in which the method is invoked.

  • 后置条件 postcondition(后置条件：对开发者的约束，方法结束时必须满足的条件)

    The postcondition is an obligation on the implementer of the method.

  • – Precondition , indicated by the keyword requires

    – Postcondition , indicated by the keyword effects

    相应于@return和@param呢？来看课件讲义：

     Parameters are described by @param clauses and results are described by @return and @throws clauses.

     Put the preconditions into @param where possible, and postconditions into @return and @throws.

    规约强弱？


     规约的强度S2>=S1 A specification S2 is stronger than or equal to a specification S1 if

  • S2’s precondition is weaker than or equal to S1’s 前置条件更弱
  • S2’s postcondition is stronger than or equal to S1’s, for the states that satisfy S1’s precondition. 后置条件更强

     简而言之，spec变强就是更放松的前置条件 + 更严格的后置条件

漫漫实验路

-ea

 多谢橙子的提醒，在poet测试里面需要用到assert断言，而必须要在Eclipse中开启assert选项。详情

Windows -> Preferences ->Java ->Installed JREs ->待使用的JDK ->Edit ->Default VM Arguments文本框中输入:-ea

异常测试

 本人在实验里面经常用到对抛出异常的检测，下面以lab2中Board异常检测为例。Board规定了，应该为”chess”或者”go”类型，而在这里传入”tt”显然会抛出异常的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public Board(String type) {
	if(type == "chess")
		N = 8;
	else if(type == "go")
		N = 19;
	else 
		throw new RuntimeException("Not a game that we'll provide for you");
    ...
   }

/*
 * Test for exception
 * */
@Test(expected = RuntimeException.class)
public void typeExceptionTest() {
	Board board = new Board("tt");
}

3.4

区分override 和 overload

 overload用同一个方法名字但是输入不同的参数列表，比如本人在实验中构造的函数

1
2
3
4
5
6
7
8
9
public Vertex(L source,L target, int weight) {
	label = source;
    toVertex = new HashMap<L, Integer>();
	toVertex.put(target, weight);
}
public Vertex(L name) {
	this.label = name;
	this.toVertex = new HashMap<L, Integer>();
}

Evan的这篇文章很好：Java 何时需要重写hashCode()和equals()
 此外override在run time检查，而overload是在compile阶段就进行检查

3.5 Equality in ADT and OOP

Equality

 等价关系(Equivalence Relation)：自反、对称、传递

Equality in immutable types

  1. a equals b if and only if f(a) = f(b)，即AF映射同样的结果。
  2. 站在外部角度，对两个对象调用任何相同操作，都能得到相同结果，认为等价性成立。
    举例：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public class Duration {
        private final int mins;
        private final int secs;
        // Rep invariant:
        //    mins >= 0, secs >= 0
        // Abstraction function:
        //    AF(min, secs) = the span of time of mins minutes and secs seconds

        /** Make a duration lasting for m minutes and s seconds. */
        public Duration(int m, int s) {
            mins = m; secs = s;
        }
        /** @return length of this duration in seconds */
        public long getLength() {
            return mins*60 + secs;
        }
    }

其中下列那些等价呢？

1
2
3
4
Duration d1 = new Duration (1, 2);
Duration d2 = new Duration (1, 3);
Duration d3 = new Duration (0, 62);
Duration d4 = new Duration (1, 2);

区分equals和“==”

 等价性：引用等价性和对象等价性

 对基本数据类型，使用==判定相等

 对对象类型，使用equals.

  • == 和内存空间相关。

再看这个例子

1
2
3
4
5
6
7
8

public class Duration {
    ...   
    // Problematic definition of equals()
    public boolean equals(Duration that) {
        return this.getLength() == that.getLength();        
    }
}

结果呢

1
2
3
4
5
Duration d1 = new Duration (1, 2);
Duration d2 = new Duration (1, 2);
Object o2 = d2;
d1.equals(d2) → true
d1.equals(o2) → false

 答案为true和false。d2的类型是Duration，而o2的类型是Object，在类Duration里面的equals无法对这个o2进行等价判断。而且o2和d1指向并非同一内存空间，因此会返回false。

 上述给的例子是overload而非override。

1
2
3
4
5
6
7
8
9
10
public class Duration extends Object {
    // explicit method that we declared:
    public boolean equals(Duration that) {
        return this.getLength() == that.getLength();
    }
    // implicit method inherited from Object:
    public boolean equals(Object that) {
        return this == that;
    }
}

 equals三件套：（1）是否为空 （2）类型是否相同 （3）根据AF设计相等判断。但是有一弊处：在没有AF情况下判断每个域的等价性，这是不合理的。

Hashcode

 hashCode -> memory address!!!

 规定一个原则：等价的对象必须有相同的hashCode。（不相等的对象也可以映射为同样的hashCode但性能会变差）

A general rule:
Always override hashCode() when you override equals()

Equals of Mutable Types

 mutable：

  • 观察等价性（在不改变状态情况下，两个对象是否一致）
  • 行为等价性 (调用对象的任何方法都展示出一致的结果)

 对可变类型来说，往往倾向于实现严格的观察等价性(observational equality)。但在某些时候观察等价性可能导致bug甚至可能破坏RI。

immutable类型重写equals和hashCode()，但是mutable类型就不必重写

CATALOG
  1. 1. Invariants
    1. 1.1. Immutability
    2. 1.2. Immutable wrappers around mutable data types
  2. 2. Rep invariant and abstraction function
    1. 2.1. Checkint the rep invariant
    2. 2.2. No null values in the rep
    3. 2.3. Beneficnet mutation
  3. 3. Documenting the AF,RI, and safety from rep exposure
    1. 3.0.1. What an ADT specification may talk about
  • 4. ADT invariants replace preconditions
  • 5. 补充
    1. 5.1. SPEC
      1. 5.1.1. Spec Structure
      2. 5.1.2. 规约强弱？
  • 6. 漫漫实验路
    1. 6.1. -ea
    2. 6.2. 异常测试
  • 7. 3.4
    1. 7.1. 区分override 和 overload
  • 8. 3.5 Equality in ADT and OOP
    1. 8.1. Equality
    2. 8.2. Equality in immutable types
    3. 8.3. 区分equals和“==”
      1. 8.3.1. Hashcode
    4. 8.4. Equals of Mutable Types
    • Total : 18
    2020
    2019
    Invalid date
    Invalid date
    小感 笔记 软件构造笔记 英语 竹林深处 随笔
    笔记 软件构造笔记 英语 竹林深处 感想