本文内容來自MIT_6.031_sp18: Software Construction課程的Readings部分，采用CC BY-SA 4.0協定。
由于我們學校（哈工大）大二軟體構造課程的大部分素材取自此，也是推薦的閱讀材料之一，于是打算做一些翻譯工作，自己學習的同時也能幫到一些懶得看英文的朋友。另外，該課程的閱讀資料中有許多練習題，但是沒有标準答案，所給出的“正确答案”均為譯者所寫，有錯誤的地方還請指出。
（更新：從第10章開始，隻提供正确答案，不再翻譯錯誤答案）
譯者：李秋豪 江家偉
審校：李秋豪
V1.0 Thu Mar 29 00:41:23 CST 2018
本次課程的目标
- 了解“抽象資料類型(ADT)”
- 了解“表示獨立”
在這篇閱讀中，我們将會講解一個重要的概念——抽象資料類型，它會幫助我們将資料結構的使用和資料結構的具體實作分開。
抽象資料類型解決了一個很危險的問題：使用者可能對類型的内部表示做假設。我們在後面會探讨為什麼這種假設是危險的，以及如何避免它。我們也會讨論操作符的分類和如何設計好的抽象資料類型。
Java中的通路控制
閱讀: Controlling Access to Members of a Class
閱讀小練習
閱讀以下代碼并回答問題：
class Wallet {
private int amount;
public void loanTo(Wallet that) {
// put all of this wallet's money into that wallet
/*A*/ that.amount += this.amount;
/*B*/ amount = 0;
}
public static void main(String[] args) {
/*C*/ Wallet w = new Wallet();
/*D*/ w.amount = 100;
/*E*/ w.loanTo(w);
}
}
class Person {
private Wallet w;
public int getNetWorth() {
/*F*/ return w.amount;
}
public boolean isBroke() {
/*G*/ return Wallet.amount == 0;
}
}
假設程式在運作
/*A*/
語句後立即停止，上圖列出了此時的内部狀态，請問各個數字所标出的方框内應該填上什麼？
1 -> w
2 -> that
3 -> loanTo
4 -> 200
Access control A
關于語句
/*A*/
，以下哪一個說法是正确的？
that.amount += this.amount;
- [x] 在Java中允許對
this.amount
-
that.amount
Access control B
/*B*/
amount = 0;
-
amount
Access control C
/*C*/
Wallet w = new Wallet();
-
Wallet()
Access control D
/*D*/
w.amount = 100;
-
w.amount
Access control E
/*E*/
w.loanTo(w);
-
loanTo()
- [x] 在這句代碼執行之後，
w
Wallet
Access control F
/*F*/
return w.amount;
- [x] 這裡關于
w.amount
amount
- [x] 這個非法通路會被靜态捕捉
Access control G
/*G*/
return Wallet.amount == 0;
-
Wallet.amount
amount
-
Wallet.amount
amount
什麼是抽象
抽象資料類型是軟體工程中一個普遍原則的執行個體，從它衍生出很多意思相近的名詞。這裡列出了幾個能夠表達其中思想的詞：
- 抽象： 忽略底層的細節而在高層思考
- 子產品化：将系統分為一個子產品，每個子產品可以單獨的進行設計、實作、測試、推倒，并且在剩下的開發中進行複用。
- 封裝：在子產品的外部建立起一道“圍牆”，使它隻對自己内部的行為負責，并且系統别處的bug不會影響到它内部的正确性。
- 資訊隐藏：将子產品的實作細節隐藏，使未來更改子產品内部時不必改變外部代碼。
- 功能分離：一個子產品僅僅負責一個特性/功能，而不是将一個特性運用在很多子產品上或一個子產品擁有很多特性。
作為一個軟體工程師，你應該知道這些名詞，因為你會在以後的工作中經常遇到它們。這些思想的本質目的都是為了實作我們這門課的三個目标：遠離bug、易于了解、可改動。
事實上，我們在之前的課程中已經碰到過這些思想，特别是在設計方法和規格說明的時候：
- 抽象：規格說明使得使用者隻需要弄懂規格說明并遵守前置條件，而不是讓他們去弄懂底層的代碼實作
- 子產品化：單元測試和規格說明都幫助了将方法子產品化
- 封裝：方法中的局部變量都是被封裝的，因為他們僅僅可以在方法内部使用。與此相對的是全局變量和指向可變對象的别名，它們會對封裝帶來很大損害。
- 資訊隐藏：規格說明就是一種資訊隐藏，它使得實作者可以自由的更改實作代碼。
- 功能分離：一個規格說明應該是邏輯明确的，即它不能有很多特性，而應該完成好一個功能。
從今天的課程開始，我們将跳出對方法的抽象，看看對資料的抽象。但是在我們描述資料抽象時方法也會扮演很重要的角色。
使用者定義類型
在早期的程式設計語言中，使用者隻能自己定義方法，而所有的類型都是規定好的（例如整型、布爾型、字元串等等）。而現代程式設計語言允許使用者自己定義類型對資料進行抽象，這是軟體開發中的一個巨大進步。
對資料進行抽象的核心思想就是類型是通過其對應的操作來區分的：一個整型就是你能對它進行加法和乘法的東西；一個布爾型就是你能對它進行取反的東西；一個字元串就是你能對它進行連結或者取子字元串的東西，等等。在一定意義上，使用者在以前的程式設計語言上似乎已經能夠定義自己的類型了，例如定義一個名叫Date的結構體，裡面用int表示天數和年份。但是真正使得抽象類型變得新穎不同的是對操作的強調：使用者不用管這個類型裡面的資料是怎麼儲存表示的，就好像是程式員不用管編譯器是怎麼存儲整數一樣。起作用的隻是類型對應的操作。
和很多現代語言一樣，在Java中内置類型和使用者定義類型之間的關系很模糊。例如在
java.lang
中的類
Integer
和
Boolean
就是内置的——Java标準中規定它們必須存在，但是它們的定義又是和使用者定義類型的方式一樣的。另外，Java中還保留了原始類型，它們不是類和對象，例如
int
boolean
，使用者無法對它們進行繼承。
Abstract Data Types
思考抽象資料類型
Bool
，它有如下操作：
true : Bool
false : Bool
and : Bool × Bool → Bool
or : Bool × Bool → Bool
not : Bool → Bool
頭兩個操作建構了這個類型對應的兩個值，後三個操作對應邏輯操作 和、或、取非。
以下哪些選項可以是
Bool
具體的實作方法（并且滿足上面的操作符）？
- [x] 一個比特位，1代表true，0代表false
- [x] 一個
int
- [x] 一個對
String
"false"
"true"
-
int
類型和操作的分類
對于類型，不管是内置的還是使用者定義的，都可以被分為可改變 和 不可變兩種。其中可改變類型的對象能夠被改變：它們提供了改變對象内容的操作，這樣的操作執行後可以改變其他對該對象操作的傳回值。是以
Date
就是可改變的，因為你可以通過調用
setMonth
操作改變
getMonth
操作的傳回值。但
String
就是不可改變的，因為它的操作符都是建立一個新的
String
對象而不是改變現有的這個。有時候一個類型會提供兩種形式，一種是可改變的一種是不可改變的。例如
StringBuilder
就是一種可改變的字元串類型。
而抽象類型的操作符大緻分類：
- 建立者creator：建立一個該類型的新對象。一個建立者可能會接受一個對象作為參數，但是這個對象的類型不能是它建立對象對應的類型。
- 生産者producer：通過接受同類型的對象建立新的對象。例如，
String
concat
- 觀察者observer：接受一個同類型的對象然後傳回一個不同類型的對象/值。例如
List
size
int
- 改造者mutator：改變對象的内容，例如
List
add
我們可以将這種差別用映射來表示：
- creator : t* → T
- producer : T+, t* → T
- observer : T+, t* → t
- mutator : T+, t* → void | t | T
其中T代表抽象類型本身；t代表其他的類型；
+
代表這個參數可能出現一次或多次；
*
代表這個參數可能出現零次或多次。例如，
String.concat()
這個接受兩個參數的生産者：
- concat : String × String → String
有些觀察者不會接受其他類型的參數，例如：
- size : List → int
而有些則會接受很多參數：
- regionMatches : String × boolean × int × String × int × int → boolean
構造者通常都是用構造函數實作的，例如
new ArrayList()
，但是有的構造體是靜态方法（類方法），例如
Arrays.asList()
String.valueOf
，這樣的靜态方法也稱為工廠方法。
改造者通常沒有傳回值（
void
）。一個沒有傳回值的方法一定有副作用 ，因為不然這個方法就沒有任何意義了。但是不是所有的改造者都沒有傳回值。例如
Set.add()
會傳回一個布爾值用來提示這個集合是否被改變了。在Java圖形庫接口中，
Component.add()
會将它自己這個對象傳回，是以
add()
可以被連續鍊式調用。
抽象資料類型的例子
int 是Java中的原始整數類型，它是不可變類型，沒有改造者。
- creators: 字面量 ,
1
2
- producers: 算術符
+
-
*
/
- observers: 比較符号
==
!=
<
>
- mutators: 無
List 是Java中的清單類型，它是可更改類型。另外，
List
也是一個接口，是以對于它的實作可以有很多類，例如
ArrayList
LinkedList
.
- creators:
ArrayList
LinkedList
Collections.singletonList
- producers:
Collections.unmodifiableList
- observers:
size
get
- mutators:
add
remove
addAll
Collections.sort
String 是Java中的字元串類型，它是不可變類型。
-
String
valueOf
-
concat
substring
toUpperCase
-
length
charAt
這個分類告訴了我們一些有用的術語，但它不是完美的。例如對于複雜的資料類型，有些操作可能既是生産者也是改造者。
Operations
下面都是我們從Java庫中選取的幾個抽象資料類型的操作，試着通過閱讀文檔将這些操作分類。
提示：注意類型本身是不是參數或者傳回值，同時記住執行個體方法（沒有
static
關鍵詞的）有一個隐式的參數。
Integer.valueOf()
creator
BigInteger.mod()
producer
List.addAll()
mutator
String.toUpperCase()
Set.contains()
observer
Map.keySet()
BufferedReader.readLine()
抽象類型是通過它的操作定義的
這一節的重要思想就是抽象類型是通過它的操作定義的.
對于類型T來說，它的操作集合和規格說明完全定義和構造了它的特性。例如，當我們談到
List
類型時，我們并沒有特指一個數組或者連結連結清單，而是一系列模糊的值——哪些對象可以是
List
類型——滿足該類型的規格說明和操作規定，例如
get()
size()
, 等等。
上一段說到的“模糊的值”是指我們不能去檢查資料具體是在類型中怎麼存儲的，而是要通過特定的操作去處理。例如上圖中畫出的，通過規格說明這道“防火牆”，我們将類型中具體的實作和這些實作共享的私有資料封裝起來，而使用者隻能看到和使用接口上的操作。
設計抽象類型
設計一個抽象類型包括選擇合适的操作以及它們對應的行為，這裡列出了幾個重要的規則。
設計少量，簡單，可以組合實作強大功能的操作而非設計很多複雜的操作。
每個操作都應該有一個被明确定義的目的，并且應該設計為對不同的資料結構有一緻的行為，而不是針對某些特殊情況。例如，或許我們不應該為
List
類型添加一個
sum
操作。因為這雖然可能對想要操作一個整數清單的使用者有幫助，但是如果使用者想要操作一個字元串清單呢？或者一個嵌套的清單? 所有這些特殊情況都将會使得
sum
成為一個難以了解和使用的操作。
操作集合應該充分地考慮到使用者的需求，也就是說，使用者可以用這個操作集合做他們可能想做的計算。一個較好測試方法是檢查抽象類型的每個屬性是否都能被操作集提取出來。例如，如果沒有
get
操作，我們就不能提取清單中的元素。抽象類型的基本資訊的提取也不應該特别困難。例如，
size
方法對于
List
并不是必須的，因為我們可以用
get
增序周遊整個清單，直到
get
執行失敗，但是這既不高效，也不友善。
抽象類型可以是通用的：例如，清單、集合，或者圖。或者它可以是适用于特定領域的：一個街道的地圖，一個員工資料庫，一個電話簿等等。但是一個抽象類型不能兼有上述二者的特性。被設計用來代表一個紙牌序列的
Deck
類型不應該有一個通用的
add
方法來向類型執行個體中添加任意對象，比如整型和字元串類型。反過來說，對于像
dealCards
這樣的隻對特定領域(譯者注：紙牌遊戲)有效的方法，把它加入
List
這樣的通用類型中也是沒有意義的。
表示獨立
特别地，一個好的抽象資料類型應該是表示獨立的。這意味着它的使用和它的内部表示（實際的資料結構和實作）無關，是以内部表示的改變将對外部的代碼沒有影響。例如，
List
就是表示獨立的——它的使用與它是用數組還是連接配接連結清單實作無關。
如果一個操作完全在規格說明中定義了前置條件和後置條件，使用者就知道他應該依賴什麼，而你也可以安全的對内部實作進行更改（遵循規格說明）。
例子: 字元串的不同表示
讓我們先來看看一個表示獨立的例子，然後想想它為什麼很有用。下面的
MyString
抽象類型是我們舉出的例子，雖然它遠遠沒有Java中的
String
操作多，規格說明也有些不同，但是還是有解釋力的。下面是規格說明：
/** MyString represents an immutable sequence of characters. */
public class MyString {
//////////////////// Example of a creator operation ///////////////
/** @param b a boolean value
* @return string representation of b, either "true" or "false" */
public static MyString valueOf(boolean b) { ... }
//////////////////// Examples of observer operations ///////////////
/** @return number of characters in this string */
public int length() { ... }
/** @param i character position (requires 0 <= i < string length)
* @return character at position i */
public char charAt(int i) { ... }
//////////////////// Example of a producer operation ///////////////
/** Get the substring between start (inclusive) and end (exclusive).
* @param start starting index
* @param end ending index. Requires 0 <= start <= end <= string length.
* @return string consisting of charAt(start)...charAt(end-1) */
public MyString substring(int start, int end) { ... }
}
使用者隻需要/隻能知道這個類型的公共方法和規格說明。
現在讓我們看一個
MyString
簡單的表示方法，僅僅使用一個字元數組，而且它的大小剛好是字元串的長度，沒有多餘的空間：
private char[] a;
如果使用這種表示方法，我們對操作的實作可能就是這樣的：
public static MyString valueOf(boolean b) {
MyString s = new MyString();
s.a = b ? new char[] { 't', 'r', 'u', 'e' }
: new char[] { 'f', 'a', 'l', 's', 'e' };
return s;
}
public int length() {
return a.length;
}
public char charAt(int i) {
return a[i];
}
public MyString substring(int start, int end) {
MyString that = new MyString();
that.a = new char[end - start];
System.arraycopy(this.a, start, that.a, 0, end - start);
return that;
}
這裡想一個問題：為什麼
charAt
substring
不去檢查參量在合法的範圍内？你認為這種類型的對象對于非法的輸入會有什麼反應？
下面的快照圖展示了在使用者進行
substring
操作後的資料狀态：
MyString s = MyString.valueOf(true);
MyString t = s.substring(1,3);
這種實作有一個性能上的問題，因為這個資料類型是不可變的，那麼
substring
實際上沒有必要真正去複制子字元串到一個新的數組中。它可以僅僅指向原來的
MyString
字元數組，并且記錄目前的起始位置和終止位置。
為了實作這種優化，我們可以将内部表示改為：
private char[] a;
private int start;
private int end;
通過這種新的表示方法，我們可以這樣實作操作：
public static MyString valueOf(boolean b) {
MyString s = new MyString();
s.a = b ? new char[] { 't', 'r', 'u', 'e' }
: new char[] { 'f', 'a', 'l', 's', 'e' };
s.start = 0;
s.end = s.a.length;
return s;
}
public int length() {
return end - start;
}
public char charAt(int i) {
return a[start + i];
}
public MyString substring(int start, int end) {
MyString that = new MyString();
that.a = this.a;
that.start = this.start + start;
that.end = this.start + end;
return that;
}
現在進行
substring
MyString s = MyString.valueOf(true);
MyString t = s.substring(1,3);
因為
MyString
的使用者隻使用到了它的公共方法和規格說明（沒有使用私有的存儲表示），我們可以“私底下”完成這種優化而不用擔心影響使用者的代碼。這就是表示獨立的力量。
Representation 1
思考下面這個抽象類型：
/**
* Represents a family that lives in a household together.
* A family always has at least one person in it.
* Families are mutable.
*/
class Family {
// the people in the family, sorted from oldest to youngest, with no duplicates.
public List<Person> people;
/**
* @return a list containing all the members of the family, with no duplicates.
*/
public List<Person> getMembers() {
return people;
}
}
下面是一個使用者的代碼：
void client1(Family f) {
// get youngest person in the family
Person baby = f.people.get(f.people.size()-1);
...
}
假設所有的代碼都能順利運作（
Family
client1
）并通過測試。
現在
Family
的資料表示從
List
變為了
Set
：
/**
* Represents a family that lives in a household together.
* A family always has at least one person in it.
* Families are mutable.
*/
class Family {
// the people in the family
public Set<Person> people;
/**
* @return a list containing all the members of the family, with no duplicates.
*/
public List<Person> getMembers() {
return new ArrayList<>(people);
}
}
以下哪一個選項是在
Family
更改後對
client1
的影響？
- [x]
client1
Family
Representation 2
原始版本:
/**
* Represents a family that lives in a
* household together. A family always
* has at least one person in it.
* Families are mutable. */
class Family {
// the people in the family,
// sorted from oldest to youngest,
// with no duplicates.
public List<Person> people;
/** @return a list containing all
* the members of the family,
* with no duplicates. */
public List<Person> getMembers() {
return people;
}
}
新版本：
/**
* Represents a family that lives in a
* household together. A family always
* has at least one person in it.
* Families are mutable. */
class Family {
// the people in the family
public Set<Person> people;
/**
* @return a list containing all
* the members of the family,
* with no duplicates. */
public List<Person> getMembers() {
return new ArrayList<>(people);
}
}
使用者
client2
的代碼：
void client2(Family f) {
// get size of the family
int familySize = f.people.size();
...
}
以下哪一個選項是新版本對
client2
-
client2
Family
Representation 3
原始版本：
/**
* Represents a family that lives in a
* household together. A family always
* has at least one person in it.
* Families are mutable. */
class Family {
// the people in the family,
// sorted from oldest to youngest,
// with no duplicates.
public List<Person> people;
/** @return a list containing all
* the members of the family,
* with no duplicates. */
public List<Person> getMembers() {
return people;
}
}
/**
* Represents a family that lives in a
* household together. A family always
* has at least one person in it.
* Families are mutable. */
class Family {
// the people in the family
public Set<Person> people;
/**
* @return a list containing all
* the members of the family,
* with no duplicates. */
public List<Person> getMembers() {
return new ArrayList<>(people);
}
}
client3
void client3(Family f) {
// get any person in the family
Person anybody = f.getMembers().get(0);
...
}
client3
-
client3
Family
Representation 4
對于上面的
Family
資料類型，對每行/段判斷他是規格說明（specification）還是資料表示（representation）還是具體實作（implementation）？
/**
* Represents a family that lives in a household together.
* A family always has at least one person in it.
* Families are mutable.
*/
--> 規格說明
public class Family {
// the people in the family, sorted from oldest to youngest, with no duplicates.
--> 資料表示
private List<Person> people;
/**
* @return a list containing all the members of the family, with no duplicates.
*/
public List<Person> getMembers() {
return people;
--> 具體實作
抽象資料類型在Java中的實作
讓我們總結一下我們在這篇文章中讨論過的主要思想以及使用JAVA語言特性實作它們的具體方法，這些思想對于使用任何語言程式設計一般都是适用的。重點在于有很多種方式來實作，很重要的一點是：既要對大概念（比如構造操作：creator operation）有較好的了解，也要了解它們不同的實作方式。
| ADT concept | Ways to do it in Java | Examples |
|---|---|---|
| Abstract data type | Class | |
| Interface + class(es) | | |
| Enum | | |
| Creator operation | Constructor | |
| Static (factory) method | | |
| Constant | | |
| Observer operation | Instance method | |
| ||
| Producer operation | | |
| Static method | | |
| Mutator operation | | |
| ||
| Representation | |
這個表中有三項我們還沒有在之前的閱讀中講過：
- 使用接口來定義一個抽象資料類型。我們已經看到
List
ArrayList
- 使用枚舉類型(
enum
- 用不變的對象作為構造者操作。這種模式在不可變類型中很常見，在不可變類型中，最簡單或者空（emptiest譯者：喵喵喵？）的值僅僅是一個屬性為public的不變量，基于這個不變量，生産者被用來從中構造更複雜的值。
測試抽象資料類型
當我們測試一個抽象資料類型的時候，我們分别測試它的各個操作。而這些測試不可避免的要互互相動：我們隻能通過觀察者來判斷其他的操作的測試是否成功，而測試觀察者的唯一方法是建立對象然後使用觀察者。
下面是我們測試
MyString
類型時對輸入空間的一種可能劃分方案：
// testing strategy for each operation of MyString:
//
// valueOf():
// true, false
// length():
// string len = 0, 1, n
// string = produced by valueOf(), produced by substring()
// charAt():
// string len = 1, n
// i = 0, middle, len-1
// string = produced by valueOf(), produced by substring()
// substring():
// string len = 0, 1, n
// start = 0, middle, len
// end = 0, middle, len
// end-start = 0, n
// string = produced by valueOf(), produced by substring()
現在我們試着用測試用例覆寫每一個分區。注意到
assertEquals
并不能直接應用于
MyString
對象，因為我們沒有在
MyString
上定義判斷相等的操作，是以我們隻能使用之前定義的
valueOf
length
charAt
, 以及
substring
，例如：
@Test public void testValueOfTrue() {
MyString s = MyString.valueOf(true);
assertEquals(4, s.length());
assertEquals('t', s.charAt(0));
assertEquals('r', s.charAt(1));
assertEquals('u', s.charAt(2));
assertEquals('e', s.charAt(3));
}
@Test public void testValueOfFalse() {
MyString s = MyString.valueOf(false);
assertEquals(5, s.length());
assertEquals('f', s.charAt(0));
assertEquals('a', s.charAt(1));
assertEquals('l', s.charAt(2));
assertEquals('s', s.charAt(3));
assertEquals('e', s.charAt(4));
}
@Test public void testEndSubstring() {
MyString s = MyString.valueOf(true).substring(2, 4);
assertEquals(2, s.length());
assertEquals('u', s.charAt(0));
assertEquals('e', s.charAt(1));
}
@Test public void testMiddleSubstring() {
MyString s = MyString.valueOf(false).substring(1, 2);
assertEquals(1, s.length());
assertEquals('a', s.charAt(0));
}
@Test public void testSubstringIsWholeString() {
MyString s = MyString.valueOf(false).substring(0, 5);
assertEquals(5, s.length());
assertEquals('f', s.charAt(0));
assertEquals('a', s.charAt(1));
assertEquals('l', s.charAt(2));
assertEquals('s', s.charAt(3));
assertEquals('e', s.charAt(4));
}
@Test public void testSubstringOfEmptySubstring() {
MyString s = MyString.valueOf(false).substring(1, 1).substring(0, 0);
assertEquals(0, s.length());
}
Partition covering
哪一個測試覆寫了分區“
charAt()
以及字元串長度=1”？
-
testMiddleSubstring
哪一個測試覆寫了分區“子字元串的子字元串”？
-
testSubstringOfEmptySubstring
valueOf(true)
”？
-
testValueOfTrue
-
testEndSubstring
Unit testing an ADT
testValueOfTrue
測試的是哪一個“單元”？
-
valueOf
-
length
-
charAt
總結
- 抽象資料類型(ADT)是通過它們對應的操作區分的。
- 操作可以分類為建立者、生産者、觀察者、改造者。
- ADT的辨別由它的操作集合和規格說明組成。
- 一個好的ADT應該是簡單，邏輯明确并且表示獨立的。
- 對于ADT的測試應該對每一個操作進行測試，并同時利用到建立者、生産者、觀察者、改造者。
T将本次閱讀的内容和我們的三個目标聯系起來：
- 遠離bug. 一個好的ADT會在使用者和實作者之間建立“契約”，使用者知道應該如何使用，而實作者有足夠的自由決定具體實作。
- 易于了解. 一個好的ADT會将其内部的代碼和資訊隐藏起來，而使用者隻需要了解它的規格說明和操作即可。
- 可改動. 表示獨立使得實作者可以在不通知使用者的情況下對ADT内部進行改動。