麻省理工18年春軟體構造課程閱讀08“可變性與不變性”

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

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

譯者：李秋豪

審校：

V1.0 Fri Mar 23 17:20:24 CST 2018

本次課程的目标

了解可變性(mutability)和可變對象
學會判斷别名使用和了解可變性的危險
利用不變性使代碼正确、易懂、可改動

譯者注：mutability還可以翻譯為“易變性”（that can change; likely to change），“易”似乎也能突出使用應該謹慎，但後來我還是覺得“可變”更準确，是以就譯為“可變性”。

建立和使用對象

譯者注：麻省理工理工是先教的Python，Java并沒有作為課程。是以這裡提供了一組從Python到Java過渡資料。Java基礎好的朋友這節可以跳過。

From Ken Lambert’s tutorial From Python to Java, read the first 8 pages under Defining Classes:

Class Structure

Visibility Modifiers

Instance Variables and Constructors

Defining Other Constructors

Instance Methods

Method Overloading

Class ( static ) Variables and Methods

Symbolic Constants ( final Variables)

Optional: if you want to see more examples, read these Java Tutorials pages:

Declaring Classes

Declaring Member Variables

Providing Constructors for Your Classes

Understanding Class Members

Using the this Keyword

Initializing Fields

閱讀小練習

Classes and objects

class Tortoise:
    def __init__(self):
        self.position = 0

    def forward(self):
        self.position += 1

pokey = Tortoise()
pokey.forward()
print(pokey.position)

如果我們将

Tortoise

轉換為Java，應該怎麼進行聲明？

public class Tortoise

Under construction

在Python中，我們通過聲明

__init__

函數來初始化新的對象。

在Java中類似的聲明應該怎麼寫？

public Tortoise()

我們應該怎麼索引到一個新的

Tortoise

對象？

Tortoise t = new Tortoise()

Methodical

我們在一個

Tortoise

對象中聲明一個

forward

方法：

public void forward() {
    // self.position += 1 (Python)
}

以下哪一行代碼可以達到代碼中注釋行的目的：

[x] position += 1;
[ ] self.position += 1;
this.position += 1;
Tortoise.position += 1;

On your mark

在Python中，我們通過

self.position = 0

初始化

Tortoise

對象中

position

為0.

使用一行代碼将

position

初始化：

public class Tortoise {

    private int position = 0;      // (1)
    static int position = 0;       // (2)

    public Tortoise() {
        int position = 0;          // (3)
        int self.position = 0;     // (4)
        int this.position = 0;     // (5)
        int Tortoise.position = 0; // (6)
    }
    // ...
}

[x] 1
[ ] 2
[ ] 3
[ ] 4
[ ] 5
[ ] 6

或者用幾行初始化

position

：

public class Tortoise {

    private int position;          // (1)
    static int position;           // (2)

    public Tortoise() {
        self.position = 0;         // (3)
        this.position = 0;         // (4)
        Tortoise.position = 0;     // (5)
    }
    // ...
}

[x] 4

Get set

現在我們再聲明另一個方法

Tortoise

public void jump(int position) {
    // set this Tortoise's position to the input value
}

以下哪一行可以将代碼中注釋部分實作？

position = position;
position = this.position;
this.position = position;
this.position = this.position;

Static vs. instance

假設我們想到記錄和

Tortoise

類及對象有關的資訊，下面哪一個聲明是合理的？

記錄有多少個對象已經被建立了：

int numberOfTortoisesInWorld;
static int numberOfTortoisesInWorld;
[ ] 在Java中不能這樣聲明

記錄tortoise對象中shell的顔色：

Color shell;
static Color shell;

對象的母親和父親：

Tortoise mother, father;
static Tortoise mother, father;

可變性

回憶之前我們讨論過的“用快照圖了解值與對象”（譯者注：“Java基礎”），有一些對象的内容是不變的（immutable）：一旦它們被建立，它們總是表示相同的值。另一些對象是可變的（mutable）：它們有改變内部值對應的方法。

String

就是不變對象的一個例子，一個

String

對象總是表示相同的字元串。而

StringBuilder

則是可變的，它有對應的方法來删除、插入、替換字元串内部的字元，等等。

因為

String

是不變的，一旦被建立，一個

String

對象總是有一樣的值。為了在一個

String

對象字元串後加上另一個字元串，你必須建立一個新的

String

對象：

String s = "a";
s = s.concat("b"); // s+="b" and s=s+"b" also mean the same thing

與此相對，

StringBuilder

對象是可變的。這個類有對應的方法來改變對象，而不是傳回一個新的對象：

StringBuilder sb = new StringBuilder("a");
sb.append("b");

是以這有什麼關系呢？在上面這兩個例子中，我們最終都讓

