第五章
抽象一：封装
?大型程序的构造中，程序员不可避免要涉及到新数据类型的设
计和实现。
如：大学中，表示一堂课的数据对象 section，包含的信息有：
老师名、教室、最大注册数等，还可以包含一个注册学生列
表作为部件。
操作包括：创建一个 section、注册一个学生、消除一个
section等。
其实现主要涉及其表示以及对应相关操作的子程序设计。
?语言实现的目标是使得数据的各种形式的不同对程序员透明。
因此，基本类型和用户定义类型对程序员的使用来说应不存在
差别。
?有三种机制可被程序员用来创建新类型和类型上的操作。
1、子程序：可用子程序来定义实现类型的操作，但如何正
确地使用，却是程序员的责任。
2、类型声明：语言包含有定义新类型及其操作的能力。抽
象数据类型即是这种机制，它提供了检测错误使用的能力。
3、继承：基于已有类型创建新类型的机制。
5.1 抽象数据类型
数据类型概念的演化
早期类型定义为值的集合，该类型的变量可在该集合中取值。
70年代初,Pascal扩展类型定义为：变量的集合。
70年代早期，概念进一步演化，类型不仅仅是类型对象的集
合，还包含了其相关操作。正是操作展示了对象的行为。
例：对基本类型实数和整数，语言提供了声明机制和相
关操作。从而其存储表示被封装，程序员使用它们而不
需知道表示细节。
?数据抽象 —— 以数据为中心的封装方式
ADT定义为,
1、一组数据对象，通常使用一个或多个类型定义。
2、一组对这些对象的抽象操作。
3、二者的封装，使得该类型的用户只能通过这些操作来
操纵该类型的数据对象。
信息隐蔽
?“分而治之”是我们编写大型程序的一般策略，程序被分成
模块。
模块设计有两种途径：①功能分解，②数据分解。
然而，功能设计有一定缺陷，不能对数据结构的细节提供
很好隐蔽。
而使用数据抽象可以避免这些问题。
?数据类型的规约给出了所有使用该类型对象所需要的信息，
而实现细节则对外屏蔽。
?“抽象”在语言中是一个重要概念，语言以两种方式提供对
抽象的支持。首先，提供一个抽象虚拟机，它比实际计算机
更易于使用，也更强大，语言直接提供了一些有用的抽象，
称为语言的特性；第二，语言提供了辅助程序员定义抽象的
设施，这些抽象形成了特定程序定义的抽象机。
?信息隐蔽是程序定义抽象设施的设计的中心原则
—— 每个程序部件应尽可能对用户隐藏信息。
?当信息被封装在抽象中时，意味着抽象的用户,
1、为了使用该抽象，不需要知道隐蔽的信息。
2、不允许直接使用或操纵被隐蔽的信息，即使用户希望
这么做。
例如,Fortran,Pascal中的整数类型不仅隐蔽了整数的表
示细节，甚至有效地封装了表示，使得程序员不能操作整
数中的个体位。
但它们难于封装新数据类型的表示，虽然也可以构造子程
序集合来创建和操作抽象，但不能真正封装其表示，程序
员可以编写其他子程序来非法地或不合适地操作抽象。
?封装对使程序易于修改特别有用，只要保持子程序（操作）
接口不变即可。
?注意：信息隐蔽是一个程序设计问题，和语言无关。封装则
是语言设计问题。抽象被有效封装的前提是有机制防止外界
对抽象中隐蔽信息的访问。
5.2 通过子程序封装
子程序是程序员定义的抽象操作 —— 是大多数程序的基本建
筑块。对子程序可从两个方面来看,
在程序设计级 —— 子程序表示程序员定义的抽象操作。
在语言设计级 —— 涉及子程序设施的设计和实现。
子程序作为抽象操作
子程序的规约和实现均由程序员提供 。
?子程序的规约
包括,
1,子程序的名字
2,子程序的基调
3,子程序的动作
和基本原操作类似
函数子程序 —— 显示地返回单个结果数据对象。
基调为,FN,real× integer→real
过程式子例程 —— 返回多个结果, 或修改参数而不是显式地返
回结果 。 如,C语言中,
void Sub(float X,int Y,float * Z,int *W);
无显式返回, *表示指针, 可以被修改的参数 。
Ada中,procedure Sub (X,in REAL; Y,in integer;
Z,inout REAL; W,out Boolean)
其基调为,Sub,real1× integer× real2→real 3× Boolean
in和 out指出参数的性质 。
当子程序表示数学函数, 如何精确地描述其功能有如下问题,
1,子程序可能有隐式参数 （ 以非局部变量形式 ）
2,子程序可能有隐式结果 （ 副作用 ） （ 对非局部变量和 in-
out参数 ）
3,可能对某些可能的参数没有定义 。
4,子程序是历史敏感的 。
?子程序的实现
一个子程序表示了由程序员构造的虚拟机层次上的一个操
作。这样，子程序用程序语言本身提供的数据结构和操作
来实现。
子程序的实现用子程序体定义。包括,
局部数据声明 —— 定义局部结构或数据；
语句 —— 定义动作。
封装保证：局部数据和语句不可被用户单独访问，只
能通过传入参数而调用子程序。
有些语言中,Body中也允许其他子程序的定义。
子程序调用需要合适类型的参数，因此，类型检查也是需
要的。类型检查和基本操作类似处理。
子程序定义和调用
?子程序定义和子程序激活
子程序定义描述程序的静态性质，在执行中，如子程序
被调用，则子程序的一个激活被创建，当子程序执行结
果，则激活被消除，因此，定义作为创建执行过程中激
活的模板。
?定义和激活的不同是重要的。
定义是程序的语法成分，其信息只是在翻译时所用信息
（如变量类型，但其左、右值并不知道）。
激活在执行时存在（可访问左值、执行右值，但类型不
再可用，除非描述子）。
?二者的差别类似于类型（作为模板）定义和数据对象（运
行的创建）的差别。
malloc在程序运行时创建新对象。
call则是创建一个新的程序激活。
?事实上，激活也可视为一种数据对象，表示为存储块，含
有分量数据项。
?激活也有生命期。
?激活中独有的概念有：执行某激活，在执行中引用和修改
其他数据对象。
?子程序定义和激活的实现
考虑 C中的子程序定义,
float FN (float X,int Y)
{onst initval=2; 常量定义,initval有左值和右值。
#define finalval 10 宏定义,finalval无左值，只有右值。
Float M(10); int N;
……
N=initval;
If (N<finalval) {……}
Return (20*X+M(N));}
这个定义描述了子程序的运行时激活所需的部件
1,FN的基调行定义了参数和结果所需存储信息。
2、声明提供了局部变量的存储（ M和 N）。
3、文字及被定义常量的存储。
4、从子程序体中语句生成的可执行代码的存储。
图 5.1显示了子程序定义的运行时模板。
?激活的模板分为两个部分,
静态部分：称为代码段, 包含常量和可执行代码 。 它在
子程序执行中是不变的, 可被所有激活共享 。
动态部分：称为激活记录, 包含参数, 结果, 局部数据
以及其它实现项 （ 临时存储区, 返回点, 非局部变量引
用连接等 ）, 每个激活有相同结构, 但数值不同 。
图 5.2显示了子程序执行中的实际结构 。
子程序激活的结构（图 5.1）
共享代码和分开的激活记录（图 5.2）
?激活记录的结构和大小在翻译时确定，其在存储中的表示和
记录类型的数据对象类似。
?为了创建激活记录，只需要知道存储块的尺寸，不需知道其
结构细节，因为块中位移已在编译时确定，只是基地址在运
行时确定。因此，不需在运行时存放完全的激活模板，只需
存放尺寸大小即可。
?当子程序调用时，有一些隐敝动作发生，这些动作在实际代
码执行前完成。
?子程序终止时，也有一些动作，这些动作代码是编译插入的。
?类属子程序
类属子程序一个名字, 但有几个不同定义, 用不同基调
区分, 是一种重载机制 （ overload） 。
如 P207的例子, Enter子程序是重载的 。
如使用类型作参数, 则形成多态机制 。
子程序定义作为数据对象
大多数语言中，子程序定义独立于子程序执行。
某些语言，如 Lisp等，对这两个阶段没有区别，子程序定义
可作为运行时对象。
翻译 —— 以字符串形式看待子程序，并产生表示该定义的运
行时形式（编译时操作）。
执行 —— 以运行时形式定义为输入，创建其激活形式，然后
执行激活（运行时操作）。
而在 Lisp中，翻译也可在运行时进行。
5.3 类型定义
要定义一个新的抽象数据类型，需要某种机制来定义一组数
据对象，这种机制称为类型定义。
在类型定义中，给出一个类型名，以及关于数据对象结构的
声明。如,PASCAL中,
type Rational-record
numerator:integer
demominator:integer
End
声明,var A,B,C,Rational 不需要重复描述结构。
C语言中,
struct Rational Type
{int numerator;
int denominator;}
声明,struct Rational Type,A,B,C;
上述定义方式建背了我们的数据抽象原则。我们希望新类型
是语言的自然扩展，在语法和语义上类似基本类型，但 struct
的使用破坏了此规则。采用另一个方可解决这个问题。
Typedef struct Rational Type 这里 typedef类似宏
{int numerator;
int denominator;}Rational
声明,Rational A,B,C;
类型定义的优点：修改局部化，只需对类型修改即可。作为
参数时，不需全写类型定义。
类型定义在执行中用为构造数据对象的模板。
类型定义是封装和信息隐蔽的一种新形式，隐蔽了内部结构。
?实现：类型定义只在翻译过程中使用，对语言实现本身没有
什么影响。
类型等价
类型检查涉及类型的比较，类型等价带来两个相关概念,
1、两个类型相同，含义是什么？ → 类型问题
2、同类型的两个数据对象相等，含义是什么？ → 语义问题
?类型相等
例,Program main (input,output);
type Vect1,Array [1..10] of real;
Vect2,Array [1..10] of real;
Var X,Z,Vect1; Y,Vect2;
Procedure Sub (A,Vect 1);…
End
Begin
X=Y;
Sub(Y)
end
问题：是否 X,Y,Z和 A有相同类型？
?两种解决方案,
名等价 —— 两个类型是等价的，仅当他们有相同名字
这样 Vect1,Vect2不是相同类型，虽然有相同结构。
X:=Y是非法的。
名等价的缺点,
1、每个数据对象必须有类型名：不能有匿名类型。
如,Var W,array [1..10] of real
W有类型，但不能作为子程序参数，因其无类型名。
2、单个类型定义必须为所有或大部分程序服务，需有
单独的全局类型定义。
结构等价 —— 两个类型是等价的，仅当他们有相同的内部
部件（意味着相同存储表示）。这样 Vect1,Vect2是等价类
型。
缺点,
1、结构等价带来一些微妙问题，如：对记录，是否部件
名必须相同？是否数组下标域是相同的？枚举中文字和顺
序是否必须相同。
2、即使程序员将两个变量声明为不同类型，但可能是结
构等价的。
例,type Meters=integer;
Liters=integer;
Var Len,Meters; Vol,Liters;
Len和 Vol是结构等价的，这样 Len+Vol这样的类型
错便不可检测。
3、经常确定两个复杂类型是否结构等价、翻译代价较大。
类型等价的方式在语言设计中是一个重要问题。
?数据对象相等
编译器确定两个对象有相同类型，但它们是否相等？大多数
语言对此没有提供帮助。
例,struct stack struct set
{int Topstack; {int NumberInSet;
int Data [100];} X,Y; int Data [100];} A,B;
X,Y,A,B是结构等价的，然而 X=Y和 A=B的条件却不同。
栈相等性
1,X.TopStack=Y.TopStack
2,X,Data[I]=Y,Data [I]
Set相等性
1,A,NumberInSet=B.NumberInSet
2,A.Data[0],…,A Data [NumberInSet -1]是
B.Data[0],…B,Data [NumberInSet -1]的一个排列。
这是没有考虑操作的实现对其的影响。因此，没有公共
机制来刻划复杂对象的相等性，常见的方法是用户在定
义类型时，同时定义相应的相等操作。
带参数的类型定义
类型参数化可定义一组相似的类型，例,
type Section (MaxSize,integer) is
record
Room,integer;
Instructor,integer;
ClassSize,integer range 0..MaxSize;
ClassRoll,array (1..Max Size) of Student-ID;
end record;
X,Section (100)
Y,Section (25)
允许大小发生变化。
ML中允许类型为参数,
Signature OrderedIterm=Sig
Type elem
Var lessthan,elem*elem→bool
end; 定义可比元素类型
定义新类型如下,
Structure intitem,Ordered Item=
Struct type elem=int
fun less (I:elem,j:elem)=(i<j)
end;－－定义 intitem作为整数类型的变体
?实现
在编译时作为模板实现。但对带参数的变量声明的翻
译是首先将参数值填入类型定义，得到完全的无参数
类型定义。
5.4 存储管理
存储管理是程序员、语言实现者和语言设计者考虑的中心问
题之一。
语言中含有对使用的存储管理技术的某种期望和限制。
如：在 Fortran中，有对子程序非递归调用的限制。
但 Fortran中是允许递归调用的，它的实现需要返回点的运
行时栈（需要动态存储管理）。
如没有递归调用,Fortran可只用静态存储管理实现。
虽然每个语言设计通常允许某种存储管理技术的使用，但机
制的细节、在软硬件中的表示却是实现者的任务。
程序对存储的直接控制较少，只能通过不同语言特性的使用
产生间接影响。
主要的需要存储的运行时元素
?被翻译用户程序的代码段：两种形式（可执行机器代码或某
种中间形式）。
?系统运行时程序 —— 支持用户程序执行系统程序，包括：简
单的库例程、运行时的软件解释器或翻译器、控制运行时存
储管理的例程等。通常形式为硬件可执行的机器代码。
?用户定义的数据结构和常量。
?子程序返回点：子程序可在程序中任何点被调用，需分配存
储的内容包括：返回点、协同例程恢复点、被调度子程序的
事件通知等。
?引用环境 —— 指标识符关联
?表达式计值的临时空间 —— 用于存放中间结果。当递归存在
时，临时空间需要可能是无限的。
?输入、输出缓冲 —— 用于外部介质间数据的交换。
?其他零散系统数据 —— 表,I/O状态信息、以及各种状态信
息。
除此之外，有些操作也需要存储空间,
?子程序调用和返回操作 —— 子程序激活记录、局部引用环境、
及其他数据。而返回操作需要释放这些存储。
?数据结构创建和后除操作 —— 允许动态创建数据结构时，
需要动态分配存储操作。
?部件插入和删除操作
这些操作需要显式的存储管理。许多其他操作需要其他隐蔽
存储管理发生，大多涉及分配和回收。
程序员和系统控制的存储管理
程序员被允许在何种程度上直接控制存储管理？
C允许程序员通过 Malloc和 free控制存储。
而很多高级语言不允许程序员直接控制存储。
程序员控制存储管理的困难是两方面的：会大大增加程序员
的负担，也会干扰必须的系统管理。
没有任何高级语言允许程序员全面管理存储。一方面，他
不可能管理系统数据，最多只能管理局部数据。另一方面，
对程序员来说也是危险的，因为可能导致微妙的错误。
程序员管理存储的优点在于,
系统很难确定什么时候存储可被有效地分配和释放。
而程序员可以精确地知道什么时候某特定结构是需要
的，什么时候不再需要。
这种程度的确定是一个争议的话题，涉及性能、灵活性和
安全间的权衡。
?存储管理阶段
有三个基本方面,
?初始分配：在执行开始时，每个存储片可能是自由的或
被分配使用，如果自由，则可在执行过程中分配，存储管
理需要保持自由存储区的轨迹。
?恢复：被分配过的存储块可能重新可用。因此，必须收
回，简单的回收可以是堆栈指针的重定位，复杂的可以是
垃圾回收。
?合并和重用：回忆的存储可能是立即可重用的，也可能
需先将小碎片合并为大的存储块。重用和初始分配的机制
一样。
静态存储管理
静态分配是最简单的分配形式 —— 在翻译时分配并在执行中
保持不变。
通常，代码段和系统程序是静态分配的，静态分配不需要运
行时存储管理，无需回收和重用。
一般在 Fortran的实现中，所有存储都是静态分配的。
静态存储分配效率高，因为不需要为运行时存储管理花费时
间和空间。
翻译器可为所有数据项生成直接的左值，但不适合递归子程
序调用。在递归中，数据结构大小依赖于计算或输入数值。
基于栈的存储管理
最简单的运行时存储管理技术是堆栈。
在执行开始时，自由存储被变量为内存中顺序快，按栈方
式进行管理，分配和回收均在一端进行。
栈指针被用于控制存储管理，总是指向栈顶，即下一个可
用的存储位置，被视为被用存储和自由存储的分界点。
合并（ compaction）作为释放存储动作的一部份自动发生。
因为需要存储的程序和数据元素是和子程序激活紧紧关联
的，这是一个严格嵌套的子程序调用的后进先出结构。当
子程序被调用，则在栈顶创建一个新的激活记录。
大多数 Pascal实现采用一个单一的中央激活记录栈，再加
上静态分配的系统程序和子程序代码区域，图 5.5(a)是典
型的 Pascal子程序激活记录结构，图 5.5(b)是 Pascal运行时
存储组织。
PASCAL中存储组织,
LISP实现中栈略有不同。
子程序（函数）调用也是严格嵌套，栈用于激活记录。
每个激活记录包含一个返回点及表达式计值和参数传递
的临时区域。
局部引用环境也可能在同一栈中分配，但允许程序员直
接操纵这些关联的情形除外。
因此，它们通常存放在分开的栈中，表示为了一个链接
表，称为 A表。
LISP实现需要一个堆存储区域，通过自由空间表和垃圾
回收来管理，如图 5.6 。
执行时的 LISP存储组织
堆存储管理：固定长元素
?堆是一个存储块，其中片段被以某种相对无结构的方式分配
和释放。
?堆管理的需要来自当语言允许在程序执行中任意点分配和回
收存储。
?堆存储管理技术可分为两类：根据分配元素是定长或变长。
?针对定长的堆管理。
假定定长的元素占据 N个字，通常 N为 1或 2，假定堆为连
续区域。通常被概念地分为 K个元素，每个长度为 N，
K× N是总尺寸。
初始时 K个元素被链接在一起形成一自由空间表。
每次从头部分配，也从头部回收，如图 5.7 。
自由空间表结构
?恢复：引用记数和垃圾回收
将新的自由存储连到自由空间表是简单的；只要它可被
标记和恢复即可。但标识和恢复是相当困难的，需要确
定堆中哪个元素可再用。
有三种解决方案,
?程序员或系统显示归还 —— 这是最简单的恢复技术。
元素被显式地标识为,free”并归还给自由空间表。
对用于系统目的的元素，每个系统例程负责归还空间，
通过显式的 free调用。
显式归还是自然的恢复技术，但它并不总是可行的，问
题来自于“垃圾”和“悬空引用”。
如垃圾增多，可用存储将逐步减少，直至程序不能再
运行。
悬空引用可能引发错误，使剩余的存储空间丢失，或
使其他空间被看成自由空间。
对运行时系统要避免垃圾和悬空引用是非常困难的。为克
服这些问题，引用记数（检查指向给定元素的指针数，使
得不会产生悬空引用）和垃圾回收（允许创建垃圾，但不
允许悬空引用）是变通方法。
不归还，会产生垃圾
归还，有可能产生悬空引用
?引用记数
在每个元素中，使用额外空间作为引用记录器，记下指
向该元素的指针数。初始分配一个元素其指针记数为 1，
每次新有指针指向它，则计数加 1，每次有指针被删去，
则计数减 1。当记数为 0时，则可能回收。
在大多数情况下，该方法可以避免垃圾和悬空引用。
引用计数还可以对程序显式使用 free操作进行保护。如记
数不为 0，则忽略 free操作。
引用计数最大的困难是维护代价大，并会降低执行效率。
例：考虑 P,=Q,P,Q均为指针，如考虑计数，则操
作步骤为,
1、访问 P指向的元素，将其引用数减 1。
2、测试结果如为 0，归还该元素到自由空间表。
3、拷贝 Q中左值到 P。
4、访问 Q指向的元素，将其引用数增 1。
本技术在并行处理系统中是常用的。
?垃圾回收
悬空引用远比垃圾更为危险，但二者是相关的。悬空引用
是由于过早释放空间而产生的，垃圾则是由于过晚还未释
放。同时解决两个总是通常代价太大。
基本策略是允许垃圾产生以避免悬空引用。当自由空间表
耗尽且需要更多的存储时，计算暂时挂起，执行额外的垃
圾回收过程。回收涉及两个阶段,
△ 标记：此时，堆中的活动元素（是可访问数据结构
的一部分）需被标记。每个元素中有一个位，初始现为
,on”，标志算法将活动元素的标志位设为,off”。
△ Sweep（扫除）：顺序扫描堆，凡是,off”的元素被
略过，,on”元素被回收。
其中，标记部分是困难的，一个元素的检查并不能指出其
状态。
什么时候一个堆元素是活动的？
当有来自堆外的指针或来自另一个活动的堆元素的指针。
对这个标记过程有三个关键假设,
1、任何活动元素必须从堆外开始的指针链可达。
2、必须可以标识堆外的每个指向堆中元素的指针。
3、必须可以标识在任何堆中元素中的指针域（指向其
他堆元素）。
LISP满足这三个假设，因而允许垃圾回收。如这些假设不
会满足，则将可能无法标志某些元素。如 C中，假设 2,3
不成立。
在 LISP中，每个堆元素有相同格式，有两个指针域和一个
系统数据位串，这些指针在相同位置，满足假设 3。
只有少量的系统数据结构包含到堆的指针，从这些结构开
始标记可保证所有外部指针的标识，满足假设 2。
不可能到达一个堆元素而不通过堆外开始的指针链，满足
假设 1。
LISP堆和存储分配
f1(x,y,z)=(cons x (f2 y z))
f2(v,w)=(cons v w)
堆存储管理：可变长元素
涉及可变长元素的分配和回收的堆存储管理更为困难。这种
情况发生在如下情形，如：空间用于对程序员定义的结构的
分配，任务的激活记录等。
主要困难是回收空间的再利用问题，因为回收的块可能大小
不适合使用。
?初始分配和重用
对定长元素，可将整个堆分成一组元素，然后基于自由空
间表进行分配。
对变长元素，我们希望将堆作为尽可能大的自由存储块，
使用堆指针来完成分配。
当堆指针最终到达堆的尾部，归还的自由空间必须被重用，
有两种重用可能性,
1、使用自由空间表，查找表中适当大小的块来分配。
2、通过将所有活动元素移向堆的一端而合并自由空间，
使自由空间作为一个单块，设置堆指针指向该块的开始。
?直接从自由空间表重用
当请求一 N字元素时，扫描自由空间表中 N字块或多
于 N字的块。 N字块可直接使用，多于 N字块需分成两
个块，其中 N字块被使用，剩余块归还自由空间表。
1、最先适用方法：使用最先找到的 N字块或多于 N字
块。
2,最好适用方法：选用自由表中最小的 N字块或多
于 N字块。
如将自由空间表中元素按大小排序，可使分配更为高
效，然而，代价将花在排序过程中。
?带变长块的恢复
大致和定长块的恢复差不多，也存在垃圾和悬空引用
问题。
垃圾回收仍是可用技术，标记的方法差不多，但回收
会有困难。
回收需扫描元素，现在的问题是元素间边界的确定。
最简单的方法：结合标志位（在每个块的第一个字
中），维护存储块的长度。根据块长度确定边界，相
邻块可先合并。
垃圾回收也可结合全合并，从而不需自由空间表，只
要一个堆指针。
?合并和内存片数问题。
变长元素分配带来的问题就是内存片段问题。
自由空间最初是一整块，最后变成碎片。
因此，有必要将其合并成大的块以便再用。
有两种合并方法,
1、部分合并：活动块不能被移动（或移动代价太高），
只有相邻块可合并。
2、完全合并：活动块可移动到堆的一端，使自由空间
在另一端形成连续块。
抽象一：封装
?大型程序的构造中，程序员不可避免要涉及到新数据类型的设
计和实现。
如：大学中，表示一堂课的数据对象 section，包含的信息有：
老师名、教室、最大注册数等，还可以包含一个注册学生列
表作为部件。
操作包括：创建一个 section、注册一个学生、消除一个
section等。
其实现主要涉及其表示以及对应相关操作的子程序设计。
?语言实现的目标是使得数据的各种形式的不同对程序员透明。
因此，基本类型和用户定义类型对程序员的使用来说应不存在
差别。
?有三种机制可被程序员用来创建新类型和类型上的操作。
1、子程序：可用子程序来定义实现类型的操作，但如何正
确地使用，却是程序员的责任。
2、类型声明：语言包含有定义新类型及其操作的能力。抽
象数据类型即是这种机制，它提供了检测错误使用的能力。
3、继承：基于已有类型创建新类型的机制。
5.1 抽象数据类型
数据类型概念的演化
早期类型定义为值的集合，该类型的变量可在该集合中取值。
70年代初,Pascal扩展类型定义为：变量的集合。
70年代早期，概念进一步演化，类型不仅仅是类型对象的集
合，还包含了其相关操作。正是操作展示了对象的行为。
例：对基本类型实数和整数，语言提供了声明机制和相
关操作。从而其存储表示被封装，程序员使用它们而不
需知道表示细节。
?数据抽象 —— 以数据为中心的封装方式
ADT定义为,
1、一组数据对象，通常使用一个或多个类型定义。
2、一组对这些对象的抽象操作。
3、二者的封装，使得该类型的用户只能通过这些操作来
操纵该类型的数据对象。
信息隐蔽
?“分而治之”是我们编写大型程序的一般策略，程序被分成
模块。
模块设计有两种途径：①功能分解，②数据分解。
然而，功能设计有一定缺陷，不能对数据结构的细节提供
很好隐蔽。
而使用数据抽象可以避免这些问题。
?数据类型的规约给出了所有使用该类型对象所需要的信息，
而实现细节则对外屏蔽。
?“抽象”在语言中是一个重要概念，语言以两种方式提供对
抽象的支持。首先，提供一个抽象虚拟机，它比实际计算机
更易于使用，也更强大，语言直接提供了一些有用的抽象，
称为语言的特性；第二，语言提供了辅助程序员定义抽象的
设施，这些抽象形成了特定程序定义的抽象机。
?信息隐蔽是程序定义抽象设施的设计的中心原则
—— 每个程序部件应尽可能对用户隐藏信息。
?当信息被封装在抽象中时，意味着抽象的用户,
1、为了使用该抽象，不需要知道隐蔽的信息。
2、不允许直接使用或操纵被隐蔽的信息，即使用户希望
这么做。
例如,Fortran,Pascal中的整数类型不仅隐蔽了整数的表
示细节，甚至有效地封装了表示，使得程序员不能操作整
数中的个体位。
但它们难于封装新数据类型的表示，虽然也可以构造子程
序集合来创建和操作抽象，但不能真正封装其表示，程序
员可以编写其他子程序来非法地或不合适地操作抽象。
?封装对使程序易于修改特别有用，只要保持子程序（操作）
接口不变即可。
?注意：信息隐蔽是一个程序设计问题，和语言无关。封装则
是语言设计问题。抽象被有效封装的前提是有机制防止外界
对抽象中隐蔽信息的访问。
5.2 通过子程序封装
子程序是程序员定义的抽象操作 —— 是大多数程序的基本建
筑块。对子程序可从两个方面来看,
在程序设计级 —— 子程序表示程序员定义的抽象操作。
在语言设计级 —— 涉及子程序设施的设计和实现。
子程序作为抽象操作
子程序的规约和实现均由程序员提供 。
?子程序的规约
包括,
1,子程序的名字
2,子程序的基调
3,子程序的动作
和基本原操作类似
函数子程序 —— 显示地返回单个结果数据对象。
基调为,FN,real× integer→real
过程式子例程 —— 返回多个结果, 或修改参数而不是显式地返
回结果 。 如,C语言中,
void Sub(float X,int Y,float * Z,int *W);
无显式返回, *表示指针, 可以被修改的参数 。
Ada中,procedure Sub (X,in REAL; Y,in integer;
Z,inout REAL; W,out Boolean)
其基调为,Sub,real1× integer× real2→real 3× Boolean
in和 out指出参数的性质 。
当子程序表示数学函数, 如何精确地描述其功能有如下问题,
1,子程序可能有隐式参数 （ 以非局部变量形式 ）
2,子程序可能有隐式结果 （ 副作用 ） （ 对非局部变量和 in-
out参数 ）
3,可能对某些可能的参数没有定义 。
4,子程序是历史敏感的 。
?子程序的实现
一个子程序表示了由程序员构造的虚拟机层次上的一个操
作。这样，子程序用程序语言本身提供的数据结构和操作
来实现。
子程序的实现用子程序体定义。包括,
局部数据声明 —— 定义局部结构或数据；
语句 —— 定义动作。
封装保证：局部数据和语句不可被用户单独访问，只
能通过传入参数而调用子程序。
有些语言中,Body中也允许其他子程序的定义。
子程序调用需要合适类型的参数，因此，类型检查也是需
要的。类型检查和基本操作类似处理。
子程序定义和调用
?子程序定义和子程序激活
子程序定义描述程序的静态性质，在执行中，如子程序
被调用，则子程序的一个激活被创建，当子程序执行结
果，则激活被消除，因此，定义作为创建执行过程中激
活的模板。
?定义和激活的不同是重要的。
定义是程序的语法成分，其信息只是在翻译时所用信息
（如变量类型，但其左、右值并不知道）。
激活在执行时存在（可访问左值、执行右值，但类型不
再可用，除非描述子）。
?二者的差别类似于类型（作为模板）定义和数据对象（运
行的创建）的差别。
malloc在程序运行时创建新对象。
call则是创建一个新的程序激活。
?事实上，激活也可视为一种数据对象，表示为存储块，含
有分量数据项。
?激活也有生命期。
?激活中独有的概念有：执行某激活，在执行中引用和修改
其他数据对象。
?子程序定义和激活的实现
考虑 C中的子程序定义,
float FN (float X,int Y)
{onst initval=2; 常量定义,initval有左值和右值。
#define finalval 10 宏定义,finalval无左值，只有右值。
Float M(10); int N;
……
N=initval;
If (N<finalval) {……}
Return (20*X+M(N));}
这个定义描述了子程序的运行时激活所需的部件
1,FN的基调行定义了参数和结果所需存储信息。
2、声明提供了局部变量的存储（ M和 N）。
3、文字及被定义常量的存储。
4、从子程序体中语句生成的可执行代码的存储。
图 5.1显示了子程序定义的运行时模板。
?激活的模板分为两个部分,
静态部分：称为代码段, 包含常量和可执行代码 。 它在
子程序执行中是不变的, 可被所有激活共享 。
动态部分：称为激活记录, 包含参数, 结果, 局部数据
以及其它实现项 （ 临时存储区, 返回点, 非局部变量引
用连接等 ）, 每个激活有相同结构, 但数值不同 。
图 5.2显示了子程序执行中的实际结构 。
子程序激活的结构（图 5.1）
共享代码和分开的激活记录（图 5.2）
?激活记录的结构和大小在翻译时确定，其在存储中的表示和
记录类型的数据对象类似。
?为了创建激活记录，只需要知道存储块的尺寸，不需知道其
结构细节，因为块中位移已在编译时确定，只是基地址在运
行时确定。因此，不需在运行时存放完全的激活模板，只需
存放尺寸大小即可。
?当子程序调用时，有一些隐敝动作发生，这些动作在实际代
码执行前完成。
?子程序终止时，也有一些动作，这些动作代码是编译插入的。
?类属子程序
类属子程序一个名字, 但有几个不同定义, 用不同基调
区分, 是一种重载机制 （ overload） 。
如 P207的例子, Enter子程序是重载的 。
如使用类型作参数, 则形成多态机制 。
子程序定义作为数据对象
大多数语言中，子程序定义独立于子程序执行。
某些语言，如 Lisp等，对这两个阶段没有区别，子程序定义
可作为运行时对象。
翻译 —— 以字符串形式看待子程序，并产生表示该定义的运
行时形式（编译时操作）。
执行 —— 以运行时形式定义为输入，创建其激活形式，然后
执行激活（运行时操作）。
而在 Lisp中，翻译也可在运行时进行。
5.3 类型定义
要定义一个新的抽象数据类型，需要某种机制来定义一组数
据对象，这种机制称为类型定义。
在类型定义中，给出一个类型名，以及关于数据对象结构的
声明。如,PASCAL中,
type Rational-record
numerator:integer
demominator:integer
End
声明,var A,B,C,Rational 不需要重复描述结构。
C语言中,
struct Rational Type
{int numerator;
int denominator;}
声明,struct Rational Type,A,B,C;
上述定义方式建背了我们的数据抽象原则。我们希望新类型
是语言的自然扩展，在语法和语义上类似基本类型，但 struct
的使用破坏了此规则。采用另一个方可解决这个问题。
Typedef struct Rational Type 这里 typedef类似宏
{int numerator;
int denominator;}Rational
声明,Rational A,B,C;
类型定义的优点：修改局部化，只需对类型修改即可。作为
参数时，不需全写类型定义。
类型定义在执行中用为构造数据对象的模板。
类型定义是封装和信息隐蔽的一种新形式，隐蔽了内部结构。
?实现：类型定义只在翻译过程中使用，对语言实现本身没有
什么影响。
类型等价
类型检查涉及类型的比较，类型等价带来两个相关概念,
1、两个类型相同，含义是什么？ → 类型问题
2、同类型的两个数据对象相等，含义是什么？ → 语义问题
?类型相等
例,Program main (input,output);
type Vect1,Array [1..10] of real;
Vect2,Array [1..10] of real;
Var X,Z,Vect1; Y,Vect2;
Procedure Sub (A,Vect 1);…
End
Begin
X=Y;
Sub(Y)
end
问题：是否 X,Y,Z和 A有相同类型？
?两种解决方案,
名等价 —— 两个类型是等价的，仅当他们有相同名字
这样 Vect1,Vect2不是相同类型，虽然有相同结构。
X:=Y是非法的。
名等价的缺点,
1、每个数据对象必须有类型名：不能有匿名类型。
如,Var W,array [1..10] of real
W有类型，但不能作为子程序参数，因其无类型名。
2、单个类型定义必须为所有或大部分程序服务，需有
单独的全局类型定义。
结构等价 —— 两个类型是等价的，仅当他们有相同的内部
部件（意味着相同存储表示）。这样 Vect1,Vect2是等价类
型。
缺点,
1、结构等价带来一些微妙问题，如：对记录，是否部件
名必须相同？是否数组下标域是相同的？枚举中文字和顺
序是否必须相同。
2、即使程序员将两个变量声明为不同类型，但可能是结
构等价的。
例,type Meters=integer;
Liters=integer;
Var Len,Meters; Vol,Liters;
Len和 Vol是结构等价的，这样 Len+Vol这样的类型
错便不可检测。
3、经常确定两个复杂类型是否结构等价、翻译代价较大。
类型等价的方式在语言设计中是一个重要问题。
?数据对象相等
编译器确定两个对象有相同类型，但它们是否相等？大多数
语言对此没有提供帮助。
例,struct stack struct set
{int Topstack; {int NumberInSet;
int Data [100];} X,Y; int Data [100];} A,B;
X,Y,A,B是结构等价的，然而 X=Y和 A=B的条件却不同。
栈相等性
1,X.TopStack=Y.TopStack
2,X,Data[I]=Y,Data [I]
Set相等性
1,A,NumberInSet=B.NumberInSet
2,A.Data[0],…,A Data [NumberInSet -1]是
B.Data[0],…B,Data [NumberInSet -1]的一个排列。
这是没有考虑操作的实现对其的影响。因此，没有公共
机制来刻划复杂对象的相等性，常见的方法是用户在定
义类型时，同时定义相应的相等操作。
带参数的类型定义
类型参数化可定义一组相似的类型，例,
type Section (MaxSize,integer) is
record
Room,integer;
Instructor,integer;
ClassSize,integer range 0..MaxSize;
ClassRoll,array (1..Max Size) of Student-ID;
end record;
X,Section (100)
Y,Section (25)
允许大小发生变化。
ML中允许类型为参数,
Signature OrderedIterm=Sig
Type elem
Var lessthan,elem*elem→bool
end; 定义可比元素类型
定义新类型如下,
Structure intitem,Ordered Item=
Struct type elem=int
fun less (I:elem,j:elem)=(i<j)
end;－－定义 intitem作为整数类型的变体
?实现
在编译时作为模板实现。但对带参数的变量声明的翻
译是首先将参数值填入类型定义，得到完全的无参数
类型定义。
5.4 存储管理
存储管理是程序员、语言实现者和语言设计者考虑的中心问
题之一。
语言中含有对使用的存储管理技术的某种期望和限制。
如：在 Fortran中，有对子程序非递归调用的限制。
但 Fortran中是允许递归调用的，它的实现需要返回点的运
行时栈（需要动态存储管理）。
如没有递归调用,Fortran可只用静态存储管理实现。
虽然每个语言设计通常允许某种存储管理技术的使用，但机
制的细节、在软硬件中的表示却是实现者的任务。
程序对存储的直接控制较少，只能通过不同语言特性的使用
产生间接影响。
主要的需要存储的运行时元素
?被翻译用户程序的代码段：两种形式（可执行机器代码或某
种中间形式）。
?系统运行时程序 —— 支持用户程序执行系统程序，包括：简
单的库例程、运行时的软件解释器或翻译器、控制运行时存
储管理的例程等。通常形式为硬件可执行的机器代码。
?用户定义的数据结构和常量。
?子程序返回点：子程序可在程序中任何点被调用，需分配存
储的内容包括：返回点、协同例程恢复点、被调度子程序的
事件通知等。
?引用环境 —— 指标识符关联
?表达式计值的临时空间 —— 用于存放中间结果。当递归存在
时，临时空间需要可能是无限的。
?输入、输出缓冲 —— 用于外部介质间数据的交换。
?其他零散系统数据 —— 表,I/O状态信息、以及各种状态信
息。
除此之外，有些操作也需要存储空间,
?子程序调用和返回操作 —— 子程序激活记录、局部引用环境、
及其他数据。而返回操作需要释放这些存储。
?数据结构创建和后除操作 —— 允许动态创建数据结构时，
需要动态分配存储操作。
?部件插入和删除操作
这些操作需要显式的存储管理。许多其他操作需要其他隐蔽
存储管理发生，大多涉及分配和回收。
程序员和系统控制的存储管理
程序员被允许在何种程度上直接控制存储管理？
C允许程序员通过 Malloc和 free控制存储。
而很多高级语言不允许程序员直接控制存储。
程序员控制存储管理的困难是两方面的：会大大增加程序员
的负担，也会干扰必须的系统管理。
没有任何高级语言允许程序员全面管理存储。一方面，他
不可能管理系统数据，最多只能管理局部数据。另一方面，
对程序员来说也是危险的，因为可能导致微妙的错误。
程序员管理存储的优点在于,
系统很难确定什么时候存储可被有效地分配和释放。
而程序员可以精确地知道什么时候某特定结构是需要
的，什么时候不再需要。
这种程度的确定是一个争议的话题，涉及性能、灵活性和
安全间的权衡。
?存储管理阶段
有三个基本方面,
?初始分配：在执行开始时，每个存储片可能是自由的或
被分配使用，如果自由，则可在执行过程中分配，存储管
理需要保持自由存储区的轨迹。
?恢复：被分配过的存储块可能重新可用。因此，必须收
回，简单的回收可以是堆栈指针的重定位，复杂的可以是
垃圾回收。
?合并和重用：回忆的存储可能是立即可重用的，也可能
需先将小碎片合并为大的存储块。重用和初始分配的机制
一样。
静态存储管理
静态分配是最简单的分配形式 —— 在翻译时分配并在执行中
保持不变。
通常，代码段和系统程序是静态分配的，静态分配不需要运
行时存储管理，无需回收和重用。
一般在 Fortran的实现中，所有存储都是静态分配的。
静态存储分配效率高，因为不需要为运行时存储管理花费时
间和空间。
翻译器可为所有数据项生成直接的左值，但不适合递归子程
序调用。在递归中，数据结构大小依赖于计算或输入数值。
基于栈的存储管理
最简单的运行时存储管理技术是堆栈。
在执行开始时，自由存储被变量为内存中顺序快，按栈方
式进行管理，分配和回收均在一端进行。
栈指针被用于控制存储管理，总是指向栈顶，即下一个可
用的存储位置，被视为被用存储和自由存储的分界点。
合并（ compaction）作为释放存储动作的一部份自动发生。
因为需要存储的程序和数据元素是和子程序激活紧紧关联
的，这是一个严格嵌套的子程序调用的后进先出结构。当
子程序被调用，则在栈顶创建一个新的激活记录。
大多数 Pascal实现采用一个单一的中央激活记录栈，再加
上静态分配的系统程序和子程序代码区域，图 5.5(a)是典
型的 Pascal子程序激活记录结构，图 5.5(b)是 Pascal运行时
存储组织。
PASCAL中存储组织,
LISP实现中栈略有不同。
子程序（函数）调用也是严格嵌套，栈用于激活记录。
每个激活记录包含一个返回点及表达式计值和参数传递
的临时区域。
局部引用环境也可能在同一栈中分配，但允许程序员直
接操纵这些关联的情形除外。
因此，它们通常存放在分开的栈中，表示为了一个链接
表，称为 A表。
LISP实现需要一个堆存储区域，通过自由空间表和垃圾
回收来管理，如图 5.6 。
执行时的 LISP存储组织
堆存储管理：固定长元素
?堆是一个存储块，其中片段被以某种相对无结构的方式分配
和释放。
?堆管理的需要来自当语言允许在程序执行中任意点分配和回
收存储。
?堆存储管理技术可分为两类：根据分配元素是定长或变长。
?针对定长的堆管理。
假定定长的元素占据 N个字，通常 N为 1或 2，假定堆为连
续区域。通常被概念地分为 K个元素，每个长度为 N，
K× N是总尺寸。
初始时 K个元素被链接在一起形成一自由空间表。
每次从头部分配，也从头部回收，如图 5.7 。
自由空间表结构
?恢复：引用记数和垃圾回收
将新的自由存储连到自由空间表是简单的；只要它可被
标记和恢复即可。但标识和恢复是相当困难的，需要确
定堆中哪个元素可再用。
有三种解决方案,
?程序员或系统显示归还 —— 这是最简单的恢复技术。
元素被显式地标识为,free”并归还给自由空间表。
对用于系统目的的元素，每个系统例程负责归还空间，
通过显式的 free调用。
显式归还是自然的恢复技术，但它并不总是可行的，问
题来自于“垃圾”和“悬空引用”。
如垃圾增多，可用存储将逐步减少，直至程序不能再
运行。
悬空引用可能引发错误，使剩余的存储空间丢失，或
使其他空间被看成自由空间。
对运行时系统要避免垃圾和悬空引用是非常困难的。为克
服这些问题，引用记数（检查指向给定元素的指针数，使
得不会产生悬空引用）和垃圾回收（允许创建垃圾，但不
允许悬空引用）是变通方法。
不归还，会产生垃圾
归还，有可能产生悬空引用
?引用记数
在每个元素中，使用额外空间作为引用记录器，记下指
向该元素的指针数。初始分配一个元素其指针记数为 1，
每次新有指针指向它，则计数加 1，每次有指针被删去，
则计数减 1。当记数为 0时，则可能回收。
在大多数情况下，该方法可以避免垃圾和悬空引用。
引用计数还可以对程序显式使用 free操作进行保护。如记
数不为 0，则忽略 free操作。
引用计数最大的困难是维护代价大，并会降低执行效率。
例：考虑 P,=Q,P,Q均为指针，如考虑计数，则操
作步骤为,
1、访问 P指向的元素，将其引用数减 1。
2、测试结果如为 0，归还该元素到自由空间表。
3、拷贝 Q中左值到 P。
4、访问 Q指向的元素，将其引用数增 1。
本技术在并行处理系统中是常用的。
?垃圾回收
悬空引用远比垃圾更为危险，但二者是相关的。悬空引用
是由于过早释放空间而产生的，垃圾则是由于过晚还未释
放。同时解决两个总是通常代价太大。
基本策略是允许垃圾产生以避免悬空引用。当自由空间表
耗尽且需要更多的存储时，计算暂时挂起，执行额外的垃
圾回收过程。回收涉及两个阶段,
△ 标记：此时，堆中的活动元素（是可访问数据结构
的一部分）需被标记。每个元素中有一个位，初始现为
,on”，标志算法将活动元素的标志位设为,off”。
△ Sweep（扫除）：顺序扫描堆，凡是,off”的元素被
略过，,on”元素被回收。
其中，标记部分是困难的，一个元素的检查并不能指出其
状态。
什么时候一个堆元素是活动的？
当有来自堆外的指针或来自另一个活动的堆元素的指针。
对这个标记过程有三个关键假设,
1、任何活动元素必须从堆外开始的指针链可达。
2、必须可以标识堆外的每个指向堆中元素的指针。
3、必须可以标识在任何堆中元素中的指针域（指向其
他堆元素）。
LISP满足这三个假设，因而允许垃圾回收。如这些假设不
会满足，则将可能无法标志某些元素。如 C中，假设 2,3
不成立。
在 LISP中，每个堆元素有相同格式，有两个指针域和一个
系统数据位串，这些指针在相同位置，满足假设 3。
只有少量的系统数据结构包含到堆的指针，从这些结构开
始标记可保证所有外部指针的标识，满足假设 2。
不可能到达一个堆元素而不通过堆外开始的指针链，满足
假设 1。
LISP堆和存储分配
f1(x,y,z)=(cons x (f2 y z))
f2(v,w)=(cons v w)
堆存储管理：可变长元素
涉及可变长元素的分配和回收的堆存储管理更为困难。这种
情况发生在如下情形，如：空间用于对程序员定义的结构的
分配，任务的激活记录等。
主要困难是回收空间的再利用问题，因为回收的块可能大小
不适合使用。
?初始分配和重用
对定长元素，可将整个堆分成一组元素，然后基于自由空
间表进行分配。
对变长元素，我们希望将堆作为尽可能大的自由存储块，
使用堆指针来完成分配。
当堆指针最终到达堆的尾部，归还的自由空间必须被重用，
有两种重用可能性,
1、使用自由空间表，查找表中适当大小的块来分配。
2、通过将所有活动元素移向堆的一端而合并自由空间，
使自由空间作为一个单块，设置堆指针指向该块的开始。
?直接从自由空间表重用
当请求一 N字元素时，扫描自由空间表中 N字块或多
于 N字的块。 N字块可直接使用，多于 N字块需分成两
个块，其中 N字块被使用，剩余块归还自由空间表。
1、最先适用方法：使用最先找到的 N字块或多于 N字
块。
2,最好适用方法：选用自由表中最小的 N字块或多
于 N字块。
如将自由空间表中元素按大小排序，可使分配更为高
效，然而，代价将花在排序过程中。
?带变长块的恢复
大致和定长块的恢复差不多，也存在垃圾和悬空引用
问题。
垃圾回收仍是可用技术，标记的方法差不多，但回收
会有困难。
回收需扫描元素，现在的问题是元素间边界的确定。
最简单的方法：结合标志位（在每个块的第一个字
中），维护存储块的长度。根据块长度确定边界，相
邻块可先合并。
垃圾回收也可结合全合并，从而不需自由空间表，只
要一个堆指针。
?合并和内存片数问题。
变长元素分配带来的问题就是内存片段问题。
自由空间最初是一整块，最后变成碎片。
因此，有必要将其合并成大的块以便再用。
有两种合并方法,
1、部分合并：活动块不能被移动（或移动代价太高），
只有相邻块可合并。
2、完全合并：活动块可移动到堆的一端，使自由空间
在另一端形成连续块。
