第九章 子程序控制.

Presentation on theme: "第九章 子程序控制."— Presentation transcript:

1 第九章 子程序控制

2 子程序间的控制方式： 简单的调用-返回方式：特点、及实现 递归调用方式 子程序间的数据共享和传递 数据共享的相关概念 参数传递 公共环境

3 9.1 子程序顺序控制 简单的子程序“调用—返回” 程序可视为以子程序为单元的层次结构
子程序调用的控制机制可用“拷贝”规则来解释，子程序调用语句的效果可通过下面方式同样得到：执行用子程序体的拷贝来替代调用语句（合适地替换参数和冲突标识符）。 从这个观点看，子程序调用可视为这样一种控制结构，它使得不必要在程序的多个地方拷贝大量相同或几乎相同的语句。 子程序

4 “调用—返回” 控制结构 这个观点中有若干隐含假设： 1、子程序不能是递归的 2、显式的调用语句是需要的。 递归分为直接递归和间接递归。
对非递归子程序调用，在翻译时，原理上我们可以应用拷贝规则。 但如子程序是直接递归的，则拷贝规则在原理上也是不可能使用的，因为替代过程不会终止，替代一个call至少引入一个call。间接递归可允许删去某些子程序，但最终仍将带来其他的直接递归。 2、显式的调用语句是需要的。 因为需要替代，必须有显式的替代点。 而对例外处理这一类子程序，则不存在显式的调用点。

5 “调用—返回” 控制结构 3、子程序必须在每次调用中被完整地执行。 4、在调用点立即转换控制权。 5、单个执行序列。
拷贝规则应用后，则子程序需从头执行到尾。 但对协同例程子程序，可能在其终止点后继续执行。 4、在调用点立即转换控制权。 显式的调用和拷贝规则，使得程序控制权被立即转移。 但对被调度子程序的调用，子程序的执行可能被延迟一定时候。 5、单个执行序列。 在执行中某点，只有一个子程序拥有控制权，执行是单序列的。 如我们停止程序则我们总可以知道是哪个子程序拥有控制权，哪些程序的执行被挂起，哪些还未被调用，哪些已结束执行。 但用作任务的子程序可以并发执行。 Fortran基本上是以拷贝规则来看待子程序调用的。 返回

6 简单的调用—返回结构： 实现—基本原理 首先需建立完整的程序执行模型。
对表达式或语句序列，被视为运行时的可执行代码块。表达式或语句序列的执行即是代码块的执行，通过硬件解释器进行。 但对子程序而言，我们需要更多： 1、在子程序定义（翻译为模板）和子程序激活（调用时创建）间存在不同。 2、激活实现为两部分：代码段 + 激活记录。 3、代码段在执行过程中不变，子程序的每个激活使用相同代码段。 4、激活在调用时创建，返回时消除，激活中的内容会因赋值而经常变化。

7 简单的调用—返回结构： 实现—基本原理 为避免混淆，我们不是简单地说子程序中某特定语句的执行，而是说：在子程序的激活R中S的执行。
这样，为了跟踪程序执行点，我们需要两片数据，用于存放两个系统定义的指针变量。 当前指令指针：CIP 指向当前正在被硬件或软件解释器执行的指令。 当前环境指针：CEP 因为同一子程序的所有激活使用同一代码段，只知道当前指令是不够 的，还需要指向激活记录（代表了子程序的引用环境）的指针（因此称为环境指针）。

8 简单的调用—返回结构： 实现—基本原理 CEP和CIP的配合，控制了程序的执行路线。
为了保证从子程序的正确返回，CIP和CEP需合适地存放。 通常在调用时将CIP和CEP存放在被调用子程序的激活记录中。 在激活记录中包含一个系统定义的数据对象——返回点（存放两个指针值）。 当遇到call调用时，将旧的（ip, ep）存放到激活记录中返回点，将新的（ip, ep）赋给CIP、CEP，从而完成控制的转移。 遇到返回语句时，取旧的（ip, ep），重设置CIP，CEP，返回控制权。

9 子程序的执行 子程序B开始执行时的执行状态

10 简单的调用—返回结构： 实现—简化的实现方法
子程序的拷贝规则观点的重要性质是： 在程序执行中任一点，最多只有某子程序的一个激活是被使用的。子程序可以多次调用，但在其下一次激活开始时，每个激活必须完成且终止。 基于这个性质，可导出一个更简单的子程序实现模型，只要我们愿意用存储来增加执行速度： 为每个子程序静态地分配用以存放单个激活记录的空间，作为代码数的扩展，而不是运行时创建。 很多Fortran和COBOL实现采用这种方式。

11 简单的调用—返回结构： 实现—简化的实现方法
这样执行不需动态分配空间，而是重复地使用同一个激活记录，只是在调用发生时对其进行初始化而已。 这种模型也带来其他简化，CEP不再需要，因为当前激活记录总是CIP指定的代码数的扩展。 对简化的实现，硬件常提供一return-jump指令，允许子程序调用被单条硬件指令所实现。这样CIP直接表示为硬件的地址寄存器。 返回跳指令将地址寄存器中内容存放到内存或寄存器中，并为其赋新值。

12 子程序调用返回结构 返回

13 递归子程序 前面讨论的假设是不允许递归，而递归是重要的顺序控制结构之一。 如LISP中，递归是主要的控制机制。 规约
递归子程序在语法上和其他子程序设计没什么两样，概念上，也没有困难。 唯一的不同是：递归调用可以在第一个激活的生命期内创建子程序的第二个激活，如第二个激活再作一次递归调用，则产生第三个激活，如此进行下去。 递归引入的唯一新元素是同一子程序的多个激活可在执行中某点同时存在。

