當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

麻省理工18年春软件构造课程阅读11“抽象函数与表示不变量”

發布時間：2023/12/10 编程问答 19 豆豆

生活随笔收集整理的這篇文章主要介紹了麻省理工18年春软件构造课程阅读11“抽象函数与表示不变量” 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

本文內容來自MIT_6.031_sp18: Software Construction課程的Readings部分，采用CC BY-SA 4.0協議。

由于我們學校（哈工大）大二軟件構造課程的大部分素材取自此，也是推薦的閱讀材料之一，于是打算做一些翻譯工作，自己學習的同時也能幫到一些懶得看英文的朋友。另外，該課程的閱讀資料中有的練習題沒有標準答案，所給出的“正確答案”為譯者所寫，有錯誤的地方還請指出。

（更新：從第10章開始只翻譯正確答案）

譯者：李秋豪

審校：

V1.0 Sun Apr 1 22:23:37 CST 2018

本次課程的目標

今天我們會介紹以下幾個思想：

不變量（invariants）
表示暴露（representation exposure）
抽象函數（abstraction functions）
表示不變量（representation invariants）

在這篇閱讀中，我們會學習用一種正規的數學思想（抽象函數和表示不變量）去理解抽象數據類型ADT的實現。這些思想在軟件設計的實踐中非常重要。其中，抽象函數會讓我們清晰的定義對兩個ADT判斷相等的操作（我們會在后面的課程中深入介紹），而表示不變量會讓我們更易發現破壞數據結構導致的bug。

不變量

回想我們之前討論過的關于ADT的內容，什么設計會產生好的ADT？其中最重要的一點就是它會保護/保留自己的不變量。 不變量是一種屬性，它在程序運行的時候總是一種狀態，而不變性就是其中的一種：一旦一個不變類型的對象被創建，它總是代表一個不變的值。當一個ADT能夠確保它內部的不變量恒定不變（不受使用者/外部影響），我們就說這個ADT保護/保留自己的不變量.

當一個ADT保護/保留自己的不變量時，對代碼的分析會變得更簡單。例如，你能夠依賴字符串不變性的特點，在分析的時候跳過那些關于字符串的代碼；或者當你嘗試基于字符串建立其他的不變量的時候，也會變得更簡單。與此相對，對于可變的對象，你將不得不對每一處使用它的代碼處進行審查。

不變性

在這篇閱讀的后面，我們會看到許多關于不變量的例子，現在我們先看一看不變性：

/*** This immutable data type represents a tweet from Twitter.*/ 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對象是不可變的（一旦被創建，author, message, 和 date都不能被改變）？

第一個威脅就是使用者可以直接訪問Tweet內部的數據，例如：

Tweet t = new Tweet("justinbieber", "Thanks to all those beliebers out there inspiring me every day", new Date()); t.author = "rbmllr";

這就是一個表示暴露（Rep exposure）的例子，就是說類外部的代碼可以直接修改類內部存儲的數據。上面的表示暴露不僅影響到了不變量，也影響到了表示獨立性（譯者注：“抽象數據類型”），如果我們改變類內部數據的表示方法，使用者也會受到影響。

幸運地是，Java給我們提供了處理這樣的表示暴露的方法：

public class Tweet {private final String author;private final String text;private final Date timestamp;public Tweet(String author, String text, Date timestamp) {this.author = author;this.text = text;this.timestamp = timestamp;}/** @return Twitter user who wrote the tweet */public String getAuthor() {return author;}/** @return text of the tweet */public String getText() {return text;}/** @return date/time when the tweet was sent */public Date getTimestamp() {return timestamp;}}

其中， private 表示這個區域只能由同類進行訪問；而final確保了該變量的索引不會被更改，對于不可變的類型來說，就是確保了變量的值不可變。

但是這并沒有解決全部問題，表示還是會暴露！思考下面這個代碼：

/** @return a tweet that retweets t, one hour later*/ public static Tweet retweetLater(Tweet t) {Date d = t.getTimestamp();d.setHours(d.getHours()+1);return new Tweet("rbmllr", t.getText(), d); }

retweetLater 希望接受一個Tweet對象然后修改Date后返回一個新的Tweet對象。

