3.3 抽象数据类型(ADT)

一.

  抽象数据类型与表示独立性： 如何设计良好的抽象数据结构，通过封装来避免客户端获取数据的内部表示（即“表示泄露”），避免潜在的 bug 在 client 和 implementer 之间建立“防火墙”。

• ADT 的特性：表示泄漏、抽象函数 AF 、表示不变量 RI
• 基于数学的形式对 ADT 的这些核心特征进行描述并应用于设计中。

二. Abstraction and User Defined Types 抽象与用户定义类型

  数据抽象：由一组操作所刻画的数据类型（而非…)

  传统的类型定义：关注数据的具体表示。

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

1.Classifying Types and Operations

  对于可变和不可变数据类型：可变类型的对象：提供了可改变其内部数据的值的操作；不变数据类型： 其操作不改变内部值，而是构造新的对象。
   构造器：从无到有，构造器：可能实现为构造函数或静态函数，构造器实现的静态方法通常称为工厂方法。
   生产器：从旧到新
   观察器：从旧类型到新类型
   变值器：改变对象属性的方法，通常返回 void。如果返回值为 void ，则必然意
味着它改变了对象的某些内部状态。变值器也可能返回非空类型。

• creator : t* → T
• producer : T+, t* → T
• observer : T+, t* → t
• mutator : T+, t* → void | t | T

2. Abstract Data Type Examples

  略

3. Designing an Abstract Type

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

• 设计简洁、一致的操作
• 要足以支持 client 对数据所做的所有操作需要，且用操作满足 client 需要的难度要低

  基本信息不应太难获得。如 list 的 size 可以循环获得但过麻烦。
  操作集应该是足够的，因为必须有足够的操作来完成客户机可能想要完成的计算。
  一个好的测试是检查是否可以提取类型对象的每个属性。
  如：没有get()操作就无法获取列表的内部数据。

4. Representation Independence

  表示独立性： client 使用 ADT 时无需考虑其内部如何实现，ADT 内部表示的变化不应影响外部 spec 和客户端。例如：例如，List提供的操作独立于List表示为链表还是数组。
  除非 ADT 的操作指明了具体的 pre 和 post condition ，否则不能改变 ADT 的内部表示 spec 规定了 client 和 implementer 之间的契约。

  通过操作访问属性而不是直接访问属性。

5. Testing an Abstract Data Type

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

6. Invariants

  保持不变量
  不变量：在程序运行的任何时候总是 true。例如：immutability 就是一个典型的“不变量”
  由 ADT来负责其不变量，与 client 端的任何行为无关。