2.3 用户定义类型
有些语言，如ALGOL 68，Pascal和Ada等，除了语言定义的内部类型外，还允许用户借助于语言提供的机制，自己定义新的数据类型。语言允许程序员规定基本数据对象的聚合(Aggregate)，乃至聚合的聚合。例如，数组构造符array构造同种类型的聚合。一个聚合对象具有唯一的名字，可对它的单个分量进行操作，可选择适当的操作访问每个分量。许多语言也可对整个聚合赋值或比较。
我们在现有语言的聚合方法中，抽象出一些机制加以讨论。
2.3.1 笛卡儿积
n个集合A1，A2，…，An的笛卡儿积(Cartesian Product)表示为
A1×A2×…×An
它是一个集合，其元素是有序的n元式(a1，a2，…，an)，其中ai∈Ai，i=1，2，…，n。例如，一个正多边形用一个整数(正多边形边数)和一个实数(边的长度)来描述，那么任意正多边形都是笛卡儿积
integer×real
的一个元素。COBOL和Pascal的记录(Record )，PL/l，ALGOL 68和C语言的结构(Struc-ture)都是笛卡儿积的例子。用Pascal定义如下
type polygon = record no_of_edges：integer；
edge_size ：real
end
语言把笛卡儿积数据对象看成由若干个域(Field)组成，每一个域都可以具有一个名字。在上述正多边形的例子中，以polygon命名变量的类型，它的每个变量具有两个域，一个名为no_of_edges的整型域，用来保存边数，一个名为edge_size的实型域，用来保存边的长度。笛卡儿积的域可用域名(Field Name)来选取，也可用语言规定的选择符(Selector)来选取。例如，在Pascal中为了使polygon tl为一个边长7.53的等边三角形，应当写成
tl.no_of_edges：=3；
tl.edge_size：=7.53；
其中圆点“.”是Pascal规定的选择符。而在ALGOL 68和Ada语言中具有简单的形式
tl：=(3，7.53)
2.3.2 有限映像
从定义域类型DT值的有限集合到值域类型RT值的有限集合的函数称为有限映像(Fi-nite Mapping)。语言的数组构造符array就是有限映像的实例。例如，Pascal说明
var a：array[1..50]of char
可看成从1～50的整数集合到字符集的有限映像。值域的对象可由下标索引(Indexing)来选取，即通过在定义域中提供相应的值作为下标(Index)来选取。a[k]称为下标变量(Indexed Variable)，它可以看成上述映像对自变量k的一个应用。
带有不在定义域中值的下标会导致一个错误，例如a[55]就是对上述数组元素的一个引用错误。通常，这类错误要在运行时才能查出。
某些语言，例如APL，ALGOL 68和Ada，下标可用来选取值域的多个元素。Ada的a [3..20]说明一个包含18个元素的a的一维子数组(Subarray)，这样的操作称为分割(Sli-cing)，它选取数组的一个切片(Slice)。
SNOBOL 4语言提供更为有趣的有限映像，array可构造值域集的所有元素不是同一类型的数组，数组的一个元素可能是整型，另一个可能是实型，第三个可能是字符串。换句话说，值域集的类型是其元素的所有类型的联合。
有限映像定义域类型DT到相应值的特定子集的绑定策略随语言而异，它有三种基本方式。
(1)编译时绑定
例如FORTRAN，C和Pascal语言，程序员在编写程序时这个子集就已固定，所以在编译时就能冻结。
(2)对象建立时绑定
ALGOL 60最先采用这种限制，后来在SIMULA 67和Ada中也得到采用。在程序运行时，变量实例一旦建立，子集就固定了。
(3)对象处理时绑定
这是在运行时期内执行的选择，它是最灵活也是代价最高的选择。例如，ALGOL 68的灵活数组(Flexible Array)在运行中对象的生成期内，子集的范围是随时可变的，只有在处理对象时约束当前的子集范围。典型的动态语言SNOBOL 4和APL和后来的CLU都采用这种绑定。
2.3.3 序列
序列(Sequence)由任意多个数据项组成，这些项称为该序列的成分(Component)。每个成分都具有相同的类型，记为CT。在这种构造机制中，成分出现的个数不需要说明，原则上要求能容纳任意大小的对象。
串是众所周知的序列，其成分类型为字符。数据处理中的顺序文件(Sequential File)的思想也来自于序列的概念。
现有语言中提供的序列构造形式不多，而且差异也较大，要抽象出共同的特性是困难的。例如，SNOBOL 4把串看成具有丰富操作的数据对象，而Pascal和C语言却把串看成简单的字符数组，没有特别规定对串的操作。PL/1和Ada提供了基本的串操作，但为了简化动态存储分配问题，要求程序员在串说明中规定一个串的最大长度。
串的一般操作有下列4种：
(1)连接(Concatenation)
串“THIS_IS_”和串“AN_EXAMPLE”的连接的结果是“THIS_IS_AN_EXAMPLE”。
(2)首项选取
选取一个串的第一个成分，对上述连接的结果的首项选取是‘T’。
(3)尾项选取
选取一个串的最后一个成分，对上述连接的结果的尾项选取是‘E’。
(4)子串
以专门的说明指出从给定的串中取出期望的子串(Substring)，要求说明标出子串的第一个字符和最后一个字符的位置。
顺序文件呈现更多的特殊问题，它依赖于与操作系统的接口。通常对文件只提供简单的基本操作，例如，Pascal文件只允许在现有文件末端加入新值来修改文件，且只能顺序读取文件。
2.3.4 递归
若数据类型T包含属于同一数据类型T的成分，那么类型T称为递归类型(Recursive Type)。递归类型允许在类型定义中使用被定义类型的名字。例如，二叉树可通过递归来定义。类型binary_tree可以定义成一个三元式，第一个元素或者为空，或者为原子元素(Atomic El-ement)；第二个元素为(Left)binary_tree；第三个元素为(Right)binary_tree (参见2.4.3节)。
递归用来定义聚合的构造机制，这个聚合的大小是任意增加的，结构也可以很复杂。递归与序列相反，允许程序员为选取成分建立任意的访问路径。
指针(Pointer)是语言提供的最常用的建立递归数据对象的机制。递归类型的每个成分由一个单元表示，存储单元的内容是一个指向数据对象的指针，而不是数据对象本身。常常会遇到这样的情况，即数据对象的大小是任意的，所以我们需要这样的指针，以间接方式来标识这类可变的数据对象。例如，二叉树的每个结点都具有两个相关单元，一个包含指向左子树的指针，另一个包含指向右子树的指针(这里忽略了每个结点还应保存的其他信息)。树自身用另一个单元来标识，这个单元包含指向树根的指针，从这个单元出发，沿着适当的指针链可以访问每个结点。空指针对应空(子)树。
2.3.5 判定或
判定或(Discriminated Union)是一个选择对象结构的构造机制，规定在两个不同选择对象之间做出适当的选择，每个选择对象结构称为一个变体(Variant)。
COBOL语言的重定义子句REDEFINES就是这样的结构，它支持判定或。在公用数据处理中，有这样的情况：某些存储记录的结构绝大部分都是相同的，仅有少部分域是不同的，因此可使用判定或构造机制来定义不同的变体。例如，在一个工资管理程序中，有一个域表示付给雇员的薪金，或者是月薪，或者是时薪，这取决于雇员的支付方式。为了说明这个问题，我们写一个COBOL程序段：
01 EMPLOYEE_ERCOD
05 NAME PIC X(20)
05 SALARY PIC 9999.
05 HOUR_RATE REDEFINES SALARY PIC 99V99.
其中，SALARY和HOUR_RATE指同一域，但两者具有不同的PICTURE (类似于类型概念)。
大多数近期的程序设计语言允许程序员在不同程度上以判定或机制来定义变量类型，例如，ALGOL 68和C语言的union，Pascal和Ada的变体记录(Variant Record)。
2.3.6 幂集
通常，我们需要定义这样的变量，其值是某个类型T的各元素集合的任意子集，该变量的类型记为Powerset(T)，即类型T的元素的所有子集的集合。这种构造机制称为幂集(Pow-erset)，T称为基类型(Base TyPe)。例如，语言处理器接受下列选择集合Set：
LIST_S 列源程序表的过程
LIST_O 列目标程序表的过程
OPTTIMIZE 优化目标代码
SAVE_O 在后备存储器上保留目标代码
SAVE_S 在后备存储器上保留源程序
EXEC 执行目标代码
让处理器执行的命令可以是Set的任意子集。例如：
{LIST_S，LIST_O}
{LIST_S，EXEC}
{OPTIMIZE，SAVE_O，EXEC}
上述命令的类型均是powerset(Set)。
类型powerset的变量是一个集合，因此对它们的基本操作是集合的操作，可以是“联合”、“与”，以及测试类型T的给定对象是否在这个集合中。有的语言缺乏支持集合的类型，为了表示幂集，程序员只好使用布尔数组、链表或其他低级机制来实现。
语言中允许程序员利用上述从现有语言中抽象出来的机制，定义以复杂的数据对象作为基本项的聚合。例如，Pascal的结构变量说明
var a ：record x：integer；
y：array[1..10]of char
end
定义了一个记录结构变量a，而a的类型没有显式名字，但却描述了它的类型结构，这个结构是笛卡儿积，具有两个域，其中一个域是有限映像。许多语言，例如ALGOL 68，Pascal和Ada等语言提供了定义新类型的手段，使程序员可能对现有的类型重新命名，或聚合若干基本类型定义新类型。例如，Pascal可以说明下列的笛卡儿积的类型：
type complex=record radius：real；
angle：real
end
其中，类型complex的所有变量由两个域(radius和angle)组成，它们分别保存复数的绝对值和辐角。然后可再说明
var cl，c2，c3：complex；
规定名为cl，c2和c3的变量，其类型为complex。
从上述两个Pascal的类型说明可以看出，一个对类型显式命名为complex，一个未对定义的类型命名。
对程序设计来说，显式命名具有下列4个优点。
(1)可读性
适当选择新类型名能提高程序的可读性。严格使用逐步求精的过程使通过类型定义的层次结构反映出一类数据的定义。例如，在complex定义之后，可以说明类型
type voltage = complex；
voltage_table = array[1..10]of voltage；
其中，第一个语句表明voltage由复数表示，第二个语句表明类型voltage的值在10点的空间内由类型voltage_table表示。
(2)可修改性
表示对给定类型的变量数据结构的改变，只需改变类型说明，无须改变所有变量说明。但是，变量类型的改变要求对这些变量的操作也要做相应的改变，因此需要改变程序的某些指令。
(3)可分性(Factorization)
复杂数据结构的样板定义只需书写一次，然后就可多次用于需要说明的变量。若在一个程序中有许多变量需要重复同一定义，就可使用这种机制，即以一个名字来代表这个定义，减少了再用时可能出现的错误。语言中可分性概念用得比较普遍，在早期的语言中，子程序(过程)就使用了可分性。把程序中相同的代码“分”出来，用一个名字来标识，待使用这段代码时，调用标识这段代码的名字即可。
(4)一致性检查
因为允许程序员应用简单类型来定义新类型，所以影响了类型检查(Type Checking)的有效性。在这种情况下，原来只限于内部类型的检查，现在必须扩充到用户定义类型的检查。许多类型检查都可用语言规定的类型相容性(Type Compatibility)，即等价性(Equivalence)来实现(参看2 .11节)，类型检查机制将两个相容的类型作为同一类型来处理。
下面将以Pascal，Ada，C和Java语言的部分类型结构，说明上述内部类型和构造用户定义类型的6种机制。