問題出在哪里呢？其中的 getTimestamp 調用返回一個一樣的Date對象，它會被 t.t.timestamp 和 d 同時索引。所以當我們調用 d.setHours()后，t也會受到影響，如下圖所示：

這樣，Tweet的不變性就被破壞了。這里的問題就在于Tweet將自己內部對于可變對象的索引“泄露”了出來，因此整個對象都變成可變的了，使用者在使用時也容易造成隱秘的bug。

我們可以通過防御性復制來彌補這個問題：在返回的時候復制一個新的對象而不會返回原對象的索引。

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

可變類型通常都有一個專門用來復制的構造者，你可以通過它產生一個一模一樣的復制對象。在上面的例子中，Date的復制構造者就接受了一個timestamp值，然后產生了一個新的對象。另一個復制可變對象的方法是使用clone() ，但是它沒有被很多類支持（譯者注：標準庫里面只有5%支持），在Java中，使用clone()可能會帶來一些麻煩。你可以在 Josh Bloch, Effective Java, item 11, 或者 Copy Constructor vs. Cloning獲得更多有關這方面的信息。

現在我們已經通過防御性復制解決了 getTimestamp返回值的問題，但是我們還沒有完成任務！思考這個使用者的代碼：

/** @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; }

這個代碼嘗試創建24個Tweet對象，每一個對象代表一個小時，如下圖所示：

但是，Tweet的不變性再次被打破了，因為每一個Tweet創建時對Date對象的索引都是一樣的。所以我們應該對創建者也進行防御性編程：

public Tweet(String author, String text, Date timestamp) {this.author = author;this.text = text;this.timestamp = new Date(timestamp.getTime()); }

通常來說，你要特別注意ADT操作中的參數和返回值。如果它們之中有可變類型的對象，確保你的代碼沒有直接使用索引或者直接返回索引。

你可能會提出異議。這樣不會很浪費嗎？畢竟你要復制創建這么多新的對象。為什么不直接在規格說明中解決這個問題：

/*** 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. Caller must never * mutate this Date object again!*/ public Tweet(String author, String text, Date timestamp) {

這種方法一般只在迫不得已的時候使用——例如，這個可變對象的數據量非常大，如果進行防御性復制的話會花費很多資源（當然，這取決于你對程序的判斷）。如果不是極端情況，確保ADT會保留/保護自己的不變量總比通過規格說明來限定使用者要好。

而更好的解決方案是使用不可變類型。例如上面的例子中，如果我們使用的是 java.time.ZonedDateTime而非 java.util.Date, 那么我們只需要添加 private和final即可，不用再擔心表示保留。

可變類型的不可變包裝

Java的collections類提供了一種有趣的“折中”：不可變包裝。

Collections.unmodifiableList() 會接收一個（可變）List然后將其包裝為一個不可變對象——它的 set(), add(), remove(),等操作都會拋出異常。所以你可以將一個List包裝為不可變對象（記得將以前對于List的索引丟掉），然后將它傳入其他地方使用。

這種方法的缺點就是你只能在運行時獲得不可變性，而不是編譯時。Java不會在編譯的時候對你對“不可變”列表的修改提出警告。但是這總比什么都不做好，所以使用不可變的列表、映射、和集合也是減少bug的好方法。

閱讀小練習

Rep exposure

思考下面這個有問題的數據類型：

/** Represents an immutable right triangle. */class RightTriangle { /*A*/ private double[] sides;/*B*/ public 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 }; /*D*/ this.hypotenuse = hypotenuse;}/** Get the two sides of the right triangle.* @return two-element array with the triangle's side lengths*/public double[] getAllSides() { /*E*/ return sides;}/** @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, hypotenuse*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, hypotenuse);}}

以下哪些說法是正確的？

[ ] The line marked /*A*/ is a problem for rep exposure because arrays are mutable.
[x] /*B*/ 處有問題，因為這種表示方法會讓使用者依賴于類型內部的表示。
[ ] The line marked *C* is a problem because creator operations should not have preconditions.
[ ] The two lines marked /*D*/ are a problem because they put legA, legB, and hypotenuse into the rep without doing a defensive copy first.
[x] /*E*/ 處有問題，因為這影響到了類的不可變性。

表示不變量和抽象函數