14 递归子程序：实现 由于多个激活同时存在的可能性，我们需要CIP和CEP。
在A中，创建A的一个新激活记录和创建一个子程序B的激活记录是一样的。 在A调用B的情形，A和B的任意两个激活记录的生命期是不交的，A的生命期完整地包含了B的生命期。在A调用A时，上述性质同样成立。 每个激活记录包含一个返回点，存放值对（ip,ep）。如只观察ep值，注意到它们形成了一个链表，以创建顺序将激活记录在中心栈上链在一起。CEP指向栈顶，并可沿ep链（这个链称为动态链，以程序执行中动态创建的顺序将子程序激活链在一起）到达较早创建的激活记录。

15 递归子程序：实现 计算机硬件有时也提供这种中心栈支持，但其实现代价通常高于简单的无递归的调用—返回结构。
将以简单方式实现的子程序和使用中心栈的子程序混合是不困难，只要编译器能分辨清楚即可。 只有实际递归调用的子程序需要中心栈，因此，有的语言对递归子程序给出显式语法标志，有的语言假设子程序总是递归的。 返回

16 9.2 数据控制的属性 语言的数据控制特性涉及： 当写程序时，通常知道程序必须执行的操作及其顺序，但对这些操作的操作数则较少了解。考虑例子。
数据在不同执行点的可访问性。 确定数据如何提供给操作，如何存放操作的结果，将结果又如何取出供以后的操作作为操作数使用。 当写程序时，通常知道程序必须执行的操作及其顺序，但对这些操作的操作数则较少了解。考虑例子。 X:=Y+2*Z 其中有乘、加和赋值三个操作，但操作数是什么呢？ 2显然是乘法的操作数，但X、Y、Z仅是标识符，他们不是操作数，只是以某种方式指定了操作数。

17 数据控制的属性 Y可能是实数、整数或无参数子程序的名字，也可能由于程序员出错，Y实际上是布尔值、或串、或语句标号。Y可能指定一个在附近计算的值，也可能是在较早计算中计算的值（被几层子程序调用分开），甚至Y可能在程序的不同地方用作不同的名字。那么，当前Y是什么？

18 数据控制的属性 因此，数据控制的中心问题是：Y在这样一个赋值语句的每次执行中意味着什么？
标识符的使用范围、以及引用环境 Y可能是形态参数，问题涉及参数传递技术。 Y可能是无参数子程序，总是涉及子程序返回结果的机制。

19 名字和引用环境 基本上只有两种方式将数据对象作为操作的操作数。 直接传递： 通过给数据对象的引用命名：
某数据对象作为某处操作的计算结果可直接传递给另一操作作为操作数，如上面例中，2×Z作为加法的操作数。这种对象无需命名，而是分配临时存储。 通过给数据对象的引用命名： 数据对象在创建时可给定名字，名字可用来作为操作数。数据对象也可作为另一有名数据对象的部件。通过名字和选择操作指定。 直接传递用作表达式中的数据控制，但大多数数据控制涉及名字的使用和名字的引用，名字的意义形成数据控制的中心问题。 名字的使用、引用，及名字的别名

20 数据对象的命名 可以命名的程序元素 这里，1~3是我们考虑的重点。4 ~9的大多数名引用在翻译时确定，虽然也有特例，但无新观念引入。
1、命名变量 2、形参名 3、子程序名 4、定义类型的名字 5、定义常量的名字 6、语句标号（语句的名字） 7、例外名 8、原始操作名，如+，*，SORT 9、常量名，如17，3.25 这里，1~3是我们考虑的重点。4 ~9的大多数名引用在翻译时确定，虽然也有特例，但无新观念引入。 上述名字均是简单名字，也可以有复合名字，如A[3]。 返回

21 关联和引用环境 数据控制涉及标识符（简单变量）到特殊数据对象和子程序的绑定. 这种绑定称为关联，表示为一个对（标识符、数据/子程序）。
在大多数语言的程序执行中，我们观察到： 1、在子程序执行的开始点完成的关联有： 声明的变量名→特定数据对象 调用的子程序名→特定的子程序定义。 2、当子程序执行时，它调用引用操作来确定和标识符关联的特定对象或子程序，如： A:=B+FN(C) 需要4个引用操作，对应A、B、C和FN。

22 关联和引用环境 这种“创建—使用—消除”模式，涉及一些主要概念。 3、当调用一新子程序，将为该子程序创建一关联集合，涉及局部标识符。
4、子程序执行中，调用引用操作确定每个标识符的关联，有的引用指向子程序中所创建的，有的可以是主程序中创建的。 5、子程序返回控制权，则其关联被消除。 6、当主程序得回控制权，执行继续进行。 这种“创建—使用—消除”模式，涉及一些主要概念。

23 子程序的引用环境 引用环境 引用环境可包含如下分量： 引用环境——标识符关联的集合，用于执行中的引用。
子程序的引用环境在执行中通常是不变的。 引用环境可包含如下分量： 1、局部引用环境（或局部环境） 子程序进入时创建，涉及形参、局部变量、局部定义子程序。 2、非局部引用环境。 用于某子程序中，但不是在该子程序进入时创建。 3、全局引用环境 在主程序开始开始时创建，可为所有子程序使用。 4、预定义引用环境 有的标识符有预定义引用，直接在语言定义中指定。 任何程序或子程序可直接使用。

24 子程序的引用环境：相关概念 可见性（visibility） 动态作用域
一个标识符的某关联称为在某子程序中是可见的，如果它是该子程序引用环境的一部分。 一个关联存在，但不是当前执行子程序的引用环境的一部分，则称为对该子程序是隐藏的。通常隐藏是由于标识符的重定义而产生。 动态作用域 每个关联有一个动态作用域，该域是程序执行的一部分，该关联存在于其引用环境中。某关联的动态作用域由它在其中可见的子程序激活所构成。

25 子程序的引用环境：相关概念 引用操作 局部、非局部和全局引用 基调为： 分别对应局部环境、非局部环境或全局环境。
ref-op: id×referencing-environment →data-object or subprogram 局部、非局部和全局引用 分别对应局部环境、非局部环境或全局环境。 返回

