partychicken
Articles12
Tags3
Categories3
抽象数据类型 (ADT)

抽象数据类型 (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

都是不可变的,没有变值器。

image-20220609200207104

image-20220609200215955

List

image-20220609200313155

Designing an Abstract Type

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

Rules:

  1. 设计简洁、一致的操作
  2. 要足以支持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

image-20220609203619895

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:

image-20220611080656778

The abstract value space alone doesn’t determine AF or RI

设计ADT:

  1. 选择R和A;
  2. RI —- 合法的表示值;
  3. 如何解释合法的表示值 —-映射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 表示泄漏的安全声明

给出理由,证明代码并未对外泄露其内部表示——自证清白

image-20220612143727647

ADT的规约里只能使用client可见的内容来撰写,包括参数、返回值、异常等。如果规约里需要提及“值”,只能使用A空间中的“值”。ADT的规约里也不应谈及任何内部表示的细节,以及R空间中的任何值,ADT的内部表示(私有属性)对外部都应严格不可见。故在代码中以注释的形式写出AF和RI而不能在Javadoc文档中,防止被外部看到而破坏表示独立性/信息隐藏。

在对象的初始状态不变量为true,在对象发生变化时,不变量也要为true。即:

  • 构造器和生产器在创建对象时要确保不变量为true
  • 变值器和观察器在执行时必须保持不变性。
  • 在每个方法return之前,用checkRep()检查不变量是否得以保持。

ADT invariants replace preconditions

用ADT不变量取代复杂的Precondition,相当于将复杂的precondition封装到了ADT内部。

image-20220612144457364

Author:partychicken
Link:http://partychicken.github.io/2022/06/14/6%20%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%20(ADT)/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
×