第七章
子 程 序 控 制
主要讨论子程序间的交互，特别是如何以结构的、高效的方式
传递数据。
7.1 子程序顺序控制
简单的子程序“调用 —返回”
程序可视为以子程序为单元的层次结构
主程序
子程序 … 子程序
子程序 … 子程序 子程序 … 子程序
子程序调用的控制机制可用“拷贝”规则来解释，子程序调
用语句的效果可通过下面方式同样得到：执行用子程序体的
拷贝来替代调用语句（合适地替换参数和冲突标识符）。
从这个观点看，子程序调用可视为这样一种控制结构，它使
得不必要在程序的多个地方拷贝大量相同或几乎相同的语句。
这个观点中有若干隐含假设，如果适当放松可得到更一般的
子程序控制结构。
1、子程序不能是递归的
递归分为直接递归和间接递归。
对非递归子程序调用，在翻译时，原理上我们可以应用
拷贝规则。
但如子程序是直接递归的，则拷贝规则在原理上也是不
可能使用的，因为替代过程不会终止，替代一个 call至少
引入一个 call。间接递归可允许删去某些子程序，但最终
仍将带来其他的直接递归。
2、显式的调用语句是需要的。
因为需要替代，必须有显式的替代点。
而对例外处理这一类子程序，则不存在显式的调用点。
3、子程序必须在每次调用中被完整地执行。
拷贝规则应用后，则子程序需从头执行到尾。
但对协同例程子程序，可能在其终止点后继续执行。
4、在调用点立即转换控制权。
显式的调用和拷贝规则，使得程序控制权被立即转移。
但对被调度子程序的调用，子程序的执行可能被延迟一
定时候。
5、单个执行序列。
在执行中某点，只有一个子程序拥有控制权，执行是单
序列的。
如我们停止程序则我们总可以知道是哪个子程序拥有控
制权，哪些程序的执行被挂起，哪些还未被调用，哪些
已结束执行。
但用作任务的子程序可以并发执行。
Fortran基本上是以拷贝规则来看待子程序调用的。
简单的调用 — 返回结构
?实现
首先需建立完整的程序执行模型。对表达式或语句序列，被
视为运行时的可执行代码块。表达式或语句序列的执行即是
代码块的执行，通过硬件解释器进行。
但对子程序而言，我们需要更多,
1、在子程序定义（翻译为模板）和子程序激活（调用时
创建）间存在不同。
2、激活实现为两部分，代码段十激活记录。
3、代码段在执行过程中不变，子程序的每个激活使用相
同代码段。
4、激活在调用时创建，返回时消除，激活中的内容会因
赋值而经常变化。
为避免混淆，我们不是简单地说子程序中某特定语句的执行，
而是说：在子程序的激活 R中 S的执行。
这样，为了跟踪程序执行点，我们需要两片数据，用于存放
两个系统定义的指针变量。
?当前指令指针
CIP指向当前正在被硬件或软件解释器执行的指令。
?当前环境指针
因为同一子程序的所有激活使用同一代码段，只知道当
前指令是不够 的，还需要指向激活记录（代表了子程序
的引用环境）的指针（因此称为环境指针）。
CEP——当前环境指针。
CEP和 CIP的配合，控制了程序的执行路线。
为了保证从子程序的正确返回,CIP和 CEP需合适地存放。
通常在调用时将 CIP和 CEP存放在被调用子程序的激活记
录中。
在激活记录中包含一个系统定义的数据对象 ——返回
点（存放两个指针值）。
当遇到 call调用时，将旧的（ ip,ep）存放到激活记录中返
回点，将新的（ ip,ep）赋给 CIP,CEP，从而完成控制的
转移。
遇到返回语句时，取旧的（ ip,ep），重设置 CIP,CEP，
返回控制权。
图 7.1，给出了一个主程序，两个子程序执行的例子。
子
程
序
B
开
始
执
行
时
的
执
行
状
态
这个实现子程序调用返回的模型通常足以作为以后讨论
的几个子程序控制结构变体的基础。
子程序的拷贝规则观点的重要性质是：在程序执行中任
一点，最多只有某子程序的一个激活是被使用的。子程
序可以多次调用，但在其下一次激活开始时，每个激活
必须完成且终止。
基于这个性质，可导出一个更简单的子程序实现模型，
只要我们愿意用存储来增加执行速度。
?作法,
为每个子程序静态地分配用以存放单个激活记录的空
间，作为代码数的扩展，而不是运行时创建。
很多 Fortran和 COBOL实现采用这种方式。
这样执行不需动态分配空间，而是重复地使用同一个
激活记录，只是在调用发生时对其进行初始化而已。
这种模型也带来其他简化,CEP不再需要，因为当前
激活记录总是 CIP指定的代码数的扩展。
对调用 —返回的更一般实现，底层硬件很少能提供帮助。
然而，对简化的实现，硬件常提供一 return-jump指令，允
许子程序调用被单条硬件指令所实现。这样 CIP直接表示
为硬件的地址寄存器。
返回跳指令将地址寄存器中内容存放到内存或寄存器中，
并为其赋新值。
图 7.2是一个例子。
子
程
序
调
用
返
回
结
构
递归子程序
前面讨论的假设是不允许递归，而递归是重要的顺序控制结
构之一。
如 LISP中，递归是主要的控制机制。
?规约
递归子程序在语法上和其他子程序设计没什么两样，概
念上，也没有困难。
唯一的不同是：递归调用可以在第一个激活的生命期内
创建子程序的第二个激活，如第二个激活再作一次递归
调用，则产生第三个激活，如此进行下去。
递归引入的唯一新元素是同一子程序的多个激活可在执
行中某点同时存在。
?实现
由于多个激活同时存在的可能性，我们需要 CIP和 CEP。
在 A中，创建 A的一个新激活记录和创建一个子程序 B的激活
记录是一样的。在 A调用 B的情形,A和 B的任意两个激活记
录的生命期是不交的,A的生命期完整地包含了 B的生命期。
在 A调用 A时，上述性质同样成立。
每个激活记录包含一个返回点，存放值对（ ip,ep）。如只观
察 ep值，注意到它们形成了一个链表，以创建顺序将激活记
录在中心栈上链在一起。 CEP指向栈顶，并可沿 ep链（这个
链称为动态链，以程序执行中动态创建的顺序将子程序激活
链在一起）到达较早创建的激活记录。
计算机硬件有时也提供这种中心栈支持，但其实现代价通常
高于简单的无递归的调用 —返回结构。
将以简单方式实现的子程序和使用中心栈的子程序混合是不
困难，只要编译器能分辨清楚即可。
只有实际递归调用的子程序需要中心样，因此，有的语言对
递归子程序给出显式语法标志，有的语言假设子程序总是递
归的。
7.2 数据控制的属性
语言的数据控制特性涉及,
数据在不同执行点的可访问性。
确定数据如何提供给操作，如何存放操作的结果，将结
果又如何取出供以后的操作作为操作数使用。
当写程序时，通常知道程序必须执行的操作及其顺序，但对
这些操作的操作数则较少了解。考虑例子。
X:=Y+2*Z
其中有乘、加和赋值三个操作，但操作数是什么呢？
2显然是乘法的操作数，但 X,Y,Z仅是标识符，他们不
是操作数，只是以某种方式指定了操作数。如,
Y可能是实数、整数或无参数子程序的名字，也
可能由于程序员出错,Y实际上是布尔值、或串、
或语句标号。 Y可能指定一个在附近计算的值，
也可能是在较早计算中计算的值（被几层子程序
调用分开），甚至 Y可能在程序的不同地方用作
不同的名字。那么，当前 Y是什么？
因此，数据控制的中心问题是,Y在这样一个赋值语句
的每次执行中意味着什么？
Y可能是局部或非局部变量，问题涉及需知道声明的
作用域规则。
Y可能是形态参数，问题涉及参数传递技术。
Y可能是无参数子程序，总是涉及子程序返回结果的
机制。
名字和引用环境
基本上只有两种方式将数据对象作为操作的操作数。
?直接传递,
某数据对象作为某处操作的计算结果可直接传递给另一
操作作为操作数，如上面例中,2× Z作为加法的操作数。
这种对象无需命名，而是分配临时存储。
?通过命名数据对象引用,
数据对象在创建时可给定名字，名字可用来作为操作数。
数据对象也可作为另一有名数据对象的部件。通过名字
和选择操作指定。
直接传递用作表达式中的数据控制，但大多数数据控制涉及
名的使用和名的引用，名字的意义形成数据控制的中心问题。
?可以命名的程序元素
1、命名变量
2、形参名
3、子程序名
4、定义类型的名字
5、定义常量的名字
6、语句标号（语句的名字）
7、例外名
8、原操作名，如 +,*,SORT
9、常量名，如 17,3.25
这里,1~3是我们考虑的重点。 4 ~9的大多数名引用在翻译
时确定，虽然也有特例，但无新观念引入。
上述名字均是简单名字，也可以有复合名字，如 A[3]。
?关联和引用环境
数据控制涉及标识符（简单变量）到特殊数据对象和子程序
的绑定,
这种绑定称为关联，表示为一个对（标识符、数据 /子程
序）。
在大多数语言的程序扫行中，我们观察到,
1、在子程序执行的开始点完成的关联有,
声明的变量名 → 特定数据对象
调用的子程序名 → 特定的子程序定义。
2、当子程序执行时，它调用引用操作来确定和标识符关
联的特定对象或子程序，如,
A:=B+FN(C)
需要 4个引用操作，对应 A,B,C和 FN。
3、当调用一新子程序，将为该子程序创建一关联集合，
涉及局部标识符。
4、子程序执行中，调用引用操作确定每个标识符的关联，
有的引用指向子程序中所创建的，有的可以是主程序中
创建的。
5、子程序返回控制权，则其关联被消除。
6、当主程序得回控制权，执行继续进行。
这种“创建 —使用 —消除”模式，涉及一些主要概念。
?引用环境
引用环境 ——标识符关联的集合，用于执行中的引用。
子程序的引用环境在执行中通常是不变的。
引用环境可包含如下分量,
1、局部引用环境（或局部环境）
子程序进入时创建，涉及形参、局部变量、局部定义
子程序。
2、非局部引用环境。
用于某子程序中，但不是在该子程序进入时创建。
3、全局引用环境
在主程序开始开始时创建，可为所有子程序使用。
4、预定义引用环境
有的标识符有预定义引用，直接在语言定义中指定。
任何程序或子程序可直接使用。
?可见性（ visibility）
一个标识符的某关联称为在某子程序中是可见的，如果它
是该子程序引用环境的一部分。
一个关联存在，但不是当前执行子程序的引用环境的一部
分，则称为对该子程序是隐藏的。通常隐藏是由于标识符
的重定义而产生。
?动态作用域
每个关联有一个动态作用域，该域是程序执行的一部分，
该关联存在于其引用环境中。某关联的动态作用域由它在
其中可见的子程序激活所构成。
?引用操作
基调为,
ref-op,id× referencing-environment
→data -object or subprogram
?局部、非局部和全局引用
分别对应局部环境、非局部环境或全局环境。
?数据对象的别名
在生命期中，数据对象可有多个名字，即可能有几个关
联存在于不同的引用环境，每个为数据对象提供不同的
名字。如,
数据对象“按引用传递” ——有形参名和原来名
数据对象可变成另一对象的元素 ——具有复合名。
当某数据对象在某单个引用环境中可通过多个名字可见，
每个名字称为数据对象的别名。
一个数据对象有多个名字，但在每个引用环境中是唯一
的，则不会有什么问题。
然而，在同一引用环境中用不同名字引用同一对象可能
对用户和语言实现者均产生严重问题。
图 7-4有两个 Pascal程序。
其中某整数变量有两个名 I,J（在执行中不同点）。
在第一个例子中，没有别名发生，因为没有 I,J同时用在同
一子程序中的情形。第二例子中，在 sub1中,I,J是同一对
象的别名,I是按引用传递。
别名带来的问题之一是理解困难。
如,X:=A+B
Y:=C+D
X,Y的赋值是独立的，顺序可以互换。如 X不在以后引
用，则第一个赋值还可被删去。
但如 X和 C是别名，则两个赋值实质上互相依赖，重排序
或删去均有麻烦。
别名给实现者带来的问题是类似的，因为为了优化目的
而进行的步骤重排序和删去不需要步骤均是困难的。
PASCAL中的别名
静态和动态作用域
如前所述，某标识符关联的动态作用域是在执行中关联可见
的子程序激活的集合。
动态作用域总是包含这样的子程序激活，在其中关联被创建
作为局部环境的一部分。它也可能作为非局部关联在其他程
序激活中可见。
动态作用域规则 ——根据程序的执行，定义每个关联的动态
作用域。
例如，一个典型的动态作用域规则陈述：在子程序 P的激活
中创建的某关联的作用域不仅包含该激活，还包含被 P调用
的、或传递调用的子程序的激活，除非后面的激活定义新的
局部关联隐藏了以前的原始关联。
根据这个规则，关联的动态作用域和子程序激活的动态链有
关系。
每个声明或标识符的其他定义有一定作用域，称为静态作用
域。例如：图 7.3中
在 C:=C+B语句中,B,C的引用是和特定的 C,B声明
（作为变量或形参）相连系的，但到底采用哪个声明？
一个声明的静态作用域是程序文本的一部分，这里标识符的
使用是对该标识符的特定声明的引用。
静态作用域规则 ——决定声明的静态作用域
如 Pascal中的规则,P中 X的引用指定 X在 P中头部的声明，
如不在这里表明，则指向子程序 Q（ Q的声明包含 P的声
明）中头部的 X声明，如此继续。
静态规则将程序文本中的引用和名字声明相连系。
动态规则将程序执行中的引用和名字关联相连系。
PASCAL程序中的引用环境
二者关系是什么？作用域规则则必须一致。
例如,Pascal的静态规则将 C:=C+B中变量 B的引用和主程
序中 B的声明相连系，则动态规则也必须将 B的引用和主
程序中命名为 B的数据对象相连系。
在文本中可有多个 B的声明，在执行中的子程序激活中，
也可有多个命名 B的数据对象。
维护静态和动态规则间的一致性是重要的。
?静态作用域的重要性
假定语言不使用静态作用域规则，考虑子程序中语句
X:=X+Max
没有静态作用域规则，则在翻译时对 X和 Max不可能确定
什么。
在执行时，引用操作需首先发现 X和 Max的相关关联，然
后确定类型和其他属性。
对每个标识符是否存在关联？
Max是子程序名、变量名、语句标号、类型名或形参
名？
如果 X是变量名，是否是可以和 Max相加的类型？
这些问题的回答需在执行中试图引用 X和 Max时才可作出。
而且，每次执行该语句，上述完整的过程需重复一次，
因为 X,Max的关联可能在语句的两次执行间改变。
LISP,SNOBOL4,APL几乎没有静态规则，这样对名字
的引用需要复杂而且代价很高的解释过程，首先找到相
关关联，然后确定类型和属性。
静态作用域规则允许这个过程的大多数工作在程序翻译
时一次完成，而不需要重复进行。
例,X:=X+Max 是 Pascal中语句
Max是常量,const Max=30
从而编译器可以确定 Max的值总为 30，语句翻译为 30
加到 X上，从而没有对 Max的引用操作。
对 X，如有声明,X,real，编译器将进行静态检查，
确定当语句被执行时,
①存在一个 X到数据对象的关联
②数据对象为实数类型
③其值是可以完成加法操作的类型。
编译器不能确定 X引用的数据对象的位置，也不能确
定其值。但静态检查使程序的执行更快、更可靠。
静态规则可允许在名字的引用和其声明中建立很多不同
的连接。如,
变量名和变量声明的连接,
常量名和常量声明的连接,
类型名和类型声明,
形参和形参规约
子程序调用和子程序声明
goto语句中标号和特定语句的标号等。
翻译时不同的简化使程序执行更高效。
静态规则对程序员读程序是重要的，可使程序易于理解。
块结构
块结构的概念来自于块结构语言。程序和子程序被组织为一
组嵌套的块。
块的主要特征是：引入了一个新的局部引用环境。
块以一组名字声明开始（变量声明、类型定义、常量定义
等），后跟一组语句，语句中将引用这些名字。
为简化起见，我们将块等价于子程序声明。
块中的声明定义了自己的局部引用环境，该环境在形成块体
的语句的执行中保持不变。
块的嵌套允许一个块的定义完全包括另一块的定义。在最外
层，程序由一个块构成，此即主程序。
主程序块中含有其他子程序块，从主程序调用，这些子程序
中又可包含下一层的子程序块，以此类推。
程
序
的
静
态
块
结
构
?和块结构程序关联的静态作用域规则如下,
1、每个块头的声明定义了该块的局部引用环境。在块体
中对标识符的任何引用被视为对该标识符局部声明的引用
（如存在）。
2、如某标识符在块体中引用，而且没有局部声明，则该
引用被视为对该块的立即外围块中声明的引用，如仍不存
在，则再向外推一层，以此类推。如最外层亦未声明，则
查预定义语言环境，再没有，则报错。
3、如块含有另一块定义，则在内层块的局部声明是完全
对外层块隐藏的，不能对其引用。内层块封装声明，对外
层块不可见。
4、块可以命名（通常当其表示命名子程序时），块名
变成其包含块的局部引用环境的一部分。
注意，使用静态规则，同一标识符可在多个块中声明，内
层块的声明将覆写外层块声明。
静态规则允许在任意块中对名字的引用和该名字的唯一声
明关联。
程序员的工作只是提供在适当的块中提供适当的局部声明。
编译器可提供静态检查和其它运行时结构的简化（基于这
些规则）。
局部数据和局部引用环境
局部引用环境形成最简单的数据控制结构。
子程序 Q的局部环境包含各种在 Q头声明的标识符、变量名、
形参名和子程序（ Q中声明的子程序）名等。
对局部环境，静态和动态规则是易于一致的。
静态规则 ——对 Q中标识符 X的引用是和 X在 Q头部的声明
相关的。
动态规则 ——在 Q中执行中时 X的作用指 X在 Q的当前激活
中的关联。
为实现静态规则，编译器维护一个标识符和局部声明表。当
编译 Q的体时，只要当需要标识符的声明时，去查找这个表
即可。
动态规则的实现可以两种方式实现，各自给局部引用不同的
语义。
局
部
引
用
环
境
考虑子程序 P,Q,R，局部变量 X声明在 Q中。
X在执行中的顺序,
1、当 P在执行时,X在 P中不可见,X对 Q局部。
2、当 P调用 Q,X变成可见的，作为初始值为 30的整数数
据对象的名字。当 P执行时，第一个语句引用 X并打印其
当前值 30。
3、当 Q调用 R，对 X的关联变成隐藏的，但在 R执行中将
保持。
4、当 R返回控制给 Q,X的关联又可见,X仍然命名相同
数据对象，值仍为 30。
5,Q恢复执行,X被引用和增值，新值为 31。
6,Q返回控制给 P,X的关联又变成隐蔽，但对这个关联
可提供两个不同的意义。
Retention(保留 ),X的关联可能被保留，直至 Q再次被
调用。如保留，当 Q被再次调用时，它仍关联同一对
象，其值为 31。
Deletion（删除）,X的关联可被删去。当 Q被调用，
创建一个新的数据对象并赋初值 30，关联也重建。
这是两种不同方法，涉及环境的生命期，不同语言，有不
同选择。
?实现
讨论引用环境的实现，方便的方法是将子程序的局部变量
表示为局部的环境表，该表由对组成，每个对为
（标识符、被关联对象）
如图 7.7所示。
PASCAL中的局部环境表
使用局部环境表，保持和删除方法的实现是直接的。
?保持
单个的包含被保持变量的局部环境表被分配为代码段的
一部分，如图 7.8所示。
因为这是静态分配的，在执行中将保持存在。
对这种实现方式，为了保持数据对象的值不需特殊动作。
同时，从一个局部环境转向另一个局部环境也不需特殊
动作，因为每个子程序的代码和局部数据是同一代码段
的一部分。
?删除
包含被删去变量的局部环境表被分配为激活记录的一部
分。
CEP指向当前激活记录的基地址，图 7.9是一个例子。
被
保
持
的
局
部
变
量
的
分
配
和
引
用
被
删
去
局
部
变
量
的
分
配
和
引
用
上述两种方式在我们的子程序实现一般模型中均是易于实现
的。另外一些值得注意的点包括,
1、在前面的简单的调用一返回结构的实现中
如无递归，则保持和删除实质上导致相同的实现，因为
没有多个激活记录，可以静态地分配。然而，如对变量
提供，初值，则产生两种不同的初始化含义。
2、个体变量可以有意识地给予两种不同处理
需保留值在代码段中分配空间，而删除值在激活记录中
分配空间。
3、子程序名，和局部环境中子程序申明相关联，总是处
理为保持的
名字和定义的关联可以表示为指针数据对象（在代码段
中），指向某代码段。
4、形参名表示的数据对象在每次调用时被初始化为新值
因此，处理为删除关联。
5、如允许递归子程序调用，则可能有同一子程序的多个
激活同时存在
如变量 Y处理为删除型的，则每个激活记录都包含一个名
为 Y的分别对象，每个激活执行时，将引用自己的局部拷
贝。在这种情形，引用环境的删除是常见的。
然而，某些局部变量的保持也是有价值的，这种变量将
为多个激活记录所共享。
?优、缺点
保持：允许历史敏感性
删除：对递归是自然的策略
节省存储空间，因为局部环境只对运行的或挂起
的子程序存在。
7.3 子程序中的共享数据
严格局部的数据对象只能在单一的局部引用环境中被操作。
然而，有时需要一个数据对象被多个子程序共享。
数据对象可以在子程序间以显式参数传递，但有时这种方式是麻
烦的。如：考虑一组子程序共享一个公共的数据表，则参数传递
是烦琐的。
数据共享通常是基于标识符关联的共享。如：子程序 P,Q,R需
要访问同一变量 X，则简单地允许 X在每个子程序中有相同关联。
X的关联变成某个子程序的局部环境的一部分，并成为其它子程
序非局部环境的公共部分。
通过非局部环境共享数据对象是一种重要的方式。
语言中有 4种基本的非局部环境方法,① 显式的公共环境或隐蔽
的非局部环境, 基于 ② 动态作用域； ③ 静态作用域； ④ 继承
参数和参数传递
显式传递参数和结果是主要的数据共享方法。
作为参数传递的数据对象和结果被不赋名字地传递。
在接收子程序中，每个数据对象被给定一个新的局部名。
这种共享方式对子程序的每次调用被给定不同数据的情形是
非常有用的。
?实参和形参
Argument（参数、自变量）：指作为操作数传递给子程
序或原操作数据对象。可通过参数或非局部引用得到。
Result（结果）：操作执行结束后返回的数据对象或值。
通过参数，非局部变量赋值或显式函数值返回。
形参（ formal parameter）：子程序中的一种特殊局部数
据对象。子程序定义通常在头部列出形参的名字和声明
作为规约的一部分。形参名是简单标识符，声明给出其
类型和其它属性。
例,C过程头
SUB(int X; char Y);
实参（ actual parameter）：和调用子程序共享的数据对象。
实参可以是属于调用者的局部数据，也可以是调用者的
形式参数，也可是调用者可见的非局部数据对象，或者
也可以是函数返回结果被立即传递给被调用子程序。
实参在子程序调用点表示为表达式，称为实参表达式。
通常，子程序被调用时，实参表达式被计值，计值结果
作为实参传递，然后再进入子程序。当然，也有特例，
表达式不计值而直接传递。
?建立对应
调用子程序时，需建立实参表和形参表间的对应，有两
个方法,
?位置对应,
根据各自的位置对实参和形参配对。
?由显式的名字对应
在调用语句中，和每个实参配对的形参被显式地
命名。例,SUB （ Y→B, X→27 ）
大多数语言彩位置配对。
?传递参数的方法
实参和形参的关联通常有两个途径,
先计值实参，然后将值传给形参。
或实际数据对象被传给形参。
?call by name按名调用
将子程序调用视为子程序体的全部替换，每个形参代表特
定实参的实际计值。每次形参引用需要对应的实参的实际
计值。
在子程序调用点，实参不计值，直至它在子程序中被实际
引用时才计值。
按名调用在 ALGOL语言中扮演了重要角色，具有重要理
论意义，但执行开销大。
基本的按名调用规则可用替代来陈述：在子程序开始执行
前，将子程序体中的形参均用实参替代。
这种替代带来的问题：对调用 call Sub (X),Y是形参,X是
实参。在 Sub执行前，用 X替代 Y，但 X的关联可能不在
Sub的关联中。因此，用 X替代我们还必须指出对 X的不同
引用环境，如果 X已对 Sub可见，则还可能带来含混性。
实现的基本技术是将实参处理为简单的无参数子程序（称
为 thunks）
?call by reference按引用调用
这是最常见的参数传递机制，即将指向数据对象位置的指
针传给子程序，数据对象本身并不改变其在存储中的位置。
子程序执行开始时，实参的左值被用于初始化形参的局部
存储位置。
传递参数以两步进行,
1、在调用子程序序中，每个实参表达式被计值，以给
一个指针到实参数据对象。这样的指针表被存放在公
共存储区域，可被被调用子程序访问，然后，控制传
给子程序。
2、在被调用子程序中，指向实参的指针表被访问以查
找实参合适的右值。
在子程序执行中，对形参名的引用被处理为一般的局部变
量引用。
子程序终止时，结果也通过实参数据对象返回。
?call by value按值调用
也称按拷贝调用（ call by copy），实参的值被传递给形参，
其实现类似于按引用调用，除了,
△按引用调用传递左值，而按值调用传递右值。
△按引用调用参数使用存放在形参中的左值去访问实际
数据对象。而在按值调用中，形参中包含了被使用的值。
一旦实际参数被接值传递，形参对实参不再会访问并修
改其值。
?call by value-result按值 —结果调用
形参是和实参同类型的局部变量。调用时，实参的右值
被拷贝进形参，效果上相当于显式的赋值。
子程序执行中，对形参名的引用就象对一般局部变量一
样。
子程序终止时，形参的值被拷贝回实参，也类似显式的
赋值。
?call by constant value按常量值调用
形参的值在子程序运行中不可改变，即不允许对参数赋
新值及修改。
形参也不能传递给其他子程序（除了作为常量值参数），
即形参作为局部常量。
可有两种方式实现：按值传递方式和按引用传递方式。
?call by result
仅用于从子程序传递回结果。
实参的初始值没有差别，并不可被子程序使用。
形参是无初值的局部变量，子程序终止时，形参值被赋
给实参。
?传递的语义
上面的方式描述了参数是如何实现的，然而程序员并不
需要知道实现细节，只需知道参数如何使用即可。
在 Ada中，不是描述传递模式，而是刻划参数的角色。
参数可以为 in,out,in out三种类型。实现者可以选择自
己的实现方式，具体实现方式对程序员无影响。
Ada的 83版，允许实现者对 in,out参数选择采用按引用
调用或按值调用方式。这产生了符合性问题：正确的程
序被不同的正确编译器编译可能产生不同结果。
而 Ada 95中规定,
基本数据类型，如为 in参数，按常量值传递；如为 out
和 in out参数，按值一结果方式传递。
复合数据类型，按引用传递。
?显式函数值
大多数语言中，单个结果可作为显式函数值而不是作为
参数返回。子程序需声明为函数，结果类型声明是规约
的一部分。
在函数子程序中，返回结果作为函数值可以两种方式刻
划,
使用显式的返回语句，如 return 2*X。
对函数名进行赋值，最后赋值结果作为返回结果。
?参数传递的实现
因为子程序激活接收不同参数集，子程序形参的存储分
配作为激活的一部分，而不是代码段的一部分。
每个形参是子程序的一个局部数据。
如形参 P有类型 T，则有两种实现方式（根据不同传递模
式）,
P被处理为类型 T的局部数据对象。
P被处理为 T的指针的局部数据对象。
参数传递相关的各种动作分成两组：调用点，进入和退
出。
调用点：在调用子程序中，每个实参表达式被计值，到
实参的指针表被设置。实参确定后，控制权被转移，此
时涉及 CIP和 CEP的改变。
在控制权转移后，子程序的前奏（ prologue）完成参数传
递的动作，即拷贝实参内容或指针。
子程序终止前，子程序的 epilogue完成返回值的动作。即
拷贝结果回实参，或函数值被拷到寄存器或临时区域。
在实现参数传递方面，编译器有两个主要任务,
首先，保证产生正确的执行代码来完成参数传递、结果
返回和形参引用。
第二，完成必需的静态检查以保证实参和形参类型匹配，
此时，必须知道子程序的规约。
?参数传递例子
?简单变量和常量
Q有两个形参，一个传值，一个传引用。
执行结果为,12 13 2 13
当 P调用 Q，实参表达式 a和 &b被计值，即调用引用操作，
确定 a,b的当前关联。传递的实参是 a的右值和 b的左值。
实参 a在 Q的执行中不会改变。
而 b由于传引用，故 b数据对象被 Q实质地改变。
?数据结构
考虑 Q的不同版本（用 PASCAL，因需要数组的按值调用）
type vect = array[1..3] of integer;
procedure Q(k,vect; var l,vect);
var n,integer;
begin
k[2]:= k[2]+10;
l[2]:= l[2]+10;
for n:= 1 to 3 do write(k[n]);
for n:= 1 to 3 do write(l[n])
end;
过程 P如图 7.11所示 。
P执行结果,6 17 8 6 17 8 6 7 8 6 17 8
实参 c被拷贝给 k,c,k以后没有关系 。
实参 d的左值传给形参 l（ 指向数组的指针 ）, 因此, l指
向 d数组 。
图 7.12显示了 Q执行结束时的运行时栈 。
数据结构参数
Q
终
止
前
的
运
行
时
栈
?数据结构的分量
假定 Q仍为图 7.10(a)所示,P为,
P()
{int c[4];
int m;
c[1] = 6; c[2] = 7; c[3] = 8;
Q(c[1],&c[2]);
For (m = 1; m <= 3; m++) printf(“%d\n”,c[m]);
}
执行结果为,16 17 6 17 8
?具有计算下标的数组分量
R(int *i,int *j)
{*i = *i +1;
*j = *j +1;
printf(“%d %d\n”,*i,*j);}
P()
{int c[4];
int m;
c[1] = 6; c[2] = 7; c[3] = 8; m = 2;
R(&m,&c[m]);
For (m = 1; m <= 3; m++) printf(“%d\n”,c[m]);
}
执行结果为,3 8 6 8 8
关键是 m的初值为 2,在 R中被改为 3。 那么, 到底是
C[2]还是 C[3]被增值？ 当然应该是 C[2],因为在调用
时 m为 2 。
?指针
如 X在 P中声明为,vect *X；
Q中对应形参声明为,vect *h；
如按值调，则 h是 x的拷贝，均指向相同向量。
如按引用调用，则 h包含指向 X的指针,X包含指向向量的
指针。
由于 C中有显式的左值和右值操作，故按值调用就足够了。
?表达式的结果
按引用传递表达式,Q(&(a+b),&b)
首先计值表达式，然后存放到临时位置，再传递指向该位
置的指针为参数。
但 Q中的修改无法在 P中引用，故这种方式没有太大价值。
?别名和参数
大多数语言中都有别名问题（在单一引用环境中，多个名字
表示同一数据对象）。
别名对程序理解、正确性验证及优化均有影响。
参数传递中别名的产生有两种方式,
1、形参和非局部变量
作为实参传递的数据对象可直接在子程序中通过非局部
名访问。
这样形参名和非局部名变成别名，如图 7.4所示。
2、两个形式参数
同一数据对象按引用方式作为实参传给不同形参。
则两个形参名变成别名。
别名的产生
?子程序作为参数
很多语言允许子程序作为实参传递。这时实参数表达式是子
程序名，对应的形参类型为子程序。如 PASCAL中,
procedure Q(x;intger; function R(y,z:integer):integer);
子程序参数的两个主要问题是,
?静态类型检查
当用形参名调用子程序时，最重要的是要有可能通过静态
类型检查保证调用包含实参的数量和类型。
因为在调用点还不知道被调用子程序的实际名字，编译器
难于确定是否形参子程序中的实参可以匹配实参子程序所
期望的参数。
编译器需要形参子程序的完整规约，不仅包含类型
procedure或 function，还包含参数（结果）的数量、顺序
和类型。
在上例中，子程序 Q中 R的调用可以静态地检查。在 Q的调
用中，对应 R的实参子程序也可以静态地检查。
?非局部引用（自由变量）
假定子程序包含了对非局部变量的引用，但不含有对该
变量的定义。
这样的非局部引用通常称为自由变量，因为在子程序定
义中没有局部绑定。
通常当一个子程序被调用时，一个非局部引用环境被建
立。
然而，当一个包含非局部引用的子程序 fn被作为参数从 P
传递给子程序 Q时，什么是在 Q中 fn调用时的非局部环境
（通过对应的形参 R来调用 fn）?
最简单的回答是：该局部环境和简单地用 fn代替 R所使用
局部环境一样。
但这在大多数情形都是一个错误的答案。
如图 7.13所示,
fn包含非局部引用 x和 i,x在主程序声明,i在 P中声明
（根据静态规则）。
P将 fn作为参数传给 Q,Q中通过形参 R实际地调用 fn。
Q中有对 i,x的局部定义,fn不能被允许不正确地检索这
些局部变量（当被调用时）。
这种函数作为参数传递带来的自由变量问题在很多语言
中都会发生。
一般解决方案：采用如下关于自由变量意义的规则。
一个非局部引用在作为参数传递的子程序的执行中，
应该意味着和它在子程序作为实参出现的位置被调用
的情形一样的事。
自
由
变
量
作
为
子
程
序
参
数
例如：图 7.13中,fn作为实参出现在 P对 Q的调用中。
这样,fn中 i,x的非局部引用，不管 fn后来在哪儿被调用，
仅意味着和在 P中Ｑ被调用处 fn被调用一样，即 x在主程序
中声明,i在Ｐ中声明。
为了正确实现这个规则，应可重新在子程序参数的调用
点创建正确的引用环境，使其可以正确地执行。
在 7.3.4节讨论了非局部引用的静态链实现方式可直接解
决这个问题。所需做的是为子程序参数确定正确的静态
链指针，并一起被传递。这样子程序参数变成一个指针
对 (CP,SCP)，分别为代码段指针和静态链指针。
这个对可通过多层子程序传递，直至调用该子程序。此
时，激活记录被创立，被传递的 SCP被建立，子程序代码
段的执行继续。
图 7.14给出了图 7.13例子的执行。
执
行
中
某
一
时
刻
的
中
心
栈
显式公共环境
直接建立共享数据对象的公共环境是最直接的共享方法。
将共享的数据对象分配为一个分开的命名块，每个子程序在
其中声明该块。块中对象对其声明块可见。
Fortran中的 Common块是典型例子。
?规约
对子程序而言，公共环境和局部环境是一样的，除了它不是
任何单独子程序的一部分。
公共环境可包含变量常量和类型的定义但没有子程序和形
参。
例,Ada中 Package规约,
Package shared-Tables is
Tab-size:constant integer:=100;
Type Table is array (1..Tab.Size) of real;
Table1,Table2,Table;
Curr-Entry,integer range 1..Tab-Size;
End
包中定义了一个类型，一个常量，两个表和一个整数变量。
这些组成由几个子程序需要的一组数据对象。
如果 P需访问，则在其中加入声明,
with shared-Tables;
然后可以对其中对象直接使用。
?实现
Fortran,C中，使用公共环境的子程序必须包含每个共享
变量的声明，使得编译器知道相关声明，即使公共环境也
被在其他地方声明。
在 Ada中，编译器在遇到 with语句时将先检索公共环境的
声明（从库中或程序文本的其他部分）。
公共环境的声明被加入到编译器符号表中，作为局部名的
附加集合。
在子程序中引用，子程序体中对名字的每个引用按通常方
式在表中查找，以便于静态检查和代码生成。
运行时，公共环境表示为存储块，包含了定义中声明的数
据对象。
因为数据对象潜在地是混合类型，其声明在编译时知道，
因此，块可以处理为记录，用基地址 +位移方式来引用记
录分量。
公共环境存储块必须持续在内块中存在，至少和任何潜在
可能访问它的子程序同生命期，因为这些子程序的任一个
的激活均将访问该块。
因此，块通常是静态分配的。程序开始执行即存在，执行
结束时消除。
引用公共环境中数据对象的子程序必须知道块的基地址。
简单的实现：在子程序代码块中分配一个位置，保存到公
共块的指针，图 7.15给出一个例子。
子
程
序
中
到
公
共
块
的
链
接
?共享显式变量
数据对象显式共享的另一形式是提供一种方法，使局部环境
中的数据对象对其他子程序可见。
这样，不是一组公共变量和子程序分开，而是每个变量有
“拥有者”。
为使得局部变量对外界可见，须给出显式的 export定义。
例,procedure P(…)
defines X,Y,Z; X,Y,Z对外移出。
X,Y,Z,real;
U,V,integer;
begin … end;
另一子程序通过显式的 import定义移入定量。
Procedure Q (…)
uses P.X,P.Z; 移入 P中的 X和 Z
Y,integer;
begin …end;
?实现
效果类似于公共环境中变量的使用。
移出的局部变量必须保持，因此，常分配在代码段。
其他子程序对其的引用也是采用基地址＋位移方式。
动态作用域
另一种共享数据的方式是为每个执行子程序关联一个非局部
环境。
子程序 P的非局部环境包含其他在执行过程中对 P可访问的子
程序激活的局部环境。当变量 X在 P中引用，且 X没有局部关
联时，则用非局部环境去确定 X的关联。
那么,什么是 P的非局部环境？
在块结构语言中，静态作用域规则确定了每个子程序的隐含
非局部环境。
一个更简单的方法是：使用在当前动态链中的子程序局部环
境。
考虑一种语言，当子程序退出时局部变量被删去，而且没
有子程序嵌套定义，子程序定义是分开的。
这样，没有静态程序结构作为引用非局部标识符的作用域
规则的基础。
如,P中引用 X,X不在 P中局部定义，那么，在其他子程
序中哪个 X定义被使用？
自然的回答是：考虑通往 P的激活的子程序激活动态链。
考虑程序执行过程,
主程序 － → A － → B － → P
P中引用 X，且 X不是局部定义。则先查 B，如没有，
再找 A，如没有，在找主程序。
这样，在运态链中使用 X的最近创建关联。
最近关联规则 ——基于动态作用域的引用规则。
调用 调用 调用
如果非局部环境用最近关联规则来确定，不使用静态域规则，
即不在翻译时确定非局部引用的标识符的定义关联。
在程序执行时，当数据对象 X被创建作为子程序 P的激活的一
部分，则 X的关联的动态作用域变成所有从 P开始调用的子程
序关联,X在动态作用域中可见（除非被后面的 X定义所覆
写）。
这样，子程序激活 P的非局部环境包含通往它的完整的子程
序激活动态链。
这种非局部环境最麻烦的方面是它可能在 P的激活中改变,P
的不同激活中可能有不同的 X关联。
这样，动态类型检查是需要的。
?实现
对非局部引用的最近关联规则的实现是直接的，采用子程序
激活记录的中心栈来实现。每个子程序的局部环境是其激活
记录的一部分。
假设子程序 P调用子程序 Q,Q再调用 R，当 R执行时，中心栈
如图 7.16所示。为了引用非局部 X，在栈中查找，从局部环
境开始，直至 X的最近关联被找到。
最近关联规则的实现代价较高，非局部引用的查找需要时间，
同时需要在局部关联表中存放标识符的某些表示，因为 X的
关联的位置在各个局部表中可能是不同的。从而不可能用基
地址＋位移的方式。
如何避免对非局部引用的查找？
在非局部引用和子程序进入 —退出间可以有代价上的权
衡。如果非局部引用比子程序进入 —退出更为频繁（即
使用比修改更频繁），则避免查找是有意义的。
执
行
过
程
中
的
活
跃
引
用
环
境
另一种实现方式使用对所有子程序公共的中心表 ——中心引
用环境表。
中心表设置为在程序执行的所有时间内包含所有当前活动的
标识符关联，不管其是局部还是非局部。
为了简单化，我们假定在任何子程序中引用的标识符集合可
以在翻译的确定，则中心栈初始化为对每个标识符包含一个
项，不管标识符出现在其中的不同子程序的数量。
表中每个项包含一个激活标志，指出是否特殊的标识符有一
个活动关联。还包含一个指针，指向关联的数据对象。
所有子程序中的引用被导向到该中心表，使用基地址十位移
模式，因为标识符 X的当前关联宫殿是位于当前表的同一位
置。
每个引用只需要在项中的激活标志被检查，以保证表中的关
联当前活动的。使用中心表，我们可达到不需查找而有效地
实现非局部引用的目标。
由于在引用环境中的每次变动需要修改中心表，因此，子程
序的进入和退出代价很高。当子程序 P调用 Q，必须修改中心
表以反映 Q的局部环境。
每一个对应 Q的局部标识符的项必须修改以反映新的局部关
联。
同时，如旧表项是活动的，还必须存放起来，以便 Q退出时
重被激活。由于修改的项可能散落在整个中心表中，修改必
须逐项进行。退出 Q时，恢复工作也需逐项进行。
这样，又需要一个执行时栈来作为存放非激活态关联的隐蔽
栈，当退出 Q时，栈的顶部关联块被恢复进中心表中适当位
置，图 7.17给出了一例子。
非
局
部
引
用
的
中
心
环
境
表
静态作用域和块结构
在使用块结构的语言中，非局部引用的处理更为复杂。
由于在一个子程序中某标识符的每次引用是和程序文本中该
标识符的定义相关联，即使该标识符不是局部于子程序。
这样，执行中每个子程序的非局部引用环境已经在翻译时由
静态作用域规则确定。
实现问题是，保持静态和动态作用域规则间的一致性，使得
在程序执行中非局部引用正确地关联相关数据对象。
图 7.18给出了个静态作用域规则的例子（对块结构程序）。
具
有
非
局
部
引
用
的
P
A
S
C
A
L
过
程
主程序,P和 Q中均定义了变量 X，而 R中局部引用 X。主程序
调用 P,P调用 Q,Q调用 R。
静态规则定义了对 X的引用为主程序中 X定义，对 X的非局部
引用的含义是独立于特定的动态调用链。
而最近关联规则将 X和 P或 Q中 X相关联（根据 R 的调用者）。
静态作用域规则在编译器中的实现是直接的。
当在编译中处理每个子程序定义时，创建声明的局部表
并将其附到局部表链上去。
这样在编译 R时，编译器将 R声明的局部表加到链中（目
前只含有主程序定义）。
当 R编译结束时，编译器从链中删去的 R的局部表。
声明的局部表链表示了子程序定义的静态嵌套，而不是
执行中的动态调用链。
在块结构语言的程序执行中，中心栈用于子程序激活记录。
每个子程序的局部环境存放在其激活记录中。
图 7.19给出了静态作用域和动态作用域规则间的矛盾。
当 R被调用时，如遇到对 X的非局部引用，引用操作必须
在主程序中查找 X的关联，而不是在 R的调用者 Q中。
然而，简单地沿栈查找，将指向 Q中的 X关联。
问题在于：栈中的局部表序列表示了子程序激活的动态嵌
套（基于执行时调用链），但是，是子程序定义的静态嵌
套确定非局部引用环境。
图 7.19中栈没有包含关于静态嵌套的信息。
使
用
静
态
作
用
域
的
不
完
全
中
心
栈
为了完全这个实现，必须在执行中表示静态块结构，使其可
用来控制非局部引用。
我们注意到，为了找到关联满足对 X的引用，我们查找局部
环境表链直到 X的一个关联被找到。
然而，局部环境表链不包含所有当前在栈中的局部表，而只
是那些表示块或子程序的局部表。
这些块或子程序的定义静态地在程序文本中包含当前子程
序定义。
查找仍是沿栈中表进行，但只是那些实际上是引用环境一部
分的表。
?静态链实现
只需简单地修改栈中的局部环境表，在表头加上一项 ——
静态链指针。
静态链指针总是包含另一个局部表的基地址，局部表表示
静态地包含的块或子程序的局部环境。
当然，局部环境表是激活记录的一部分，我们可使用激活
记录的基地址。
静态链指针形成了简单引用模式的基础。
为满足对 X的引用，我们循 CEP得到栈顶的当前引用环
境。
如没有 X的关联，则沿静态链指针到栈中第二个表，
如此继续。
图 7.20给出了图 7.18例子的静态链。
执行时中心栈
虽然似乎需要查找每个静态链接环境直至 X被找到，但不
一定要这样做。
当编译器为每个局部声明创建局部环境表时，它保持了哪
个子程序被静态地嵌套在该环境中的轨迹。对每个对 X的
引用，编译器记下为了发现正确关联所必须查找的外国环
境层数，然后生成代码来循静态链指针到达合适的激活记
录，这样避免了在执行栈中保持标识符名。
这是一个相当有效的实现。通常，对声明在 K层而使用
K+N层的变量的访问需要 N次静态链指针的访问。
由于子程序很少嵌套到 4—5层深（通常 2—3层）,n很少
大于 1—2。
然而，我们可以访问任意正确环境，只通过对静态链指针
的一次访问。
静态链技术允许子程序的直接进入和退出。当子程序被
调用，其激活记录在栈顶创建，此时需建立合适的静态
链指针，以指向栈中的下一个激活记录。退出时仅需从
栈中删去激活记录即可，对静态指针没有别的动作。
在子程序进入时如何建立合适的静态链指针？
如图 7.19,R定义在主程序中,Q调用 R。
当 R在执行中进入时，合适的静态链指针被设置到主
程序的激活记录。
在调用点,Q的激活记录在栈顶,R的记录被堆在 Q之
上，那么，如何确定静态链指针是指向主程序？
标识符 R是子程序名，在 Q中是非局部引用。
在 Q的调用点，可以确定 R的静态链指针指向主程
序。
此情形好象是 R在主程序中定义为局部变量而在 Q
中非局部引用一样。
?Display实现
我们有如下观察,
1、对任意子程序 R，当 R在执行时，从 R的局部表沿栈下
降的长度是常量，且简单地等于 R定义的静态嵌套深度，
而且在执行中是固定的。
如图 7.18中,R的静态链长度为 2。
2、在这个常量长度的链中，非局部引用总是在链中的同
一点被满足。
如图 7.20中,R中 X的非局部引用总在链中的第二个表被
满足。
3、链中非局部引用将被满足的位置可在编译时确定。
由此，我们具有了实现有效引用操作的基础。
我们不需显式地沿静态链查找，只需沿链跳过固定的数
的表，然后使用基地址十位移计算得到合适的表项。
在执行中，我们将标识符表示为对 ——（链位置、位移）。
这样，在上面例子中,R中 X的引用表示为（ 1,3）,1表
示沿链下降的第一个表,3表示第三个表项。
在这个实现中，当前静态链在进入每个子程序时，被拷贝
到分开的矢量中，称为 display。
Display和中心栈分开，经常表示在高速寄存器集中。
在执行中任意点,display包含了和出现在当前被执行的子
程序的静态莲中相同的指针序列。
图 7.21给出了图 7.18例子的 display。
使用 display完成引用是特别简单的。
我们在执行中使用稍微修改过的标识符表示，即使用
整数对，如：（ 3,2）,3表示从链尾到合适激活记录
的步数,2仍然表示位移。
现在给定非局部引用（ 3,10），适当的关联可在两步内
得到,
1、考虑第一个项 3作为 display的下标。
基地址＝ display[3]，从而得到激活记录的基地址。
2、计算标识符位置。
基地址 +10
通常，这两步可合为一，采用间接取址法。
如 display存放在高速寄存器中，则对每个标识符引用，只
需一次内存访问。
虽然使用 display可使引用简化，但子程序进入和退出却更
困难，因为必须修改 display以反映当前活动静态链。
执
行
中
的
中
心
栈
和
DISPLAY
?局部块中的声明
有的语言，如 C，允许语句块中声明局部变量。如,
real proc1(parameters)
{int i,j;
…/*statements*/
{int k,l; …/*statements*/}
{int m,n;
…/*statements*/
{int x; … /*statements*/}
{int y; … /*statements*/}
}}
第一眼看去，似乎每个块需要分别的激活记录来存放变量。
然而，在这些块和前面讨论的激活记录间有重要差异。由于
过程调用的动态性质，通常我们不能确定哪个过程当前被执
行。
这样如上面块每个均表示过程，则包含 k的块和包含 m的块可
能同时被执行，因此，需要分开的激活记录。
然而，在上面例子中，这是不可能的，在变量 k的块中就不能
在变量 m 的块中，从而允许简单的存储策略。
如图 7.22所示。
在激活记录中的重叠变量存储
子 程 序 控 制
主要讨论子程序间的交互，特别是如何以结构的、高效的方式
传递数据。
7.1 子程序顺序控制
简单的子程序“调用 —返回”
程序可视为以子程序为单元的层次结构
主程序
子程序 … 子程序
子程序 … 子程序 子程序 … 子程序
子程序调用的控制机制可用“拷贝”规则来解释，子程序调
用语句的效果可通过下面方式同样得到：执行用子程序体的
拷贝来替代调用语句（合适地替换参数和冲突标识符）。
从这个观点看，子程序调用可视为这样一种控制结构，它使
得不必要在程序的多个地方拷贝大量相同或几乎相同的语句。
这个观点中有若干隐含假设，如果适当放松可得到更一般的
子程序控制结构。
1、子程序不能是递归的
递归分为直接递归和间接递归。
对非递归子程序调用，在翻译时，原理上我们可以应用
拷贝规则。
但如子程序是直接递归的，则拷贝规则在原理上也是不
可能使用的，因为替代过程不会终止，替代一个 call至少
引入一个 call。间接递归可允许删去某些子程序，但最终
仍将带来其他的直接递归。
2、显式的调用语句是需要的。
因为需要替代，必须有显式的替代点。
而对例外处理这一类子程序，则不存在显式的调用点。
3、子程序必须在每次调用中被完整地执行。
拷贝规则应用后，则子程序需从头执行到尾。
但对协同例程子程序，可能在其终止点后继续执行。
4、在调用点立即转换控制权。
显式的调用和拷贝规则，使得程序控制权被立即转移。
但对被调度子程序的调用，子程序的执行可能被延迟一
定时候。
5、单个执行序列。
在执行中某点，只有一个子程序拥有控制权，执行是单
序列的。
如我们停止程序则我们总可以知道是哪个子程序拥有控
制权，哪些程序的执行被挂起，哪些还未被调用，哪些
已结束执行。
但用作任务的子程序可以并发执行。
Fortran基本上是以拷贝规则来看待子程序调用的。
简单的调用 — 返回结构
?实现
首先需建立完整的程序执行模型。对表达式或语句序列，被
视为运行时的可执行代码块。表达式或语句序列的执行即是
代码块的执行，通过硬件解释器进行。
但对子程序而言，我们需要更多,
1、在子程序定义（翻译为模板）和子程序激活（调用时
创建）间存在不同。
2、激活实现为两部分，代码段十激活记录。
3、代码段在执行过程中不变，子程序的每个激活使用相
同代码段。
4、激活在调用时创建，返回时消除，激活中的内容会因
赋值而经常变化。
为避免混淆，我们不是简单地说子程序中某特定语句的执行，
而是说：在子程序的激活 R中 S的执行。
这样，为了跟踪程序执行点，我们需要两片数据，用于存放
两个系统定义的指针变量。
?当前指令指针
CIP指向当前正在被硬件或软件解释器执行的指令。
?当前环境指针
因为同一子程序的所有激活使用同一代码段，只知道当
前指令是不够 的，还需要指向激活记录（代表了子程序
的引用环境）的指针（因此称为环境指针）。
CEP——当前环境指针。
CEP和 CIP的配合，控制了程序的执行路线。
为了保证从子程序的正确返回,CIP和 CEP需合适地存放。
通常在调用时将 CIP和 CEP存放在被调用子程序的激活记
录中。
在激活记录中包含一个系统定义的数据对象 ——返回
点（存放两个指针值）。
当遇到 call调用时，将旧的（ ip,ep）存放到激活记录中返
回点，将新的（ ip,ep）赋给 CIP,CEP，从而完成控制的
转移。
遇到返回语句时，取旧的（ ip,ep），重设置 CIP,CEP，
返回控制权。
图 7.1，给出了一个主程序，两个子程序执行的例子。
子
程
序
B
开
始
执
行
时
的
执
行
状
态
这个实现子程序调用返回的模型通常足以作为以后讨论
的几个子程序控制结构变体的基础。
子程序的拷贝规则观点的重要性质是：在程序执行中任
一点，最多只有某子程序的一个激活是被使用的。子程
序可以多次调用，但在其下一次激活开始时，每个激活
必须完成且终止。
基于这个性质，可导出一个更简单的子程序实现模型，
只要我们愿意用存储来增加执行速度。
?作法,
为每个子程序静态地分配用以存放单个激活记录的空
间，作为代码数的扩展，而不是运行时创建。
很多 Fortran和 COBOL实现采用这种方式。
这样执行不需动态分配空间，而是重复地使用同一个
激活记录，只是在调用发生时对其进行初始化而已。
这种模型也带来其他简化,CEP不再需要，因为当前
激活记录总是 CIP指定的代码数的扩展。
对调用 —返回的更一般实现，底层硬件很少能提供帮助。
然而，对简化的实现，硬件常提供一 return-jump指令，允
许子程序调用被单条硬件指令所实现。这样 CIP直接表示
为硬件的地址寄存器。
返回跳指令将地址寄存器中内容存放到内存或寄存器中，
并为其赋新值。
图 7.2是一个例子。
子
程
序
调
用
返
回
结
构
递归子程序
前面讨论的假设是不允许递归，而递归是重要的顺序控制结
构之一。
如 LISP中，递归是主要的控制机制。
?规约
递归子程序在语法上和其他子程序设计没什么两样，概
念上，也没有困难。
唯一的不同是：递归调用可以在第一个激活的生命期内
创建子程序的第二个激活，如第二个激活再作一次递归
调用，则产生第三个激活，如此进行下去。
递归引入的唯一新元素是同一子程序的多个激活可在执
行中某点同时存在。
?实现
由于多个激活同时存在的可能性，我们需要 CIP和 CEP。
在 A中，创建 A的一个新激活记录和创建一个子程序 B的激活
记录是一样的。在 A调用 B的情形,A和 B的任意两个激活记
录的生命期是不交的,A的生命期完整地包含了 B的生命期。
在 A调用 A时，上述性质同样成立。
每个激活记录包含一个返回点，存放值对（ ip,ep）。如只观
察 ep值，注意到它们形成了一个链表，以创建顺序将激活记
录在中心栈上链在一起。 CEP指向栈顶，并可沿 ep链（这个
链称为动态链，以程序执行中动态创建的顺序将子程序激活
链在一起）到达较早创建的激活记录。
计算机硬件有时也提供这种中心栈支持，但其实现代价通常
高于简单的无递归的调用 —返回结构。
将以简单方式实现的子程序和使用中心栈的子程序混合是不
困难，只要编译器能分辨清楚即可。
只有实际递归调用的子程序需要中心样，因此，有的语言对
递归子程序给出显式语法标志，有的语言假设子程序总是递
归的。
7.2 数据控制的属性
语言的数据控制特性涉及,
数据在不同执行点的可访问性。
确定数据如何提供给操作，如何存放操作的结果，将结
果又如何取出供以后的操作作为操作数使用。
当写程序时，通常知道程序必须执行的操作及其顺序，但对
这些操作的操作数则较少了解。考虑例子。
X:=Y+2*Z
其中有乘、加和赋值三个操作，但操作数是什么呢？
2显然是乘法的操作数，但 X,Y,Z仅是标识符，他们不
是操作数，只是以某种方式指定了操作数。如,
Y可能是实数、整数或无参数子程序的名字，也
可能由于程序员出错,Y实际上是布尔值、或串、
或语句标号。 Y可能指定一个在附近计算的值，
也可能是在较早计算中计算的值（被几层子程序
调用分开），甚至 Y可能在程序的不同地方用作
不同的名字。那么，当前 Y是什么？
因此，数据控制的中心问题是,Y在这样一个赋值语句
的每次执行中意味着什么？
Y可能是局部或非局部变量，问题涉及需知道声明的
作用域规则。
Y可能是形态参数，问题涉及参数传递技术。
Y可能是无参数子程序，总是涉及子程序返回结果的
机制。
名字和引用环境
基本上只有两种方式将数据对象作为操作的操作数。
?直接传递,
某数据对象作为某处操作的计算结果可直接传递给另一
操作作为操作数，如上面例中,2× Z作为加法的操作数。
这种对象无需命名，而是分配临时存储。
?通过命名数据对象引用,
数据对象在创建时可给定名字，名字可用来作为操作数。
数据对象也可作为另一有名数据对象的部件。通过名字
和选择操作指定。
直接传递用作表达式中的数据控制，但大多数数据控制涉及
名的使用和名的引用，名字的意义形成数据控制的中心问题。
?可以命名的程序元素
1、命名变量
2、形参名
3、子程序名
4、定义类型的名字
5、定义常量的名字
6、语句标号（语句的名字）
7、例外名
8、原操作名，如 +,*,SORT
9、常量名，如 17,3.25
这里,1~3是我们考虑的重点。 4 ~9的大多数名引用在翻译
时确定，虽然也有特例，但无新观念引入。
上述名字均是简单名字，也可以有复合名字，如 A[3]。
?关联和引用环境
数据控制涉及标识符（简单变量）到特殊数据对象和子程序
的绑定,
这种绑定称为关联，表示为一个对（标识符、数据 /子程
序）。
在大多数语言的程序扫行中，我们观察到,
1、在子程序执行的开始点完成的关联有,
声明的变量名 → 特定数据对象
调用的子程序名 → 特定的子程序定义。
2、当子程序执行时，它调用引用操作来确定和标识符关
联的特定对象或子程序，如,
A:=B+FN(C)
需要 4个引用操作，对应 A,B,C和 FN。
3、当调用一新子程序，将为该子程序创建一关联集合，
涉及局部标识符。
4、子程序执行中，调用引用操作确定每个标识符的关联，
有的引用指向子程序中所创建的，有的可以是主程序中
创建的。
5、子程序返回控制权，则其关联被消除。
6、当主程序得回控制权，执行继续进行。
这种“创建 —使用 —消除”模式，涉及一些主要概念。
?引用环境
引用环境 ——标识符关联的集合，用于执行中的引用。
子程序的引用环境在执行中通常是不变的。
引用环境可包含如下分量,
1、局部引用环境（或局部环境）
子程序进入时创建，涉及形参、局部变量、局部定义
子程序。
2、非局部引用环境。
用于某子程序中，但不是在该子程序进入时创建。
3、全局引用环境
在主程序开始开始时创建，可为所有子程序使用。
4、预定义引用环境
有的标识符有预定义引用，直接在语言定义中指定。
任何程序或子程序可直接使用。
?可见性（ visibility）
一个标识符的某关联称为在某子程序中是可见的，如果它
是该子程序引用环境的一部分。
一个关联存在，但不是当前执行子程序的引用环境的一部
分，则称为对该子程序是隐藏的。通常隐藏是由于标识符
的重定义而产生。
?动态作用域
每个关联有一个动态作用域，该域是程序执行的一部分，
该关联存在于其引用环境中。某关联的动态作用域由它在
其中可见的子程序激活所构成。
?引用操作
基调为,
ref-op,id× referencing-environment
→data -object or subprogram
?局部、非局部和全局引用
分别对应局部环境、非局部环境或全局环境。
?数据对象的别名
在生命期中，数据对象可有多个名字，即可能有几个关
联存在于不同的引用环境，每个为数据对象提供不同的
名字。如,
数据对象“按引用传递” ——有形参名和原来名
数据对象可变成另一对象的元素 ——具有复合名。
当某数据对象在某单个引用环境中可通过多个名字可见，
每个名字称为数据对象的别名。
一个数据对象有多个名字，但在每个引用环境中是唯一
的，则不会有什么问题。
然而，在同一引用环境中用不同名字引用同一对象可能
对用户和语言实现者均产生严重问题。
图 7-4有两个 Pascal程序。
其中某整数变量有两个名 I,J（在执行中不同点）。
在第一个例子中，没有别名发生，因为没有 I,J同时用在同
一子程序中的情形。第二例子中，在 sub1中,I,J是同一对
象的别名,I是按引用传递。
别名带来的问题之一是理解困难。
如,X:=A+B
Y:=C+D
X,Y的赋值是独立的，顺序可以互换。如 X不在以后引
用，则第一个赋值还可被删去。
但如 X和 C是别名，则两个赋值实质上互相依赖，重排序
或删去均有麻烦。
别名给实现者带来的问题是类似的，因为为了优化目的
而进行的步骤重排序和删去不需要步骤均是困难的。
PASCAL中的别名
静态和动态作用域
如前所述，某标识符关联的动态作用域是在执行中关联可见
的子程序激活的集合。
动态作用域总是包含这样的子程序激活，在其中关联被创建
作为局部环境的一部分。它也可能作为非局部关联在其他程
序激活中可见。
动态作用域规则 ——根据程序的执行，定义每个关联的动态
作用域。
例如，一个典型的动态作用域规则陈述：在子程序 P的激活
中创建的某关联的作用域不仅包含该激活，还包含被 P调用
的、或传递调用的子程序的激活，除非后面的激活定义新的
局部关联隐藏了以前的原始关联。
根据这个规则，关联的动态作用域和子程序激活的动态链有
关系。
每个声明或标识符的其他定义有一定作用域，称为静态作用
域。例如：图 7.3中
在 C:=C+B语句中,B,C的引用是和特定的 C,B声明
（作为变量或形参）相连系的，但到底采用哪个声明？
一个声明的静态作用域是程序文本的一部分，这里标识符的
使用是对该标识符的特定声明的引用。
静态作用域规则 ——决定声明的静态作用域
如 Pascal中的规则,P中 X的引用指定 X在 P中头部的声明，
如不在这里表明，则指向子程序 Q（ Q的声明包含 P的声
明）中头部的 X声明，如此继续。
静态规则将程序文本中的引用和名字声明相连系。
动态规则将程序执行中的引用和名字关联相连系。
PASCAL程序中的引用环境
二者关系是什么？作用域规则则必须一致。
例如,Pascal的静态规则将 C:=C+B中变量 B的引用和主程
序中 B的声明相连系，则动态规则也必须将 B的引用和主
程序中命名为 B的数据对象相连系。
在文本中可有多个 B的声明，在执行中的子程序激活中，
也可有多个命名 B的数据对象。
维护静态和动态规则间的一致性是重要的。
?静态作用域的重要性
假定语言不使用静态作用域规则，考虑子程序中语句
X:=X+Max
没有静态作用域规则，则在翻译时对 X和 Max不可能确定
什么。
在执行时，引用操作需首先发现 X和 Max的相关关联，然
后确定类型和其他属性。
对每个标识符是否存在关联？
Max是子程序名、变量名、语句标号、类型名或形参
名？
如果 X是变量名，是否是可以和 Max相加的类型？
这些问题的回答需在执行中试图引用 X和 Max时才可作出。
而且，每次执行该语句，上述完整的过程需重复一次，
因为 X,Max的关联可能在语句的两次执行间改变。
LISP,SNOBOL4,APL几乎没有静态规则，这样对名字
的引用需要复杂而且代价很高的解释过程，首先找到相
关关联，然后确定类型和属性。
静态作用域规则允许这个过程的大多数工作在程序翻译
时一次完成，而不需要重复进行。
例,X:=X+Max 是 Pascal中语句
Max是常量,const Max=30
从而编译器可以确定 Max的值总为 30，语句翻译为 30
加到 X上，从而没有对 Max的引用操作。
对 X，如有声明,X,real，编译器将进行静态检查，
确定当语句被执行时,
①存在一个 X到数据对象的关联
②数据对象为实数类型
③其值是可以完成加法操作的类型。
编译器不能确定 X引用的数据对象的位置，也不能确
定其值。但静态检查使程序的执行更快、更可靠。
静态规则可允许在名字的引用和其声明中建立很多不同
的连接。如,
变量名和变量声明的连接,
常量名和常量声明的连接,
类型名和类型声明,
形参和形参规约
子程序调用和子程序声明
goto语句中标号和特定语句的标号等。
翻译时不同的简化使程序执行更高效。
静态规则对程序员读程序是重要的，可使程序易于理解。
块结构
块结构的概念来自于块结构语言。程序和子程序被组织为一
组嵌套的块。
块的主要特征是：引入了一个新的局部引用环境。
块以一组名字声明开始（变量声明、类型定义、常量定义
等），后跟一组语句，语句中将引用这些名字。
为简化起见，我们将块等价于子程序声明。
块中的声明定义了自己的局部引用环境，该环境在形成块体
的语句的执行中保持不变。
块的嵌套允许一个块的定义完全包括另一块的定义。在最外
层，程序由一个块构成，此即主程序。
主程序块中含有其他子程序块，从主程序调用，这些子程序
中又可包含下一层的子程序块，以此类推。
程
序
的
静
态
块
结
构
?和块结构程序关联的静态作用域规则如下,
1、每个块头的声明定义了该块的局部引用环境。在块体
中对标识符的任何引用被视为对该标识符局部声明的引用
（如存在）。
2、如某标识符在块体中引用，而且没有局部声明，则该
引用被视为对该块的立即外围块中声明的引用，如仍不存
在，则再向外推一层，以此类推。如最外层亦未声明，则
查预定义语言环境，再没有，则报错。
3、如块含有另一块定义，则在内层块的局部声明是完全
对外层块隐藏的，不能对其引用。内层块封装声明，对外
层块不可见。
4、块可以命名（通常当其表示命名子程序时），块名
变成其包含块的局部引用环境的一部分。
注意，使用静态规则，同一标识符可在多个块中声明，内
层块的声明将覆写外层块声明。
静态规则允许在任意块中对名字的引用和该名字的唯一声
明关联。
程序员的工作只是提供在适当的块中提供适当的局部声明。
编译器可提供静态检查和其它运行时结构的简化（基于这
些规则）。
局部数据和局部引用环境
局部引用环境形成最简单的数据控制结构。
子程序 Q的局部环境包含各种在 Q头声明的标识符、变量名、
形参名和子程序（ Q中声明的子程序）名等。
对局部环境，静态和动态规则是易于一致的。
静态规则 ——对 Q中标识符 X的引用是和 X在 Q头部的声明
相关的。
动态规则 ——在 Q中执行中时 X的作用指 X在 Q的当前激活
中的关联。
为实现静态规则，编译器维护一个标识符和局部声明表。当
编译 Q的体时，只要当需要标识符的声明时，去查找这个表
即可。
动态规则的实现可以两种方式实现，各自给局部引用不同的
语义。
局
部
引
用
环
境
考虑子程序 P,Q,R，局部变量 X声明在 Q中。
X在执行中的顺序,
1、当 P在执行时,X在 P中不可见,X对 Q局部。
2、当 P调用 Q,X变成可见的，作为初始值为 30的整数数
据对象的名字。当 P执行时，第一个语句引用 X并打印其
当前值 30。
3、当 Q调用 R，对 X的关联变成隐藏的，但在 R执行中将
保持。
4、当 R返回控制给 Q,X的关联又可见,X仍然命名相同
数据对象，值仍为 30。
5,Q恢复执行,X被引用和增值，新值为 31。
6,Q返回控制给 P,X的关联又变成隐蔽，但对这个关联
可提供两个不同的意义。
Retention(保留 ),X的关联可能被保留，直至 Q再次被
调用。如保留，当 Q被再次调用时，它仍关联同一对
象，其值为 31。
Deletion（删除）,X的关联可被删去。当 Q被调用，
创建一个新的数据对象并赋初值 30，关联也重建。
这是两种不同方法，涉及环境的生命期，不同语言，有不
同选择。
?实现
讨论引用环境的实现，方便的方法是将子程序的局部变量
表示为局部的环境表，该表由对组成，每个对为
（标识符、被关联对象）
如图 7.7所示。
PASCAL中的局部环境表
使用局部环境表，保持和删除方法的实现是直接的。
?保持
单个的包含被保持变量的局部环境表被分配为代码段的
一部分，如图 7.8所示。
因为这是静态分配的，在执行中将保持存在。
对这种实现方式，为了保持数据对象的值不需特殊动作。
同时，从一个局部环境转向另一个局部环境也不需特殊
动作，因为每个子程序的代码和局部数据是同一代码段
的一部分。
?删除
包含被删去变量的局部环境表被分配为激活记录的一部
分。
CEP指向当前激活记录的基地址，图 7.9是一个例子。
被
保
持
的
局
部
变
量
的
分
配
和
引
用
被
删
去
局
部
变
量
的
分
配
和
引
用
上述两种方式在我们的子程序实现一般模型中均是易于实现
的。另外一些值得注意的点包括,
1、在前面的简单的调用一返回结构的实现中
如无递归，则保持和删除实质上导致相同的实现，因为
没有多个激活记录，可以静态地分配。然而，如对变量
提供，初值，则产生两种不同的初始化含义。
2、个体变量可以有意识地给予两种不同处理
需保留值在代码段中分配空间，而删除值在激活记录中
分配空间。
3、子程序名，和局部环境中子程序申明相关联，总是处
理为保持的
名字和定义的关联可以表示为指针数据对象（在代码段
中），指向某代码段。
4、形参名表示的数据对象在每次调用时被初始化为新值
因此，处理为删除关联。
5、如允许递归子程序调用，则可能有同一子程序的多个
激活同时存在
如变量 Y处理为删除型的，则每个激活记录都包含一个名
为 Y的分别对象，每个激活执行时，将引用自己的局部拷
贝。在这种情形，引用环境的删除是常见的。
然而，某些局部变量的保持也是有价值的，这种变量将
为多个激活记录所共享。
?优、缺点
保持：允许历史敏感性
删除：对递归是自然的策略
节省存储空间，因为局部环境只对运行的或挂起
的子程序存在。
7.3 子程序中的共享数据
严格局部的数据对象只能在单一的局部引用环境中被操作。
然而，有时需要一个数据对象被多个子程序共享。
数据对象可以在子程序间以显式参数传递，但有时这种方式是麻
烦的。如：考虑一组子程序共享一个公共的数据表，则参数传递
是烦琐的。
数据共享通常是基于标识符关联的共享。如：子程序 P,Q,R需
要访问同一变量 X，则简单地允许 X在每个子程序中有相同关联。
X的关联变成某个子程序的局部环境的一部分，并成为其它子程
序非局部环境的公共部分。
通过非局部环境共享数据对象是一种重要的方式。
语言中有 4种基本的非局部环境方法,① 显式的公共环境或隐蔽
的非局部环境, 基于 ② 动态作用域； ③ 静态作用域； ④ 继承
参数和参数传递
显式传递参数和结果是主要的数据共享方法。
作为参数传递的数据对象和结果被不赋名字地传递。
在接收子程序中，每个数据对象被给定一个新的局部名。
这种共享方式对子程序的每次调用被给定不同数据的情形是
非常有用的。
?实参和形参
Argument（参数、自变量）：指作为操作数传递给子程
序或原操作数据对象。可通过参数或非局部引用得到。
Result（结果）：操作执行结束后返回的数据对象或值。
通过参数，非局部变量赋值或显式函数值返回。
形参（ formal parameter）：子程序中的一种特殊局部数
据对象。子程序定义通常在头部列出形参的名字和声明
作为规约的一部分。形参名是简单标识符，声明给出其
类型和其它属性。
例,C过程头
SUB(int X; char Y);
实参（ actual parameter）：和调用子程序共享的数据对象。
实参可以是属于调用者的局部数据，也可以是调用者的
形式参数，也可是调用者可见的非局部数据对象，或者
也可以是函数返回结果被立即传递给被调用子程序。
实参在子程序调用点表示为表达式，称为实参表达式。
通常，子程序被调用时，实参表达式被计值，计值结果
作为实参传递，然后再进入子程序。当然，也有特例，
表达式不计值而直接传递。
?建立对应
调用子程序时，需建立实参表和形参表间的对应，有两
个方法,
?位置对应,
根据各自的位置对实参和形参配对。
?由显式的名字对应
在调用语句中，和每个实参配对的形参被显式地
命名。例,SUB （ Y→B, X→27 ）
大多数语言彩位置配对。
?传递参数的方法
实参和形参的关联通常有两个途径,
先计值实参，然后将值传给形参。
或实际数据对象被传给形参。
?call by name按名调用
将子程序调用视为子程序体的全部替换，每个形参代表特
定实参的实际计值。每次形参引用需要对应的实参的实际
计值。
在子程序调用点，实参不计值，直至它在子程序中被实际
引用时才计值。
按名调用在 ALGOL语言中扮演了重要角色，具有重要理
论意义，但执行开销大。
基本的按名调用规则可用替代来陈述：在子程序开始执行
前，将子程序体中的形参均用实参替代。
这种替代带来的问题：对调用 call Sub (X),Y是形参,X是
实参。在 Sub执行前，用 X替代 Y，但 X的关联可能不在
Sub的关联中。因此，用 X替代我们还必须指出对 X的不同
引用环境，如果 X已对 Sub可见，则还可能带来含混性。
实现的基本技术是将实参处理为简单的无参数子程序（称
为 thunks）
?call by reference按引用调用
这是最常见的参数传递机制，即将指向数据对象位置的指
针传给子程序，数据对象本身并不改变其在存储中的位置。
子程序执行开始时，实参的左值被用于初始化形参的局部
存储位置。
传递参数以两步进行,
1、在调用子程序序中，每个实参表达式被计值，以给
一个指针到实参数据对象。这样的指针表被存放在公
共存储区域，可被被调用子程序访问，然后，控制传
给子程序。
2、在被调用子程序中，指向实参的指针表被访问以查
找实参合适的右值。
在子程序执行中，对形参名的引用被处理为一般的局部变
量引用。
子程序终止时，结果也通过实参数据对象返回。
?call by value按值调用
也称按拷贝调用（ call by copy），实参的值被传递给形参，
其实现类似于按引用调用，除了,
△按引用调用传递左值，而按值调用传递右值。
△按引用调用参数使用存放在形参中的左值去访问实际
数据对象。而在按值调用中，形参中包含了被使用的值。
一旦实际参数被接值传递，形参对实参不再会访问并修
改其值。
?call by value-result按值 —结果调用
形参是和实参同类型的局部变量。调用时，实参的右值
被拷贝进形参，效果上相当于显式的赋值。
子程序执行中，对形参名的引用就象对一般局部变量一
样。
子程序终止时，形参的值被拷贝回实参，也类似显式的
赋值。
?call by constant value按常量值调用
形参的值在子程序运行中不可改变，即不允许对参数赋
新值及修改。
形参也不能传递给其他子程序（除了作为常量值参数），
即形参作为局部常量。
可有两种方式实现：按值传递方式和按引用传递方式。
?call by result
仅用于从子程序传递回结果。
实参的初始值没有差别，并不可被子程序使用。
形参是无初值的局部变量，子程序终止时，形参值被赋
给实参。
?传递的语义
上面的方式描述了参数是如何实现的，然而程序员并不
需要知道实现细节，只需知道参数如何使用即可。
在 Ada中，不是描述传递模式，而是刻划参数的角色。
参数可以为 in,out,in out三种类型。实现者可以选择自
己的实现方式，具体实现方式对程序员无影响。
Ada的 83版，允许实现者对 in,out参数选择采用按引用
调用或按值调用方式。这产生了符合性问题：正确的程
序被不同的正确编译器编译可能产生不同结果。
而 Ada 95中规定,
基本数据类型，如为 in参数，按常量值传递；如为 out
和 in out参数，按值一结果方式传递。
复合数据类型，按引用传递。
?显式函数值
大多数语言中，单个结果可作为显式函数值而不是作为
参数返回。子程序需声明为函数，结果类型声明是规约
的一部分。
在函数子程序中，返回结果作为函数值可以两种方式刻
划,
使用显式的返回语句，如 return 2*X。
对函数名进行赋值，最后赋值结果作为返回结果。
?参数传递的实现
因为子程序激活接收不同参数集，子程序形参的存储分
配作为激活的一部分，而不是代码段的一部分。
每个形参是子程序的一个局部数据。
如形参 P有类型 T，则有两种实现方式（根据不同传递模
式）,
P被处理为类型 T的局部数据对象。
P被处理为 T的指针的局部数据对象。
参数传递相关的各种动作分成两组：调用点，进入和退
出。
调用点：在调用子程序中，每个实参表达式被计值，到
实参的指针表被设置。实参确定后，控制权被转移，此
时涉及 CIP和 CEP的改变。
在控制权转移后，子程序的前奏（ prologue）完成参数传
递的动作，即拷贝实参内容或指针。
子程序终止前，子程序的 epilogue完成返回值的动作。即
拷贝结果回实参，或函数值被拷到寄存器或临时区域。
在实现参数传递方面，编译器有两个主要任务,
首先，保证产生正确的执行代码来完成参数传递、结果
返回和形参引用。
第二，完成必需的静态检查以保证实参和形参类型匹配，
此时，必须知道子程序的规约。
?参数传递例子
?简单变量和常量
Q有两个形参，一个传值，一个传引用。
执行结果为,12 13 2 13
当 P调用 Q，实参表达式 a和 &b被计值，即调用引用操作，
确定 a,b的当前关联。传递的实参是 a的右值和 b的左值。
实参 a在 Q的执行中不会改变。
而 b由于传引用，故 b数据对象被 Q实质地改变。
?数据结构
考虑 Q的不同版本（用 PASCAL，因需要数组的按值调用）
type vect = array[1..3] of integer;
procedure Q(k,vect; var l,vect);
var n,integer;
begin
k[2]:= k[2]+10;
l[2]:= l[2]+10;
for n:= 1 to 3 do write(k[n]);
for n:= 1 to 3 do write(l[n])
end;
过程 P如图 7.11所示 。
P执行结果,6 17 8 6 17 8 6 7 8 6 17 8
实参 c被拷贝给 k,c,k以后没有关系 。
实参 d的左值传给形参 l（ 指向数组的指针 ）, 因此, l指
向 d数组 。
图 7.12显示了 Q执行结束时的运行时栈 。
数据结构参数
Q
终
止
前
的
运
行
时
栈
?数据结构的分量
假定 Q仍为图 7.10(a)所示,P为,
P()
{int c[4];
int m;
c[1] = 6; c[2] = 7; c[3] = 8;
Q(c[1],&c[2]);
For (m = 1; m <= 3; m++) printf(“%d\n”,c[m]);
}
执行结果为,16 17 6 17 8
?具有计算下标的数组分量
R(int *i,int *j)
{*i = *i +1;
*j = *j +1;
printf(“%d %d\n”,*i,*j);}
P()
{int c[4];
int m;
c[1] = 6; c[2] = 7; c[3] = 8; m = 2;
R(&m,&c[m]);
For (m = 1; m <= 3; m++) printf(“%d\n”,c[m]);
}
执行结果为,3 8 6 8 8
关键是 m的初值为 2,在 R中被改为 3。 那么, 到底是
C[2]还是 C[3]被增值？ 当然应该是 C[2],因为在调用
时 m为 2 。
?指针
如 X在 P中声明为,vect *X；
Q中对应形参声明为,vect *h；
如按值调，则 h是 x的拷贝，均指向相同向量。
如按引用调用，则 h包含指向 X的指针,X包含指向向量的
指针。
由于 C中有显式的左值和右值操作，故按值调用就足够了。
?表达式的结果
按引用传递表达式,Q(&(a+b),&b)
首先计值表达式，然后存放到临时位置，再传递指向该位
置的指针为参数。
但 Q中的修改无法在 P中引用，故这种方式没有太大价值。
?别名和参数
大多数语言中都有别名问题（在单一引用环境中，多个名字
表示同一数据对象）。
别名对程序理解、正确性验证及优化均有影响。
参数传递中别名的产生有两种方式,
1、形参和非局部变量
作为实参传递的数据对象可直接在子程序中通过非局部
名访问。
这样形参名和非局部名变成别名，如图 7.4所示。
2、两个形式参数
同一数据对象按引用方式作为实参传给不同形参。
则两个形参名变成别名。
别名的产生
?子程序作为参数
很多语言允许子程序作为实参传递。这时实参数表达式是子
程序名，对应的形参类型为子程序。如 PASCAL中,
procedure Q(x;intger; function R(y,z:integer):integer);
子程序参数的两个主要问题是,
?静态类型检查
当用形参名调用子程序时，最重要的是要有可能通过静态
类型检查保证调用包含实参的数量和类型。
因为在调用点还不知道被调用子程序的实际名字，编译器
难于确定是否形参子程序中的实参可以匹配实参子程序所
期望的参数。
编译器需要形参子程序的完整规约，不仅包含类型
procedure或 function，还包含参数（结果）的数量、顺序
和类型。
在上例中，子程序 Q中 R的调用可以静态地检查。在 Q的调
用中，对应 R的实参子程序也可以静态地检查。
?非局部引用（自由变量）
假定子程序包含了对非局部变量的引用，但不含有对该
变量的定义。
这样的非局部引用通常称为自由变量，因为在子程序定
义中没有局部绑定。
通常当一个子程序被调用时，一个非局部引用环境被建
立。
然而，当一个包含非局部引用的子程序 fn被作为参数从 P
传递给子程序 Q时，什么是在 Q中 fn调用时的非局部环境
（通过对应的形参 R来调用 fn）?
最简单的回答是：该局部环境和简单地用 fn代替 R所使用
局部环境一样。
但这在大多数情形都是一个错误的答案。
如图 7.13所示,
fn包含非局部引用 x和 i,x在主程序声明,i在 P中声明
（根据静态规则）。
P将 fn作为参数传给 Q,Q中通过形参 R实际地调用 fn。
Q中有对 i,x的局部定义,fn不能被允许不正确地检索这
些局部变量（当被调用时）。
这种函数作为参数传递带来的自由变量问题在很多语言
中都会发生。
一般解决方案：采用如下关于自由变量意义的规则。
一个非局部引用在作为参数传递的子程序的执行中，
应该意味着和它在子程序作为实参出现的位置被调用
的情形一样的事。
自
由
变
量
作
为
子
程
序
参
数
例如：图 7.13中,fn作为实参出现在 P对 Q的调用中。
这样,fn中 i,x的非局部引用，不管 fn后来在哪儿被调用，
仅意味着和在 P中Ｑ被调用处 fn被调用一样，即 x在主程序
中声明,i在Ｐ中声明。
为了正确实现这个规则，应可重新在子程序参数的调用
点创建正确的引用环境，使其可以正确地执行。
在 7.3.4节讨论了非局部引用的静态链实现方式可直接解
决这个问题。所需做的是为子程序参数确定正确的静态
链指针，并一起被传递。这样子程序参数变成一个指针
对 (CP,SCP)，分别为代码段指针和静态链指针。
这个对可通过多层子程序传递，直至调用该子程序。此
时，激活记录被创立，被传递的 SCP被建立，子程序代码
段的执行继续。
图 7.14给出了图 7.13例子的执行。
执
行
中
某
一
时
刻
的
中
心
栈
显式公共环境
直接建立共享数据对象的公共环境是最直接的共享方法。
将共享的数据对象分配为一个分开的命名块，每个子程序在
其中声明该块。块中对象对其声明块可见。
Fortran中的 Common块是典型例子。
?规约
对子程序而言，公共环境和局部环境是一样的，除了它不是
任何单独子程序的一部分。
公共环境可包含变量常量和类型的定义但没有子程序和形
参。
例,Ada中 Package规约,
Package shared-Tables is
Tab-size:constant integer:=100;
Type Table is array (1..Tab.Size) of real;
Table1,Table2,Table;
Curr-Entry,integer range 1..Tab-Size;
End
包中定义了一个类型，一个常量，两个表和一个整数变量。
这些组成由几个子程序需要的一组数据对象。
如果 P需访问，则在其中加入声明,
with shared-Tables;
然后可以对其中对象直接使用。
?实现
Fortran,C中，使用公共环境的子程序必须包含每个共享
变量的声明，使得编译器知道相关声明，即使公共环境也
被在其他地方声明。
在 Ada中，编译器在遇到 with语句时将先检索公共环境的
声明（从库中或程序文本的其他部分）。
公共环境的声明被加入到编译器符号表中，作为局部名的
附加集合。
在子程序中引用，子程序体中对名字的每个引用按通常方
式在表中查找，以便于静态检查和代码生成。
运行时，公共环境表示为存储块，包含了定义中声明的数
据对象。
因为数据对象潜在地是混合类型，其声明在编译时知道，
因此，块可以处理为记录，用基地址 +位移方式来引用记
录分量。
公共环境存储块必须持续在内块中存在，至少和任何潜在
可能访问它的子程序同生命期，因为这些子程序的任一个
的激活均将访问该块。
因此，块通常是静态分配的。程序开始执行即存在，执行
结束时消除。
引用公共环境中数据对象的子程序必须知道块的基地址。
简单的实现：在子程序代码块中分配一个位置，保存到公
共块的指针，图 7.15给出一个例子。
子
程
序
中
到
公
共
块
的
链
接
?共享显式变量
数据对象显式共享的另一形式是提供一种方法，使局部环境
中的数据对象对其他子程序可见。
这样，不是一组公共变量和子程序分开，而是每个变量有
“拥有者”。
为使得局部变量对外界可见，须给出显式的 export定义。
例,procedure P(…)
defines X,Y,Z; X,Y,Z对外移出。
X,Y,Z,real;
U,V,integer;
begin … end;
另一子程序通过显式的 import定义移入定量。
Procedure Q (…)
uses P.X,P.Z; 移入 P中的 X和 Z
Y,integer;
begin …end;
?实现
效果类似于公共环境中变量的使用。
移出的局部变量必须保持，因此，常分配在代码段。
其他子程序对其的引用也是采用基地址＋位移方式。
动态作用域
另一种共享数据的方式是为每个执行子程序关联一个非局部
环境。
子程序 P的非局部环境包含其他在执行过程中对 P可访问的子
程序激活的局部环境。当变量 X在 P中引用，且 X没有局部关
联时，则用非局部环境去确定 X的关联。
那么,什么是 P的非局部环境？
在块结构语言中，静态作用域规则确定了每个子程序的隐含
非局部环境。
一个更简单的方法是：使用在当前动态链中的子程序局部环
境。
考虑一种语言，当子程序退出时局部变量被删去，而且没
有子程序嵌套定义，子程序定义是分开的。
这样，没有静态程序结构作为引用非局部标识符的作用域
规则的基础。
如,P中引用 X,X不在 P中局部定义，那么，在其他子程
序中哪个 X定义被使用？
自然的回答是：考虑通往 P的激活的子程序激活动态链。
考虑程序执行过程,
主程序 － → A － → B － → P
P中引用 X，且 X不是局部定义。则先查 B，如没有，
再找 A，如没有，在找主程序。
这样，在运态链中使用 X的最近创建关联。
最近关联规则 ——基于动态作用域的引用规则。
调用 调用 调用
如果非局部环境用最近关联规则来确定，不使用静态域规则，
即不在翻译时确定非局部引用的标识符的定义关联。
在程序执行时，当数据对象 X被创建作为子程序 P的激活的一
部分，则 X的关联的动态作用域变成所有从 P开始调用的子程
序关联,X在动态作用域中可见（除非被后面的 X定义所覆
写）。
这样，子程序激活 P的非局部环境包含通往它的完整的子程
序激活动态链。
这种非局部环境最麻烦的方面是它可能在 P的激活中改变,P
的不同激活中可能有不同的 X关联。
这样，动态类型检查是需要的。
?实现
对非局部引用的最近关联规则的实现是直接的，采用子程序
激活记录的中心栈来实现。每个子程序的局部环境是其激活
记录的一部分。
假设子程序 P调用子程序 Q,Q再调用 R，当 R执行时，中心栈
如图 7.16所示。为了引用非局部 X，在栈中查找，从局部环
境开始，直至 X的最近关联被找到。
最近关联规则的实现代价较高，非局部引用的查找需要时间，
同时需要在局部关联表中存放标识符的某些表示，因为 X的
关联的位置在各个局部表中可能是不同的。从而不可能用基
地址＋位移的方式。
如何避免对非局部引用的查找？
在非局部引用和子程序进入 —退出间可以有代价上的权
衡。如果非局部引用比子程序进入 —退出更为频繁（即
使用比修改更频繁），则避免查找是有意义的。
执
行
过
程
中
的
活
跃
引
用
环
境
另一种实现方式使用对所有子程序公共的中心表 ——中心引
用环境表。
中心表设置为在程序执行的所有时间内包含所有当前活动的
标识符关联，不管其是局部还是非局部。
为了简单化，我们假定在任何子程序中引用的标识符集合可
以在翻译的确定，则中心栈初始化为对每个标识符包含一个
项，不管标识符出现在其中的不同子程序的数量。
表中每个项包含一个激活标志，指出是否特殊的标识符有一
个活动关联。还包含一个指针，指向关联的数据对象。
所有子程序中的引用被导向到该中心表，使用基地址十位移
模式，因为标识符 X的当前关联宫殿是位于当前表的同一位
置。
每个引用只需要在项中的激活标志被检查，以保证表中的关
联当前活动的。使用中心表，我们可达到不需查找而有效地
实现非局部引用的目标。
由于在引用环境中的每次变动需要修改中心表，因此，子程
序的进入和退出代价很高。当子程序 P调用 Q，必须修改中心
表以反映 Q的局部环境。
每一个对应 Q的局部标识符的项必须修改以反映新的局部关
联。
同时，如旧表项是活动的，还必须存放起来，以便 Q退出时
重被激活。由于修改的项可能散落在整个中心表中，修改必
须逐项进行。退出 Q时，恢复工作也需逐项进行。
这样，又需要一个执行时栈来作为存放非激活态关联的隐蔽
栈，当退出 Q时，栈的顶部关联块被恢复进中心表中适当位
置，图 7.17给出了一例子。
非
局
部
引
用
的
中
心
环
境
表
静态作用域和块结构
在使用块结构的语言中，非局部引用的处理更为复杂。
由于在一个子程序中某标识符的每次引用是和程序文本中该
标识符的定义相关联，即使该标识符不是局部于子程序。
这样，执行中每个子程序的非局部引用环境已经在翻译时由
静态作用域规则确定。
实现问题是，保持静态和动态作用域规则间的一致性，使得
在程序执行中非局部引用正确地关联相关数据对象。
图 7.18给出了个静态作用域规则的例子（对块结构程序）。
具
有
非
局
部
引
用
的
P
A
S
C
A
L
过
程
主程序,P和 Q中均定义了变量 X，而 R中局部引用 X。主程序
调用 P,P调用 Q,Q调用 R。
静态规则定义了对 X的引用为主程序中 X定义，对 X的非局部
引用的含义是独立于特定的动态调用链。
而最近关联规则将 X和 P或 Q中 X相关联（根据 R 的调用者）。
静态作用域规则在编译器中的实现是直接的。
当在编译中处理每个子程序定义时，创建声明的局部表
并将其附到局部表链上去。
这样在编译 R时，编译器将 R声明的局部表加到链中（目
前只含有主程序定义）。
当 R编译结束时，编译器从链中删去的 R的局部表。
声明的局部表链表示了子程序定义的静态嵌套，而不是
执行中的动态调用链。
在块结构语言的程序执行中，中心栈用于子程序激活记录。
每个子程序的局部环境存放在其激活记录中。
图 7.19给出了静态作用域和动态作用域规则间的矛盾。
当 R被调用时，如遇到对 X的非局部引用，引用操作必须
在主程序中查找 X的关联，而不是在 R的调用者 Q中。
然而，简单地沿栈查找，将指向 Q中的 X关联。
问题在于：栈中的局部表序列表示了子程序激活的动态嵌
套（基于执行时调用链），但是，是子程序定义的静态嵌
套确定非局部引用环境。
图 7.19中栈没有包含关于静态嵌套的信息。
使
用
静
态
作
用
域
的
不
完
全
中
心
栈
为了完全这个实现，必须在执行中表示静态块结构，使其可
用来控制非局部引用。
我们注意到，为了找到关联满足对 X的引用，我们查找局部
环境表链直到 X的一个关联被找到。
然而，局部环境表链不包含所有当前在栈中的局部表，而只
是那些表示块或子程序的局部表。
这些块或子程序的定义静态地在程序文本中包含当前子程
序定义。
查找仍是沿栈中表进行，但只是那些实际上是引用环境一部
分的表。
?静态链实现
只需简单地修改栈中的局部环境表，在表头加上一项 ——
静态链指针。
静态链指针总是包含另一个局部表的基地址，局部表表示
静态地包含的块或子程序的局部环境。
当然，局部环境表是激活记录的一部分，我们可使用激活
记录的基地址。
静态链指针形成了简单引用模式的基础。
为满足对 X的引用，我们循 CEP得到栈顶的当前引用环
境。
如没有 X的关联，则沿静态链指针到栈中第二个表，
如此继续。
图 7.20给出了图 7.18例子的静态链。
执行时中心栈
虽然似乎需要查找每个静态链接环境直至 X被找到，但不
一定要这样做。
当编译器为每个局部声明创建局部环境表时，它保持了哪
个子程序被静态地嵌套在该环境中的轨迹。对每个对 X的
引用，编译器记下为了发现正确关联所必须查找的外国环
境层数，然后生成代码来循静态链指针到达合适的激活记
录，这样避免了在执行栈中保持标识符名。
这是一个相当有效的实现。通常，对声明在 K层而使用
K+N层的变量的访问需要 N次静态链指针的访问。
由于子程序很少嵌套到 4—5层深（通常 2—3层）,n很少
大于 1—2。
然而，我们可以访问任意正确环境，只通过对静态链指针
的一次访问。
静态链技术允许子程序的直接进入和退出。当子程序被
调用，其激活记录在栈顶创建，此时需建立合适的静态
链指针，以指向栈中的下一个激活记录。退出时仅需从
栈中删去激活记录即可，对静态指针没有别的动作。
在子程序进入时如何建立合适的静态链指针？
如图 7.19,R定义在主程序中,Q调用 R。
当 R在执行中进入时，合适的静态链指针被设置到主
程序的激活记录。
在调用点,Q的激活记录在栈顶,R的记录被堆在 Q之
上，那么，如何确定静态链指针是指向主程序？
标识符 R是子程序名，在 Q中是非局部引用。
在 Q的调用点，可以确定 R的静态链指针指向主程
序。
此情形好象是 R在主程序中定义为局部变量而在 Q
中非局部引用一样。
?Display实现
我们有如下观察,
1、对任意子程序 R，当 R在执行时，从 R的局部表沿栈下
降的长度是常量，且简单地等于 R定义的静态嵌套深度，
而且在执行中是固定的。
如图 7.18中,R的静态链长度为 2。
2、在这个常量长度的链中，非局部引用总是在链中的同
一点被满足。
如图 7.20中,R中 X的非局部引用总在链中的第二个表被
满足。
3、链中非局部引用将被满足的位置可在编译时确定。
由此，我们具有了实现有效引用操作的基础。
我们不需显式地沿静态链查找，只需沿链跳过固定的数
的表，然后使用基地址十位移计算得到合适的表项。
在执行中，我们将标识符表示为对 ——（链位置、位移）。
这样，在上面例子中,R中 X的引用表示为（ 1,3）,1表
示沿链下降的第一个表,3表示第三个表项。
在这个实现中，当前静态链在进入每个子程序时，被拷贝
到分开的矢量中，称为 display。
Display和中心栈分开，经常表示在高速寄存器集中。
在执行中任意点,display包含了和出现在当前被执行的子
程序的静态莲中相同的指针序列。
图 7.21给出了图 7.18例子的 display。
使用 display完成引用是特别简单的。
我们在执行中使用稍微修改过的标识符表示，即使用
整数对，如：（ 3,2）,3表示从链尾到合适激活记录
的步数,2仍然表示位移。
现在给定非局部引用（ 3,10），适当的关联可在两步内
得到,
1、考虑第一个项 3作为 display的下标。
基地址＝ display[3]，从而得到激活记录的基地址。
2、计算标识符位置。
基地址 +10
通常，这两步可合为一，采用间接取址法。
如 display存放在高速寄存器中，则对每个标识符引用，只
需一次内存访问。
虽然使用 display可使引用简化，但子程序进入和退出却更
困难，因为必须修改 display以反映当前活动静态链。
执
行
中
的
中
心
栈
和
DISPLAY
?局部块中的声明
有的语言，如 C，允许语句块中声明局部变量。如,
real proc1(parameters)
{int i,j;
…/*statements*/
{int k,l; …/*statements*/}
{int m,n;
…/*statements*/
{int x; … /*statements*/}
{int y; … /*statements*/}
}}
第一眼看去，似乎每个块需要分别的激活记录来存放变量。
然而，在这些块和前面讨论的激活记录间有重要差异。由于
过程调用的动态性质，通常我们不能确定哪个过程当前被执
行。
这样如上面块每个均表示过程，则包含 k的块和包含 m的块可
能同时被执行，因此，需要分开的激活记录。
然而，在上面例子中，这是不可能的，在变量 k的块中就不能
在变量 m 的块中，从而允许简单的存储策略。
如图 7.22所示。
在激活记录中的重叠变量存储