26 数据对象的别名 在生命期中，数据对象可有多个名字，即可能有几个关联存在于不同的引用环境，每个为数据对象提供不同的名字。如：
数据对象“按引用传递”——有形参名和原来名 数据对象可变成另一对象的元素——具有复合名。 当某数据对象在某单个引用环境中可通过多个名字可见，每个名字称为数据对象的别名。 一个数据对象有多个名字，但在每个引用环境中是唯一的，则不会有什么问题。 然而，在同一引用环境中用不同名字引用同一对象可能对用户和语言实现者均产生严重问题。

27 数据对象的别名 别名带来的问题之一是理解困难。 如：X:=A+B Y:=C+D
X、Y的赋值是独立的，顺序可以互换。如X不在以后引用，则第一个赋值还可被删去。 但如X和C是别名，则两个赋值实质上互相依赖，重排序或删去均有麻烦。 别名给实现者带来的问题是类似的，因为为了优化目的而进行的步骤重排序和删去不需要步骤均是困难的。 返回

28 动态作用域 标识符关联的动态作用域是在执行中关联可见的子程序激活的集合。
动态作用域总是包含这样的子程序激活，在其中关联被创建作为局部环境的一部分。它也可能作为非局部关联在其他程序激活中可见。 动态作用域规则——根据程序的执行，定义每个关联的动态作用域。 例如，一个典型的动态作用域规则陈述：在子程序P的激活中创建的某关联的作用域不仅包含该激活，还包含被P调用的、或传递调用的子程序的激活，除非后面的激活定义新的局部关联隐藏了以前的原始关联。 根据这个规则，关联的动态作用域和子程序激活的动态链有关系。

29 静态作用域 每个声明或标识符的其他定义有一定作用域，称为静态作用域。
一个声明的静态作用域是程序文本的一部分，这里标识符的使用是对该标识符的特定声明的引用。 静态作用域规则——决定声明的静态作用域 如Pascal中的规则：P中X的引用指定X在P中头部的声明，如不在这里表明，则指向子程序Q（ Q的声明包含P的声明）中头部的X声明，如此继续。 静态规则将程序文本中的引用和名字声明相连系。 动态规则将程序执行中的引用和名字关联相连系。

30 静态和动态作用域 二者关系是什么？作用域规则必须一致。
例如：Pascal的静态规则将C:=C+B中变量B的引用和主程序中B的声明相连系，则动态规则也必须将B的引用和主程序中命名为B的数据对象相连系。 在文本中可有多个B的声明，在执行中的子程序激活中，也可有多个命名B的数据对象。 维护静态和动态规则间的一致性是重要的。

31 静态作用域 假定语言不使用静态作用域规则，考虑子程序中语句 没有静态作用域规则，则在翻译时对X和Max不可能确定什么。
X:=X+Max 没有静态作用域规则，则在翻译时对X和Max不可能确定什么。 在执行时，引用操作需首先发现X和Max的相关关联，然后确定类型和其他属性。 对每个标识符是否存在关联？ Max是子程序名、变量名、语句标号、类型名或形参名？ 如果X是变量名，是否是可以和Max相加的类型？ 这些问题的回答需在执行中试图引用X和Max时才可作出。 而且，每次执行该语句，上述完整的过程需重复一次，因为X、Max的关联可能在语句的两次执行间改变。 LISP、SNOBOL4、APL几乎没有静态规则，这样对名字的引用需要复杂而且代价很高的解释过程，首先找到相关关联，然后确定类型和属性。

32 静态作用域 静态作用域规则允许这个过程的大多数工作在程序翻译时一次完成，而不需要重复进行。 例：X:=X+Max
其中， Max是常量，const Max=30 从而编译器可以确定Max的值总为30，语句翻译为30加到X上，从而没有对Max的引用操作。 对X，如有声明：X: real，编译器将进行静态检查，确定当语句被执行时， ①存在一个X到数据对象的关联 ②数据对象为实数类型 ③其值是可以完成加法操作的类型。 编译器不能确定X引用的数据对象的位置，也不能确定其值。但静态检查使程序的执行更快、更可靠。

33 静态作用域 静态规则可允许在名字的引用和其声明中建立很多不同的连接。如： 翻译时不同的简化使程序执行更高效。
变量名和变量声明的连接， 常量名和常量声明的连接， 类型名和类型声明， 形参和形参规约 子程序调用和子程序声明 goto语句中标号和特定语句的标号等。 翻译时不同的简化使程序执行更高效。 静态规则对程序员读程序是重要的，可使程序易于理解。

34 块结构 块结构的概念来自于块结构语言。程序和子程序被组织为一组嵌套的块。 块的主要特征是：引入了一个新的局部引用环境。
块以一组名字声明开始（变量声明、类型定义、常量定义等），后跟一组语句，语句中将引用这些名字。 为简化起见，我们将块等价于子程序声明。 块中的声明定义了自己的局部引用环境，该环境在形成块体的语句的执行中保持不变。 块的嵌套允许一个块的定义完全包括另一块的定义。在最外层，程序由一个块构成，此即主程序。 主程序块中含有其他子程序块，从主程序调用，这些子程序中又可包含下一层的子程序块，以此类推。

35 程序的静态块结构

36 静态作用域规则 和块结构程序关联的静态作用域规则如下：
1、每个块头的声明定义了该块的局部引用环境。在块体中对标识符的任何引用被视为对该标识符局部声明的引用（如存在）。 2、如某标识符在块体中引用，而且没有局部声明，则该引用被视为对该块的立即外围块中声明的引用，如仍不存在，则再向外推一层，以此类推。如最外层亦未声明，则查预定义语言环境，再没有，则报错。 3、如块含有另一块定义，则在内层块的局部声明是完全对外层块隐藏的，不能对其引用。内层块封装声明，对外层块不可见。 4、块可以命名（通常当其表示命名子程序时），块名变成其包含块的局部引用环境的一部分。

37 静态作用域规则 使用静态规则，同一标识符可在多个块中声明，内层块的声明将覆写外层块声明。
静态规则允许在任意块中对名字的引用和该名字的唯一声明关联。 程序员的工作只是提供在适当的块中提供适当的局部声明。 编译器可提供静态检查和其它运行时结构的简化（基于这些规则）。 返回