和

sb

索引到了

"ab"

。當對象的索引隻有一個時，它們兩确實沒什麼去呗。但是當有别的索引指向同一個對象時，它們的行為會大不相同。例如，當另一個變量

指向

對應的對象，

tb

sb

對應的對象，這個時候對

tb

做更改就會導緻不同的結果：

String t = s;
t = t + "c";

StringBuilder tb = sb;
tb.append("c");

可以看到，改變

并沒有對

産生影響，但是改變

tb

确實影響到了

sb

——這可能會讓程式設計者驚訝一下（如果他沒有注意的話）。這也是下面我們會重點讨論的問題。

既然我們已經有了不變的

String

類，為什麼還要使用可變的

StringBuilder

類呢？一個常見的使用環境就是當你要同時建立大量的字元串，例如：

String s = "";
for (int i = 0; i < n; ++i) {
    s = s + i;
}

如果使用不變的字元串，這會發生很多“暫時拷貝”——第一個字元“0”實際上就被拷貝了n次，第二個字元被拷貝了n-1次，等等。總的來說，它會花費O(N^2)的時間來做拷貝，即使最終我們的字元串隻有n個字元。

StringBuilder

的設計就是為了最小化這樣的拷貝，它使用了簡單但是聰明的内部結構避免了做任何拷貝（除非到了極限情況）。如果你使用

StringBuilder

，可以在最後用

toString()

方法得到一個

String

的結果：

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
  sb.append(String.valueOf(i));
}
String s = sb.toString();

優化性能是我們使用可變對象的原因之一。另一個原因是為了分享：程式中的兩個地方的代碼可以通過共享一個資料結構進行交流。

Follow me

一個

terrarium

的使用者可以更改紅色的

Turtle

對象嗎？

[ ] 不能，因為到 terrarium 的索引是不變的
[x] 不能，因為 Turtle 對象是不變的
[ ] 可以，因為從清單的0下标處到 Turtle 的索引是可變的。
[ ] 可以，因為 Turtle 對象是可變的

george

的使用者可以更改藍色的

Gecko

george
Gecko
[ ] 可以，因為從清單的1下标處到 Gecko
Gecko

petStore

的使用者可以使得另一個

terrarium

的使用者無法通路藍色的

Gecko

對象嗎？選出最好的答案

terrarium
[ ] 不能，因為 Gecko
[ ] 可以，因為到 petStore 的索引是可變的
PetStore
[x] 可以，因為 List
Gecko

可變性帶來的風險

可變的類型看起來比不可變類型強大的多。如果你在“資料類型商場”購物，為什麼要選擇“無聊的”不可變類型而放棄強大的可變類型呢？例如

StringBuilder

應該可以做任何

String

可以做的事情，加上

set()

append()

這些功能。

答案是使用不可變類型要比可變類型安全的多，同時也會讓代碼更易懂、更具備可改動性。可變性會使得别人很難知道你的代碼在幹嗎，也更難制定開發規定（例如規格說明）。這裡舉出了兩個例子：

#1: 傳入可變對象

下面這個方法将清單中的整數相加求和：

/** @return the sum of the numbers in the list */
public static int sum(List<Integer> list) {
    int sum = 0;
    for (int x : list)
        sum += x;
    return sum;
}

假設現在我們要建立另外一個方法，這個方法将清單中數的絕對值相加，根據DRY原則（Don’t Repeat Yourself），實作者寫了一個利用

sum()

的方法：

/** @return the sum of the absolute values of the numbers in the list */
public static int sumAbsolute(List<Integer> list) {
    // let's reuse sum(), because DRY, so first we take absolute values
    for (int i = 0; i < list.size(); ++i)
        list.set(i, Math.abs(list.get(i)));
    return sum(list);
}

注意到這個方法直接改變了數組 —— 這對實作者來說很合理，因為利用一個已經存在的清單會更有效率。如果這個清單有幾百萬個元素，那麼你節省記憶體的同時也節省了大量時間。是以實作者的理由很充分：DRY與性能。

但是使用者可能會對結果很驚奇，例如：

// meanwhile, somewhere else in the code...
public static void main(String[] args) {
    // ...
    List<Integer> myData = Arrays.asList(-5, -3, -2);
    System.out.println(sumAbsolute(myData));
    System.out.println(sum(myData));
}

Risky #1

上面的代碼會列印出哪兩個數？

讓我們想想這個問題的關鍵點：

