@TOC

一、抽象和用户定义类型

除了编程语言所提供的基本数据类型和对象数据类型，程序员可定义自己的数据类型。

传统的类型定义：关注数据的具体表示。
抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。

二、分类类型和操作

对抽象类型的操作进行分类：
（1）构造器创造这种类型的新对象（构造器：可能实现为构造函数或静态函数）
（2）生产器从该类型的旧对象创建新对象。
（3）观察器接受抽象类型的对象并返回不同类型的对象。
（4）变值器，改变对象属性的方法（通常返回void）

例子：

被静态方法实现的构造器常常被叫做工厂方法。

三、抽象数据类型示例

int和String：

List：

四、设计抽象类型

设计好的ADT，靠“经验法则”，提供一组操作，设计其行为规约 spec。

规则：
（1）设计简洁、一致的操作
（2）要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低。

五、表示独立性

表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端。

除非ADT的操作指明了具体的pre-和post-condition，否则不能改变ADT的内部表示——spec规定了client和implementer之间的契约。

六、测试一个抽象数据类型

（1）测试creators, producers, and mutators：调用observers来观察这些operations的结果是否满足spec；
（2）测试observers：调用creators, producers, and mutators等方法产生或改变对象，来看结果是否正确。
风险：如果被依赖的其他方法有错误，可能导致被测试方法的测试结果失效。

七、不变量

好的抽象数据类型最重要的特性是它保持自己的不变量。不变量：在任何时候总是true。例如：immutability就是一个典型的“不变量”。
由ADT来负责其不变量，与client端的任何行为无关

为什么需要不变量：保持程序的“正确性”，容易发现错误。

总是要假设client有“恶意”破坏ADT的不变量—defensive programming

表示泄露不仅影响不变性，也影响了表示独立性：无法在不影响客户端的情况下改变其内部表示。
除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自己的invariants，并避免“表示泄露”。最好的办法就是使用immutable的类型，彻底避免表示泄露

保持不变性和避免表示泄漏，是ADT最重要的一个Invariant！

八、Rep Invariant and Abstraction Function

R:表示空间(代表值)由实际实现实体的值组成。
A：抽象值构成的空间：client看到和使用的值

ADT开发者关注表示空间R，client关注抽象空间A

R和A之间的映射：必然是满射、未必是单射、未必是双射

抽象函数：R和A之间映射关系的函数，即如何去解释R中的每一个值为A中的每一个值。
AF : R → A

表示不变性RI：某个具体的“表示”是否是“合法的”；也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值；也可将RI看作：一个条件，描述了什么是“合法”的表示值

如何确定AF和RI
选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值。

即使是同样的R、同样的RI，也可能有不同的AF，即“解释不同”。

checkRep()例子：

在所有可能改变rep的方法内都要检查， Observer方法可以不用，但建议也要检查，以防止你的“万一”

十、记录AF, RI和Rep暴露的安全性

在代码中用注释形式记录AF和RI
要精确的记录RI：rep中的所有fields何为有效；要精确记录AF：如何解释每一个R值。



ADT的规约里只能使用client可见的内容来撰写，包括参数、返回值、异常等。 如果规约里需要提及“值”，只能使用A空间中的“值”。