38 局部数据和局部引用环境 局部引用环境形成最简单的数据控制结构。
子程序Q的局部环境包含各种在Q头声明的标识符、变量名、形参名和子程序（Q中声明的子程序）名等。 对局部环境，静态和动态规则是易于一致的。 静态规则——对Q中标识符X的引用是和X在Q头部的声明相关的。 动态规则——在Q中执行中时X的作用指X在Q的当前激活中的关联。 为实现静态规则，编译器维护一个标识符和局部声明表。当编译Q的体时，只要当需要标识符的声明时，去查找这个表即可。 动态规则的实现可以两种方式实现，各自给局部引用不同的语义。

39 局部引用环境 ：例子

40 局部引用环境：例子 考虑子程序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的关联又变成隐蔽。

41 局部引用环境 当控制从子程序Q返回给P时，Q中的局部变量X的关联又变成隐蔽，但对这个关联可提供两个不同的意义。
Retention(保留)：X的关联可能被保留，直至Q再次被调用。如保留，当Q被再次调用时，它仍关联同一对象，其值为31。 Deletion（删除）：X的关联可被删去。当Q被调用，创建一个新的数据对象并赋初值30，关联也重建。 这是两种不同方法，涉及环境的生命期，不同语言，有不同选择。

42 局部引用环境：实现 讨论引用环境的实现，方便的方法是将子程序的局部变量表示为局部的环境表，该表由对组成，每个对为：
（标识符、被关联对象） 如：PASCAL中的局部环境表

43 局部引用环境：实现 使用局部环境表，保持和删除方法的实现是直接的。 保持 单个的包含被保持变量的局部环境表被分配为代码段的一部分。
因为这是静态分配的，在执行中将保持存在。 对这种实现方式，为了保持数据对象的值不需特殊动作。 同时，从一个局部环境转向另一个局部环境也不需特殊动作，因为每个子程序的代码和局部数据是同一代码段的一部分。

44 局部变量的保持

45 局部引用环境：实现 删除 包含被删去变量的局部环境表被分配为激活记录的一部分。 CEP指向当前激活记录的基地址。

46 局部变量的删除

47 局部引用环境：实现 上述两种方式在我们的子程序实现一般模型中均是易于实现的。另外一些值得注意的点包括：
1、在前面的简单的“调用——返回”结构的实现中如无递归，则保持和删除实质上导致相同的实现，因为没有多个激活记录，可以静态地分配。然而，如对变量提供初值，则产生两种不同的初始化含义。 2、个体变量可以有意识地给予两种不同处理需保留值在代码段中分配空间，而删除值在激活记录中分配空间。 3、子程序名，和局部环境中子程序申明相关联，总是处理为保持，名字和定义的关联可以表示为指针数据对象（在代码段中），指向某代码段。

48 局部引用环境：实现 4、形参名表示的数据对象在每次调用时被初始化为新值，因此，处理为删除关联。
5、如允许递归子程序调用，则可能有同一子程序的多个激活同时存在 如变量Y处理为删除型的，则每个激活记录都包含一个名为Y的分别对象，每个激活执行时，将引用自己的局部拷贝。在这种情形，引用环境的删除是常见的。 然而，某些局部变量的保持也是有价值的，这种变量将为多个激活记录所共享。

49 局部引用环境：实现 优、缺点 保持：允许历史敏感性 删除：对递归是自然的策略 节省存储空间，因为局部环境只对运行的或挂起的子程序存在。 返回

50 9.3 参数传递 严格局部的数据对象只能在单一的局部引用环境中被操作。 然而，有时需要一个数据对象被多个子程序共享。
9.3 参数传递 严格局部的数据对象只能在单一的局部引用环境中被操作。 然而，有时需要一个数据对象被多个子程序共享。 数据对象可以在子程序间以显式参数传递，但有时这种方式是麻烦的。如：考虑一组子程序共享一个公共的数据表，则参数传递是烦琐的。 数据共享通常是基于标识符关联的共享。如：子程序P、Q、R需要访问同一变量X，则简单地允许X在每个子程序中有相同关联。X的关联变成某个子程序的局部环境的一部分，并成为其它子程序非局部环境的公共部分。

51 共享数据的基本方式 通过非局部环境共享数据对象是一种重要的方式。 语言中有4种基本的非局部环境方法： ①显式的公共环境或隐蔽的非局部环境，
②基于动态作用域； ③基于静态作用域； ④基于继承

52 参数和参数传递 显式传递参数和结果是主要的数据共享方法。 这种共享方式对子程序的每次调用被给定不同数据的情形是非常有用的。
作为参数传递的数据对象和结果被不赋名字地传递。 在接收子程序中，每个数据对象被给定一个新的局部名。 这种共享方式对子程序的每次调用被给定不同数据的情形是非常有用的。

53 参数和参数传递 基本概念： 形参和实参、及其对应方式 参数传递的基本方法 参数传递的语义 参数传递的实现 例子

54 参数和参数传递 实参和形参 Argument（参数、自变量）：指作为操作数传递给子程序或原操作数据对象。可通过参数或非局部引用得到。
Result（结果）：操作执行结束后返回的数据对象或值。通过参数，非局部变量赋值或显式函数值返回。

55 参数：形参和实参 形参（formal parameter）：子程序中的一种特殊局部数据对象。子程序定义通常在头部列出形参的名字和声明作为规约的一部分。形参名是简单标识符，声明给出其类型和其它属性。 例，C过程头 SUB(int X; char Y); 实参（actual parameter）：和调用子程序共享的数据对象。实参可以是属于调用者的局部数据，也可以是调用者的形式参数，也可是调用者可见的非局部数据对象，或者也可以是函数返回结果被立即传递给被调用子程序。 实参在子程序调用点表示为表达式，称为实参表达式。 通常，子程序被调用时，实参表达式被计值，计值结果作为实参传递，然后再进入子程序。当然，也有特例，表达式不计值而直接传递。