遠離bug？在這個例子中，很容易就會把指責轉向 sumAbsolute() 的實作者，因為他可能違背了規格說明。但是，傳入可變對象真的（可能）會導緻隐秘的bug。隻要有一個程式員不小心将這個傳入的清單更改了（例如為了複用或性能），程式就可能會出錯，而且bug很難追查。
易懂嗎？當閱讀 main() 的時候，你會對 sum() sumAbsolute() 做出哪些假設？對于讀者來說，他能清晰的知道 myData 會被更改嗎？

#2: 傳回可變對象

我們剛剛看到了傳入可變對象可能會導緻問題。那麼傳回一個可變對象呢？

Date

是一個Java内置的類，同時

Date

也正好是一個可變類型。假設我們寫了一個判斷春天的第一天的方法：

/** @return the first day of spring this year */
public static Date startOfSpring() {
    return askGroundhog();
}

這裡我們使用了有名的土撥鼠算法 (Harold Ramis, Bill Murray, et al. Groundhog Day, 1993).

現在使用者用這個方法來計劃他們的派對開始時間：

// somewhere else in the code...
public static void partyPlanning() {
    Date partyDate = startOfSpring();
    // ...
}

這段代碼工作的很好。不過過了一段時間，

startOfSpring()

的實作者發現“土撥鼠”被問的不耐煩了，于是打算重寫

startOfSpring()

，使得“土撥鼠”最多被問一次，然後緩存下這次的答案，以後直接從緩存讀取：

/** @return the first day of spring this year */
public static Date startOfSpring() {
    if (groundhogAnswer == null) groundhogAnswer = askGroundhog();
    return groundhogAnswer;
}
private static Date groundhogAnswer = null;

（思考：這裡緩存使用了

private static

修飾符，你認為它是全局變量嗎？）

另外，有一個使用者覺得

startOfSpring()

傳回的日期太冷了，是以他把日期延後了一個月：

// somewhere else in the code...
public static void partyPlanning() {
    // let's have a party one month after spring starts!
    Date partyDate = startOfSpring();
    partyDate.setMonth(partyDate.getMonth() + 1);
    // ... uh-oh. what just happened?
}

（思考：這裡還有另外一個隐秘的bug——

partyDate.getMonth() + 1

，你知道為什麼嗎？）

這兩個改動發生後，你覺得程式會出現什麼問題？更糟糕的是，誰會先發現這個bug呢？是這個

startOfSpring()

，還是

partyPlanning()

？或是在另一個地方使用

startOfSpring()

的無辜者？

Risky #2

我們不知道

Date

具體是怎麼存儲月份的，是以這裡用抽象的值

...march...

...april...

表示，

Date

中有一個

mounth

索引到這些值上。

以下哪一個快照圖表現了上文中的bug？

麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”

Understanding risky example #2

partyPlanning

在不知不覺中修改了春天的起始位置，因為

partyDate

groundhogAnswer

指向了同一個可變

Date

對象。

更糟糕的是，這個bug可能不會在這裡的

partyPlanning()

或

startOfSpring()

中出現。而是在另外一個調用

startOfSpring()

的地方出現，得到一個錯誤的值然後繼續進行運算。

上文中的緩存

groundhogAnswer

是全局變量嗎？

[ ] 是全局變量，這是合理的
[ ] 是全局變量，這是不合理的
[x] 不是全局變量

A second bug

上文中的代碼在加上1月的時候存在另一個bug，請閱讀 Java API documentation for

Date.getMonth

setMonth

對于

partyDate.getMonth()

，它的哪一個傳回值會導緻bug的發生？

NoSuchMonthException

上面關于

Date.setMonth

文檔中說：

month: the month value between 0-11

.那麼當這個bug觸發的時候可能會發生什麼？

[x] 這個方法不會做任何事情
[x] 這個方法會按照我們原本的想法運作
[x] 這個方法會使得 Date 對象不可用，并報告一個錯誤的值
[ ] 這個方法會抛出一個已檢查異常
[x] 這個方法會抛出一個未檢查異常
[x] 這個方法會将時間設定為9/9/99
[x] 這個方法會使得其他的 Date 對象也不可用
[x] 這個方法永遠不會傳回

SuchTerribleSpecificationsException

在關于

Date

的文檔中，有一句話是這樣說的，“傳入方法的參數并不一定要落在指定的區域内，例如傳入1月32号意味着2月1号”。

這看起來像是前置條件...但它不是的！

下面哪一個選項表現了

Date

這個特性是不合理的？

[ ] 不要寫重複的代碼 (DRY)
[x] 快速失敗/報錯
[ ] 土撥鼠算法
[ ] 使用異常報告特殊結果
[ ] 使用前置條件限制使用者

關鍵點：

遠離bug？沒有，我們産生了一個隐晦的bug。
可改動？很顯然，這裡的可改動指的是我們可以改動一部分代碼而不用擔心其他代碼的改動，而不是可變對象本身的可改動性。在上面的例子中，我們在程式的兩個地方做了改變，結果導緻了一個隐晦的bug。

