抽象数据类型(ADT)是对某一类值及其可用操作的数学或逻辑规约。它定义这些操作的含义,但不规定值如何存储,也不规定操作如何实现。例如,栈(数据类型)的特征是后进先出:移除元素时,返回的是最近加入且尚未被移除的元素。至于实现时采用连续数组、链式节点,还是其他表示方式,则是另一个问题。
抽象数据类型是计算机科学和软件工程的基础概念,因为它将组件应履行的职责与履行这些职责所采用的机制分离开来。使用组件的一方可以依据规定的行为来推理组件的运作,而实现者可以改变组件的表示方式,无须使用该组件的程序做出相应修改。这种分离有助于模块化软件构建、对正确性的数学推理、可复用程序库的开发,以及对各种实现的系统比较。
这一术语既用于编程实践,也用于有关规约的数学理论。在实践中,抽象数据类型通常通过接口、文档和行为契约来描述。在形式化处理中,则可以通过方程、数学模型或状态转移关系来规定。这些方法都体现了一个核心区别:抽象类型描述用户可以依赖的行为,而具体实现则提供实现这些行为所需的存储方式和操作过程。
抽象、表示与可观察行为
抽象数据类型规定了一个抽象值域以及该值域上的操作。例如,由集合 中的元素构成的栈,可以建模为由 中的成员组成的有限序列。它的操作可以包括创建空栈、将元素压入栈、查看栈顶元素、移除栈顶元素,以及判断栈是否为空。这个数学序列描述了栈的内容,但不必与程序运行时字节的排列方式相似。
相比之下,数据结构是用于存储和操作数据的具体组织方式。数组(数据结构)和链表是两种不同的表示方式,但都可以用来实现栈。反过来,同一种底层数据结构也可以支持多种抽象类型。链式结构可以实现栈、队列、序列或集合,具体取决于它对外提供哪些操作,以及这些操作保证什么行为。因此,两者并非一一对应:抽象类型并不只是省略了实现细节的数据结构。
这种区别取决于使用方获准观察到什么。两个栈如果包含相同的元素序列,那么通过栈接口通常应当无法区分它们,即使其中一个使用留有空余容量的数组,另一个使用单独分配的节点。未使用的容量、节点地址和内存分配策略都属于表示细节,除非接口明确将其暴露出来。这一思想通常称为观察等价:对于某个特定接口,如果允许的观察无法区分不同实现的抽象行为,那么这些实现就是等价的。
实现之间的差异并不都会自动被隐藏起来。接口可能会暴露对象身份、迭代顺序、异常、资源所有权或时间保证。一旦这些属性成为契约的一部分,即使不同实现返回相同的值,也可能据此加以区分。未规定迭代顺序的集合,比承诺按插入顺序迭代的集合容许更多种实现。同样,压栈操作可能报告“栈已满”的有界栈,其契约也不同于理想化的无界栈。因此,抽象并不意味着忽略所有与实现有关的问题,而是有意识地区分哪些属性已有明确规定,哪些属性仍可由实现自行决定。
历史发展
抽象数据类型源于20世纪60年代和70年代为使大型程序更易于理解、验证和维护而开展的探索。早期编程语言已经支持具名数据类型和过程边界,但这些机制未必能防止使用它们的代码依赖具体的存储布局。例如,记录声明可以为一组字段赋予一个有意义的名称,却仍允许程序的任何部分直接操作这些字段。
戴维·帕纳斯于1972年发表的论文《论将系统分解为模块时应采用的准则》,阐明了以信息隐藏作为模块分解基础的思想。其核心观点是,模块应当隐藏可能发生变化的设计决策,而不应仅仅对应处理流程中的各个步骤。这一原则与抽象数据类型密切相关:集合、数系或符号表的表示方式,都是使用者不应需要了解的设计决策。不过,信息隐藏的范围比抽象数据类型更广,因为模块还可以隐藏算法、设备依赖关系及其他实现选择。
芭芭拉·利斯科夫与斯蒂芬·齐勒斯于1974年发表的论文《使用抽象数据类型编程》,推动了这一概念的明确确立。他们将类型视为一组对象及其配套操作,而这些操作的实现可以独立于其使用而提供。随后,麻省理工学院对CLU编程语言的研究,为数据抽象提供了影响深远的语言机制。CLU的簇将一种表示与获准访问它的操作组织在一起,使抽象边界成为编程语言的一部分,而不再仅仅是文档中的约定。
另一条相关的研究路线发展了用于规约抽象类型的数学方法。约翰·古塔格于1977年发表的论文《抽象数据类型与数据结构的开发》,提出用代数规约将抽象行为与实现开发联系起来。通过描述操作之间相互关系的等式,人们无需选定具体表示,就能陈述类型的性质。后续研究进一步将这些思想发展为规约语言和证明方法。
这些发展与面向对象编程、模块化编程和类型系统的进步相伴而行,而非仅仅发生在它们之后。这些传统相互交叠,却并不相同。对象强调状态、身份以及动态选择的操作三者的结合;抽象数据类型则强调围绕一个值域建立行为边界。现代语言往往将这两种方法结合起来,当今的程序库也继承了上述多条历史脉络中的思想。
操作签名与类型参数
抽象数据类型(ADT)规约的第一层确定可用的操作及其类型。这一层通常称为签名。对于以元素类型 为参数的栈,纯函数式签名可以包含:
这里, 是单元素域,用来表示操作不接受携带实际信息的参数;偏函数箭头则表明,top 和 pop 并非对所有栈都有定义。签名规定了合法调用的形式,但尚未规定后进先出的规则。许多互不相容的行为都可能满足这些输入与输出类型。
操作通常按其与抽象值的关系来分类。构造操作创建值,例如创建一个空集合。观察操作提供信息,例如大小或某个元素是否属于集合。变换操作从已有值推导出新值。在命令式接口中,修改操作会改变已有实例的状态。这些类别只是描述性的划分,并非普遍适用的准则:一个操作可以在返回观察结果的同时改变状态,例如队列操作在移除队首元素的同时将其返回。
类型参数使一份抽象规约能够描述一族类型。只要栈操作不依赖元素的内部属性,整数栈与字符串栈就遵循相同的结构性法则。这是参数多态的一个例子。其他抽象数据类型则需要对参数作出更强的假设。有序集合需要一种序关系;基于哈希的字典需要相互兼容的相等性判断与哈希操作。这些要求应纳入契约,因为正确性可能依赖于它们。
失败行为也是签名及其解释的一部分。对于从空栈移除元素的操作,可以用前置条件禁止这种调用,也可以返回可选结果、返回带标记的错误值,或抛出指定异常。对客户端代码而言,这些选择不能相互替代。同样,接口应当区分字典条目不存在的情况与条目中存储的值恰好为 null 的情况。明确考虑这些情形,才能将一组非正式的操作名称变成可用的契约;不过,仍然需要行为法则来说明各项操作之间的关系。
代数规约与等式
代数规约使用操作和等式来定义抽象类型。这些等式描述了任何有效实现都必须满足的关系。对于栈的签名,典型的定律如下:
这些陈述规定了压入、查看和移除元素等操作之间的相互关系,而不涉及指针、数组索引或内存分配。其中的变量都隐含地在各自适用的域上作全称量化。
这些等式也可以用于符号推理。考虑表达式 。应用 pop–push 定律可消去外层的 push,再应用 top–push 定律即可得到 。这一计算过程不依赖任何实现。这说明,代数规约不仅可用作文档,还可作为证明和测试性质的基础。
这类规约的数学模型为每个类指定一个载体集合,并为每个操作符号指定一个实际函数,且这些指定必须满足规约中的等式。对同一规约采用不同的解释方式,所允许的模型也可能不同。在初始代数解释下,值由构造子项生成,并依据所规定的等式判定哪些值相等。其他方法则着重于所有可用观察下的相等性。这种选择十分重要:一组约束宽松的等式可能允许出现原本无意引入的额外值,或将原本无意视为相等的值等同起来。因此,形式化规约不仅需要关注写出的公理,还需要关注用于解释这些公理的语义。
部分操作会使纯粹基于等式的描述变得复杂。如果 top(empty()) 未定义,仅靠普通等式无法说明程序应如何处理这一表达式。规约可以采用条件等式、显式的有定义性条件、额外的错误值,或返回结果类型的全操作。不同方法会显露出失败的不同方面。
等式方法尤其适合不可变值,因为此时表达式表示的是值,而不会改变外部存储状态。可变状态、对象身份、回调以及效应,都需要额外的建模机制,或对状态作出适当的解释。不过,即使采用可变实现,关于抽象数学值的等式仍然很有价值。对于会修改状态的压栈操作,可以将其规定为把对象的抽象内容从 改为 ,这样既保留了代数描述,又将其与状态变化的具体机制分离开来。
基于模型的契约与状态转换
另一种主要方法是通过数学状态模型及操作契约来描述抽象数据类型。它不以操作表达式之间的等式为主要依据,而是选取一个抽象状态空间,并规定每个操作如何观察或转换该状态。例如,队列可以用有限序列 来建模,入队操作在一端追加元素,出队操作则从另一端移除元素。这里的序列是用于描述规格的工具,并不要求具体实现采用类似序列的表示方式。
对于参数为 的入队操作,可以规定如下后置条件:
其中, 是操作后的状态, 表示序列连接。出队操作可以要求 ,并保证返回值为原序列的首个元素,而新状态为移除首个元素后剩余的后缀序列。这些规定体现了契约式设计:前置条件描述调用时必须满足的要求,后置条件则描述操作成功完成时必须满足的要求。
契约还必须说明操作不会改变什么。通常,查询某个元素是否属于集合的操作应当保持集合的抽象内容不变。在包含多个可变对象的系统中,还可能需要明确一次更新会影响哪些对象。这类框架条件可以防止表面上正确的后置条件容许对其他部分进行任意更改。如果出队操作的规格正确描述了队列,却对无关对象只字未提,那么除非规格框架提供了适当的框架规则,否则这样的规格不足以支持模块化推理。
状态转换规格既可以描述确定性行为,也可以描述非确定性行为。某个操作若从非空集合中移除“某个元素”,就可以允许多种结果,只要被移除的元素属于原集合,且新集合恰好包含其余元素即可。符合规格的实现不必在每次调用时都作出相同选择。这种有意保留选择余地的规定不同于无意的遗漏:它明确界定了允许的结果范围。
异常结束和终止也可以纳入契约。操作可以保证失败时抽象状态保持不变,也可以允许产生文档中明确说明的部分影响。对于阻塞队列,完整的说明可能需要区分立即返回、等待、中断和关闭。这些区分使基于模型的规格非常适合描述那些行为不仅涉及返回值,还涉及可变状态和控制效应的接口。
表示不变式与实现正确性
要实现一个抽象数据类型,程序员需要选择一种具体表示,并确立它与抽象模型之间的对应关系。其中有两个核心概念:表示不变式,用于界定哪些具体状态是有效的;以及抽象函数,用于将这些有效状态映射为抽象值。两者共同搭起了一座桥梁,将实现层面的推理与向使用方承诺的行为联系起来。
考虑一个以数组为底层存储的栈,其表示由数组 和计数 构成。它的表示不变式可以要求 ,并规定有效元素存放在位置 到 上。抽象函数将这一表示映射为序列 ,其中最右端的元素为栈顶。数组中超过 的位置不影响抽象值,但仍可能影响资源管理:在未使用的位置保留引用,可能使原本已不可达的对象在垃圾回收机制下仍然存活。
对于实现抽象操作 的具体操作 ,一个简化的正确性条件是:
其中, 是有效的具体状态, 是抽象函数。这个等式假定操作会改变状态,但未对返回值单独建模;更完整的表述还会关联输出、错误和终止行为。只要前置条件成立,实现就必须保持表示不变式。这种不同层次之间的联系是数据精化的一个实例。
抽象函数通常是多对一的。容量不同的两个数组可以表示同一个栈,形状不同的平衡树也可以表示同一个集合。只要所有对外可见的操作都保持所要求的抽象行为,表示甚至可以采用惰性方式进行规范化。有些验证问题使用关系而非单一的抽象函数,尤其是在具体步骤与抽象步骤并非一一对应的情况下。
正确性还取决于能否保护内部表示。如果栈返回了一个指向其底层数组的可变引用,使用方就可能绕过栈操作直接修改数组内容。此时,表示不变式和操作的正确性证明便无法再涵盖所有可能的更改。这一问题通常称为表示暴露,它将抽象数据类型的实现与程序中的混叠、所有权及访问控制联系起来。如果指向内部可变对象的引用可能泄露到外部,仅仅隐藏字段名并不足够。
集合类型、算法与复杂度契约
集合类抽象数据类型说明了为何应将行为与实现分离。集合通常支持成员查询、插入和删除,并忽略重复插入。映射将键与值关联起来。优先队列按优先级而非到达顺序选取元素供访问。这些抽象都对结果作出了约束,却没有唯一确定存储策略。根据需求和工作负载的不同,映射可以用哈希表、二叉搜索树或小型无序数组来实现。
这种区分使我们能够在适当的抽象层次上描述算法。广度优先搜索依赖队列先进先出的行为,而深度优先探索可以使用栈。图遍历算法无须知道其队列使用的是链式节点还是循环缓冲区。不过,复杂度分析必须考虑所调用的抽象操作的成本。对于执行线性次数队列操作的遍历算法,只有在每次操作的成本得到适当保证时,队列管理的总成本才是线性的。
基本的行为规约并不会自动提供这些保证。在对散列方式和负载作出明确假设的情况下,哈希表查找的期望时间通常被分析为 ,但其最坏情况可能为 。平衡搜索树通常能在 时间内完成查找、插入和删除。两者都可以实现映射的行为,但其性能保证成立的条件不同。因此,程序库可以在抽象数据类型的功能契约之外,补充一份时间复杂度契约。
摊还分析又引入了另一种区分。向动态扩容的数组追加元素时,如果扩容需要复制元素,单次操作可能耗时 ;但采用适当的增长策略后,一系列追加操作的每次操作摊还成本仍可达到 。摊还界并不意味着每一次操作都很快,也不依赖随机输入。它约束的是操作序列的总成本。这一区别对有延迟要求的应用很重要:即使总体成本的界较好,偶尔出现一次耗时很长的操作也可能令人无法接受。
空间用量、遍历顺序、元素稳定性和迭代器有效性同样会约束实现方式的选择。有序映射所承诺的某些行为,是无序映射不作保证的。如果迭代器契约要求插入后已有的元素引用仍然有效,就会排除某些直接搬移元素的策略。这些都是在行为抽象之上附加的要求,而不是“映射”一词本身所隐含的性质。精确地区分这些概念,可以让使用方依赖必要的保证,而不至于无意间依赖某个特定实现。
编程语言机制及相关概念
编程语言提供了多种机制来建立抽象数据类型的边界。模块可以导出操作声明,同时将表示方式保持为私有。在C编程语言中,头文件可以声明一个不完整的结构体类型,以及使用该类型指针的操作,而将结构体的定义留在实现文件中。这样便能构建实用的不透明类型接口,不过,类型转换、指针操作和其他底层功能意味着,这种保护并非语义上的绝对保证。
具有更强模块系统或可见性控制机制的语言,可以更直接地强制维护这一边界。OCaml 的模块签名可以公开抽象类型 t,而不暴露其定义。Java 类可以将字段设为私有,并公开公共方法;Rust 模块则可以隐藏字段,通过公共函数和方法控制访问。这些机制在处理标识、继承、所有权和独立编译的方式上各不相同,但都能支持以不依赖具体实现的方式使用类型。
应用程序编程接口本身并不等同于抽象数据类型。API 可以描述一项服务、一种协议,或一组互不相关的函数。即使 API 描述的是一个类型,操作名称和参数类型也不一定足以确立所需的语义。两个类可能都提供 add、remove 和 contains,却在重复元素、相等性或迭代顺序的处理上有所不同。反过来,同一个抽象数据类型也可以通过多种 API 来实现,这些 API 只是以不同方式封装了相同的底层行为。
抽象数据类型也不同于抽象类。抽象类是一种与继承和不完整实现相关的语言构造。它可以帮助实现抽象数据类型,但抽象数据类型并不要求继承,而抽象类也不一定能保证表示独立性。同样,封装是一种将相关内容组织在一起并限制访问的机制,而抽象决定了哪些属性属于对外公开的语义。
另一个需要区分的概念是代数数据类型,它在函数式编程中很常见。代数数据类型通过和、积等组合方式构造,通常用变体和记录来表达。公开的构造器允许使用方直接检查和分解值。相比之下,抽象数据类型将表示隐藏在操作之后。这两个概念也可以结合使用:隐藏的代数数据类型可以充当抽象数据类型的内部表示。不能仅仅因为两者有时都缩写为“ADT”,就将它们等同起来。
验证、测试与表示无关性
抽象数据类型将推理拆分为彼此独立的证明义务,从而支持模块化的形式验证。一方面,证明实现满足其抽象契约;另一方面,在假定该契约成立的前提下,证明客户端程序的正确性。这样,就不必针对每一种符合契约的实现,根据其具体细节重新证明客户端的正确性。当实现规模庞大、经过优化或经常被替换时,这种划分尤为有用,因为它限制了每次论证所需考虑的代码范围。
表示无关性表达了与之对应的语义原则:只要客户端遵守抽象边界,就无法区分那些满足同一可观察规范的不同实现。这类结论通常通过在两种实现的隐藏表示之间建立关系,并证明公开操作保持这一关系来获得。定理的具体形式取决于所用语言及其允许的观察方式。反射、指针同一性、私有字段的序列化以及不受限制的内存访问,都可能使在限制更严格的环境中成立的假设失效。
测试也采用同样的分离思路,但覆盖得没有那么全面。在基于性质的测试中,测试生成器会生成大量操作参数,并检查一般性规律。对于栈,将一个元素压栈后再弹出,应当恢复原先的抽象内容。对于集合,插入一个已经存在的元素,不应增加集合的基数。这些性质能够在大量情形中发现错误,而无须为每一个具体输入单独编写预期结果。
基于模型的测试更进一步,同时在实现和一个更简单的参考模型上执行操作序列。例如,可以生成数千次入队、出队和查看操作,并将队列实现与一个数学序列模型进行比较。有状态的测试生成必须遵守前置条件,或者有意测试规范中规定的失败情形。基于序列的测试尤其适合发现涉及容量调整、循环缓冲区回绕,或反复删除与重新插入的缺陷。
无论是测试,还是一组不完备的公理,都不能确立完全正确性。一个实现可能满足若干常见等式,却在未经测试的情形下表现错误。规范也可能遗漏某项关键性质,从而允许用户并不期望的行为。包括证明助手在内的验证工具可以明确列出证明义务,但其结论仍然只针对实际写出的形式化规范。抽象边界缩小了推理的范围,却并未免除准确定义这一边界的必要。
并发、持久性与抽象的边界
顺序抽象数据类型规约将操作描述为逐一发生的过程。在并发计算中,调用可能相互重叠,各自看似合理的返回值,合在一起却未必构成有效的历史。因此,并发队列所需的规约不能只有“入队在队尾添加元素,出队从队首移除元素”这样的顺序描述,还必须有一条规则,将重叠操作与抽象行为联系起来。
线性一致性由莫里斯·赫利希和珍妮特·温于 1990 年提出,提供了一条影响深远的规则。如果已完成的操作,加上对部分待完成操作所作的规约允许的补全,能够排列成一个合法的顺序历史,并且遵守互不重叠调用之间的实时先后顺序,那么这个并发历史就是线性一致的。这样,每个操作都可以理解为在调用与响应之间的某个单一时刻生效。这是对可观察历史的约束,并不要求实现采用单一锁。
安全性与进展性仍是两个独立的问题。队列可以正确维护其抽象内容,却让某个线程无限期等待。阻塞、无锁和无等待实现提供了不同类型的进展保证,而这些保证都不能仅从队列的顺序值语义中推导出来。在分布式计算中,故障和网络延迟又引出了更多问题:哪些观察结果可能出现,以及何时可以报告某个操作已经完成。契约必须明确预期的一致性和故障行为,而不能把分布式特性当作不可见的实现细节。
可持久化数据结构带来了另一类问题:更新一个值时,仍然保留对旧版本的访问能力。可持久化映射可以在不同版本之间共享大部分内部节点,同时将每个版本呈现为可独立使用的抽象值。这与命令式映射不同:后者的更新会改变通过指向同一对象的所有别名所看到的状态。结构共享是一种实现技术,而持久性是一种对外部使用者有意义的属性。因此,规约必须区分值的变换与具有身份标识的对象的原地修改。
最后,抽象只能隐藏其模型排除在外的观察结果。两个返回值完全相同的实现,在耗时、内存分配、功耗或内存访问模式上仍可能存在差异。这些差异在实时系统和安全敏感代码中尤为重要。例如,密码学中关于恒定时间行为的声明,施加了超出通常功能等价性范围的约束。同样,对私有表示进行序列化,也可能无意中使内部格式变成必须维持兼容性的约束。有效的抽象数据类型设计,取决于能否明确哪些可观察行为属于契约的一部分,哪些仍可由实现自由决定。