我們現在深入理解一下抽象數據類型背后的理論，這些理論不僅本身很有趣，它們在ADT的設計與實現中也很有意義。如果你能夠很好的理解它們，你將會設計出更好的抽象類型，并且遠離那些隱晦的陷阱。

在研究抽象類型的時候，先思考一下兩個值域之間的關系：

表示域（space of representation values）里面包含的是值具體的實現實體。在簡單的情況下，一個抽象類型只需要實現為單個的對象，但是更常見的情況是使用一個很多對象的網絡。

抽象域里面包含的則是類型設計時支持使用的值。這些值是由表示域“抽象/想象”出來的，也是使用者關注的。例如，一個無限整數對象的抽象域是整個整數域，但是它的實現域可能是一個由原始整數類型（有限）組成的數組實現的，而使用者只關注抽象域。

但是，實現者是非?！霸谝狻北硎居?#xff08;和抽象域）的，因為實現者的責任就是實現表示域到抽象域的轉換（映射）。

例如，我們選擇用字符串來表示一個字符集合：

public class CharSet {private String s;... }

如上圖所示，表示域R包含的是我們的實現實體（字符串），而抽象域里面是抽象類型表示的字符集合，我們用箭頭表示這兩個域之間的映射關系。這里要注意幾點：

每一個抽象值都是由表示值映射而來 。我們之前說過實現抽象類型的意義在于支持對于抽象值的操作，即我們需要能夠創建和管理所有的抽象值，因此它們也必須是可表示的。
一些抽象值是被多個表示值映射而來的。這是因為表示方法并不是固定的，我們可以靈活的表示一個抽象值。
不是所有的表示值都能映射到抽象域中。在上面這個例子中，“abbc”就沒有被映射。因為我們已經確定了表示值的字符串中不能含有重復的字符——這樣我們的 remove 方法就能在遇到第一個對應字符的時候停止，因為我們知道沒有重復的字符。

由于我們不可能對每一個映射一一解釋，為了描述這種對應關系和這兩個域，我們再定義兩個概念：

抽象函數abstraction function是表示值到其對應的抽象值的映射：

AF : R → A

快照圖中的箭頭表示的就是抽象函數，可以看出，這種映射是滿射，但不一定是單射（不一定是雙射）。

表示不變量rep invariant是表示值到布爾值的映射：

RI : R → boolean

對于表示值r，當且僅當r被AF映射到了A，RI(r)為真。換句話說，RI告訴了我們哪些表示值是“良好組織”的（能夠去表示A中的抽象值），在下圖中，綠色表示的就是RI(r)為真的部分，AF只在這個子集上有定義。

例如上圖中，CharSet這種類型的實現禁止有重復字符，所以 RI(“a”) = true, RI(“ac”) = true, RI(“acb”) = true, 但是 RI(“aa”) = false, RI(“abbc”) = false.其中為假的集合用紅色區域表示，合法的（為真）的字符串集合用綠色表示。

表示不變量和抽象函數都應該在表示聲明后注釋出來：