56 参数和参数传递 建立对应 调用子程序时，需建立实参表和形参表间的对应，有两个方法： 位置对应： 由显式的名字对应 大多数语言采用位置配对。
根据各自的位置对实参和形参配对。 由显式的名字对应 在调用语句中，和每个实参配对的形参被显式地命名。例：SUB （Y→B，X→27） 大多数语言采用位置配对。 返回

57 传递参数的方法 实参和形参的关联通常有两个途径： 传递参数的方法 先计值实参，然后将值传给形参。 或实际数据对象被传给形参。 按名调用
按引用调用 按值调用 按值—结果调用 按常量值调用 按结果调用

58 参数传递：按名调用 将子程序调用视为子程序体的全部替换，每个形参代表特定实参的实际计值。每次形参引用需要对应的实参的实际计值。
在子程序调用点，实参不计值，直至它在子程序中被实际引用时才计值。 按名调用在ALGOL语言中扮演了重要角色，具有重要理论意义，但执行开销大。 基本的按名调用规则可用替代来陈述：在子程序开始执行前，将子程序体中的形参均用实参替代。

59 参数传递：按名调用 这种替代带来的问题：对调用call Sub (X), Y是形参，X是实参。在Sub执行前，用X替代Y，但X的关联可能不在Sub的关联中。因此，用X替代我们还必须指出对X的不同引用环境，如果X已对Sub可见，则还可能带来含混性。 实现的基本技术是将实参处理为简单的无参数子程序（称为thunks）

60 参数传递：按引用调用 这是最常见的参数传递机制，即将指向数据对象位置的指针传给子程序，数据对象本身并不改变其在存储中的位置。
子程序执行开始时，实参的左值被用于初始化形参的局部存储位置。 传递参数以两步进行： 1、在调用子程序序中，每个实参表达式被计值，以给一个指针到实参数据对象。这样的指针表被存放在公共存储区域，可被被调用子程序访问，然后，控制传给子程序。 2、在被调用子程序中，指向实参的指针表被访问以查找实参合适的右值。 在子程序执行中，对形参名的引用被处理为一般的局部变量引用。 子程序终止时，结果也通过实参数据对象返回。

61 参数传递：按值调用 也称按拷贝调用（call by copy），实参的值被传递给形参，其实现类似于按引用调用，除了：
按引用调用传递左值，而按值调用传递右值。 按引用调用参数使用存放在形参中的左值去访问实际数据对象。而在按值调用中，形参中包含了被使用的值。 一旦实际参数被接值传递，形参对实参不再会访问并修改其值。

62 参数传递：按值—结果调用 形参是和实参同类型的局部变量。调用时，实参的右值被拷贝进形参，效果上相当于显式的赋值。
子程序执行中，对形参名的引用就象对一般局部变量一样。 子程序终止时，形参的值被拷贝回实参，也类似显式的赋值。

63 参数传递：按常量值调用 形参的值在子程序运行中不可改变，即不允许对参数赋新值及修改。
形参也不能传递给其他子程序（除了作为常量值参数），即形参作为局部常量。 可有两种方式实现：按值传递方式和按引用传递方式。

64 参数传递：按结果调用 仅用于从子程序传递回结果。 实参的初始值没有差别，并不可被子程序使用。
形参是无初值的局部变量，子程序终止时，形参值被赋给实参。 返回

65 参数传递的语义 参数的传递方式描述了参数是如何实现的，然而程序员并不需要知道实现细节，只需知道参数如何使用即可。
在Ada中，不是描述传递模式，而是刻划参数的角色。参数可以为in、out、in out三种类型。实现者可以选择自己的实现方式，具体实现方式对程序员无影响。 Ada的83版，允许实现者对in、out参数选择采用按引用调用或按值调用方式。这产生了符合性问题：正确的程序被不同的正确编译器编译可能产生不同结果。 而Ada 95中规定： 基本数据类型，如为in参数，按常量值传递；如为out和in out参数，按值一结果方式传递。 复合数据类型，按引用传递。

66 返回值：显式函数值 大多数语言中，单个结果可作为显式函数值而不是作为参数返回。子程序需声明为”函数”，结果类型声明是规约的一部分。
在函数子程序中，返回结果作为函数值可以两种方式刻划： 使用显式的返回语句，如return 2*X。 对函数名进行赋值，最后赋值结果作为返回结果。 返回

67 参数传递的实现 因为子程序激活接收不同参数集，子程序形参的存储分配作为激活的一部分，而不是代码段的一部分。 每个形参是子程序的一个局部数据。
如形参P有类型T，则有两种实现方式（根据不同传递模式）： P被处理为类型T的局部数据对象。 P被处理为T的指针的局部数据对象。

68 参数传递的实现 参数传递相关的各种动作分成两组：调用点，进入和退出。 在实现参数传递方面，编译器有两个主要任务：
调用点：在调用子程序中，每个实参表达式被计值，到实参的指针表被设置。实参确定后，控制权被转移，此时涉及CIP和CEP的改变。 在控制权转移后，子程序的前奏（prologue）完成参数传递的动作，即拷贝实参内容或指针。 子程序终止前，子程序的尾声(epilogue)完成返回值的动作。即拷贝结果回实参，或函数值被拷到寄存器或临时区域。 在实现参数传递方面，编译器有两个主要任务： 首先，保证产生正确的执行代码来完成参数传递、结果返回和形参引用。 第二，完成必需的静态检查以保证实参和形参类型匹配，此时，必须知道子程序的规约。 返回

69 参数传递例子：简单变量和常量 Q有两个形参，一个传值，一个传引用。
执行结果为： 当P调用Q，实参表达式a和&b被计值，即调用引用操作，确定a、b的当前关联。传递的实参是a的右值和b的左值。 实参a在Q的执行中不会改变。 而b由于传引用，故b数据对象被Q实质地改变。

70 参数传递例子：数据结构 考虑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

