使用高级语言进行工作的动机是通过为程序员提供一种包含适合其问题领域的原语(primitives)或抽象(abstractions)的语言来简化编程任务。这样程序员就可以把精力花费在正确的地方；程序员可以专注于解决他的问题，结果程序将更加可靠。显然，这是一个值得实现的目标。
不幸的是，设计师很难提前选择使用该语言的用户可能需要的所有抽象(abstractions)。如果要使用一种语言，它很可能会被用来解决设计者没有预见到的问题，而且这种语言中嵌入的抽象可能并不足以解决这些问题。
本文提出了一种方法，当发现需要新的数据抽象时，可以扩展内置的抽象集。这种处理抽象的方法是为结构化编程设计语言的产物。本文描述了这种语言的相关方面，并给出了抽象的用法和定义的实例。
Introduction
本文介绍了一种计算机抽象表示的方法。这种方法是在设计一种支持结构化编程的语言时开发的，他也适用于使用高级语言工作。我们首先解释它的相关性(relevance)，并比较结构化编程和高级语言的工作。
结构化编程的目的是增强程序的可靠性(reliability)和可理解性(understandability)。高级编程语言，虽然主要目的是为了通过减轻程序员的任务来提高程序员的工作效率，但同时也期望可以提高代码的可靠性和可理解性。因此，可以期望从这两个领域的工作中获得类似的好处。
然而，这两个领域的工作沿着不同的方向进行。高级编程语言试图向用户呈现抽象（操作、数据结构和控制结构）对他的应用领域很有用。用户可以使用这些抽象，而不用关心它们是如何实现的——他只关心它们做什么。因此，他能够忽略与其应用领域无关的细节，专注于解决自己的问题。
结构化编程试图对编程任务加一种约束，以便重新适应的程序具有良好的结构。在这种约束下，问题是通过一个连续分解(successive decomposition)的过程来解决的。第一步是编写一个程序来解决这个问题，但是这个程序运行在一个抽象的机器上，这个抽象的机器仅提供那些最合适解决这个问题的数据对象和操作。这些数据对象和操作中的部分或全部是真正抽象的，即，在所使用的编程语言中不作为原语呈现。目前，我们将把它们简单的归为 "abstraction" 一词。
程序员最初关心的是（或证明）他的程序是否令人满意地正确的解决了问题。在本文的分析中，他关注的是他的程序使用抽象的方式，而不是哪些抽象如何实现的细节。当他对程序的正确性感到满意时，他就把注意力转向程序使用的抽象。每个抽象都代表一个新问题，需要额外的程序来解决它。新的程序也可以编写为在抽象机器上运行，从而引入更多的抽象。当在构造程序过程中产生的所有抽象都被进一步的程序实现时，原来的问题就完全解决了。
现在很明显，高级语言和结构化编程的方法是相互关联的：每种方法都是基于利用那些对解决问题正确的抽象想法。此外，在这两种方法中使用抽象的基本原理是相同的：让程序员不用担心与他正在解决的问题无关的细节。
在高级语言中，设计者视图提前确定有用的抽象集。另一方面，结构化编程语言不包含关于特定的有用抽象集的先入为主的观念，而是必须提供一种机制，通过这种机制，语言可以扩展到包含用户需要的抽象。包含这种机制的语言可以被视为通用的、无限高级的语言(indefinitely-high-level language)。
在本文中，我们描述了一种抽象方法，当发现需要新的抽象时，允许对内置的抽象集进行扩充。我们从分析编写程序中使用的抽象开始，并确定对数据抽象的需求。非正式的描述了一种支持数据抽象的使用和定义的语言，并给出了一些示例程序。文中的其余部分讨论了该方法与之前的工作的关系，以及该语言实现的一些方面。
The Meaning of Abstraction
上一节中对结构化编程的描述是模糊的，因为它是用"抽象(abstraction)"和"抽象机器(abstract mechine)"这样没有定义的术语来描述的。在本节中，我们将分析"抽象(abstraction)"的含义，以确定程序员需要什么样的抽象，以及结构化编程语言如何支持这些需求。
我们希望从抽象中得到一种机制，它允许表达相关的细节，一直不相关的细节。在编程的情况下，抽象的使用是相关的；抽象实现的方式无关紧要。如果我们考虑传统的编程语言，我们会发现它们为抽象提供了强大的帮助：函数(function)或过程(procedure)。当一个程序员使用一个过程时，他只关心（或者应该关心）它做什么——它为他提供了什么函数。他不关心由程序执行的算法。另外，过程提供了一种分解问题的方法——在过程中执行部分编码任务，在程序中执行调用过程的另一部分。因此，过程的存在对捕捉抽象的意义有很大的帮助。
不幸的是，过程本身并不能提供足够丰富的抽象词汇表(vocabulary of abstractions)。上文提及的抽象机器的抽象数据对象(abstract data object)和控制结构(control structures)不能用独立的过程准确地表示。因为我们在结构化编程的上下文中考虑抽象，所以我们将忽略控件抽象(control abstractions)的讨论。
这就引出了抽象数据类型的概念，这是语言设计的核心。抽象数据类型定义了一个抽象对象的类，该类完全由这些对象上可用的操作来描述。这意味着抽象数据类型可以通过定义该类型的特征化操作(characterizing operations)来定义。
我们认为，上述概念抓住了抽象对象的基本属性。当程序员使用一个抽象数据对象时，他只关心该对象表现出的行为，而不关心如何通过实现(implementation)来实现该行为的任何细节。对象的行为由一组特征和操作捕获。只有在定义如何实现特征化操作时，才需要实现信息，例如对象在存储中是如何表示的。对象的用户不需要知道或提供这些信息。
抽象类型与编程语言提供的内置类型非常相似。内置类型（如整数或整数数组）的用户只关心创建该类型的对象，然后对它们执行操作。他（通常）不关心数据对象是如何表示的，他认为对象上的操作是不可分割的(indivisible)和原子的(atomic)，而实际上可能需要几个机器指令来执行它们。此外，（通常）不允许他拆分对象。例如，考虑内置类型整数。
程序员想要声明数组类型的对象，并对它们执行通常的算术运算。他通常对整数对象作为位串(bit string)不感兴趣，并且不能使用计算机内的使用的位格式。此外，他希望这种语言能够保护他不犯一些愚蠢地误用类型错误（例如，将一个整数加到一个字符上），要么将这种事情视为错误（强类型），要么通过某种类型的自动转换。
在内置数据类型的情况下，程序员正在使用以较低的细节级别实现的概念或抽象——编程语言本身以及编译器。同样，抽象数据类型在一个级别使用，并在较低的级别实现，但是较低级别不会因为是语言的一部分自动出现，相反，抽象数据类型是通过编写一种特殊的程序来实现的，称为操作cluster(operation cluster)，简称cluster，它根据可以对其执行的操作来定义类型。该语言通过允许使用抽象数据类型来促进此活动，而无需其现场(on-the-spot)定义。语言处理程序支持抽象数据类型的方法是：在类型的使用和它的定义之间建立链接（可以提前或推迟提供），并且通过一种非常强大的数据类型形式将数据类型的视图强制为一组操作。
我们注意到，抽象数据类型概念的一个结果是，程序中的大多数抽象操作(abstract operations)将属于特征抽象类型(characterizing abstract types)的操作集。我们将使用属于函数抽象(functional abstraction)来表示哪些不属于任何特征集的抽象操作。函数抽象(functional abstraction)将被时限为一个或多个数据类型的特征操作的组合，并且将以通常的方式通过过程(producer)支持。正弦波轨迹(sine routine)的实现可以是一个泰勒级数(Taylor expansion)展开，用实际类型的特征操作而表现。
The Programming Language
我们现在给出了一种编程语言的非正式描述，允许抽象数据类型的使用和定义。这种语言是在 M.I.T 下正在开发的结构化编程语言的简化版本。它主要来自 PASCALI ，并且在许多方面的是传统的编程语言一样，但它在几个重要的方面与传统语言不同。
该语言提供了两种形式的模块相对应于两种形式的抽象：过程（支持函数抽象）和操作cluster（支持抽象数据类型）。每个模块都是自己翻译（编译）的。
语言在传统意义上没有空闲变量(free variables)。在一个模块中，只有其他模块的名称是空闲的，因此需要在外部定义；也就是说，cluster名称和过程名称。这些名称借助编程器以绑定为目的创建的模块名称目录相绑定。翻译后的模块中没有任何名称需要绑定。
该语言只有结构化控制。没有 goto's或labels，而只有拼接(concatenation)、选择(selection)(if， case)和迭代(iteration)(while)结构的变体。一些结构化的错误处理机制正在开发中。在本文中，他仅用保留字的存在error来表示。
语言允许使用和定义抽象数据类型的方式可以通过一个例子来最好地说明。我们选择了以下问题：编写一个程序 Polish_gen，它将从中 INFIX 语言转换为 POLISH 修复后的语言。Polish_Gen 是一个通用程序，没有关于输入或输出设备（或文件）的假设(assumptions)。他只有一下堆输入语言的假设(assumptions)：
- 输入语言具有运算符优先语法。
- 输入语言的符号要没事字母和数字的任意字符串，要么是单个的非字母数字字符；空格用于终止符号，但其他部分将被忽略。
例如，如果Polish_gen接收到字符串：
a + b * (c + d)
作为输入，它将生成字符串
a b c d + * +
作为输出。我们选择这个问题作为示例，是因为对编程语言感兴趣的人对这个问题及其解决方案很熟悉，而且这个问题足够复杂，可以说明许多抽象的使用。
Using Abstract Data Types
如图 1 所示，过程 Polish_gen 执行上述转换。它需要三个参数：输入，一个抽象类型的对象，包含输入语言的句子(input， an object of abstract type infile which holds the sentence of the input language)；输出，抽象类型的输出对象，它将接受输出语言的句子(output， an object of abstract type outfile which will accept a sentence of the output language)；和 g，抽象类型语法的对象可用于识别输入语言的符号并确定其优先关系(and g， an object of abstract type grammar which can be used to recognize symbols of the input language and determine their precedence relations)。此外，Polish_gen还利用了局部变量的抽象类型堆栈和令牌(stack and token)。请注意，所有的数据类型名称(data-type-names)在 Polish_gen 中都是可用的(free)，"scan"也是如此，它为 Polish_gen 使用的单个功能抽象(single functional abstraction)命名。
该语言使用相同的语法来声明抽象数据类型的变量，以声明原始类型(primitive type)的的变量。语法区分了涉及创建对象的声明和不涉及对象创建的声明。例如
t: token
声明 t 是保存抽象类型 token 对象的变量的名称，但是不创建任何 token 对象，因此 t 的值最初是未定义的。因此变量 t 的声明方式与 mustscan 相同
mustscan: boolean
类型名称后出现括号表示创建了一个对象。例如
s: stack(token)
表示 s 是保存抽象类型堆栈对象的变量的名称，堆栈对象将在 s 中创建和存储。创建对象所需的信息在参数列表中传递；在该示例中，唯一的参数 token 定义了可以放在堆栈上的元素类型。堆栈的声母类似于数组声明，例如 array[1..10]的字符，因为它们都要求指定元素的类型。
语言是强类型的;因此，抽象对象只有三种使用方式:
- 抽象对象可以由定义其抽象类型的操作来操作。
- 抽象对象可以作为参数传递给过程。在这种情况下，调用过程传递的实际实参的类型必须与被调用过程中相应形参的类型相同。
- 抽象对象可以复制给变量，但前提是该变量声明保存该类型的对象。
对抽象对象的定义操作的应用是通过使用复合名称(compound name)的操作调用来表示的，例如：
grammar$eof(g)
stack$push(s， t)
token$is_op(t)
复合名称的第一部分表示操作所属的抽象类型，而第二个组件标识操作。操作调用总是至少有一个参数——操作所属的抽象类型的对象。
操作调用(operation call)中包含 type-name 有几个原因。第一，由于操作调用可能有几个不同抽象类型的参数，缺少 type-name 可能会导致对实际操作的对象产生歧义。其次，复合名称的使用允许不同数据类型对操作使用相同的名称，而不会产生标识符冲突。第三，我们认为一旦读者习惯了这种表示方法，type-name 前缀将增强程序的可理解性。不仅操作的类型很明显，而且操作调用与过程调用也有明显的区别。
语句 t:= scan(input， g) 演示了将抽象对象作为参数传递，以及将抽象对象赋值给变量。过程扫描，如图2所示，期望类型为 infile 和 grammar 的对象作为其参数，并返回类型为token的对象，
我们已经解释了对象可以与变量声明一起创建。也可以独立于变量声明创建对象。对象创建是通过 type-name 的出现加上括号来指定的(无论是否在声明中)。例如，在 scan 的最后一行 token(g， newsymb) 声明一个token对象，表示刚刚扫描的符号，将被创建; 创建对象所需的信息(刚扫描的语法和符号)在参数列表中传递。
现在可以给出 Polish_gen 逻辑的简要描述。Pollsh__gen 使用函数抽象扫描从输入字符串中获取语法符号。Scan 以 token 的形式返回符号——引入 token 的目的是提供高效执行，而不会透露语法如何表示符号的信息。Polish_gen 将包含新扫描符号的 token 存储在变量t中。如果t持有一个表示标识符(如"a")而不是操作符(如"+")的 token ，该标识符将立即被放入输出文件。否则，将栈顶部的 token 与t进行比较，以确定它们之间的优先关系。如果关系是 "~"，t被推到栈上(例如，"+" < "*")。如果关系是"="，t和栈顶 token 都被丢弃(例如，"("=")")，如果关系是 "~"，栈顶 token 中的操作符被追加到输出文件中，暴露一个新的栈顶 token。由于运算符 token 的优先级比 t 更高，因此布尔变量 mustscan 用于放置扫描新符号并确保下一个比较是具有 t 的当前值。由于文件符号末尾的语法依赖表示(grammar$eof(g))最初被推到堆栈上，因此堆栈将变为空，导致 Polish__gen 只有在耗尽输入生成匹配的eof token时才会完成。(我们已经做了一个简化的假设，即输入是中缀语言的合法句子。)
scan 过程通过定义抽象类型 infile 的操作输入问题中获取字符。它使用数据类型 char 和 string，以及对这些类型的对象的操作。虽然这些类型如内置所示，但它们很容易地变成抽象类型。在这种情况下，内置的谓词字母数字(predicate alphanumeric)将被表示为 char$alphanumeric。只有语法会被改变；在任何一种情况下，类型的含义和使用都是相同的。
综上所述，Polish_gen使用了 5 个数据抽象，infile， outfile， grammar， token 和 stack，外加一个函数抽象(functional abstraction)， scan。数据抽象的强大功能可以通过类型 infile 和 outfile 来说明，它们分别用来屏蔽与 Polish_gen 的输入和输出相关的任何物理事实。当 I/O 实际发生时，Polish_gen 不知道正在使用什么输入和输出设备，也不知道字符串是如何在设备上表示的。对于参数 output，它知道如何添加一个字符串字符(outfile$out_str)，以及如何表示输出已经完成(outfile$close)。对于参数 input，他知道如何获取下一个字符(infile$get)，如何查看下一个字符而不将其从输入中删除(infile$peek)，以及如何识别输入的结尾(infile$eof)。（注意，为了正确的 scan 操作，infile 必须在到达文件结束后的 infile$get 或 infile$peek 上的任何调用中提供非空白的非字母数字字符串）在每种情况下，它的知识(knowledge)都由提供这些服务的操作的名称组成。
Defining Abstract Data Types
在本节中，我们描述了编程对象 —— 操作cluster(operation cluster) —— 其翻译(编译)提供了类型的实现。该cluster包含实现每个特征操作的代码，从而体现了数据类型由一组操作定义的想法。
例如，考虑 Polish_gen 使用的抽象类型 stack。cluster支持 stack 如图 3 所示。该cluster实现了一种非常常用的 stack 对象，其中 stack 元素的类型是预先知道的。cluster 参数 element_type 表示特定 stack 对象要包含的元素类型。
cluster定义的第一部分非常简短地描述了cluster呈现给用户的接口。cluster接口定义了cluster的名称，创建cluster实例(cluster 实现的抽象类型对象)所需的参数，以及定义 cluster 实现的类型的操作列表，例如：
stack: cluster(element-type: type)
is push, pop, top, erasetop, empty
保留字 is 是值数据类型的特征是一组操作。
cluster 定义的其余部分描述了如何实际支持抽象类型，包含三个部分：对象表示、创建对象的代码和操作定义。
对象表示(Object Representation)。抽象数据类型的用户将该类型的对象视为不可分割的实体。然而，在 cluster 内部，对象被视为可分解为更基本类型的元素。 rep(Representation) 描述为：
rep{(<rep-parameters>)} = <type-definition>
定义了一个新类型，用保留字 rep 表示，该类型只能在 cluster 中访问，并描述了在 cluster 中如何查看对象。<type-definition>定义了一个模版，该末班允许构建和分解该类型的对象。通常，它会利用语言提供的数据结构方法：数组（可能是无界的）或 PASCAL 记录。可选的 ("{}") <rep-parameters> 使得可以延迟指定 <type-definition> 的某些方面，知道创建了 rep 的实例。考虑 stack cluster 的 rep 描述：
rep(type_param: type) = (tp: integer; e_type: type; stk: array[1..] of type_param)
<type-definition>指定 stack 对象由包含名为 tp, stk 和 e 类型的三个组件的记录表示。参数 type_param，它可以存储在名为 stk 的无界数组中，该数组将保存推入 task 对象的元素。同样的类型也将存储在 e_type 组件中，并用于类型检查，如下所述。tp 组件保存 stack 最顶层元素的索引。
对象创建(Object Creation)。保留字 create 标记为 create_code，这是创建抽象类型对象时要执行的代码。cluster 可以被视为一个过程，其过程主体是创建代码。当用户指示要创建抽象类型的对象时，例如，s: stack(token) ，发生的一件事（在执行时）是对 create_code 的调用，导致该过程体被执行。cluster 的参数实际上是 create_code 的参数。由于除了对外部定义模块的引用之外，没有提供自由变量，因此这些参数对 rep 中的操作或 <type definition> 都是不可访问的。因此，关于要保存的参数的任何信息都必须显式插入到 rep 的每个实例中。
stack cluster 中显示的代码是典型的 create_code。首先，创建 rep 的对象；也就是说，分配空间以将对象保存由 rep 定义。然后，一些初始值存储在对象中。最后，对象将返回给调用者。返回对象后，其类型从 rep 类型更改为 cluster 定义的抽象类型。
操作(Operations)。cluster 的其余部分由一组操作定义组成，这些定义提供了对数据类型允许的操作的实现。操作定义与普通的过程定义类似，除了它们可以访问 cluster 的 rep 之外，这允许它们分解 cluster 类型的对象。操作本身不是模块；它们将被编译器接受，仅作为 cluster 的一部分。
操作总是至少有一个参数 —— 类型为 rep。因为 cluster 可以同时支持多个其定义类型的对象，所以这个参数告诉操作要操作的特定对象。请注意，在调用者和操作之间传递时，该参数的类型将从抽象类型更改为 rep 类型。
因为该语言是强类型的，所以必须检查推送到给定 stack 上的对象类型是否与 stack 可容纳的元素类型一致。这个一致性要求在语法上是通过声明 push 的第二个参数的类型与 stack 对象的 rep 的 e_type 组件（即 push 的第一个参数）相同来指定的。翻译（编译）程序可以生成代码来验证类型在运行时是否匹配，如果不匹配则引发错误。
Controlling the Use of Information
引入抽象数据类型是为了让程序员在使用数据抽象时不必担心无关的细节。但事实上，我们已经走得更远了。因为语言是强类型的，用户无法使用任何实现细节。在本节中，我们将讨论这种限制所带来的好处：结果是程序更模块化，更容易理解、修改、维护和证明其正确性。
token 是个很好的类型示例，创建它是为了控制对实现细节的访问。与其引入一个新的类型，Polish_gen 可以被写为接受来自 scan 的字符串，将字符串存储在 stack 上，并比较字符串以确定优先关系（通过一个适当的操作 grammar$prec_rel）。这样的解决方案是低效的。因为优先级矩阵可以由 grammar 的保留字表中运算符的位置索引，因此有效的实现将仅查找一次字符串，一旦发现如果是操作者符号，则使用在 Polish_gen 中的操作符的索引。
然而，这会暴露有关 grammar 表示的信息。如果 Polish_gen 或使用 grammar 的一些其他模块利用此信息，则 grammar cluster 的正常维护和修改可以引入难以追踪的错误。因此，引入了新类型，token，以限制关于 grammar 是如何表示的信息的分布。限制，grammar cluster 的重新定义只能影响 token cluster —— token cluster 对从 grammar 接收到的索引没有任何假设。如果在查找优先关系（如索引越界）时发生错误，则该错误只能是由 token 或 grammar cluster 中的某些内容引起的。
事实上，选择 token 的实现——例如，token 是用整数还是字符串表示——涉及到设计决策。这个决策可以延迟到 token 的 cluster 被定义时，而不必在 Polish_gen 编码期间做出来。因此，Polish_gen 的编程可以根据 Dijkstra 的编程原则之一来完成：每次只构建一个决策。遵循这一原则，可以简化 Polish_gen 的逻辑，使其更容易理解和维护。
使 representation 无法访问也导致一个更容易证明正确的程序。程序的证明分为两部分：证明 cluster 正确实现该类型，以及使用类型的程序是正确的。只有在前一种证明中才需要考虑类型对象的实现细节；后一个证明仅仅基于类型的抽象属性，这些抽象属性可以用每种类型的特征操作之间的关系来表示。
Relationship to Previous Work
在为定义数据类型创建合适的机制方面已经做了很多工作。这里不可能调研所有的工作，也不是说所有的工作都与本文相关。在本节中，我们将概述与 cluster 最密切相关的工作领域，因为它们提供了一些用于定义抽象数据类型的工具，并讨论 cluster 方法与这些工作的区别。相关工作可以大致分为三类：可扩展语言(extensible languages)、一组标准抽象操作符的实现规范(implementation specifications for a set of standard abstract operators)和 SIMULA 67 类定义(SIMULA 67 class definitions)。
Extensible Languages
可扩展语言的大部分工作和成功都是在数据类型定义领域。然而，这项工作主要面向定义表示(defining representations)，而不是抽象类型。通过使用语言的基本模式构造工具(primitive mode construction facilities of the language)，根据现有模式构造表示()，可以创建新的数据表示(new data representations)，或者通常称为模式(mode)。可扩展语言提供的模式构建工具通常包括定义对象指针、定义不同模式类的联合以及构造对象聚合（数组和记录）的机制。这些与本文中用来定义 rep 的方法密切对应。这些模式定义机制的使用意味着定义了一组构造函数(constructors)、选择器(selectors)和谓词(predicates)，它们可以应用于所定义模式的对象。在某些语言中，模式定义可以允许这组操作被特定的操作扩充，比如在语言中明确规定的赋值操作。
可扩展语言的主要问题是它们不鼓励使用数据抽象。一般来说，在模式定义中定义描述抽象数据类型的所有操作是不可能的。正如我们注意到的，只有数据类型的 representation 是使用模式扩展机制定义的。任何不等同于 representation 的构造函数、选择器或谓词的抽象操作都必须由过程或宏在模式定义之外定义，可以使用语法扩展功能使其看起来像操作符。因此，用户必须学习两种不同的机制；定义不是像在操作 cluster 中那样收集在一个地方，而是被分割成不同的部分。此外，很难限制对抽象数据类型的特征操作的对 representation 的访问。
Standard Abstract Operations
源自 Mealy 和 Balzer 早期工作的作品在精神上更接近于这里采取的方法。Mealy 建立这样一个观点，即数据集合是从一组选择器到一组值的 map ，对数据集合的操作要么是 map 上的转换，要么是使用 map 来访问元素。这种观点导致了标准化一组用于数据集合的抽象操作符的尝试。例如，Balzer 为这样的集合提出了一个特定的抽象，它定义了一组四个抽象操作符，用于创建、访问、修改和销毁抽象数据集合。用户将通过指定如何实现每个抽象操作来定义一个特定的集合。这项工作已经被扩展（例如，Earley），但是它的主要重点仍然是定义一个标准的抽象操作集。更复杂的操作被定义为根据这些操作编写的过程。
尽管区分一些抽象操作（如"create"）很有用，因为他们很可能适用于所有抽象数据类型，但期望一组预先确定的操作足以操作所有抽象数据对象似乎是不合理的。因此，将操作的选择留给类型的创建者，就像操作 cluster 一样，提供了一个更紧密定制的抽象。
SIMULA Classes
在行驶时，最接近的语言是 SIMULA 67。SIMULA 类定义与 cluster 定义有很多相似之处。然而，这两种语言有一个非常重要的哲学差异，这导致了几个重要的语言差异。SIMULA 的类被设计用来表示和提供对数据对象的完全访问。类中的每个属性和函数都可以在嵌入类定义的块中访问。因此，用户总是知道 representation 的实际形式。
与此相反，cluster 的 representation 在 cluster 之外是不可访问的。cluster 中的操作提供了访问 representation 内容的唯一访问，即使这样，也只有 cluster 的定义的操作的一个子集可以从外部访问。由于这种哲学上的差异，两种语言中引用数据的机制、非局部变量引用的使用以及块和块结构的使用都有很大的不同。
Implementation Considerations
cluster 实现的大部分方面都和常规处理方式一样。然而，该实现有几个方面值得特别提及，因为它们是和常规实现不同的，或者对使用 cluster 来表示抽象数据的实用性有重大影响。
Modules and Module-Names
编译器接收一个模块作为输入。模块通常是一个 cluster，但有时也会是一个过程，如 Polish_gen 或 scan。在模块转换的过程中，会遇到外部定义的模块名，用来指代过程和数据类型。（请注意，对抽象数据类型上操作的引用不会引入任何额外的外部引用，因为它们是相对于操作名前缀的抽象类型。）
当编译器处理一个模块时，它会构建或添加一个描述单元(description-unit)，该描述单元包含关于该模块的信息。描述单元中包含的信息包括：
- 由编译器生成的目标代码的位置。
- 模块对其用户可用的接口的描述。特别是，维护关于模块期望的所有参数和值类型的完整信息。如果该模块是一个 cluster，则将保留 cluster 中每个操作的信息。
- 使用该模块的所有模块的列表。
显然更多信息可以存储在描述单元：以符号表等形式调试信息，文档信息，以输入/输出关系的谓词演算描述的形式，甚至是基本原理的分析对于设计模块的决定。
描述单元(description unit)是关于模块的所有信息的焦点。它可以在处理模块时创建，也可以创建为其他模块引用的目标。在处理描述单元所代表的的模块之前创建描述单元支持自顶向下设计，并提供了一种定义递归的简单方法。由于描述单元保存了所有使用模块的列表，所以当模块实际定义时，可以检查使用和定义的一致性，并在那时生成适当的错误消息。实际的定义可能会延迟一段时间，因为描述单元可以用来定位代码，以模拟模块的行为，已达到调试的目的。
在翻译（编译）模块的过程中，翻译器必须将每个模块名绑定到对应模块的代码，从而为每个模块名赋予含义。这是通过描述单元完成的。翻译程序通过一个目录获得对描述单元的访问，该目录包含一组 module-name/description unit pair，它将其作为参数接收。所有外部引用都必须通过此目录解析；如果无法解析它们，则生成适当的错误消息。
该目录是一个用户构造的对象，一般来说，构建该对象是为了控制一组特定相关模块的翻译。实际的描述单元存储在一个类似于 MULTICS 文件系统的多级树形文件系统中，对于目录中描述单元的引用实际上是对这个文件系统的引用。用于构造目录和操作文件的原语独立于语言，形成了 "file system cluster" 和 "directory cluster"。
Type Checking
本文中描述的语言是基于强类型检查的思想，语言翻译器应该在两个独立编程过程之间的接口上执行强类型检查。在本节中，我们将讨论由强类型检查引起的一些问题。
强类型检查意味着，每当一个对象从调用函数传递到被调用函数时，它的类型必须与被调用函数中声明的类型兼容。如果被调用的函数是一个过程，则类型必须完全匹配。如果被调用的函数是一个操作，那么类型必须完全匹配，除非对象是由该操作所属的 cluster 定义的抽象类型。在本例中，对象的类型更改为该 cluster 的 rep 类型。因此，类型检查机制控制对象的 representation 是否对给定的操作可见。在这种情况下，如果类型错误未被检测到，则应该在 cluster 之外不可访问的信息将变为可访问的，程序模块化将被破坏。
这种语言中的类型检查比大多数传统语言中的要复杂。这是因为用户定义的抽象，包括数据类型和过程，都可以使用类型作为参数。考虑上面定义的数据类型 stack 。我们已经注意到 stack 和数组之间的相似性：在每种情况下，都必须在创建实例之前提供结果组件的类型规范。构造器(constructs)，如 stack 和 array，被称为类型生成器(tyoe generators)，因为它们定义了一个 class 类型(type of class)，而不是单个类型。类中的每个单独类型都是通过为类型生成器的每个类型参数提供类型定义来生成的。类型生成器（如 stack）是为了满足未来用户的需要而创建的，它定义一个开放的类型类，并且在编译 stack cluster 时不知道其他 class 类型的成员。
允许用户定义类型生成器的影响之一是，cluster 中针对该 “类型” 的一些操作是多态的(polymorphic)；也就是说，操作可以在许多不同的类型域(type domains)上定义，这会受到任何给定的参数集的类型是类型一致的(type-consistent)约束。这种操作的一个例子是 stack cluster 中的 push 操作。push 的操作数是一个 stack 和一个值。push 的类型一致性要求是，如果 stack 的类型是 "stack of T"，那么 push 的值必须是 T 类型；因此，操作 push 的强类型检查包括确定其 stack 参数是否真的是一个 stack、确定 stack 参数的类型、确定被 push 值的类型以及确定它们是否满足一致性要求。
最好进行编译时类型检查，因为类型错误可以尽早检测到。然而，由于在语言中可以自由地使用类型，编译时类型检查可以有多完整还不清楚。因此，该语言的设计是基于运行时类型检查机制的，该机制通过尽可能多的编译时检查进行扩充。
很明显，给定合适的 representation 类型表示形式，就可以编写运行时检查是否具有相同匹配的类型。导致对象的 representation 暴露给操作的那种类型检查可以在运行时通过 Morris I0 描述的技术来处理，该技术是操作系统汇总保护工作的产物。（cluster 和受保护的子系统之间有很强的相关性；cluster提供了封装私有信息的自然机制。）
在未来，我们也许可以不用运行时机制，因为 John Reynolds 最近的工作表明，完整的编译时类型检查是可能的。我们期待 Reynolds 的工作的完成，并打算在不久的将来设计一个基于编译时类型检查的语言版本。
Retention
该语言被设计成允许使用 stack 规则(discipline)实现 cluster、procedure 和 operation 的激活。cluster、procedure 和 operation 在执行时没有自由变量，其中定义的所有变量都是纯本地的。要保留或共享的所有信息都必须存储在对象的 representation 中。在使用保留策略的堆中分配对象。在实践中，有许多容易识别的情况， 对象不需要放在堆中，而是可以在 stack 上分配，要么是因为对象不共享，要么是因为一旦分配了对象，其内容就永远不会更改。这些情况可以由语言翻译（编译）人员进行优化。
Efficiency
我们认为将两个结构与一个程序相联系是有帮助的：它的逻辑结构(logical structure)和物理结构(physical structure)。程序员的主要任务是构建一个具有良好逻辑结构的程序——一个易于理解、易于修改和维护的程序。然而，一个好的逻辑结构并不一定意味着一个好的物理结构——一个有效执行的物理结构。事实上，用于实现良好逻辑结构（层次结构，仅通过函数访问数据等）的技术在许多情况下似乎意味着糟糕的物理结构。
我们相信编译器的任务是把好的逻辑结构映射成好的物理结构。这两个结构可能有差异的事实是可以接受的，前提是编译器被验证了，并且所有编程工具（例如，调试工具）都被定义为隐藏差异。
该语言旨在优化编译器进行编译，从而在输出代码中实现良好的物理结构。语言对于操作调用的一样具有灵活性，这一事实可以获得一个重要的效率。每个操作调用可以被对应操作的实际调用或操作的内联代码替换。语言设计的两个方面使得这种灵活性成为可能：
- 因为操作调用的语法在两种情况下都是相同的，所以可以更改所使用的编译技术，而无需重写使用操作符的过程。
- cluster 的不变部分——操作代码——已经被小心地与 rep 分开，rep 保存着依赖于对象的信息；因此，代码的内联嵌入(inline insertion)是可能的。
操作代码的内联插入允许该代码受编译器中可用的优化转换(optimization transformations)。优化转换，例如编译时间评估和常见的子表达式消除，删除冗余计算，从而降低执行操作所需的时间。例如，如果在 Polish_gen 中插入哪些操作，则可以消除 stack cluster 操作中的所有错误检查。这些标准优化技术应该非常有效，因为编译器正在处理结构化程序；缺乏自由变量，以及 goto 和其他混乱的控制结构意味着可以执行彻底的数据和控制流程分析。换句话说，编译器可以从程序的良好逻辑结构中受益，以获得对它的彻底了解，就像一个人一样。
获得这种执行时间优化的代价是增加了重新定义或修改模块的成本。每次这样的修改都可能需要重新编译使用内联修改函数的模块。由于使用内联代码的决定可能会延迟，直到性能测量表明系统的哪些部分是关机的，因此只有当内联代码会带来积极的性能好处时，才需要放弃简单的程序修改的灵活性。请注意，保存在描述单元中的模块的使用列表可能用于在进行更改时自动重新编译。
Conclusions
本文描述了一种新的抽象——抽象数据类型，它增强类我们利用抽象构建程序的能力。这种方法作为一个概念和编程语言的一部分进行了讨论。给出了几个应用实例。抽象数据类型被定义为一类对象，其特征完全是对这些对象执行的操作。为了提供对抽象数据类型的编程语言支持，引入了一种新的语言结构—— operation cluster。
开发该语言背后的根本原因是，通过提供一种语言来表达程序设计过程中暴露的抽象，从而使结构化编程的时间更容易理解。我们认为抽象数据类型的概念以一种对程序员最有用的形式提供了数据抽象：他只需要知道抽象对象的行为，这正是他编写程序所需要的信息，而有关对象在存储中如何表示以及操作如何实现的无关细节对他来说是隐藏的。事实上，他无法利用实现细节，从而导致了程序质量的改进：程序将更加模块化，更容易理解、修改、维护和证明其正确性。
当然，程序的质量在很大程度上决定于好的程序设计。尽管一门语言永远不能教会程序员什么构成了一个良好的程序，但它可以引导他思考正确的事情。我们相信抽象是优秀设计的关键，并且我们在使用该语言的实验中发现，它鼓励程序员有意识的寻找抽象，特别是数据抽象，并认真思考它们的使用和定义。
我们相信，本文中讨论的抽象方法可以有效地整合到许多不同类型的语言中。任何一种语言，无论多高级，都不可能包含任何使用它的人所需要的所有抽象。因此，本文中描述的抽象构建机制(abstraction-building-mechanism)将是一种非常高级的语言的有用特性。
Acknowledgements
作者非常感谢Jack Dennis、Austin Henderson、Greg Pflster和其他推荐人对论文的内容和结构所作的有益的评论。
References
- Wirth, N. The progranmting language PASCAL. Acta Informatica, Vol. I (1971), pp 35-63.
- Parnas, D.L. Information distribution aspects of design methodology, Proceedings of the IFIP Congress, August 1971.
- DiJkstra, E. W. Notes on structured programming. Structured Programming, A.P.I.C. Studies in Data Processing, No. 8, Academic Press, New York, 1972, pp 1-81.
- Schuman, S. A. and P. Jorrand. Definition mechanisms in extensible programming languages. Proceedings of the AFIPS, Vol. 37, 1970, pp 9-19.
- Mealy, G. Another look at data. Proceedings of the AFIPS, Vol. 31, 1967, pp 525-534.
- Balzer, R. M. Dataless programming. Proceedings of the AFIPS, Vol. 31, 1967, pp 557-566.
- Earley, J. Toward an understanding of data structures. Comm. of the ACM, Vol. 14, No. I0 (October 1971), pp 617-627.
- Dahl, O.-J., B. Myhrhaug, and K. Nygaard. The SIMULA 67 Common Base Language. Norwegian Computing Center, Oslo, Publication S-22, 1970.
- Daley, R. C., and P. G. Neumann. A general purpose file system for secondary storage. Proceedings of the AFIPS, Vol. 27, 1965, pp 213-229.
- Morris, J. H., Jr. Protection in programming languages. Comm. of the ACM, Vol. 16, No. i (January 1973), pp 15-21.
- Zilles, S. N. Procedural encapsulation: a linguistic protection technique. SIGPLAN Notices, Vol. 8, No. 9 (September 1973), pp 140-146.
- Reynolds, J. Personal communication.
- Liskov, B. H. A design methodology for reliable software systems. Proceedings of the AFIPS, Vol. 41, 1972, pp 191-199.
本文来源
PROGRAMMING WITH ABSTRACT DATA TYPES
Barbara Liskov Massachusetts Institute of Technology Project MAC
Cambridge， Massachusetts
Stephen Zilles Cambridge Systems Group
IBM Systems Development Division Cambridge， Massachusetts