在上面舉出的兩個例子（

List<Integer>

Date

）中，如果我們采用不可變對象，這些問題就迎刃而解了——這些bug在設計上就不可能發生。

事實上，你絕對不應該使用

Date

！而是使用包

java.time

LocalDateTime

Instant

, 等等這些類，它們規格說明都保證了對象是不可變的。

這個例子也說明了使用可變對象可能會導緻性能上的損失。因為為了在不修改規格說明和接口的前提下避開這個bug，我們必須讓

startOfSpring()

傳回一個複制品：

return new Date(groundhogAnswer.getTime());

這樣的模式稱為防禦性複制，我們在後面講抽象資料類型的時候會講解更多關于防禦性複制的東西。這樣的方法意味着

partyPlanning()

可以自由的操控

startOfSpring()

的傳回值而不影響其中的緩存。但是防禦性複制會強制要求

startOfSpring()

為每一個使用者複制相同資料——即使99%的内容使用者都不會更改，這會很浪費空間和時間。相反，如果我們使用不可變類型，不同的地方用不同的對象來表示，相同的地方都索引到記憶體中同一個對象，這樣會讓程式節省空間和複制的時間。是以說，合理利用不變性對象（譯者注：大多是有多個變量索引的時候）的性能比使用可變性對象的性能更好。

别名會讓可變類型存在風險

事實上，如果你隻在一個方法内使用可變類型而且該類型的對象隻有一個索引，這時并不會有什麼風險。而上面的例子告訴我們，如果一個可變對象有多個變量索引到它——這也被稱作“别名”，這時就會有産生bug的風險。

Aliasing 1

以下代碼的輸出是什麼？

List<String> a = new ArrayList<>();
a.add("cat");
List<String> b = a;
b.add("dog");
System.out.println(a);
System.out.println(b);

["cat"]
```
`["cat", "dog"]`
           
```
["cat", "dog"]
```
`["cat", "dog"]`
           
```
["cat"]
```
`["cat"]`
           
```
["dog"]
```
`["dog"]`
           
```

現在試着使用快照圖将上面的兩個例子過一遍，這裡隻列出一個輪廓：

在 List 例子中，一個相同的清單被 list （在 sum sumAbsolute 中）和 myData main 中）同時索引。一個程式員（ sumAbsolute 的）認為更改這個清單是ok的；另一個程式員（ main ）希望清單保持原樣。由于别名的使用， main 的程式員得到了一個錯誤的結果。
而在 Date 的例子中，有兩個變量 groundhogAnswer partyDate 索引到同一個 Date 對象。這兩個别名出現在程式的不同地方，是以不同的程式員很難知道别人會對這個 Date 對象做哪些改變。

先在紙上畫出快照圖，但是你真正的目标應該是在腦海中建構一個快照圖，這樣以後你在看代碼的時候也能将其“視覺化”。

更改參數對象的（mutating）方法的規格說明

從上面的分析來看，我們必須使用之前提到過的格式對那些會更改參數對象的方法寫上特定的規格說明。

下面是一個會更改參數對象的方法：

static void sort(List<String> lst)
- requires:
  nothing
- effects:
  puts lst in sorted order, i.e. lst[i] ≤ lst[j] for all 0 ≤ i < j < lst.size()

而這個是一個不會更改參數對象的方法：

static List<String> toLowerCase(List<String> lst)
- requires:
  nothing
- effects:
  returns a new list t where t[i] = lst[i].toLowerCase()

如果在effects内沒有顯式強調輸入參數會被更改，在本門課程中我們會認為方法不會修改輸入參數。事實上，這也是一個程式設計界的一個約定俗成的規則。

對清單和數組進行疊代

接下來我們會看看另一個可變對象——疊代器。疊代器會嘗試周遊一個聚合類型的對象，并逐個傳回其中的元素。當你在Java中使用

for (... : ...)

這樣的周遊元素的循環時，其實就隐式的使用了疊代器。例如：

List<String> lst = ...;
for (String str : lst) {
    System.out.println(str);
}

會被編譯器了解為下面這樣：

List<String> lst = ...;
Iterator<String> iter = lst.iterator();
while (iter.hasNext()) {
    String str = iter.next();
    System.out.println(str);
}

一個疊代器有兩種方法：

next() 傳回聚合類型對象的下一個元素
hasNext() 測試疊代器是否已經周遊到聚合類型對象的結尾

注意到

next()

是一個會修改疊代器的方法（mutator method），它不僅會傳回一個元素，而且會改變内部狀态，使得下一次使用它的時候會傳回下一個元素。

