【软件构造】课件精译（七）抽象数据类型

一、抽象和用户定义类型

抽象意味着什么
抽象、模块化、封装、信息隐藏、关注点分离（模块具有单独的责任，不要将一个责任分散在不同的模块中）
用户定义类型
数据抽象
数据抽象：一个类型的特征由可对其执行的操作刻画
抽象类型的新颖性和以往不同之处在于对操作的关注

二、类型和操作的分类

可变和不可变数据类型
可变类型的对象可以被修改，是因为提供了可修改其状态的操作。
抽象类型操作的分类
Creators：产生类型的新对象
Producer：在已有对象基础上产生新的对象
Observer：输入抽象类型的对象，返回其他类型的对象
Mutators：改变对象
操作的签名

Creator的签名

Creator通常通过构造函数和静态方法实现。

Mutator的签名
Mutator大多数情况返回值为void，有的时候也是boolean等类型。

三、抽象数据类型举例

举例
int：不可变数据类型，没有mutator函数
List：可变数据类型，接口，有mutator函数
String：不可变数据类型，没有mutator函数
认识Java中的ADT概念

抽象类型是用操作定义的
类型是由其操作集以及规格说明所表征的。

抽象类型的值是不透明的，因为客户端无法检查存储在其中的数据，除非操作允许。 隐藏了数据和实现。

四、设计一个抽象类型

ADT的设计需要选择良好的操作以及确定操作的行为。
规则
设计一组简单操作，通过简单操作的组合实现复杂的操作
操作的行为应是内聚的(单一职责)，某个操作不要包罗万象的将所有特例都考虑进去)
List中不应增加sum方法，缺乏通用性
操作集应该是完备的，覆盖该类型所有应支持的行为（判断方法：检查对象的每个需要被访问到的属性是否都能够被访问到。另外，要提供基本信息的获取方法）
类型不应该混合领域无关的（通用的）和领域特定的特征，例如表示扑克牌序列的牌组类型不应具有接受整数或字符串等任意对象的通用加法方法。

五、表示独立

概念
抽象类型的表示是独立与其表示（真是的数据结构和成员）
只有当我们通过前置条件和后置条件充分明确了ADT的操作，使调用者知道可以依赖哪些内容，实现者知道可以安全更改哪些内容，此时才可以修改内部表示。
举例：不同的字符串表示

如果其内部表示为

private char[] a;

实现如下：

如果是

private char[] a; 
private int start; 
private int end;

什么是表示独立
MyString的现有调用者仅依赖其public方法，而不依赖其private字段，因此我们可以在不检查和更改所有调用者代码的情况下进行更改。

六、测试抽象数据类型

测试方法间不可避免的会相互影响，测试时尽量把独立，不依赖其他操作的且被后面其他方法调用的方法放在前面测试。
划分ADT操作的输入空间

七、不变性

ADT的不变性
好的ADT最重要属性是保持其不变性。
在程序运行过程中，程序始终保持不变的性质，不可变就是不可变类型的重要不变性。ADT自身有责任确保其不变性，而不是依赖于调用者或者其他模块 。
为什么需要不变性？
当ADT保持自己的不变性时，推理代码变得容易得多。
如果您可以指望字符串永远不会改变，那么在调试使用字符串的代码时，或者在尝试为另一个使用字符串的ADT建立不变量时，可以排除这种可能性。与之形成对比的是，字符串类型保证只有当其客户承诺不更改它时，它才是不可变的。然后您必须检查代码中可能使用字符串的所有位置。
要假设用户会有意或者无意地挑战不变性。

八、表示不变性和抽象方法

两种值空间

R：表示空间，实现时用到的值空间
A：抽象值空间，需要支持的值空间
两种空间的例子
抽象类型的实现者只需要关注表示值。以下例子是用String来表示字符集。

这个映射是满射，但未必是单射，所以也未必是双射。
抽象函数：一个从R空间映射到A空间的映射。
表示不变性
RI : R → boolean
RI告诉我们空间R中的r是否被AF映射到了空间A中的某个值。
RI形成了空间R的一个子集(子集中的所有元素均被AF映射到了空间A中)
为RI和AF编写文档

什么决定了AF和RI
AF和 RI 既不由选定的表示值空间决定，也不由抽象值空间单独决定，表示值空间确定后，AF和RI也不是确定的。
比如，我们有同样的R空间，单射可能会有不同的表示不变性。

即使相同的表示值空间和相同的表示不变性RI，我们仍然可以用不同的抽象函数AF来映射。

RI和AF如何影响ADT设计
ADT设计的关键：不仅是选择两个空间(面向规格说明的抽象值空间和面向实现的表示值空间), 而且要决定表示值(RI)和如何映射(AF)。
为其编写注释是很重要的。
举例：


检测表示不变性
在实现中采用断言技术来检查不变性是否保持，可以更早地捕获bug。
应该在所有有create和mutate作用类型方法的最后检查不变性。
在所有方法中调用checkRep() 有助于捕获因为表示泄露造成的不变性错误。
表示中没有Null：x != null check

九、有益的突变

抽象值永远不可改变，在确保其映射的抽象值不变前提下，表示值可以变化。这类改变称作“有益的突变”（Beneficent mutation）。
举例
不要求不含公约数

参与运算时，可以有公约数；显示输出时，需要简化（没有公约数）

另外一种理解：AF是多对一的映射，rep value改变为了“多”中的另外一个。
为什么需要有益的突变： 实现的自由为性能改善提供了可能，例如实现缓存、数据结构重新平衡、惰性计算、惰性清理

十、为AF、RI编写文档并且远离表示泄露

在类中说明AF、RI、不变性，在定义Rep的位置。
表示泄露是指在类的外面可以直接修改内部表示的值。
对表示泄露安全相关的参数，特别是输入参数和返回值，给出保证不泄露内部表示的策略。
为AF和RI编写文档：示例1

为AF和RI编写文档：示例2

如何设置不变性
不变量是整个程序的一个属性，在对象不变量的情况下，它会减少对象的整个生命周期。
设置不变性就要：
在初始化时使之为真，所有修改都使不变性得到保持。在ADT操作中，要保证creators和producers方法必须为新创建的对象建立不变性，mutators和observers必须保持不变性，保证没有表示泄露发生。

十一、ADT不变性替代前置条件

良好设计的ADT，可以替代spec中的部分preconditions。