第六节 类型检查
1,类型检查
对数据对象的类型和使用的操作是否匹
配的一致性检查称为 类型检查
2,静态检查和动态检查
① 静态检查使程序更正确更有效
② 动态检查使编程方便,但影响了可读
性,且降低了执行效率
3.强类型语言
若一个语言允许 所有 的类型静态检查
4,Pascal是非强类型语言
① 编译时,不能确定一个过程中的过程参
数和子程序参数类型
procedure who_knows(i,j:integer;procedure f);
var k:boolean;
begin k:=j<i;
if k then f(k) else f(j)
end;
② Pascal的子界不能静态检查
如, a:=b+c;
且 a,b,c均属于子界类型 1..10
③ 变体记录的标识符可以在运行时改
变
④ Pascal没有严格规定类型的一致性
规则
第七节 类型转换
1,语言应该提供类型转换机制
如 A+B
2,两种转换方式
① 拓展,整型 → 实型
② 收缩,实型 → 整型
有的, 截断,,有的, 四舍五入,
3,注意语言规定的转换规则
① Fortran:低级类型 → 高级类型
② Pascal允许,整数 → 实数 ;实数 → 整数 。 但
必须显式转换 (frunc,round)
③ ALGOL 68提供了六种强制转换规则 (隐
式的 )
④ Ada要求必须显式转换
例如, 派生类型到母体类型的转换
P是 POSITIVE的变量, L是 LENGTH的变量
P:=POSITIVE(2*L+35);
第八节 类型等价
? T1和 T2是相容的,T1可赋给 T2,T1可对应 T2
的形参；反之亦然。
1,名字等价
两个变量的类型名相同。
2,结构等价
两个变量的类型具有相同的结构。
验证法,用用户定义类型的定义来代替用户定
义名，重复这一过程，直到没有用户
定义类型名为止。
3,两种相容性实现时的比较
①名字等价的实现比较简单
②结构等价的实现需要的模式匹配过程可能十
分复杂
第九节 抽象数据类型
1,用户定义类型与内部类型的异同
① 都建立某种基本表示的抽象
如,integer是位串的抽象 ;
reg_polygon是记录的抽象
② 每一类型都关联一组操作
③ 内部类型隐蔽了基本表示, 不能对
它的成分进行操作 ;用户定义类型具
有更高级别的抽象, 可以对其基本
表示的成分进行操作 。
2,抽象数据类型的定义
满足下述特性的用户定义类型称为 抽
象数据类型,
① 在实现该类型的程序单元中,建立与
表示有关的基本操作 ;
② 对使用该类型的程序单元来说,该类
型的表示是隐蔽的 。
一, SIMULA 67的类机制
1.类的说明
<类头 >;<类体 >
<类头 >包括类名和形式参数
<类体 >是传统的分程序,可包含变量, 过程
和类的局部说明, 以及一些执行语句
例：复数表示 (幅角,半径 )
class complex（ x,y）； real x,y；
begin real angle,radius；
radius,=sqrt（ x**2+y**2）；
if abs（ x） <epsilon
then begin if abs(y)<epsilon
then error
else begin if y>epsilon
then angle:=pi/2
else angle:=3*pi/2
end
end
else angle:=arctan(y/x)
end complex
2,类的有关性质
① 类说明定义了一类数据对象的原型
或样板
② 类的每个实例是一个可操作的数据
对象
③ 类的实例可多次动态建立,且仅能通
过指针引用
例, ref(complex) c;
c:- new complex(1.0,1.0);
c
0.78
1.42
1.0
1.0
angle
radius
x
y
④ 类实例的属性是指类体的 局部变量
和类头中的 参数
my_angle:=c.angle;
my_radius:=c.radius;
my_x:=c.x;
my_y:=c.y;
⑤ 类支持抽象数据类型的封装机制,它
可以封装实现对数据操作的各种过程
例, 可将复数加和乘的过程 add和 multiply封
装入类 complex的类体说明中,作为
complex的属性。
procedure add(operand);ref (complex) operand
procedure multiply(operand);ref (complex) operand
变量 c1,c2引用的两个复数相加可表示为：
c1.add(c2)
或
c3.angle:=c1.angle;
c3.radius:=c1.radius+c2.radius;
用户可以直接访问复数的内部表示,故 add
和 multiply不是复数对象的唯一操作
3,子类
用以定义类型的判定或和类属 。
要求：定义一个栈, 完成
?引用栈顶元素
?入栈
?出栈
?判栈是否空
(这些操作与栈中元素的类型无关 )
栈内成员的元素类
class stack_member;
begin ref (stack_member) next_member;
next_member:-none
end
指针型局部变量
class stack;
begin ref (stack_member) first;
ref (stack_member) procedure top;
top:-first;
procedure pop;
if ?empty then first:-first.next_member;
procedure push(e);ref (stack_member) e;
begin if first =/=none
then e.next_member:-first;
first:-e
end push;
boolean procedure empty;
empty:=first= =none;
first:-none
end stack
stack_member class complex(……);
……
end complex
定义了一个复数栈
其中 complex称为 stack_member的子类
加在类说明之前
① 子类 complex具有自己的属性,同时
继承了 stack_member的属性
new complex
产生的对象具有 stack_member和 complex的
所有属性
ref(stack) s;
s:-new stack;
s.push(c1);
s.push(c2);
s.push(c3);
建立一个复数栈
② 具有 ref(stack_member)的变量可引用
多种类型的量,但不同类型的元素不得压
入同一栈实例中
下述语句说明向量也可是栈中元素,
stack_member class vector(…);
……
end vector
二,CLU的抽象数据类型
例, 定义复数完成, 建立、加、判等
complex=cluster is create,add,equal
rep=record[x,y:real]
create=proc(a,b:real) returns(cvt)
return(rep $ {x:a,y:b})
end create
add=proc(a,b:cvt) returns(cvt)
return(rep $ {x:a.x+b.x,y:a.y+b.y})
end add
equal=proc(a,b:cvt) returns(bool)
return(a.x=b.x and a.y=b.y)
end equal
end complex
1,簇（ Cluster）是 CLU用来定义抽象数据
类型的机制
①簇内,需要内部表示
②簇外,看到的是抽象表示
?rep说明数据对象的具体表示
?cvt用于抽象表示和具体表示之间的相互转
换,仅能在簇内使用
?return(rep $ …) 的含义为返回一个具体表示
类型的对象
2,CLU的性质
① CLU变量的作用域和生存期互不相干
P:complex 仅仅是一个说明
而 P:=complex $ create(h,k)才产生一个对象赋
于 P
② CLU变量被一致看成是对数据对象的引用
如 x:=e
其中 x类似于指针变量
③ CLU的参数传递由赋值定义
complex $ add(x,y)
把 x和 y分别赋予形式参数 a和 b
三, Ada的抽象数据类型
1,Ada用程序包描述抽象数据类型
程序包包括规格说明和程序包体
2.,移出, 的概念
这是程序包向外部世界提供的可以访问的实
体, 是程序包的可见部分
3.私有类型
① 私有类型的表示细节在程序包外是不
可见的
② 允许的操作,移出的子程序, 函数；
赋值, 相等, 不等
package COMPLEX-NUMBERS is
type COMPLEX is private；
procedure INITIALIZE（ A,B:in REAL;X:out COMPLEX);
function ADD(A,B:in COMPLEX) return COMPLEX;
private
type COMPLEX is
record R,I:REAL;
end record;
end COMPLEX-NUMBERS;
package body COMPLEX-NUMBER is
procedure INITIALIZE(A,B:in REAL;X:out COMPLEX) is
begin X.R:=A;
X.I:=B;
end INITIALIZE;
function ADD(A,B:in COMPLEX) return COMPLEX is
TEMP:COMPLEX;
begin TEMP.R:=A.R+B.R;
TEMP.I:=A.I+B.I;
return TEMP;
end ADD;
end COMPLEX-NUMBER;
4,受限私有类型
只允许程序包移出的子程序和函数,不
允许赋值, 相等和不相等
5,类属的描述
使用 generic子句说明类型是一个参数,
实例化时代以具体的类型
例, package INTEGER is new SET-MANIPULATION（ INTEGER） ；
package FLAVORS is new SET-MANIPULATION（ FLAVOR） ；
generic
type COMPONENT is private;
package SET-MANIPULATION is
type SET is limited private;
procedure INSERT(S:out SET;ELEM:in COMPONENT);
procedure DELETE(S:out SET;ELEM:in COMPONENT);
procedure IS-IN(S:in SET;ELEM)in COMPONENT) return BOOLEAN;
private
type SET is
record STORE,array(1..MAX-CARDINALITY) of COMPONENT;
CARDINALITY:INTEGER range 0..MAX-cardinality:=0;
end record;
end SET-MANIPULATION;
四, Modula-2的抽象数据类型
1,移入 (Inport)和移出 (Export)子句说明模块的
移入和移出实体
2,Modula-2 的模块可以封装一组相关子程序
3,抽象数据类型的描述由 定义模块 和 实现模块
两部分组成
4,Modula-2的模块可以移出类型，类型的细节
可通过“不透明移出”加以屏蔽
definition module ComplexNumber;
export qualified Complex,Initialize,Add;
type Complex; /* 不透明移出 */
Procedure Initialize(A,B:real;var x:Complex);
Procedure Add(A,B:Complex):Complex
end ComplexNumber,
implementation module ComplexNumber;
type C=record
R,I:real
end;
type Complex=pointer to C;
procedure Initialize(A,B:real;var x:Complex);
begin
new(x);
x?.R:=A;
x?.I:=B
end Initialize;
procedure Add(A,B:Complex):Complex;
var T:Complex;
begin
new(T);
T?.R:=A?.R+B?.R;
T?.I:=A?.I+B?.I;
return(T)
end Add
end ComplexNumber,
第十节 实现模型
描述符,描述数据对象的所有属性
数据
数据对象 (存储区及其值 )
一, 内部类型和用户定义的非结构类型
1,描述符一般由“类型”和一个指针组成
2,子界的描述符必须包括子界的界值
3,布尔型和字符型可以压缩存储
如, 整型
integer
二, 结构类型
1,笛卡尔积
① 各成分顺序排列
② 描述符包含,类型名, 构造符, 若干
三元式 。 每个域对应一个三元式 (选
择符名,域类型,指针 )
③ 每个成分占整数个可编址的存储单
元 (字编址或字节编址 ）
④ 可以用 packed显式说明压缩存储
数据对象
浮点值
定点值
描述符
类型名
构造符
选择符
选择符
类型
类型
引用
引用
t
record
a
real
b
integer
域 1
域 2
type t=record a,real；
b,integer；
end；
2,有限映象
①为 每一成分分配整数个可编址的存储单
元
②描述符包括,类型名、构造符、定义域的
基类型、下界、上界、成分类型、单元个数、
首地址
③ 地址公式的计算
b+k(i-m)=b-km+ki
其中 b 为首地址, k为所占单元数, m为下界
④ 内情向量
描述符
类型名
构造符
基类型
成分类型
下界
单元个数
上界
引用
a
array
integer
0
real
1
下标类型
10
数据对象
浮点值
浮点值
浮点值
type a=array[1..10] of real;
3,序列
可变长串的表示,
静态描述符 +动态描述符 +堆
string 5
A L
P H
A nil
4,判定或
① 判定或类型的变量分配的空间应足以容
纳需要最大空间的变体的值
② Pascal的变量记录的表示包括,描述符, 数
据对象, case表, 若干变体描述符
type v=record a:integer;
case b:boolean of
true:(c:integer);
false:(d:integer;
e:real)
end;
v
variant record
a
integer
b
boolean
?
?
?
?
?
?
?
?
(false) (true)
d
integer
e
real
c
integer
定点值
布尔值
true
false
case表
描述符 数据对象
变体描述符
5,幂集
① 集合关联一个机器字,通过每一位的
取值可知该集合中有基类型的哪些
元素
② 位操作
6,指针
指针变量的表示类似于内部类型, 只是
其值为一地址, 并且它指向的数据对象
分配在堆上
7,层次结构数据结构对象的表示
描述符中的类型可以指向另外的描述符
type t1=array[0..3] of integer;
t=record a:real;
b:t1;
c:integer
end;
t4=array[0..5] of integer;
t2=array[0..2] of t4;
t
record
a
real
b
c
integer
浮点值
定点值
定点值
定点值
定点值
定点值
t1
array
integer
0
3
integer
1
t2
array
integer
0
2
6
t4
array
integer
0
5
integer
1
定点值
第三章 控制结构
第一节 语句级控制结构
?控制结构,程序员用来规定程序各个成分
的执行流程的控制部分 。
?语句级控制结构,语言用来构造各种语句
执行顺序的机制 。
?传统语言的三种语句级控制结构,顺序,
选择, 重复 。
一, 顺序
?顺序运算符；
?语句括号 begin,,, end
?复合语句
二, 选择
1,if语句
① ALGOL 60的选择结构引起二义性
if x>0 then if x<10 then x:=0 else x:=1000
② PL/1和 Pascal的“最近匹配原则”
③ ALGOL 68中 if语句的结束符号 fi
④ ALGOL 68和 Ada对 else if 进行缩写
2,多重选择
① PL/1的 select结构
SELECT,
WHEN(A)S1;
WHEN(B)S2;
WHEN(C)S3;
OTHERWISE S4;
END
② 多种语言的 case语句
var operator:char;
operand1,operand2,result:boolean;
……
case operator of
‘.’:result:=operand1 and operand2;
‘+’:result:=operand1 or operand2;
‘=’:result:=operand1 = operand2;
end
③ Dijkestra选择结构的非确定性
if B1→S 1
? B2 →S 2
? B3 →S 3
…,.,
? BN →SN
其中, Bi是布尔表达式, 称为卫哨 。 若有
多个卫哨为真时执行任一 Si。
三, 重复
1,记数器制导
当预先知道重复次数时,在循环计数器值的有
限集合上重复 。
① FORTRAN的 DO循环中,用标号控制循环体
DO 7 I=1,10
A（ I） =0
B（ I） =0
7 CONTINUE
② Pascal的 for 语句,
?记数重复的值可在任何有序集上
? for,,, to
? for,,, downto
?在循环外循环控制变量的值无定义
2,条件制导
① while 循环：描述 0或任意多次的重复
② repeat until循环：至少一次以上的重复
③ ALGOL 68循环的一般形式,
for i from j by k to m while b do...od
④ Ada 的循环结构
loop /*可以在 loop前加重复说明 */
循环体 (语句序列 )
end loop;
?重复说明可以是,
while <条件 >
或 for <计数变量 > in <离散范围 >
或 for <计数变量 > in reverse <离散范围 >
?可由 exit或 exit when<条件 >终止循环
⑤ Dijkstra的卫哨命令表示法
do B1→S 1
? B2→S 2
,,,,,,
? BN→SN
od
四, 语句级控制结构讨论
?顺序, 选择, 重复是一定意义的抽象
?关于 goto语句的讨论
?控制结构的选择
五, 用户定义控制结构
如,Pascal的计数控制变量可以是枚举
类型
第二节 单元级控制结构
?单元级控制结构,规定程序单元之间控制
流程的机制
?四种单元级控制结构,显示调用,异常处
理,协同程序,并发单元
一, 显式调用从属单元
1.调用方式
由调用语句使用被调用单元的名字来
进行调用
2,参数的两种绑定方式
位臵绑定
关键字绑定
subprogram S(F1,F2,…,FN);
……
end
?位置绑定, call S(A1,A2,…,AN)
call S(A1,,A3,,,,,A8,,A10)
?关键字绑定,
call S(A1=>F1,A3=>F3,A8=>F8,A10=>F10)
3,副作用
—— 对非局部环境的修改
① 副作用降低了程序的可读性
② 副作用限制了数学运算律的使用
如,w:=x+f(x,y)+z
③ 副作用影响目标代码的优化
如,u:=x+z+f(x,y)+f(x,y)+x+z
1,类型检查
对数据对象的类型和使用的操作是否匹
配的一致性检查称为 类型检查
2,静态检查和动态检查
① 静态检查使程序更正确更有效
② 动态检查使编程方便,但影响了可读
性,且降低了执行效率
3.强类型语言
若一个语言允许 所有 的类型静态检查
4,Pascal是非强类型语言
① 编译时,不能确定一个过程中的过程参
数和子程序参数类型
procedure who_knows(i,j:integer;procedure f);
var k:boolean;
begin k:=j<i;
if k then f(k) else f(j)
end;
② Pascal的子界不能静态检查
如, a:=b+c;
且 a,b,c均属于子界类型 1..10
③ 变体记录的标识符可以在运行时改
变
④ Pascal没有严格规定类型的一致性
规则
第七节 类型转换
1,语言应该提供类型转换机制
如 A+B
2,两种转换方式
① 拓展,整型 → 实型
② 收缩,实型 → 整型
有的, 截断,,有的, 四舍五入,
3,注意语言规定的转换规则
① Fortran:低级类型 → 高级类型
② Pascal允许,整数 → 实数 ;实数 → 整数 。 但
必须显式转换 (frunc,round)
③ ALGOL 68提供了六种强制转换规则 (隐
式的 )
④ Ada要求必须显式转换
例如, 派生类型到母体类型的转换
P是 POSITIVE的变量, L是 LENGTH的变量
P:=POSITIVE(2*L+35);
第八节 类型等价
? T1和 T2是相容的,T1可赋给 T2,T1可对应 T2
的形参；反之亦然。
1,名字等价
两个变量的类型名相同。
2,结构等价
两个变量的类型具有相同的结构。
验证法,用用户定义类型的定义来代替用户定
义名，重复这一过程，直到没有用户
定义类型名为止。
3,两种相容性实现时的比较
①名字等价的实现比较简单
②结构等价的实现需要的模式匹配过程可能十
分复杂
第九节 抽象数据类型
1,用户定义类型与内部类型的异同
① 都建立某种基本表示的抽象
如,integer是位串的抽象 ;
reg_polygon是记录的抽象
② 每一类型都关联一组操作
③ 内部类型隐蔽了基本表示, 不能对
它的成分进行操作 ;用户定义类型具
有更高级别的抽象, 可以对其基本
表示的成分进行操作 。
2,抽象数据类型的定义
满足下述特性的用户定义类型称为 抽
象数据类型,
① 在实现该类型的程序单元中,建立与
表示有关的基本操作 ;
② 对使用该类型的程序单元来说,该类
型的表示是隐蔽的 。
一, SIMULA 67的类机制
1.类的说明
<类头 >;<类体 >
<类头 >包括类名和形式参数
<类体 >是传统的分程序,可包含变量, 过程
和类的局部说明, 以及一些执行语句
例：复数表示 (幅角,半径 )
class complex（ x,y）； real x,y；
begin real angle,radius；
radius,=sqrt（ x**2+y**2）；
if abs（ x） <epsilon
then begin if abs(y)<epsilon
then error
else begin if y>epsilon
then angle:=pi/2
else angle:=3*pi/2
end
end
else angle:=arctan(y/x)
end complex
2,类的有关性质
① 类说明定义了一类数据对象的原型
或样板
② 类的每个实例是一个可操作的数据
对象
③ 类的实例可多次动态建立,且仅能通
过指针引用
例, ref(complex) c;
c:- new complex(1.0,1.0);
c
0.78
1.42
1.0
1.0
angle
radius
x
y
④ 类实例的属性是指类体的 局部变量
和类头中的 参数
my_angle:=c.angle;
my_radius:=c.radius;
my_x:=c.x;
my_y:=c.y;
⑤ 类支持抽象数据类型的封装机制,它
可以封装实现对数据操作的各种过程
例, 可将复数加和乘的过程 add和 multiply封
装入类 complex的类体说明中,作为
complex的属性。
procedure add(operand);ref (complex) operand
procedure multiply(operand);ref (complex) operand
变量 c1,c2引用的两个复数相加可表示为：
c1.add(c2)
或
c3.angle:=c1.angle;
c3.radius:=c1.radius+c2.radius;
用户可以直接访问复数的内部表示,故 add
和 multiply不是复数对象的唯一操作
3,子类
用以定义类型的判定或和类属 。
要求：定义一个栈, 完成
?引用栈顶元素
?入栈
?出栈
?判栈是否空
(这些操作与栈中元素的类型无关 )
栈内成员的元素类
class stack_member;
begin ref (stack_member) next_member;
next_member:-none
end
指针型局部变量
class stack;
begin ref (stack_member) first;
ref (stack_member) procedure top;
top:-first;
procedure pop;
if ?empty then first:-first.next_member;
procedure push(e);ref (stack_member) e;
begin if first =/=none
then e.next_member:-first;
first:-e
end push;
boolean procedure empty;
empty:=first= =none;
first:-none
end stack
stack_member class complex(……);
……
end complex
定义了一个复数栈
其中 complex称为 stack_member的子类
加在类说明之前
① 子类 complex具有自己的属性,同时
继承了 stack_member的属性
new complex
产生的对象具有 stack_member和 complex的
所有属性
ref(stack) s;
s:-new stack;
s.push(c1);
s.push(c2);
s.push(c3);
建立一个复数栈
② 具有 ref(stack_member)的变量可引用
多种类型的量,但不同类型的元素不得压
入同一栈实例中
下述语句说明向量也可是栈中元素,
stack_member class vector(…);
……
end vector
二,CLU的抽象数据类型
例, 定义复数完成, 建立、加、判等
complex=cluster is create,add,equal
rep=record[x,y:real]
create=proc(a,b:real) returns(cvt)
return(rep $ {x:a,y:b})
end create
add=proc(a,b:cvt) returns(cvt)
return(rep $ {x:a.x+b.x,y:a.y+b.y})
end add
equal=proc(a,b:cvt) returns(bool)
return(a.x=b.x and a.y=b.y)
end equal
end complex
1,簇（ Cluster）是 CLU用来定义抽象数据
类型的机制
①簇内,需要内部表示
②簇外,看到的是抽象表示
?rep说明数据对象的具体表示
?cvt用于抽象表示和具体表示之间的相互转
换,仅能在簇内使用
?return(rep $ …) 的含义为返回一个具体表示
类型的对象
2,CLU的性质
① CLU变量的作用域和生存期互不相干
P:complex 仅仅是一个说明
而 P:=complex $ create(h,k)才产生一个对象赋
于 P
② CLU变量被一致看成是对数据对象的引用
如 x:=e
其中 x类似于指针变量
③ CLU的参数传递由赋值定义
complex $ add(x,y)
把 x和 y分别赋予形式参数 a和 b
三, Ada的抽象数据类型
1,Ada用程序包描述抽象数据类型
程序包包括规格说明和程序包体
2.,移出, 的概念
这是程序包向外部世界提供的可以访问的实
体, 是程序包的可见部分
3.私有类型
① 私有类型的表示细节在程序包外是不
可见的
② 允许的操作,移出的子程序, 函数；
赋值, 相等, 不等
package COMPLEX-NUMBERS is
type COMPLEX is private；
procedure INITIALIZE（ A,B:in REAL;X:out COMPLEX);
function ADD(A,B:in COMPLEX) return COMPLEX;
private
type COMPLEX is
record R,I:REAL;
end record;
end COMPLEX-NUMBERS;
package body COMPLEX-NUMBER is
procedure INITIALIZE(A,B:in REAL;X:out COMPLEX) is
begin X.R:=A;
X.I:=B;
end INITIALIZE;
function ADD(A,B:in COMPLEX) return COMPLEX is
TEMP:COMPLEX;
begin TEMP.R:=A.R+B.R;
TEMP.I:=A.I+B.I;
return TEMP;
end ADD;
end COMPLEX-NUMBER;
4,受限私有类型
只允许程序包移出的子程序和函数,不
允许赋值, 相等和不相等
5,类属的描述
使用 generic子句说明类型是一个参数,
实例化时代以具体的类型
例, package INTEGER is new SET-MANIPULATION（ INTEGER） ；
package FLAVORS is new SET-MANIPULATION（ FLAVOR） ；
generic
type COMPONENT is private;
package SET-MANIPULATION is
type SET is limited private;
procedure INSERT(S:out SET;ELEM:in COMPONENT);
procedure DELETE(S:out SET;ELEM:in COMPONENT);
procedure IS-IN(S:in SET;ELEM)in COMPONENT) return BOOLEAN;
private
type SET is
record STORE,array(1..MAX-CARDINALITY) of COMPONENT;
CARDINALITY:INTEGER range 0..MAX-cardinality:=0;
end record;
end SET-MANIPULATION;
四, Modula-2的抽象数据类型
1,移入 (Inport)和移出 (Export)子句说明模块的
移入和移出实体
2,Modula-2 的模块可以封装一组相关子程序
3,抽象数据类型的描述由 定义模块 和 实现模块
两部分组成
4,Modula-2的模块可以移出类型，类型的细节
可通过“不透明移出”加以屏蔽
definition module ComplexNumber;
export qualified Complex,Initialize,Add;
type Complex; /* 不透明移出 */
Procedure Initialize(A,B:real;var x:Complex);
Procedure Add(A,B:Complex):Complex
end ComplexNumber,
implementation module ComplexNumber;
type C=record
R,I:real
end;
type Complex=pointer to C;
procedure Initialize(A,B:real;var x:Complex);
begin
new(x);
x?.R:=A;
x?.I:=B
end Initialize;
procedure Add(A,B:Complex):Complex;
var T:Complex;
begin
new(T);
T?.R:=A?.R+B?.R;
T?.I:=A?.I+B?.I;
return(T)
end Add
end ComplexNumber,
第十节 实现模型
描述符,描述数据对象的所有属性
数据
数据对象 (存储区及其值 )
一, 内部类型和用户定义的非结构类型
1,描述符一般由“类型”和一个指针组成
2,子界的描述符必须包括子界的界值
3,布尔型和字符型可以压缩存储
如, 整型
integer
二, 结构类型
1,笛卡尔积
① 各成分顺序排列
② 描述符包含,类型名, 构造符, 若干
三元式 。 每个域对应一个三元式 (选
择符名,域类型,指针 )
③ 每个成分占整数个可编址的存储单
元 (字编址或字节编址 ）
④ 可以用 packed显式说明压缩存储
数据对象
浮点值
定点值
描述符
类型名
构造符
选择符
选择符
类型
类型
引用
引用
t
record
a
real
b
integer
域 1
域 2
type t=record a,real；
b,integer；
end；
2,有限映象
①为 每一成分分配整数个可编址的存储单
元
②描述符包括,类型名、构造符、定义域的
基类型、下界、上界、成分类型、单元个数、
首地址
③ 地址公式的计算
b+k(i-m)=b-km+ki
其中 b 为首地址, k为所占单元数, m为下界
④ 内情向量
描述符
类型名
构造符
基类型
成分类型
下界
单元个数
上界
引用
a
array
integer
0
real
1
下标类型
10
数据对象
浮点值
浮点值
浮点值
type a=array[1..10] of real;
3,序列
可变长串的表示,
静态描述符 +动态描述符 +堆
string 5
A L
P H
A nil
4,判定或
① 判定或类型的变量分配的空间应足以容
纳需要最大空间的变体的值
② Pascal的变量记录的表示包括,描述符, 数
据对象, case表, 若干变体描述符
type v=record a:integer;
case b:boolean of
true:(c:integer);
false:(d:integer;
e:real)
end;
v
variant record
a
integer
b
boolean
?
?
?
?
?
?
?
?
(false) (true)
d
integer
e
real
c
integer
定点值
布尔值
true
false
case表
描述符 数据对象
变体描述符
5,幂集
① 集合关联一个机器字,通过每一位的
取值可知该集合中有基类型的哪些
元素
② 位操作
6,指针
指针变量的表示类似于内部类型, 只是
其值为一地址, 并且它指向的数据对象
分配在堆上
7,层次结构数据结构对象的表示
描述符中的类型可以指向另外的描述符
type t1=array[0..3] of integer;
t=record a:real;
b:t1;
c:integer
end;
t4=array[0..5] of integer;
t2=array[0..2] of t4;
t
record
a
real
b
c
integer
浮点值
定点值
定点值
定点值
定点值
定点值
t1
array
integer
0
3
integer
1
t2
array
integer
0
2
6
t4
array
integer
0
5
integer
1
定点值
第三章 控制结构
第一节 语句级控制结构
?控制结构,程序员用来规定程序各个成分
的执行流程的控制部分 。
?语句级控制结构,语言用来构造各种语句
执行顺序的机制 。
?传统语言的三种语句级控制结构,顺序,
选择, 重复 。
一, 顺序
?顺序运算符；
?语句括号 begin,,, end
?复合语句
二, 选择
1,if语句
① ALGOL 60的选择结构引起二义性
if x>0 then if x<10 then x:=0 else x:=1000
② PL/1和 Pascal的“最近匹配原则”
③ ALGOL 68中 if语句的结束符号 fi
④ ALGOL 68和 Ada对 else if 进行缩写
2,多重选择
① PL/1的 select结构
SELECT,
WHEN(A)S1;
WHEN(B)S2;
WHEN(C)S3;
OTHERWISE S4;
END
② 多种语言的 case语句
var operator:char;
operand1,operand2,result:boolean;
……
case operator of
‘.’:result:=operand1 and operand2;
‘+’:result:=operand1 or operand2;
‘=’:result:=operand1 = operand2;
end
③ Dijkestra选择结构的非确定性
if B1→S 1
? B2 →S 2
? B3 →S 3
…,.,
? BN →SN
其中, Bi是布尔表达式, 称为卫哨 。 若有
多个卫哨为真时执行任一 Si。
三, 重复
1,记数器制导
当预先知道重复次数时,在循环计数器值的有
限集合上重复 。
① FORTRAN的 DO循环中,用标号控制循环体
DO 7 I=1,10
A（ I） =0
B（ I） =0
7 CONTINUE
② Pascal的 for 语句,
?记数重复的值可在任何有序集上
? for,,, to
? for,,, downto
?在循环外循环控制变量的值无定义
2,条件制导
① while 循环：描述 0或任意多次的重复
② repeat until循环：至少一次以上的重复
③ ALGOL 68循环的一般形式,
for i from j by k to m while b do...od
④ Ada 的循环结构
loop /*可以在 loop前加重复说明 */
循环体 (语句序列 )
end loop;
?重复说明可以是,
while <条件 >
或 for <计数变量 > in <离散范围 >
或 for <计数变量 > in reverse <离散范围 >
?可由 exit或 exit when<条件 >终止循环
⑤ Dijkstra的卫哨命令表示法
do B1→S 1
? B2→S 2
,,,,,,
? BN→SN
od
四, 语句级控制结构讨论
?顺序, 选择, 重复是一定意义的抽象
?关于 goto语句的讨论
?控制结构的选择
五, 用户定义控制结构
如,Pascal的计数控制变量可以是枚举
类型
第二节 单元级控制结构
?单元级控制结构,规定程序单元之间控制
流程的机制
?四种单元级控制结构,显示调用,异常处
理,协同程序,并发单元
一, 显式调用从属单元
1.调用方式
由调用语句使用被调用单元的名字来
进行调用
2,参数的两种绑定方式
位臵绑定
关键字绑定
subprogram S(F1,F2,…,FN);
……
end
?位置绑定, call S(A1,A2,…,AN)
call S(A1,,A3,,,,,A8,,A10)
?关键字绑定,
call S(A1=>F1,A3=>F3,A8=>F8,A10=>F10)
3,副作用
—— 对非局部环境的修改
① 副作用降低了程序的可读性
② 副作用限制了数学运算律的使用
如,w:=x+f(x,y)+z
③ 副作用影响目标代码的优化
如,u:=x+z+f(x,y)+f(x,y)+x+z