感興趣的話，你可以讀讀Java API中關于疊代器的定義 .

`MyIterator`

為了更好的了解疊代器是如何工作的，這裡有一個

ArrayList<String>

疊代器的簡單實作：

/**
 * A MyIterator is a mutable object that iterates over
 * the elements of an ArrayList<String>, from first to last.
 * This is just an example to show how an iterator works.
 * In practice, you should use the ArrayList's own iterator
 * object, returned by its iterator() method.
 */
public class MyIterator {

    private final ArrayList<String> list;
    private int index;
    // list[index] is the next element that will be returned
    //   by next()
    // index == list.size() means no more elements to return

    /**
     * Make an iterator.
     * @param list list to iterate over
     */
    public MyIterator(ArrayList<String> list) {
        this.list = list;
        this.index = 0;
    }

    /**
     * Test whether the iterator has more elements to return.
     * @return true if next() will return another element,
     *         false if all elements have been returned
     */
    public boolean hasNext() {
        return index < list.size();
    }

    /**
     * Get the next element of the list.
     * Requires: hasNext() returns true.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @return next element of the list
     */
    public String next() {
        final String element = list.get(index);
        ++index;
        return element;
    }
}

MyIterator

使用到了許多Java的特性，例如構造體，static和final變量等等，你應該確定自己已經了解了這些特性。參考： From Python to Java 或 Classes and Objects in the Java Tutorials

上圖畫出了

MyIterator

初始狀态的快照圖。

注意到我們将

list

的索引用雙箭頭表示，以此表示這是一個不能更改的final索引。但是list索引的

ArrayList

本身是一個可變對象——内部的元素可以被改變——将

list

聲明為final并不能阻止這種改變。

那麼為什麼要使用疊代器呢？因為不同的聚合類型其内部實作的資料結構都不相同（例如連接配接連結清單、哈希表、映射等等），而疊代器的思想就是提供一個通路元素的通用中間件。通過使用疊代器，使用者隻需要用一種通用的格式就可以周遊通路聚合類的元素，而實作者可以自由的更改内部實作方法。大多數現代語言（Python、C#、Ruby）都使用了疊代器。這是一種有效的設計模式（一種被廣泛測試過的解決方案）。我們在後面的課程中會看到很多其他的設計模式。

MyIterator.next signature

疊代器的實作中使用到了執行個體方法（instance methods），執行個體方法是在一個執行個體化對象上進行操作的，它被調用時會傳入一個隐式的參數

this

（就像Python中的

self

一樣），通過這個

this

該方法可以通路對象的資料（fields）。

我們首先看看

MyIterator

中的

next

public class MyIterator {

    private final ArrayList<String> list;
    private int index;

    ...

    /**
     * Get the next element of the list.
     * Requires: hasNext() returns true.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @return next element of the list
     */
    public String next() {
        final String element = list.get(index);
        ++index;
        return element;
    }
}

next

的輸入是什麼類型？

void – 沒有輸入
ArrayList
MyIterator
String
boolean
int

next

的輸出是什麼類型？

void – 沒有輸出
ArrayList
MyIterator
String
boolean
int

MyIterator.next precondition

next

有前置條件

requires: hasNext() returns true.

next

的哪一個輸入被這個前置條件所限制？

[ ] 都沒有被限制
this
hasNext
element

目前置條件不滿足時，實作的代碼可以去做任何事。具體到我們的實作中，如果前置條件不滿足，代碼會有什麼行為？

[ ] 傳回 null
[ ] 傳回清單中其他的元素
[ ] 抛出一個已檢查異常
[x] 抛出一個非檢查異常

MyIterator.next postcondition

next

的一個後置條件是

@return next element of the list

next

的哪一個輸出被這個後置條件所限制？

this
hasNext
[x] 傳回值

next

的另外一個後置條件是

modifies: this iterator to advance it to the element following the returned element.

什麼會被這個後置條件所限制？

this
hasNext
[ ] 傳回值

可變性對疊代器的損害

現在讓我們試着将疊代器用于一個簡單的任務。假設我們有一個MIT的課程代号清單，例如

["6.031", "8.03", "9.00"]

，我們想要設計一個

dropCourse6

方法，它會将清單中所有以“6.”開頭的代号删除。根據之前所說的，我們先寫出如下規格說明：

/**
 * Drop all subjects that are from Course 6. 
 * Modifies subjects list by removing subjects that start with "6."
 * 
 * @param subjects list of MIT subject numbers
 */
public static void dropCourse6(ArrayList<String> subjects)

dropCourse6

顯式的強調了它會對參數

subjects

做修改。

接下來，根據測試優先程式設計的原則，我們對輸入空間進行分區，并寫出了以下測試用例：