71 参数传递例子：数据结构 过程P如图所示。 P执行结果：6 17 8 6 17 8 6 7 8 6 17 8
实参c被拷贝给k，c、k以后没有关系。 实参d的左值传给形参l（指向数组的指针），因此，l指向d数组。

72 参数传递例子：数据结构 Q执行结束时的运行时栈。

73 参数传递例子：数据结构的分量 假定P为： 执行结果为：16 17 6 17 8 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]); } 执行结果为：

74 参数传递例子：具有计算下标的数组分量 设R如下，P改为调用R： 执行结果为：3 8 6 8 8
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]); } 执行结果为： 关键是m的初值为2，在R中被改为3。那么，到底是C[2]还是C[3]被增值？当然应该是C[2]，因为在调用时m为2 。 R(int *i, int *j) { *i = *i +1; *j = *j +1; printf(“%d %d\n”, *i, *j); }

75 参数传递例子：指针 如X在P中声明为：vect *X； Q中对应形参声明为：vect *h； 如按值调，则h是x的拷贝，均指向相同向量。
如按引用调用，则h包含指向X的指针，X包含指向向量的指针。 由于C中有显式的左值和右值操作，故按值调用就足够了。

76 参数传递例子：表达式的结果 按引用传递表达式：Q(&(a+b), &b) 首先计值表达式，然后存放到临时位置，再传递指向该位置的指针为参数。
但Q中的修改无法在P中引用，故这种方式没有太大价值。

77 别名和参数 大多数语言中都有别名问题（在单一引用环境中，多个名字表示同一数据对象）。 别名对程序理解、正确性验证及优化均有影响。
参数传递中别名的产生有两种方式： 1、形参和非局部变量 作为实参传递的数据对象可直接在子程序中通过非局部名访问。 这样形参名和非局部名变成别名，如图7.4所示。 2、两个形式参数 同一数据对象按引用方式作为实参传给不同形参。 则两个形参名变成别名。

78 别名的产生

79 子程序作为参数 很多语言允许子程序作为实参传递。这时实参数表达式是子程序名，对应的形参类型为子程序。如PASCAL中：
procedure Q(x;intger; function R(y,z:integer):integer); 子程序参数的两个主要问题： 静态类型检查 当用形参名调用子程序时，最重要的是要有可能通过静态类型检查保证调用包含实参的数量和类型。 因为在调用点还不知道被调用子程序的实际名字，编译器难于确定是否形参子程序中的实参可以匹配实参子程序所期望的参数。 编译器需要形参子程序的完整规约，不仅包含类型procedure或function，还包含参数（结果）的数量、顺序和类型。

80 子程序作为参数 子程序参数的两个主要问题： 非局部引用（自由变量） 假定子程序包含了对非局部变量的引用，但不含有对该变量的定义。
这样的非局部引用通常称为自由变量，因为在子程序定义中没有局部绑定。 通常当一个子程序被调用时，一个非局部引用环境被建立。 然而，当一个包含非局部引用的子程序fn被作为参数从P传递给子程序Q时，什么是在Q中fn调用时的非局部环境（通过对应的形参R来调用fn）? 最简单的回答是：该局部环境和简单地用fn代替R所使用局部环境一样。 但这在大多数情形都是一个错误的答案。

81 子程序作为参数 自由变量作为子程序参数 如图所示： fn包含非局部引用x和i，x在主程序声明，i在P中声明（根据静态规则）。
P将fn作为参数传给Q，Q中通过形参R实际地调用fn。 Q中有对i、x的局部定义，fn不能被允许不正确地检索这些局部变量（当被调用时）。

82 子程序作为参数 自由变量作为子程序参数 这种函数作为参数传递带来的自由变量问题在很多语言中都会发生。
一般解决方案：采用如下关于自由变量意义的规则。 一个非局部引用在作为参数传递的子程序的执行中，应该意味着和它在子程序作为实参出现的位置被调用的情形一样的事。 上例中，fn作为实参出现在P对Q的调用中。 这样，fn中i、x的非局部引用，不管fn后来在哪儿被调用，仅意味着和在P中Ｑ被调用处fn被调用一样，即x在主程序中声明，i在Ｐ中声明。

83 子程序作为参数 自由变量作为子程序参数 为了正确实现这个规则，应可重新在子程序参数的调用点创建正确的引用环境，使其可以正确地执行。
非局部引用的静态链实现方式可直接解决这个问题。 所需做的是为子程序参数确定正确的静态链指针，并一起被传递。这样子程序参数变成一个指针对(CP，SCP)，分别为代码段指针和静态链指针。 这个对可通过多层子程序传递，直至调用该子程序。此时，激活记录被创立，被传递的SCP被建立，子程序代码段的执行继续。

84 子程序作为参数 执行中某一时刻的中心栈 返回

85 9.4 显式的公共环境 直接建立共享数据对象的公共环境是最直接的共享方法。 规约
将共享的数据对象分配为一个分开的命名块，每个子程序在其中声明该块。块中对象对其声明块可见。 Fortran中的Common块是典型例子。 规约 对子程序而言，公共环境和局部环境是一样的，除了它不是任何单独子程序的一部分。 公共环境可包含变量常量和类型的定义但没有子程序和形参。

86 显式的公共环境：规约 例：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; 然后可以对其中对象直接使用。

87 显式的公共环境：实现 Fortran、C中，使用公共环境的子程序必须包含每个共享变量的声明，使得编译器知道相关声明，即使公共环境也被在其他地方声明。 在Ada中，编译器在遇到with语句时将先检索公共环境的声明（从库中或程序文本的其他部分）。 公共环境的声明被加入到编译器符号表中，作为局部名的附加集合。 在子程序中引用，子程序体中对名字的每个引用按通常方式在表中查找，以便于静态检查和代码生成。 运行时，公共环境表示为存储块，包含了定义中声明的数据对象。

