抽象数据类型 (ADT)
6 抽象数据类型 (ADT)
抽象数据类型与表示独立性:如何设计良好的抽象数据结构,通过封装来避免客户端获取数据的内部表示(即“表示泄露”),避免潜在 的bug——在client和implementer之间建立“防火墙”
ADT的特性:表示泄漏、抽象函数AF、表示不变量RI
基于数学的形式对ADT的这些核心特征进行描述并应用于设计中。
Abstraction and User-Defined Types
除了编程语言所提供的基本数据类型和对象数据类型,程序员可定义自己的数据类型
数据抽象:由一组操作所刻画的数据类型
传统的类型定义:关注数据的具体表示
抽象类型:强调“作用于数据上的操作”,程序员和 client无需关心数据如何具体存储的,只需设计/使用操作即可
ADT是由操作定义的,与其内部如何实现无关!
Classifying Types and Operations
Mutable and immutable types
可变类型的对象:提供了可改变其内部数据的值的操作
不变数据类型: 其操作不改变内部值,而是构造新的对象
Operations
- 构造器
- 生产器
- 观察器
- 变值器
Abstract Data Type Examples
int and String
都是不可变的,没有变值器。


List

Designing an Abstract Type
设计好的ADT,靠“经验法则”,提供一组操作,设计其行为规约 spec
Rules:
- 设计简洁、一致的操作
- 要足以支持client对数据所做的所有操作需要,且用操作满足client需要的难度要低
Representation Independence
表示独立性:client使用ADT时无需考虑其内部如何实现,ADT内部表示的变化不应影响外部spec和客户端。
Testing an Abstract Data Type
测试creators, producers, and mutators:调用 observers 来观察这些 operations 的结果是否满足spec;
测试observers:调用creators, producers, and mutators等方法产生或改变对象,来看结果是否正确。
风险:如果被依赖的其他方法有错误,可能导致被测试方法的测试结果失效。
Invariants
不变量:在任何时候总是true
immutability就是一个典型的“不变量”
由ADT来负责其不变量,与client端的任何行为无关
可以使用 private 和 final 关键字来进行限制
Rep Invariant and Abstraction Function

R: the space of representation values (rep values) consists of the values of the actual implementation entities.
A: the space of abstract values consists of the values that the type is designed to support. client看到和使用的值
Every abstract value is mapped to by some rep value (surjective, 满射).
Some abstract values are mapped to by more than one rep value (not injective, 未必单射).
Not all rep values are mapped (not bijective, 未必双射)
Abstraction Function
抽象函数:R和A之间映射关系的函数,即如何去解释R中的每一个值为A中的每一个值。
Rep Invariant
表示不变性RI:某个具体的“表示”是否是“合法的”
也可将RI看作:所有表示值的一个子集,包含了所有合法的表示值
也可将RI看作:一个条件,描述了什么是“合法”的表示值
Both the rep invariant and the abstraction function should be documented in the code, right next to the declaration of the rep itself:

The abstract value space alone doesn’t determine AF or RI
设计ADT:
- 选择R和A;
- RI —- 合法的表示值;
- 如何解释合法的表示值 —-映射AF 做出具体的解释:每个rep value如何映射到abstract value
在所有可能改变rep的方法内都要检查
Observer方法可以不用,但建议也要检查,以防止你的“万一”
- Calling checkRep() in every method, including observers, means you’ll be more likely to catch rep invariant violations caused by rep exposure.
Beneficent mutation
对immutable的ADT来说,它在A空间的abstract value应是不变的。但其内部表示的R空间中的取值则可以是变化的。这种变化称为有益的可变性(Beneficent mutation)
Documenting the AF, RI, and Safety from Rep Exposure
在代码中用注释形式记录AF和RI
要精确的记录RI:rep中的所有fields何为有效
要精确记录AF:如何解释每一个R值
Another piece of documentation is a rep exposure safety argument 表示泄漏的安全声明
给出理由,证明代码并未对外泄露其内部表示——自证清白

ADT的规约里只能使用client可见的内容来撰写,包括参数、返回值、异常等。如果规约里需要提及“值”,只能使用A空间中的“值”。ADT的规约里也不应谈及任何内部表示的细节,以及R空间中的任何值,ADT的内部表示(私有属性)对外部都应严格不可见。故在代码中以注释的形式写出AF和RI而不能在Javadoc文档中,防止被外部看到而破坏表示独立性/信息隐藏。
在对象的初始状态不变量为true,在对象发生变化时,不变量也要为true。即:
- 构造器和生产器在创建对象时要确保不变量为true
- 变值器和观察器在执行时必须保持不变性。
- 在每个方法return之前,用checkRep()检查不变量是否得以保持。
ADT invariants replace preconditions
用ADT不变量取代复杂的Precondition,相当于将复杂的precondition封装到了ADT内部。