// Testing strategy:
//   subjects.size: 0, 1, n
//   contents: no 6.xx, one 6.xx, all 6.xx
//   position: 6.xx at start, 6.xx in middle, 6.xx at end

// Test cases:
//   [] => []
//   ["8.03"] => ["8.03"]
//   ["14.03", "9.00", "21L.005"] => ["14.03", "9.00", "21L.005"]
//   ["2.001", "6.01", "18.03"] => ["2.001", "18.03"]
//   ["6.045", "6.031", "6.813"] => []

最後，我們實作

dropCourse6

public static void dropCourse6(ArrayList<String> subjects) {
    MyIterator iter = new MyIterator(subjects);
    while (iter.hasNext()) {
        String subject = iter.next();
        if (subject.startsWith("6.")) {
            subjects.remove(subject);
        }
    }
}

但是當我們測試的時候，最後一個例子報錯了：

// dropCourse6(["6.045", "6.031", "6.813"])
//   expected [], actual ["6.031"]

dropCourse6

似乎沒有将清單中的元素清空，為什麼？為了追查bug是在哪發生的，我們建議你畫出一個快照圖，并逐漸模拟程式的運作。

Draw a snapshot diagram

現在畫出一個初始（代碼未執行）快照圖。你需要參考上面

MyIterator

類和

dropCourse6()

方法的代碼實作。

在你的初始快照圖中有哪些标簽？

iter
index
list
subjects
subject
ArrayList
List
MyIterator
String
dropCourse6

現在執行第一條語句

MyIterator iter = new MyIterator(subjects);

，你的快照圖中又有哪些标簽？

iter
index
list
subjects
subject
ArrayList
List
MyIterator
String
dropCourse6

Entering the loop

現在執行接下來的語句

String subject = iter.next()

.，你的快照圖中添加了什麼東西？

[ ] 一個從 subject 到ArrayList 下标的箭頭
subject 1
index 到的箭頭
[x] 一個從 index 1

這個時候

subject.startsWith("6.")

傳回是什麼？

[x] 真，因為 subject 索引到了字元串 "6.045"
[ ] 真，因為 subject "6.031"
subject "6.813"
[ ] 假，因為 subject 索引到了其他字元串

Remove an item

現在畫出在

subjects.remove(subject)

語句執行後的快照圖。

現在ArrayList

subjects

是什麼樣子？

[ ] 下标0對應 "6.045"
[x] 下标0對應 "6.031"
"6.813"
[ ] 沒有下标0
[ ] 下标1對應 "6.045"
"6.031"
[x] 下标1對應 "6.813"
[ ] 沒有下标1
[ ] 下标2對應 "6.045"
"6.031"
"6.813"
[x] 沒有下标2

Next iteration of the loop

現在進行下一次循環，執行語句

iter.hasNext()

String subject = iter.next()

，此時

subject.startsWith("6.")

的傳回是什麼？

subject "6.045"
subject "6.031"
subject "6.813"
subject

在這個測試用例中，哪一個ArrayList中的元素永遠不會被

MyIterator.next()

傳回？

"6.045"
"6.031"
"6.813"

如果你想要解釋這個bug是如何發生的，以下哪一些聲明會出現在你的報告裡？

list subjects 是一對别名，它們都指向同一個 ArrayList 對象.
[x] 一個清單在程式的兩個地方被使用别名，當一個别名修改清單時，另一個别名處不會被告知。
[ ] 代碼沒有檢查清單中奇數下标的元素。
MyIterator 在疊代的時候是假設疊代對象不會發生更改的。

其實，這并不是我們設計的

MyIterator

帶來的bug。Java内置的

ArrayList

疊代器也會有這樣的問題，在使用

for

周遊循環這樣的文法糖是也會出現bug，隻是表現形式不一樣，例如：

for (String subject : subjects) {
    if (subject.startsWith("6.")) {
        subjects.remove(subject);
    }
}

這段代碼會抛出一個

ConcurrentModificationException

異常，因為這個疊代器檢測到了你在對疊代對象進行修改（你覺得它是怎麼檢測到的？）。

那麼應該怎修改這個問題呢？一個方法就是使用疊代器的

remove()

方法（而不是直接操作疊代對象），這樣疊代器就能自動調整疊代索引了：

Iterator iter = subjects.iterator();
while (iter.hasNext()) {
    String subject = iter.next();
    if (subject.startsWith("6.")) {
        iter.remove();
    }
}

事實上，這樣做也會更有效率，因為

iter.remove()

知道要删除的元素的位置，而

subjects.remove()

對整個聚合類進行一次搜尋定位。

但是這并沒有完全解決問題，如果有另一個疊代器并行對同一個清單進行疊代呢？它們之間不會互相告知修改！