88 显式的公共环境：实现 因为数据对象潜在地是混合类型，其声明在编译时知道，因此，块可以处理为记录，用基地址+位移方式来引用记录分量。
公共环境存储块必须持续在内块中存在，至少和任何潜在可能访问它的子程序同生命期，因为这些子程序的任一个的激活均将访问该块。 因此，块通常是静态分配的。程序开始执行即存在，执行结束时消除。 引用公共环境中数据对象的子程序必须知道块的基地址。 简单的实现：在子程序代码块中分配一个位置，保存到公共块的指针。

89 显式的公共环境：实现 简单的实现

90 显式的公共环境：共享显式变量 数据对象显式共享的另一形式是提供一种方法，使局部环境中的数据对象对其他子程序可见。
这样，不是一组公共变量和子程序分开，而是每个变量有“拥有者”。 为使得局部变量对外界可见，须给出显式的export定义。

91 显式的公共环境：共享显式变量 实现 例：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; 实现 效果类似于公共环境中变量的使用。 移出的局部变量必须保持，因此，常分配在代码段。 其他子程序对其的引用也是采用基地址＋位移方式。

92 动态作用域 另一种共享数据的方式是为每个执行子程序关联一个非局部环境。
子程序P的非局部环境包含其他在执行过程中对P可访问的子程序激活的局部环境。当变量X在P中引用，且X没有局部关联时，则用非局部环境去确定X的关联。 那么，什么是P的非局部环境？ 在块结构语言中，静态作用域规则确定了每个子程序的隐含非局部环境。 一个更简单的方法是：使用在当前动态链中的子程序局部环境。 考虑一种语言，当子程序退出时局部变量被删去，而且没有子程序嵌套定义，子程序定义是分开的。

93 动态作用域 这样，没有静态程序结构作为引用非局部标识符的作用域规则的基础。
如：P中引用X，X不在P中局部定义，那么，在其他子程序中哪个X定义被使用？ 自然的回答是：考虑通往P的激活的子程序激活动态链。 考虑程序执行过程： 主程序  A  B  P P中引用X，且X不是局部定义。则先查B，如没有，再找A，如没有，在找主程序。 这样，在运态链中使用X的最近创建关联。 最近关联规则——基于动态作用域的引用规则。 调用 调用 调用

94 动态作用域 如果非局部环境用最近关联规则来确定，不使用静态域规则，即不在翻译时确定非局部引用的标识符的定义关联。
在程序执行时，当数据对象X被创建作为子程序P的激活的一部分，则X的关联的动态作用域变成所有从P开始调用的子程序关联，X在动态作用域中可见（除非被后面的X定义所覆写）。 这样，子程序激活P的非局部环境包含通往它的完整的子程序激活动态链。 这种非局部环境最麻烦的方面是它可能在P的激活中改变，P的不同激活中可能有不同的X关联。 这样，动态类型检查是需要的。

95 动态作用域：实现 对非局部引用的最近关联规则的实现是直接的，采用子程序激活记录的中心栈来实现。每个子程序的局部环境是其激活记录的一部分。
假设子程序P调用子程序Q，Q再调用R，当R执行时，中心栈如图7.16所示。为了引用非局部X，在栈中查找，从局部环境开始，直至X的最近关联被找到。 最近关联规则的实现代价较高，非局部引用的查找需要时间，同时需要在局部关联表中存放标识符的某些表示，因为X的关联的位置在各个局部表中可能是不同的。从而不可能用基地址＋位移的方式。 如何避免对非局部引用的查找？ 在非局部引用和子程序进入—退出间可以有代价上的权衡。如果非局部引用比子程序进入—退出更为频繁（即使用比修改更频繁），则避免查找是有意义的。

96 动态作用域：实现 执行过程中的活跃引用环境

97 动态作用域：实现 另一种实现方式使用对所有子程序公共的中心表——中心引用环境表。
中心表设置为在程序执行的所有时间内包含所有当前活动的标识符关联，不管其是局部还是非局部。 为了简单化，我们假定在任何子程序中引用的标识符集合可以在翻译的确定，则中心栈初始化为对每个标识符包含一个项，不管标识符出现在其中的不同子程序的数量。 表中每个项包含一个激活标志，指出是否特殊的标识符有一个活动关联。还包含一个指针，指向关联的数据对象。 所有子程序中的引用被导向到该中心表，使用基地址 + 位移模式，因为标识符X的当前关联总是位于中心表的同一位置。

98 动态作用域：实现 每个引用只需要在项中的激活标志被检查，以保证表中的关联当前活动的。使用中心表，我们可达到不需查找而有效地实现非局部引用的目标。 由于在引用环境中的每次变动需要修改中心表，因此，子程序的进入和退出代价很高。当子程序P调用Q，必须修改中心表以反映Q的局部环境。 每一个对应Q的局部标识符的项必须修改以反映新的局部关联。 同时，如旧表项是活动的，还必须存放起来，以便Q退出时重被激活。由于修改的项可能散落在整个中心表中，修改必须逐项进行。退出Q时，恢复工作也需逐项进行。 这样，又需要一个执行时栈来作为存放非激活态关联的隐蔽栈，当退出Q时，栈的顶部关联块被恢复进中心表中适当位置，图7.17给出了一例子。

99 动态作用域：实现 非局部引用的中心环境表

100 静态作用域和块结构 在使用块结构的语言中，非局部引用的处理更为复杂。
由于在一个子程序中某标识符的每次引用是和程序文本中该标识符的定义相关联，即使该标识符不是局部于子程序。 这样，执行中每个子程序的非局部引用环境已经在翻译时由静态作用域规则确定。 实现问题是，保持静态和动态作用域规则间的一致性，使得在程序执行中非局部引用正确地关联相关数据对象。

101 静态作用域和块结构 具有非局部引用的PASCAL过程