public class CharSet {private String s;// Rep invariant:// s contains no repeated characters// Abstraction function:// AF(s) = {s[i] | 0 <= i < s.length()}... }

一個常見的疑惑就是，抽象函數和表示不變量似乎是被表示域和抽象域決定的，甚至似乎抽象域就可以決定它。如果是這樣的話，那么它們的定義似乎沒什么用。

首先證明抽象域并不能獨立決定AF和RI：對于同樣的抽象類型可以有多種表示方法。例如對于一個字符集合，我們既可以用字符串來表示，也可以用比特向量來表示，每一個比特位對應一個可能的字符。顯然我們需要兩個不同的抽象函數來表示這兩種不同的映射。

現在我們再來證明表示域和抽象域也不能決定AF和RI。這里的關鍵點在于，當我們確定表示域（表示值的空間）后，我們并不能決定哪一些表示值是合法的，以及如果它是合法的，它會被怎么解釋/映射。例如在上面的例子中，我們也可以允許表示值有重復的字符，但是我們要求表示值中的字符必須是排好序的，因為這樣我們就可以對其進行二分查找而非線性的遍歷了。對于同一個表示域，我們得到了不同的表示不變量：

public class CharSet {private String s;// Rep invariant:// s[0] <= s[1] <= ... <= s[s.length()-1]// Abstraction function:// AF(s) = {s[i] | 0 <= i < s.length()}... }

最后，即使是同樣的抽象域和表示域以及同樣的表示不變量，我們也可能有不同的解釋方法/抽象函數。還是上面的例子，我們可以對表示值中相鄰的字符做不同的解釋： "acgg" 被解釋為[a-c] 和 [g-g]中的字符，即{a,b,c,g}?，F在的映射如下圖所示：

public class CharSet {private String s;// Rep invariant:// s.length() is even// s[0] <= s[1] <= ... <= s[s.length()-1]// Abstraction function:// AF(s) = union of { c | s[2i] <= c <= s[2i+1] } // for all 0 <= i < s.length()/2... }

總之，一個ADT的實現不僅是選擇表示域（規格說明）和抽象域（具體實現），同時也要決定哪一些表示值是合法的（表示不變量），合法表示會被怎么解釋/映射（抽象函數）。

所以，你必須像我們一樣在代碼中寫出這些設計，以便別的程序員（或者未來的你）明白這些表示到底意味著什么。為什么呢？當程序員不明白表示的含義時會發生什么問題呢？請完成下面的閱讀小練習。

你可以在Github上找到上面例子中CharSet的三種實現的代碼。

閱讀小練習

Exploring a rep

請思考上面 CharSet 的最后一種實現方式：

下面哪個選項的 s 滿足了表示不變量？

[ ] "abc"
[x] "abcd"
[x] "eeee"
[x] "ad"
[ ] "adad"
[ ] "" (譯者注：s.length()-1)

AF("acfg") 會映射到哪一個集合？

[ ] {a,b,c,d,e,f,g}
[x] {a,b,c,f,g}
[ ] {a,c,f,g}
[ ] some other abstract value
[ ] no abstract value, because "acfg" does not satisfy the rep invariant

下面哪一個選項會和 "tv"映射到同一個抽象值？

[ ] "ttv"
[x] "ttuuvv"
[x] "ttuv"
[ ] "tuv"

Who knows what?

以下哪一些選項是使用者需要了解的？

[x] 抽象域
[ ] 抽象函數
[x] 創建者
[x] 觀察者
[ ] 表示域
[ ] 表示不變量

以下哪一些選項是開發者需要了解的？

[x] 抽象域
[x] 抽象函數
[x] 創建者
[x] 觀察者
[x] 表示域
[x] 表示不變量

Rep invariant pieces

假設 C 這種抽象數據類型的表示用到了兩個字符串：

class C {private String s;private String t;... }

假設你不知道任何關于C抽象的信息，以下哪一些選項可能是C的表示不變量？

[x] s 只能包含字母
[x] s.length() == t.length()
[ ] s represents a set of characters
[ ] C’s observers
[x] s 是 t反序過來的結果
[ ] s+t

Trying to implement without an AF/RI

假設Louis 是這樣表示CharSet的：

public class CharSet {private String s;... }

不幸的是，Louis忘記寫下抽象函數（AF）和表示不變量（RI）了。這里有四中可能的AF/RI對。它們在之前的例子中已經提到過了：

SortedRep:

// AF(s) = {s[i] | 0 <= i < s.length()} // RI: s[0] < s[1] < ... < s[s.length()-1]

SortedRangeRep:

// AF(s) = union of { c | s[2i] <= c <= s[2i+1] } // for all 0 <= i < s.length()/2 // RI: s.length() is even, and s[0] <= s[1] <= ... <= s[s.length()-1]

NoRepeatsRep:

// AF(s) = {s[i] | 0 <= i < s.length()} // RI: s contains no character more than once

AnyRep:

// AF(s) = {s[i] | 0 <= i < s.length()} // RI: true

假設Louis有三個不同的朋友在幫助他分別實現該類型的三個操作: add(), remove(), and contains()，每一個朋友對這種類型的表示都有自己的猜想。

對于下面 add()的實現，哪一種AF/RI是可以對的上的？

/*** Modifies this set by adding c to the set.* @param c character to add*/ public void add(char c) {s = s + c; }

[ ] SortedRep
[ ] SortedRangeRep
[ ] NoRepeatsRep
[x] AnyRep

Trying to implement without an AF/RI #2

對于下面 remove()的實現，哪一種AF/RI是可以對的上的？

/*** Modifies this set by removing c, if found.* If c is not found in the set, has no effect.* @param c character to remove*/ public void remove(char c) {int position = s.indexOf(c);if (position >= 0) {s = s.substring(0, position) + s.substring(position+1, s.length());} }

[x] SortedRep
[ ] SortedRangeRep
[x] NoRepeatsRep
[ ] AnyRep

Trying to implement without an AF/RI #3

對于下面 contains()的實現，哪一種AF/RI是可以對的上的？

/*** Test for membership.* @param c a character* @return true iff this set contains c*/ public boolean contains(char c) {for (int i = 0; i < s.length(); i += 2) {char low = s.charAt(i);char high = s.charAt(i+1);if (low <= c && c <= high) {return true;}}return false; }

[ ] SortedRep
[x] SortedRangeRep
[ ] NoRepeatsRep
[ ] AnyRep

例子：有理數

這里列出了一個表示有理數的例子。仔細觀察表示不變量和抽象函數。我們似乎可以允許更多的表示值是合法的，但是這樣做會讓一些操作的實現變得復雜（假設變了），另一些操作則可能變得簡單。

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 termsint g = gcd(n, d);n = n / g;d = d / g;// make denominator positiveif (d < 0) {numerator = -n;denominator = -d;} else {numerator = n;denominator = d;}checkRep();} }

閱讀小練習

RatNum

閱讀上面的代碼和快照圖，對于下面的每一種現象/屬性，哪一行代碼“負有最大的責任”（導致）？

RatNum(1,-2) 出現在 R的紅色區域：

[ ] private final int numerator;
[ ] private final int denominator;
[ ] // Rep invariant:
[x] // denominator > 0
[ ] // numerator/denominator is in reduced form
[ ] // Abstraction function:
[ ] // AF(numerator, denominator) = numerator/denominator

RatNum(2,4) 出現在 R的紅色區域：

[ ] private final int numerator;
[ ] private final int denominator;
[ ] // Rep invariant:
[ ] // denominator > 0
[x] // numerator/denominator is in reduced form
[ ] // Abstraction function:
[ ] // AF(numerator, denominator) = numerator/denominator

RatNum(-1,2)到 -1/2 有一個箭頭：

[ ] private final int numerator;
[ ] private final int denominator;
[ ] // Rep invariant:
[ ] // denominator > 0
[ ] // numerator/denominator is in reduced form
[ ] // Abstraction function:
[x] // AF(numerator, denominator) = numerator/denominator

檢查表示不變量

表示不變量不僅是一個簡潔的數學概念，你還可以通過斷言檢查它的不變屬性來動態捕捉bug。例如上面的RatNum，這里就舉出了一種檢查的方法：

// 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() 檢查不變量，換句話說，就是在使用創建者、生產者以及改造者之后。在上面的RatNum中，你可以看到我們在兩個創建者的最后都使用了 checkRep() 進行檢查。

雖然說觀察者通常不需要使用 checkRep() 進行檢查，但這也是一個不錯的主意。為什么？因為在每一個操作中調用 checkRep() 檢查不變量更能夠幫助你捕捉因為表示暴露而帶來的bug。

為什么 checkRep() 是私有的？誰應該為為表示不變量負責？使用者還是實現者？

閱讀小練習

Checking the rep invariant

以下哪一個選項的說法是正確的？

[ ] checkRep() is the abstraction function
[x] checkRep() 斷言檢查了表示不變量
[x] 對于實現者來說，在每一個類的公共方法返回前調用 checkRep() 進行檢查是一個好主意
[ ] it’s good for a client to call checkRep() just after calling a public method of an ADT class

不要在表示中使用Null

回憶一下我們之前說過的使用null的壞處（譯者注：“規格說明”），我們應該盡可能在編程中避免它。正因為如此，我們之前說如果沒有特殊說明，前置條件和后置條件中都隱式包含不會有null值出現。

現在我們將這種閑置擴展到抽象數據類型的表示中。默認情況下，我們不允許表示中的索引出現null值（包括數組或者列表中的元素）。例如，如果你的表示是：

class CharSet {String s; }

那么表示不變量中默認就會有 s != null ——你不需要專門在表示不變量的注釋中進行說明。

然而，當你在實現檢查表示不變量的 checkRep() 時，你應該顯式的檢查 s != null，確保當 s 是 null 的時候會快速失敗。通常來說，這種檢查會是自動的，因為很多操作在內容是null時會自動拋出異常，例如:

private void checkRep() {assert s.length() % 2 == 0;... }

這個時候你就不需要使用 assert s != null,因為對 s.length() 的調用會在s為null的時候自動失敗報錯。但是如果沒有對null的自動檢查，你就需要顯式的使用 assert s != null了。

友善改動

回憶之前我們對于不可變類型的定義：對象一旦被創建其值不會發生更改?，F在我們學習了抽象數據類型中的表示域和抽象域，我們可以將這個定義更加細化一下：對象一旦被創建，其抽象值不會發生改變。也就是說，對于使用者來說，其代表的值是不會變的，但是實現者可以在底層對表示域做一些改動，這些不會影響到抽象域的改動就稱為友善改動（beneficent mutation）.

這里舉出了一個之前提到的RatNum類型，不過我們將表示不變量的限制放寬了，不再要求分子和分母必須是最簡形式：

public class RatNum {private int numerator;private int denominator;// Rep invariant:// denominator != 0// Abstraction function:// AF(numerator, denominator) = numerator/denominator/*** 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 {if (d == 0) throw new ArithmeticException();numerator = n;denominator = d;checkRep();}... }

這樣的話，再顯示值之前，我們要對其進行簡化：

/*** @return a string representation of this rational number*/@Overridepublic String toString() {int g = gcd(numerator, denominator);numerator /= g;denominator /= g;if (denominator < 0) {numerator = -numerator;denominator = -denominator;}checkRep();return (denominator > 1) ? (numerator + "/" + denominator) : (numerator + "");}

注意到 toString 實現更改了私有區域 numerator 和 denominator, 即它改變了表示域——雖然這還是一個觀察者！但是關鍵點在于，這種改動并沒有改變映射到的抽象值。我們對分子分母進行的約分和同乘-1的操作并沒有改變AF(numerator, denominator) = numerator/denominator的行為。也可以這樣想，AF是一種多對一函數，即一個表示值可以用多種表示值來實現。所以這種改動是無害的，也就是“友善”的。

我們會在后面的課程中看到很多使用友善改動的例子。這種實現上的自由通?？梢詭硇阅苌系奶嵘?#xff0c;例如緩沖、數據結構再平衡、延遲清除等策略。

AF, RI以及表示暴露安全性的注解

你應該在抽象類型（私有的）表示聲明后寫上對于抽象函數和表示不變量的注解，這是一個好的實踐要求。我們在上面的例子中也是這么做的。

當你在描述抽象函數和表示不變量的時候，注意要清晰明確：

對于RI（表示不變量），僅僅寬泛的說什么區域是合法的并不夠，你還應該說明是什么使得它合法/不合法。
對于AF（抽象函數）來說，僅僅寬泛的說抽象域表示了什么并不夠。抽象函數的作用是規定合法的表示值會如何被解釋到抽象域。作為一個函數，我們應該清晰的知道從一個輸入到一個輸入是怎么對應的。

本門課程還要求你將表示暴露的安全性注釋出來。這種注釋應該說明表示的每一部分，它們為什么不會發生表示暴露，特別是處理的表示的參數輸入和返回部分（這也是表示暴露發生的位置）。

下面是一個Tweet類的例子，它將表示不變量和抽象函數以及表示暴露的安全性注釋了出來：

// Immutable type representing a tweet. public class Tweet {private final String author;private final String text;private final Date timestamp;// Rep invariant:// author is a Twitter username (a nonempty string of letters, digits, underscores)// text.length <= 140// Abstraction function:// AF(author, text, timestamp) = a tweet posted by author, with content text, // at time timestamp // Safety from rep exposure:// All fields are private;// author and text are Strings, so are guaranteed immutable;// timestamp is a mutable Date, so Tweet() constructor and getTimestamp() // make defensive copies to avoid sharing the rep's Date object with clients.// Operations (specs and method bodies omitted to save space)public Tweet(String author, String text, Date timestamp) { ... }public String getAuthor() { ... }public String getText() { ... }public Date getTimestamp() { ... } }

注意到我們并沒有對 timestamp 的表示不變量進行要求（除了之前說過的默認 timestamp!=null）。但是我們依然需要對timestamp 的表示暴露的安全性進行說明，因為整個類型的不變性依賴于所有的成員變量的不變性。

下面是關于 RatNum的另一個例子：

// Immutable type representing a rational number. public class RatNum {private final int numerator;private final int denominator;// Rep invariant:// denominator > 0// numerator/denominator is in reduced form, i.e. gcd(|numerator|,denominator) = 1// Abstraction function:// AF(numerator, denominator) = numerator/denominator// Safety from rep exposure:// All fields are private, and all types in the rep are immutable.// Operations (specs and method bodies omitted to save space)public RatNum(int n) { ... }public RatNum(int n, int d) throws ArithmeticException { ... }... }

可以看到，對于不可變類型的表示，表示暴露的安全性說明會簡單很多。

你可以在GitHub獲取RatNum的所有代碼

閱讀小練習

Arguing against rep exposure

思考這個抽象數據類型：

// Mutable type representing Twitter users' followers. public class FollowGraph {private final Map<String,Set<String>> followersOf;// Rep invariant:// all Strings in followersOf are Twitter usernames// (i.e., nonempty strings of letters, digits, underscores)// no user follows themselves, i.e. x is not in followersOf.get(x)// Abstraction function:// AF(followersOf) = the follower graph where Twitter user x is followed by user y// if and only if followersOf.get(x).contains(y)// Safety from rep exposure:// All fields are private, and ..???..// Operations (specs and method bodies omitted to save space)public FollowGraph() { ... }public void addFollower(String user, String follower) { ... }public void removeFollower(String user, String follower) { ... }public Set<String> getFollowers(String user) { ... } }

對于上面代碼中的注解，下面哪一個選項可以正確的替代 ..???.. ，從而使得表示暴露的安全性得到說明？

1. “Strings are immutable.”

2. “followersOf 是一個可變的 Map，其包含著可變的 Set 對象，但是 getFollowers() 在返回時會對 Set 進行防御性復制，并且其他的參數和返回值都是不可變類型的 String 或者 void .”

Yes

3. “This class is mutable, so rep exposure isn’t an issue.”

4. “followersOf is a mutable Map, but it is never passed or returned from an operation.”

5. “FollowGraph() does not expose the rep; addFollower() does not expose the rep; removeFollower() does not expose the rep; getFollowers() does not expose the rep.”

6. “String 是不可變的, 并且表示中的 Set 對象都使用了不可變包裝。雖然Map類型是可變的，但是沒有操作傳入或者返回這種類型的對象?！?/p>

Yes

一個ADT的規格說明應該寫什么？

由于我們已經講了如何對表示不變量和抽象函數做注解，現在我們就來更新一下我們對于規格說明的理解，即一個ADT的規格說明應該寫什么？

如上圖所示，規格說明在使用者和實現者之間構建起了一道“防火墻”。抽象類型的規格說明（包含操作的說明）應該只關注使用者可見的部分，這包括參數、返回值、可能拋出的異常。例如規格說明需要引用T的值時，它應該是抽象域的值而非表示域。

規格說明不應該談論具體的表示/實現細節，例如表示域里面的值。它應該認為表示本身（私有區域）對于使用者是不可見的，就像是方法里面的局部變量對外部不可見。這也是為什么我們在注解表示不變量和抽象函數的時候使用的是"\\"注釋而非典型的Javadoc格式。如果我們使用Javadoc注釋的話，內部的實現細節會出現在規格說明中，而這會影響表示獨立性以及信息隱藏。

用ADT不變量替換前置條件

良好設計的ADT的一個大優點在于我們可以使用它將本該寫在前置條件中的限制封裝起來。例如，現在有一個規格說明是這樣：

/** * @param set1 is a sorted set of characters with no repeats* @param set2 is likewise* @return characters that appear in one set but not the other,* in sorted order with no repeats */ static String exclusiveOr(String set1, String set2);

我們可以利用ADT（SortedSet）的不變量屬性要求這種前置條件：

/** @return characters that appear in one set but not the other */ static SortedSet<Character> exclusiveOr(SortedSet<Character> set1, SortedSet<Character> set2);

這滿足了我們所有的要求：

遠離bug：因為要求的條件（排序、無重復）都已經是ADT的不變量了，所以Java可以對其進行靜態檢查，在編譯期阻止所有不滿足的操作。
易于理解：因為這樣寫更簡單，并且ADT SortedSet 的名字就已經表明了它該有的屬性。
可改動：因為我們可以改變 SortedSet 的內部實現而不影響 exclusiveOr 或其他的使用者代碼。

我們以前很多用前置條件的地方現在都可以用定制的ADT來替換。

閱讀小練習

Encapsulating preconditions in ADTs

思考下面這個方法：

/*** Find tweets written by a particular user.* * @param tweets a list of tweets with distinct timestamps, not modified by this method.* @param username Twitter username (a nonempty sequence of letters, digits, and underscore)* @return all and only the tweets in the list whose author is username,* in the same order as in the input list.*/ public static List<Tweet> writtenBy(List<Tweet> tweets, String username) { ... }

你會創建一個什么ADT來避開這種繁雜的前置要求？

[ ] TweetsAndUsername
[x] TweetList
[x] Username
[ ] UsernameCharacter

如何建立不變量

不變量是一種在程序中一直為真的屬性，對于對象而言，就是從對象創建開始一直具有的屬性。

為了保持一個不變量，我們需要：

確保在對象創建的時候不變量成立
確保對對象在接下來的每一個改變后不變量依然成立
譯者注：這就是狀態機中的不變性狀態機：如何構建穩定的婚姻

翻譯成對于ADT的操作，就是：

創建者和生產者必須對新的對象就建立不變量
改造者和觀察者必須保持/保護這種不變量

表示暴露會使得情況更加復雜，如果一個表示被暴露出來，那么程序的任何地方都可能對其進行修改，我們也就沒法確保不變量一直成立了。所以使用不變量完整的規則應該是：

結構歸納法. 如果一個抽象數據類型的不變量滿足：

被創建者或生產者創建；

被改造者和觀察者保持；

沒有表示暴露。

那么這種類型的所有實例的不變量都是成立的。

閱讀小練習

Structural induction

Recall this data type from the first exercise in this reading:回憶在第一個練習中的數據類型：

/** Represents an immutable right triangle. */ class RightTriangle {private double[] sides;// RI: ???// AF: ???// 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: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.* Requires hypotenuse^2 = legA^2 + legB^2 * (within the error tolerance of double arithmetic)*/public RightTriangle(double legA, double legB, double hypotenuse) {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() {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(sides[0], sides[1]);return new RightTriangle (bigLeg, bigLeg, sides[2]);}}

這個數據類型中有一個重要的不變量，那就是直角邊和斜邊之間的勾股關系。

假設使用者遵守了規格說明，以下哪一個說法是正確的？

[x] 創建者 RightTriangle() 建立的不變量
[ ] The observer getAllSides() preserves the invariant
[x] 觀察者 getHypotenuse() 保持了不變量
[x] 生產者 scale() 保持了不變量
[ ] The producer regularize() preserves the invariant

總結

不變量是指對于一個對象，它有一種能夠在整個生命周期保證為真的屬性。
一個好的ADT會確保它的不變量為真。不變量是由創建者和生產者創建，被觀察者和改造者保持。
表示不變量明確了什么是合法的表示值，并且這些表示應該在運行時調用checkRep()檢查。
抽象函數將具體的表示映射到抽象值上。
表示暴露會威脅到表示獨立性和表示不變量。

下面將這篇閱讀的知識點與我們的三個目標聯系起來：

遠離bug. 一個好的ADT會確保它的不變量為真，因此它們不會被使用者代碼中的bug所影響。同時，通過顯式的聲明和動態檢查不變量，我們可以盡早的發現bug，而不是讓錯誤的行為繼續下去。
易于理解. 表示不變量和抽象函數詳細的表述了抽象類型中表示的意義，以及它們是如何聯系到抽象值的。
可改動. 抽象數據類型分離了抽象域和表示域，這使得實現者可以改動具體實現而不影響使用者的代碼。

轉載于:https://www.cnblogs.com/liqiuhao/p/8688759.html

總結

以上是生活随笔為你收集整理的麻省理工18年春软件构造课程阅读11“抽象函数与表示不变量”的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： excel android 公式,两个超
下一篇：线程队列-queue