Pick a snapshot diagram

以下哪一個快照圖描述了上面所述并行bug的發生？

麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”
麻省理工18年春軟體構造課程閱讀08“可變性與不變性”

變化與契約（contract）

可變對象會使得契約（例如規格說明）變得複雜

這也是使用可變資料結構的一個基本問題。一個可變對象有多個索引（對于對象來說稱作“别名”）意味着在你程式的不同位置（可能分布很廣）都依賴着這個對象保持不變。

為了将這種限制放到規格說明中，規格不能隻在一個地方出現，例如在使用者的類和實作者的類中都要有。現在程式正常運作依賴着每一個索引可變對象的人遵守相應制約。

作為這種非本地制約“契約”，想想Java中的聚合類型，它們的文檔都清楚的寫出來使用者和實作者應該遵守的制約。試着找到它對使用者的制約——你不能在疊代一個聚合類時修改其本身。另外，這是哪一層類的責任？

Iterator

List

Collection

? 你能找出來嗎？

同時，這樣的全局特性也會使得代碼更難讀懂，并且正确性也更難保證。但我們不得不使用它——為了性能或者友善——但是我們也會為安全性付出巨大的代價。

可變對象降低了代碼的可改動性

可變對象還會使得使用者和實作者之間的契約更加複雜，這減少了實作者和使用者改變代碼的自由度。這裡舉出了一個例子。

下面這個方法在MIT的資料庫中查找并傳回使用者的9位數ID：

/**
 * @param username username of person to look up
 * @return the 9-digit MIT identifier for username.
 * @throws NoSuchUserException if nobody with username is in MIT's database
 */
public static char[] getMitId(String username) throws NoSuchUserException {        
    // ... look up username in MIT's database and return the 9-digit ID
}

假設有一個使用者：

char[] id = getMitId("bitdiddle");
System.out.println(id);

現在使用者和實作者都打算做一些改變：使用者覺得要照顧使用者的隐私，是以他隻輸出後四位ID：

char[] id = getMitId("bitdiddle");
for (int i = 0; i < 5; ++i) {
    id[i] = '*';
}
System.out.println(id);

而實作者擔心查找的性能，是以它引入了一個緩存記錄已經被查找過的使用者：

private static Map<String, char[]> cache = new HashMap<String, char[]>();

public static char[] getMitId(String username) throws NoSuchUserException {        
    // see if it's in the cache already
    if (cache.containsKey(username)) {
        return cache.get(username);
    }

    // ... look up username in MIT's database ...

    // store it in the cache for future lookups
    cache.put(username, id);
    return id;
}

這兩個改變導緻了一個隐秘的bug。如上圖所示，當使用者查找

"bitdiddle"

并得到一個字元數組後，實作者也緩存的是這個數組，他們兩個實際上索引的是同一個數組（别名）。這意味着使用者用來保護隐私的代碼會修改掉實作者的緩存，是以未來調用

getMitId("bitdiddle")

并不會傳回一個九位數，例如 “928432033” ，而是修改後的 “*****2033”。

共享可變對象會增加契約的複雜度，想想，如果這個錯誤被交到了“軟體工程法庭”審判，哪一個人會為此承擔責任呢？是修改傳回值的使用者？還是沒有儲存好傳回值的實作者？

下面是一種寫規格說明的方法：

public static char[] getMitId(String username) throws NoSuchUserException 
- requires:
  nothing
- effects:
  returns an array containing the 9-digit MIT identifier of username, or throws NoSuchUserException if nobody with username is in MIT’s database. Caller may never modify the returned array.

這是一個下下策這樣的制約要求使用者在程式中的所有位置都遵循不修改傳回值的規定！并且這是很難保證的。

下面是另一種寫規格說明的方法：

public static char[] getMitId(String username) throws NoSuchUserException 
- requires:
  nothing
- effects:
  returns a new array containing the 9-digit MIT identifier of username, or throws NoSuchUserException if nobody with username is in MIT’s database.

這也沒有完全解決問題. 雖然這個規格說明強調了傳回的是一個新的數組，但是誰又知道實作者在緩存中不是也索引的這個新數組呢？如果是這樣，那麼使用者對這個新數組做的更改也會影響到未來的使用。This spec at least says that the array has to be fresh. But does it keep the implementer from holding an alias to that new array? Does it keep the implementer from changing that array or reusing it in the future for something else?

下面是一個好的多的規格說明：

public static String getMitId(String username) throws NoSuchUserException
- requires:
  nothing
- effects:
  returns the 9-digit MIT identifier of username, or throws NoSuchUserException if nobody with username is in MIT’s database.

