ADT中AF和RI的概念

本文是对MIT讲义Reading 13: Abstraction Functions & Rep Invariants进行的部分翻译,涉及到Rep exposure的一个典型练习题、AF和RI的概念和checkRep()的设计范例


由于本人水平有限,本文难免会有不当之处,欢迎读者批评指正

Rep exposure的一个练习题

观察下面这个数据类型回答问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
      /** Represents an immutable right triangle. */
class RightTriangle {
/*A*/ private double[] sides;

// sides[0] and sides[1] are the two legs,
// and sides[2] is the hypotenuse, so declare it to avoid having a
// magic number in the code:
/*B*/ public static final int HYPOTENUSE = 2;

/** Make a right triangle.
* @param legA, legB the two legs of the triangle
* @param hypotenuse the hypotenuse of the triangle.
*C* * Requires hypotenuse^2 = legA^2 + legB^2
* (within the error tolerance of double arithmetic)
*/
public RightTriangle(double legA, double legB, double hypotenuse) {
/*D*/ this.sides = new double[] { legA, legB, hypotenuse };
}

/** Get all the sides of the triangle.
* @return three-element array with the triangle's side lengths
*/
public double[] getAllSides() {
/*E*/ return sides;
}

/** @return length of the triangle's hypotenuse */
public double getHypotenuse() {
return sides[HYPOTENUSE];
}

/** @param factor to multiply the sides by
* @return a triangle made from this triangle by
* multiplying all side lengths by factor.
*/
public RightTriangle scale(double factor) {
return new RightTriangle(sides[0]*factor, sides[1]*factor, sides[2]*factor);
}

/** @return a regular triangle made from this triangle.
* A regular right triangle is one in which
* both legs have the same length.
*/
public RightTriangle regularize() {
double bigLeg = Math.max(side[0], side[1]);
return new RightTriangle (bigLeg, bigLeg, side[2]);
}

}

问题:下面哪个陈述是正确的?

  • 标记为/*A*/的那一行有rep exposure的问题,因为数组是可变的

    这一行并没有rep exposure的问题,sides域是private的,所以这个类型的客户端不能访问它或依赖它,数组的可变性本身也不是一个问题,不可变数据类型内部可以有可变的对象作为它的表示,只这些可变对象没有暴露给客户端就可以。

  • 标记为/*B*/的那一行有representation independence的问题,因为它泄露了边数组是如何组织的

    这一行确实是有representation independence的问题。HYPOTENUSE是一个public static域,他向客户端泄露了斜边的index,并使这种情况作为了合约的一部分,结果,这种类型就不能改变斜边的表示形式了,这违反了representation independence.

  • 标记为/*C*/的那一行存在问题,因为creator操作不应该有前置条件

    这一行没有问题,因为creator操作向其他任何操作一样可以有前置条件,而且这个地方的前置条件是合理的、必要的

  • 标记为/*D*/的那一行存在问题,因为它将legA, legB, hypotenuse直接放入了rep中,而没有做防御式复制

    这一行没有问题,因为double是不可变的,所以没有必要做防御式复制。实际上,在java的底层实现上,它们已经被复制到数组中了,原始变量始终是通过复制来引用的

  • 标记为/*E*/的那一行存在问题,因为它威胁到了这个类的不可变性

    这一行存在不可变性的问题,因为它直接返回了triangle的rep中的可变数组的引用,这是一个rep暴露的问题,客户端可以无意或故意改变它,也就改变了triangle.

总结:

  • 不可变类型中可以存在可变对象作为域,只要不将它们暴露给客户端就可以
  • representation independence的思想就是不能让客户端依赖于代码内部的具体数据结构或数据域,这样当代码内部的数据结构或数据域做出改变时对客户端没有影响
  • 原始类型在java的底层实现中总是通过复制的方式来完成引用的,所以它们是不可变的

Rep invariant 和 abstraction function

接下来我们以一个更深的角度来看ADT,这个理论不仅优雅,而且非常有趣,他也实际应用于抽象类型的设计和实现中。如果理解好这个理论,你就能设计出更好的抽象类型,也更难掉入一些微妙的陷阱中。