102 静态作用域和块结构 主程序、P和Q中均定义了变量X，而R中局部引用X。主程序调用P，P调用Q，Q调用R。
静态规则定义了对X的引用为主程序中X定义，对X的非局部引用的含义是独立于特定的动态调用链。 而最近关联规则将X和P或Q中X相关联（根据R 的调用者）。 静态作用域规则在编译器中的实现是直接的。 当在编译中处理每个子程序定义时，创建声明的局部表并将其附到局部表链上去。 这样在编译R时，编译器将R声明的局部表加到链中（目前只含有主程序定义）。 当R编译结束时，编译器从链中删去的R的局部表。 声明的局部表链表示了子程序定义的静态嵌套，而不是执行中的动态调用链。

103 静态作用域和块结构 在块结构语言的程序执行中，中心栈用于子程序激活记录。每个子程序的局部环境存放在其激活记录中。
右图给出了静态作用域和动态作用域规则间的矛盾。 当R被调用时，如遇到对X的非局部引用，引用操作必须在主程序中查找X的关联，而不是在R的调用者Q中。 然而，简单地沿栈查找，将指向Q中的X关联。 问题在于：栈中的局部表序列表示了子程序激活的动态嵌套（基于执行时调用链），但是，是子程序定义的静态嵌套确定非局部引用环境。

104 静态作用域和块结构 为了完成这个实现，必须在执行中表示静态块结构，使其可用来控制非局部引用。
我们注意到，为了找到关联满足对X的引用，我们查找局部环境表链直到X的一个关联被找到。 然而，局部环境表链不包含所有当前在栈中的局部表，而只是那些表示块或子程序的局部表。 这些块或子程序的定义静态地在程序文本中包含当前子程序定义。 查找仍是沿栈中表进行，但只是那些实际上是引用环境一部分的表。

105 静态作用域和块结构：静态链实现 只需简单地修改栈中的局部环境表，在表头加上一项——静态链指针。
静态链指针总是包含另一个局部表的基地址，局部表表示静态地包含的块或子程序的局部环境。 当然，局部环境表是激活记录的一部分，我们可使用激活记录的基地址。 静态链指针形成了简单引用模式的基础。 为满足对X的引用，我们循CEP得到栈顶的当前引用环境。 如没有X的关联，则沿静态链指针到栈中第二个表，如此继续。

106 静态作用域和块结构：静态链实现 执行时中心栈

107 静态作用域和块结构：静态链实现 虽然似乎需要查找每个静态链接环境直至X被找到，但不一定要这样做。
这是一个相当有效的实现。通常，对声明在K层而使用K+N层的变量的访问需要N次静态链指针的访问。 由于子程序很少嵌套到4—5层深（通常2—3层），n很少大于1—2。 然而，我们可以访问任意正确环境，只通过对静态链指针的一次访问。

108 静态作用域和块结构：静态链实现 静态链技术允许子程序的直接进入和退出。当子程序被调用，其激活记录在栈顶创建，此时需建立合适的静态链指针，以指向栈中的下一个激活记录。退出时仅需从栈中删去激活记录即可，对静态指针没有别的动作。 在子程序进入时如何建立合适的静态链指针？ 如，R定义在主程序中，Q调用R。 当R在执行中进入时，合适的静态链指针被设置到主程序的激活记录。 在调用点，Q的激活记录在栈顶，R的记录被堆在Q之上，那么，如何确定静态链指针是指向主程序？ 标识符R是子程序名，在Q中是非局部引用。 在Q的调用点，可以确定R的静态链指针指向主程序。 此情形好象是R在主程序中定义为局部变量而在Q中非局部引用一样。

109 静态作用域和块结构：Display实现 我们有如下观察： 由此，我们具有了实现有效引用操作的基础。
1、对任意子程序R，当R在执行时，从R的局部表沿栈下降的长度是常量，且简单地等于R定义的静态嵌套深度，而且在执行中是固定的。 2、在这个常量长度的链中，非局部引用总是在链中的同一点被满足。 3、链中非局部引用将被满足的位置可在编译时确定。 由此，我们具有了实现有效引用操作的基础。 我们不需显式地沿静态链查找，只需沿链跳过固定的数的表，然后使用基地址 + 位移计算得到合适的表项。

110 静态作用域和块结构：Display实现 在执行中，我们将标识符表示为对——（链位置、位移）。
这样，在上面例子中，R中X的引用表示为（1、3），1表示沿链下降的第一个表，3表示第三个表项。 在这个实现中，当前静态链在进入每个子程序时，被拷贝到分开的矢量中，称为display。 Display和中心栈分开，经常表示在高速寄存器集中。 在执行中任意点，display包含了和出现在当前被执行的子程序的静态莲中相同的指针序列。 使用display完成引用是特别简单的。 我们在执行中使用稍微修改过的标识符表示，即使用整数对，如：（3，2），3表示从链尾到合适激活记录的步数，2仍然表示位移。

111 静态作用域和块结构：Display实现 现在给定非局部引用（3，10），适当的关联可在两步内得到：
2、计算标识符位置。 基地址+10 通常，这两步可合为一，采用间接取址法。 如display存放在高速寄存器中，则对每个标识符引用，只需一次内存访问。 虽然使用display可使引用简化，但子程序进入和退出却更困难，因为必须修改display以反映当前活动静态链。

112 静态作用域和块结构：Display实现 执行中的中心栈和DISPLAY

113 静态作用域和块结构：局部块中的声明 有的语言，如C，允许语句块中声明局部变量。如： real proc1(parameters) {
int i, j; …/*statements*/ {int k, l; …/*statements*/} {int m, n; {int x; … /*statements*/} {int y; … /*statements*/} }

114 静态作用域和块结构：局部块中的声明 第一眼看去，似乎每个块需要分别的激活记录来存放变量。
然而，在这些块和前面讨论的激活记录间有重要差异。由于过程调用的动态性质，通常我们不能确定哪个过程当前被执行。 这样如上面块每个均表示过程，则包含k的块和包含m的块可能同时被执行，因此，需要分开的激活记录。 然而，在上面例子中，这是不可能的，在变量k的块中就不能在变量m 的块中，从而允许简单的存储策略。

115 静态作用域和块结构：局部块中的声明 在激活记录中的重叠变量存储