通過使用不可變類型String，我們可以保證使用者和實作者的代碼不會互相影響。同時這也不依賴使用者認真閱讀遵守規格說明。不僅如此，這樣的方法也給了實作者引入緩存的自由。

給出以下代碼：

public class Zoo {
    private List<String> animals;

    public Zoo(List<String> animals) {
        this.animals = animals;
    }

    public List<String> getAnimals() {
        return this.animals;
    }
}

Aliasing 2

下面的輸出會是什麼？

List<String> a = new ArrayList<>();
a.addAll(Arrays.asList("lion", "tiger", "bear"));
Zoo zoo = new Zoo(a);
a.add("zebra");
System.out.println(a);
System.out.println(zoo.getAnimals());

["lion", "tiger", "bear", "zebra"]

`["lion", "tiger", "bear", "zebra"]`

["lion", "tiger", "bear", "zebra"]

`["zebra", "lion", "tiger", "bear", "zebra"]`

["lion", "tiger", "bear"]

`["lion", "tiger", "bear", "zebra"]`

["lion", "tiger", "bear", "zebra"]
```
`["lion", "tiger", "bear"]`
           
```

Aliasing 3

接着上面的問題，下面的輸出會是什麼？

List<String> b = zoo.getAnimals();
b.add("flamingo");
System.out.println(a);

["lion", "tiger", "bear"]
["lion", "tiger", "bear", "zebra"]
["lion", "tiger", "bear", "zebra", "flamingo"]
["lion", "tiger", "bear", "flamingo"]

有用的不可變類型

既然不可變類型避開了許多危險，我們就列出幾個Java API中常用的不可變類型：

所有的原始類型及其包裝都是不可變的。例如使用 BigInteger BigDecimal 進行大整數運算。
不要使用可變類型 Date ，而是使用 java.time 中的不可變類型。
Java中常見的聚合類 — List Set Map — 都是可變的： ArrayList HashMap 等等。但是 Collections 類中提供了可以獲得不可修改版本（unmodifiable views）的方法：
- Collections.unmodifiableList
- Collections.unmodifiableSet
- Collections.unmodifiableMap
你可以将這些不可修改版本當做是對list/set/map做了一下包裝。如果一個使用者索引的是包裝之後的對象，那麼 add remove put 這些修改就會觸發 UnsupportedOperationException
異常。

當我們要向程式另一部分傳入可變對象前，可以先用上述方法将其包裝。要注意的是，這僅僅是一層包裝，如果你不小心讓别人或自己使用了底層可變對象的索引，這些看起來不可變對象還是會發生變化！
Collections 也提供了擷取不可變空聚合類型對象的方法，例如 Collections.emptyList

List<String> arraylist = new ArrayList<>();
arraylist.add("hello");
List<String> unmodlist = Collections.unmodifiableList(arraylist);
// unmodlist should now always be [ "hello" ]

Unmodifiable

會出現什麼類型的錯誤？

unmodlist.add("goodbye");
System.out.println(unmodlist);

動态錯誤

Unmodifiable?

輸出是什麼？

arraylist.add("goodbye");
System.out.println(unmodlist);

[ “hello” “goodbye” ]

Immutability

以下哪些選項是正确的？

[ ] 如果一個類的所有索引都被final修飾，它就是不可變的
[x] 如果一個類的所有執行個體化資料都不會改變，它就是不可變的
[x] 不可變類型的資料可以被安全的共享
[ ] 通過使用防禦性複制，我們可以讓對象變成不可變的
[ ] 不可變性使得我們可以關注于全局而非局部代碼

總結

在這篇閱讀中，我們看到了利用可變性帶來的性能優勢和友善，但是它也會産生很多風險，使得代碼必須考慮全局的行為，極大的增加了規格說明設計的複雜性和代碼編寫、測試的難度。

確定你已經了解了不可變對象（例如

String

）和不可變索引（例如

final

變量）的差別。畫快照圖能夠幫助你了解這些概念：其中對象用圓圈表示，如果是不可變對象，圓圈有兩層；索引用一個箭頭表示，如果索引是不可變的，用雙箭頭表示。

本文最重要的一個設計原則就是不變性：盡量使用不可變類型和不可變索引。接下來我們還是将本文的知識點和我們的三個目标聯系起來：

遠離bug.不可變對象不會因為别名的使用導緻bug，而不可變索引永遠指向同一個對象，也會減少bug的發生。
易于了解. 因為不可變對象和索引總是意味着不變的東西，是以它們對于讀者來說會更易懂——不用一邊讀代碼一邊考慮這個時候對象或索引發生了哪些改動。
可改動性. 如果一個對象或者索引不會在運作時發生改變，那麼依賴于這些對象的代碼就不用在其他代碼更改後進行審查。