考虑value的两个空间有助于理解抽象类型。

  • rep value是代码内部储存值的实际方式
  • abstract value是客户端看到的方式

看一个例子:
用字符串来表示字符集合,rep space R 包含着字符串,abstract space A 是字符的数学集合。
下面这张图中的箭头表示从rep value到abstract value的映射
charset
需要注意的几点:

  • 每一个abstract value都被rep value映射到了
  • 有些abstract value被多于一个的rep value映射到了
  • 并不是所有的rep value都有对应的abstract value
  • 由前三点可知,从rep value 到 abstract value 是满射但不一定是双射

定义AF和RI

  1. abstraction function是将rep值映射到它们表示的abstract值的函数

    AF: R->A

  2. rep invariant将rep值映射到booleans

    RI: R->boolean
    对于一个rep值r,RI(r)为true当且仅当r被AF映射到了,例如下面这张图中,RI(“”) = true, RI(“abc”) = true, and RI(“bac”) = true, but RI(“abbc”) = false.
    norepeats

rep invariant和abstraction function都应该注视在代码中,就写在它声明的rep的下面:

1
2
3
4
5
6
7
8
public class CharSet {
private String s;
// Rep invariant:
// s contains no repeated characters
// Abstraction function:
// AF(s) = {s[i] | 0 <= i < s.length()}
...
}

需要注意的是:

  1. 单独abstract value space是不能决定AF和RI的,因为对于相同的abstract type,可能有几种不同的表示。例如,可以用字符串来表示字符集,也可以用位向量来表示,每个位一个字符,但是要清楚,我们要用两个不同的AF来表示这两个不同的rep value space.
  2. rep value space 和 abstract value space也不能决定AF和RI。 因为我们可以对rep value space有不同的解释,比如说我们对上面提到过的例子做一些改变,现在我们允许有相同的字符,但是规定字符序列必须是有序的,因为我们想要实现二分查找,那么这张图就变成了这样:
    sorted

这里的要点是:
实现一个抽象类型不仅是选择两个空间——为规约服务的abstract value空间和为实现服务的rep value空间,还应该定义哪些rep value是合法的、从rep value到abstract value的映射应该是怎样的。

CheckRep()

检查rep invariant
Example: rational numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class RatNum {

private final int numerator;
private final int denominator;

// Rep invariant:
// denominator > 0
// numerator/denominator is in reduced form

// Abstraction function:
// AF(numerator, denominator) = numerator/denominator

/** Make a new RatNum == n.
* @param n value */
public RatNum(int n) {
numerator = n;
denominator = 1;
checkRep();
}

/** Make a new RatNum == (n / d).
* @param n numerator
* @param d denominator
* @throws ArithmeticException if d == 0 */
public RatNum(int n, int d) throws ArithmeticException {
// reduce ratio to lowest terms
int g = gcd(n, d);
n = n / g;
d = d / g;

// make denominator positive
if (d < 0) {
numerator = -n;
denominator = -d;
} else {
numerator = n;
denominator = d;
}
checkRep();
}
}

ratnum
checkRep()如下:

1
2
3
4
5
6
7
// Check that the rep invariant is true
// *** Warning: this does nothing unless you turn on assertion checking
// by passing -enableassertions to Java
private void checkRep() {
assert denominator > 0;
assert gcd(Math.abs(numerator), denominator) == 1;
}

这里的要点是:

  • 应该在每个方法的尾部调用checkRep()
  • checkRep()方法应该是private的,即不应该让客户端可见

Beneficent mutation

the abstract value should never change. But the implementation is free to mutate a rep value as long as it continues to map to the same abstract value, so that the change is invisible to the client. This kind of change is called beneficent mutation.

小结

  • invariant是一种在ADT对象整个生命周期都为真的属性
  • 一个好的ADT必须保证它的invariants. creators和producers建立invariants. observers和mutators保证invariants不被破坏
  • rep invariant指定了表示的合法值,应该在运行时由checkRep()检查
  • abstraction function 建立了从具体表示到它表示的抽象值的映射
  • Representation exposure既威胁到representation又威胁到invariant preservation

讲义原文地址

Reading 13: Abstraction Functions & Rep Invariants