0.Outline
第六章為Abstract Data Type，主要介紹抽象資料類型的基本概念、操作的類型、表示獨立性與表示洩露、表示不變量RI、表示空間與抽象空間、抽象函數AF，以及如何在注釋中寫明RI、AF
1.ADT概述
對于ADT我們并不陌生，從資料結構開始就有了關于ADT的種種說法。ADT作為面向對象的一個重要概念，與面向過程中資料與操作混合的思路相差別，我們可以說ADT是資料和操作的封裝。但事實上，ADT的作用更在于将頂層功能與底層實作分離。
舉個例子，我們都熟知布爾代數中的true和false，我們對于true和false的需求僅在于用true和false表示某種狀态，比如開、關，并使用在其上定義的操作，比如or、and等，但我們對于true和false在計算機中實際的實作方式并不感興趣。在Java中，true和false可以被定義為boolean類型，C中true被定義為非0，false被定義為0，我們甚至可以使用字元串“true”和“false”來定義二者，無論底層實作如何，隻需要保持頂層的功能不變即可。
這就是為什麼“ADT是由操作定義的”。
2.ADT類型及其操作
2.1.ADT的四種操作
對于在ADT上定義的運算，也就是ADT的方法，可以視為ADT克林閉包上定義的某種映射或關系（具體請參考《離散數學》）。ADT的操作具體可以有很多個，但其類型無外乎以下四種：
①構造器Creator：Creator是指建立ADT的一類方法，這類方法可以是每個class中首先要寫的構造函數，也可以是靜态工廠化方法。這類方法可以使用一個或多個其他ADT的執行個體進行構造，但是不能使用自身來産生自身，這是其與Producer相差別的點。其形式化表示如下所示：
上式将Creator視為一個從其他ADT的執行個體 t 的克林閉包到目标ADT的執行個體T的映射
②生産器Producer：Producer與Creator具有一定的相似性，都是産生一個目标ADT的執行個體，但二者的差別在于Producer必須以一個目标ADT的執行個體為輸入。其形式化表示如下所示：
可以看到，與Creator不同，Producer需要一個目标ADT執行個體的正閉包作為輸入
③觀察器Obeserver：Obeserver顧名思義，就是傳回目标ADT在某一時刻某個特定狀态的方法，比如常見的getName、getSize等都屬于Obeserver方法，Obeserver方法的輸入一般情況下為空，但也有特例。其形式化表示如下所示：
④變值器Mutator：Mutator顧名思義，就是通過輸入對目标ADT執行個體的狀态進行改變，一般情況下Mutator的傳回值是void或boolean。其形式化表示如下所示：
2.2.兩種ADT：Mutable vs Immutable
上文中我們也簡單介紹過mutable和immutable的概念，Mutable指的是“值”可以改變，Immutable指的就是“值”不可變。
對于ADT而言，上述概念的了解就是其字面含義“值可變”或“值不可變”，“值可變”的Mutable類型容易了解和實作，畢竟運動是絕對的，靜止是相對的，稍微動一下值就變了。
注意到：這裡的“值可變”指的是整個ADT的所有成員變量的值，範圍還是很大的。
如何讓ADT的值保持不變還是有點挑戰的，形式上，我們可以通過将全部成員變量定義為private來防止ADT外部對成員變量值的改變；然後再不提供Mutator類方法以防止ADT外通過方法對ADT成員變量值進行改變；還可以使用final關鍵字讓ADT中的值是不可變的。如下圖例子所示，上述步驟完成後，ADT貌似就已經“不可變了”
看着貌似還挺不錯，但事實上，注意charAt方法，該方法直接将a的位址傳出（引用資料類型傳遞的是位址），這樣外部得到了a的位址，想對其進行點什麼有意思的操作也就是可能的了，這種情況就叫做表示洩露(rep exposure)，為了防止表示洩露的發生，我們通常要額外注意Creator和Obeserver這兩種方法，因為假如Creator方法是通過外部提供的Mutable類型進行初始化，我們很難保證外部程式不會對這個Mutable類型進行其他的操作，類似地，在Obeserver方法中，我們如果提供ADT内成員變量的位址，同樣很難保證外部程式不會對它做出寫有意思的修改。
對于這種情況，一種直截了當的解決辦法是把這些東西寫在spec中，以甩鍋的方式把這個問題留給client，但由于人性本惡，再精确的spec也不能保證不會有人對程式進行惡意的破壞，同樣地，由于像某位大我們幾旬的老教師那樣科研科研不行、教學教學不行的人也不在少數，我們也不能保證client有閱讀并正确了解spec的能力，是以說這種方法還不是很OK的。
比較OK的方法就是靠人不如靠自己，上文中造成表示洩露的原因就是ADT中直接使用外部程式提供的引用或将自身成員變量的引用提供給了外界，而這種情況我們完全可以避免，比如在傳回時，我們可以重新建立一個執行個體并将其傳回給client，這種方法叫做defensive copy。
3.RI與AF
這一段同學們普遍看着比較蒙，但這段内容其實并不難，隻不過是PPT上不怎麼說人話，這段搞明白了考試20+到手，有挂科風險的同學可以先看這段（不過u1s1這門課真不太容易挂科）。
PPT上和實驗中經常讓人迷惑的無外乎這幾個概念：RI、AF、rep，下面我們來細掰扯掰扯這幾個概念。
首先，就像上文提到的一樣，ADT存在的意義就是在于在底層資料和頂層操作之間形成一定的隔離，讓client使用ADT的功能即可，不要知道ADT是怎麼實作的，這就好比某些同學考試隻寫個結果，步驟一點都不寫，然後跟老師說：“我寫出來結果就行了呗，你非得讓我寫出來我怎麼算的幹啥”，這些同學應該會很喜歡面向對象的程式設計方法。
按照這個思路，就形成了下圖所示的結構，ADT成為了使用者與開發者之間的屏障（沒有這道屏障開發者寫的翔山被使用者看見了也不太好）
ADT這個圈，也就将一個空間分為了兩個部分：使用者可見的部分和僅開發者可見的部分。
使用者可見的部分叫做抽象空間 A ，因為這個空間中所有的概念都是抽象而成的，與底層實作無關，就好比你覺得你在用Boolean，這個“你覺得的Boolean”就是抽象空間的内容，換句話說抽象空間其實就是開發者給使用者形成的“假象”，開發者讓使用者覺得這個東西是這麼回事，但實際未必
僅開發者可見的這部分空間就叫做表示空間 R ，也就是我們常說的rep，這部分是ADT底層真正的實作，就比如我上文提到的Boolean，ADT中可能就是用String來實作的，String它就對應于表示空間。
說到現在，你應該已經了解了第一個概念：rep，下面我們來說另外兩個
現在我們有了兩個空間，表示空間 R 和抽象空間 A，還是以上文中的Boolean為例，String為表示空間的内容，Boolean為抽象空間中的内容。顯然，二者是存在着某種聯系的，我們在ADT中需要一個String類型的成員變量來代表true，也需要一個String來代表false，這種所謂的“代表”其實就是一種映射關系，而這種将表示空間中的内容映射到抽象空間中的内容的映射，就稱為抽象函數(Abstract Function, AF)。
換句話說，抽象函數AF描述了表示空間與抽象空間中值的對應關系，這個映射不一定是單射，但一定是滿射。這個概念在我們目前的例子中也好了解，你總不能給使用者提供一個隻有true沒有false的Boolean類型變量吧（不過這也是件好事，比如老師批卷時候）。注意到：AF并不是給使用者看的，它是寫在ADT内部給開發者看的，因為你并不想讓使用者知道你底層代碼寫的有多爛。
好，經過我這麼一番講解（扯淡）後，你應該已經了解了AF和rep，下面來說最後一個概念RI
其實順着剛才的思路走，AF是一個函數，它值域已經給定了（使用者需求确定AF的值域），那是不是也得有個定義域呀，RI就是來确定這個定義域的。還繼續我們上文的例子，所有String構成的集合理論上講是一個可數無限集，那麼問題來了，值域Boolean好像隻有兩個呀。那麼我們就需要對String這個集合進行限定，規定出哪些值對于AF來說是合法的，也就規定了AF的定義域，這就是RI的功能。
OK，說了這麼多，最後都不考，考的東西是讓你怎麼寫（填選可能會考定義）：
這個是我寫的RI和AF，其實剛才說了那麼多，最後落到筆頭還是挺容易的，AF就是把你各個成員變量都是幹嘛的、這個ADT是幹嘛的寫清楚；RI說白了就是讓你把成員變量取值範圍寫清楚。然後後面還有個Safety from rep exposure，這個也好說，也是随便說說你怎麼保證不會發生表示洩露的。
最後，注意到：不要将RI、AF、SRP(Safety from rep exposure)與spec搞混，RI、AF、SRP是針對ADT說的，spec是針對方法說的，一定不要搞混。
這章要說的基本上說完了，最後祝願被某位大我們幾旬的老教師折磨的同學們早日擺脫魔爪，考試考出個好成績，評教時候千萬别忘了要如實評價啊！