3 非局部名字引用

静态数据区：全局变量、静态局部变量

堆：malloc、free 等

没有过程嵌套的静态作用域

如 C 语言

非静态的局部变量的访问：位于栈顶的活动记录，通过基址指针 base_sp 来访问
过程体中的非局部引用、静态局部变量：直接用静态确定的地址（位于静态数据区中的数据）
过程可以作为参数来传递，也可以作为结果来返回
无须访问链

有过程嵌套的静态作用域

例如

sort                1
    readarray       2
    exchange        2
    quicksort       2
        partition   3

右边数字是嵌套深度

访问链反映过程之间的嵌套定义关系
控制链反映过程之间的调用关系

针对访问链的两个关键问题

（1）假定过程 $p$ 的嵌套深度为 $n_p$ ，它引用嵌套深度为 $n_a$ 的变量 $a$ ，且 $n_a\le n_p$ ，如何访问 $a$ 的存储单元？

追踪访问链 $n_p-n_a$ 次，到达 $a$ 的声明所在过程的活动记录
$p$ 访问 $a$ 时， $a$ 的地址由二元组（ $n_p-n_a$ ， $a$ 在活动记录中的偏移）表示

（2）假定 $p$ 调用过程 $x$ ，分别考虑 $n_p<n_x$ 和 $n_p\ge n_x$ 的情况。

$n_p<n_x$ 时， $x$ 肯定声明在 $p$ 中。调用时， $x$ 的访问链需要指向 $p$ 的访问链
$n_p\ge n_x$ 时， $p$ 和 $x$ 有公共的外围过程。此时追踪访问链 $n_p-n_x+1$ 次，到达静态包围 $x$ 和 $p$ 且离他们最近的那个过程的最新活动记录。调用时， $x$ 的访问链就指向这个活动记录

过程作为参数

过程 $f$ 作为参数传递时，它的起始地址连同它的访问链一起传递

调用者调用过程 $f$ 时，用传递过来的访问链来建立过程 $f$ 的访问链

过程作为返回值

如果允许一个函数的返回值是函数，那么有可能出现作为返回值的函数执行时，需访问的非局部数据已经不复存在

C 语言的做法

（1）不能嵌套定义

（2）当前激活的函数要访问的数据有两种情况

非静态局部变量（包括形式参数）：分配在活动记录栈顶的那个活动记录中

外部变量（包括定义在其它源文件之中的外部变量）和静态的局部变量：都分配在静态数据区

（3）允许函数（的指针）作为返回值

其他语言的一种做法：闭包
function add(x) {
    return function(y) {
        return x + y;
    }
}

var add3 = add(3); // add3 是闭包对象，包含函数及环境{x=3}
解决了过程作为返回值时要面对的问题。

过程作为参数时也存在相似的问题。

动态作用域

静态、动态作用域的对比
def main(): # 这不是python，只是为了方便叙述
    def show():
        print(r)
    def small():
        r = 0.125
        show()
    r = 0.25
    show()
    small()
静态作用域时：

show 在 main 中定义，show 中访问的 r 是 main 中定义的 r

输出 2 个 0.25

动态作用域时：

main 中调用的 show 访问的 r 是 main 中定义的

small 中调用的 show 访问的 r 是 small 中定义的

输出 0.25，0.125

实现动态作用域的方法

深访问

概念上，如果访问链指向的活动记录和控制链指向的活动记录一样，那就实现了动态作用域。因此一种简单的实现是省略访问链，并用控制链搜索运行栈，寻找包含所需非局部名字的第一个活动记录。

深访问的意思是，搜索可能要深入运行栈中，搜索的深度可能取决于程序的输入，编译时无法确定。

浅访问

为每个名字在静态数据区保存它的当前值
当过程 $p$ 的新活动出现时， $p$ 的局部名字 $n$ 使用在静态数据区分配给 $n$ 的存储单元。 $n$ 的先前值保存在 $p$ 的活动记录中，当 $p$ 的活动结束时再恢复

深访问对非局部名字需要较长的访问时间，但是它在活动的开始和结束处没有额外开销；浅访问则相反，它可以直接访问非局部名字，但在活动的开始和结束处需要花费时间来维护这些值。当函数作为参数传递和作为结果返回时，深访问可以较直截了当地实现。

参数传递

值调用

特点：实参的右值传给被调用过程

实现：

把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中
调用过程计算实参，并把其右值放入被调用过程形参的存储单元中

引用调用

特点：实参的左值传给被调用过程

实现：

把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中（和值调用一样）
调用过程计算实参，把实参的左值放入被调用过程形参的存储单元（和值调用几乎一样）
在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参

换名调用（宏展开）

特点：用实参表达式对形参进行正文替换，然后再执行

换名调用比较复杂，因此是一种不再受欢迎的机制。

swap(i, a[i])
--> temp = i; i = a[i]; a[i] = temp;
                        |--> 已经不是之前的a[i]位置了

本文阅读量