转载

PL真有意思（三）：名字、作用域和约束

这两篇写了词法分析和语法分析，比较偏向实践。这一篇来看一下语言设计里一个比较重要的部分：名字。在大部分语言里，名字就是标识符，如果从抽象层面来看名字就是对更低一级的内存之类的概念的一层抽象。但是名字还有其它相关的比如它的约束时间和生存周期等等

约束时间

约束就是两个东西之间的一种关联，例如一个名字和它所命名的事物，约束时间就是指创建约束的时间。有关的约束可以在许多不同的时间作出

语言设计时
语言实现时
编写程序时
编译时
链接时
装入时
运行时

这就是为什么基于编译的语言实现通常会比基于解释器的语言的实现更高效的原因，因为基于编译的语言在更早的时候就做了约束，比如对于全局变量在编译时就已经确定了它在内存中的布局了

对象生存期和存储管理

在名字和它们所引用的对象的约束之间有几个关键事件：

对象的创建
约束的创建
对变量、子程序、类型等的引用，所有这些都使用了约束
对可能暂时无法使用的约束进行失活或者重新约束
约束的撤销
对象的撤销

对象的生存期和存储分配机制有关

静态对象被赋予一个绝对地址，这个地址在程序的整个执行过程中都保持不变
栈对象按照后进先出的方式分配和释放，通常与子程序的调用和退出同时进行
堆对象可以在任意时刻分配或者释放，它们要求更通用的存储管理算法

静态分配

全局变量是静态对象最显而易见的例子，还有构成程序的机器语言翻译结果的那些指令，也可以看作是静态分配对象。

还有像每次调用函数都会保持相同的值的局部变量也是静态分配的。对于数值和字符串这些常量也是静态分配。

还有用来支持运行时的各种程序，比如废料收集和异常处理等等也可以看作是静态分配

基于栈的分配

如果一种语言允许递归，那么局部变量就不能使用静态分配的方式了，因为在同一时刻，一个局部变量存在的实例个数是不确定的

所以一般对于子程序，都用栈来保存它相关的变量信息。在运行时，一个子程序的每个实例都在栈中有一个相应的栈帧，保存着它的参数、返回值、局部变量和一些簿记信息

基于堆的分配

堆是一块存储区域，其中的子存储块可以在任意时间分配与释放。因为堆具有它的动态性，所以就需要对堆空间进行严格的管理。许多存储管理算法都维护着堆中当前尚未使用的存储块的一个链接表，称为自由表。

初始时这个表只有一个块，就是整个堆，每当遇到分配请求时，算法就在表中查找一个大小适当的块。所以当请求次数增多，就会出现碎片问题，也需要相应的解决

所以有废料收集的语言其实就是对堆的管理

作用域作用

一个约束起作用的那一段程序正文区域，称为这个约束的作用域。

现在大多数语言使用的都是静态作用域，也就是在编译时就确定了。也有少数语言使用动态作用域，它们的约束需要等到运行时的执行流才能确定

静态作用域

在使用静态作用域的语言，也叫作词法作用域。一般当前的约束就是程序中包围着一个给定点的最近的，其中有与该名字匹配的声明的那个快中建立的那个约束。比如C语言在进入子程序时，如果局部变量和全局变量，那么当前的约束就是与局部变量关联，直到退出子程序才撤销这个约束

但是有的语言提供了一种可以提供约束的生存期的机制，比如Fortran的save和C的static

嵌套子程序

有许多语言允许一个子程序嵌套在另一个子程序的。这样有关约束的定义通常来说都是首先用这个名字在当前、最内层的作用域中查找相应的声明，如果找不到就直接到更外围的作用域查找当前的约束，直到到达全局作用域，否则就发生一个错误

访问非局部变量

上面提到的访问外围作用域的变量，但是当前子程序只能访问到当前的栈帧，所以就需要一个调用帧链来让当前的作用域访问到外围作用，通过调用顺序形成一个静态链

声明的顺序

关于约束还有一个问题，就是在同一作用域里，先声明的名字是否能使用在此之后的声明

在Pascal里有这样两条规则：

修改变量要求名字在使用之前就进行声明
但是当前声明的作用域是整个程序块

所以在这两个的相互作用下，会造成一个让人吃惊的问题

const N = 10;

procedure foo;
const
  M = N; (*静态语义错误*)
  N = 20;

但是在C、C++和Java等语言就不会出现这个问题，它们都规定标识符的作用域不是整个块，而是从其声明到块结束的那一部分

并且C++和Java还进一步放宽了规则，免除了使用之前必须声明的要求

模块

恰当模块化的代码可以减少程序员的思维负担，因为它最大限度的减少了理解系统的任意给定部分时所需的信息量。在设计良好的程序中，模块之间的接口应尽可能的小，所有可能改变的设计决策都隐藏在某个模块里。

模块作为抽象

模块可以将一组对象（如子程序、变量、类型）封装起来。使得：

这些内部的对象相互可见
但是外部对象和内部对象，除非显示的导入，否则都是不可见的

模块作为管理器

模块使我们很容易的创建各种抽象，但是如果需要多个栈的实例，那么就需要一个让模块成为一个类型的管理器。这种管理器组织方式一般都是要求在模块中增加创建/初始化函数，并给每一个函数增加一个用于描述被操作的实例

模块类型

对于像这种多实例的问题，除了管理器，在许多语言里的解决方法都是可以将模块看作是类型。当模块是类型的时候，就可以将当前的方法认为是属于这个类型的，简单来说就是调用方法变化了

push(A, x) -> A.push(x)

本质上的实现区别不大

面向对象

在更面向对象里的方法里，可以把类看作是一种扩充了一种继承机制的模块类型。继承机制鼓励其中所有操作都被看作是从属于对象的，并且新的对象可以从现有对象继承大部分的操作，而不需要为这些操作重写代码。

类的概念最早应该是起源于Simula-67，像后来的C++，Java和C#中的类的思想也都起源于它。类也是像Python和Ruby这些脚本语言的核心概念

从模块到模块类型再到类都是有其思想基础，但是最初都是为了更好的数据抽象。但是即使有了类也不能完全取代模块，所以许多语言都提供了面向对象和模块的机制

动态作用域

在使用动态作用域的语言中，名字与对象间的约束依赖于运行时的控制流，特别是依赖子程序的调用顺序

n : integer

procedure first
  n := 1

procedure second
  n : integer
  first()

n := 2
if read_integer() > 0
  second()
else
  first()
write_integer()

这里最后的输出结果完全取决于read_integer读入的数字的正负，如果为正，输出就为2，否则就打印一个1

作用域的实现

为了跟踪静态作用域程序中的哥哥名字，编译器需要依靠一个叫做符号表的数据结构。从本质上看，符号表就是一个记录名字和它已知信息的映射关系的字典，但是由于作用域规则，所以还需要更强大的数据结构。像之前那个写编译器系列的符号表就是使用哈希表加上同一层作用域链表来实现的

而对于动态作用域来说就需要在运行时执行一些操作

作用域中名字的含义

别名

在基于指针的数据结构使用别名是很自然的情况，但是使用别名可能会导致编译器难以优化或者造成像悬空引用的问题，所以需要谨慎使用

重载

在大多数语言中都或多或少的提供了重载机制，比如C语言中（+）可以被用在整数类型也可以用在浮点数类型，还有Java中的String类型也支持(+)运算发

要在编译器的符号表中处理重载问题，就需要安排查找程序根据当前的上下文环境返回一个有意义的符号

比如C++、Java和C#中的类方法重载都可以根据当前的参数类型和数量来判断使用哪个符号

内部运算符的重载

C++、C#和Haskell都支持用户定义的类型重载内部的算术运算符，在C++和C#的内部实现中通常是将A+B看作是operator+(A, B)的语法糖

多态性

对于名字，除了重载还有两个重要的概念：强制和多态。这三个概念都用于在某些环境中将不同类型的参数传给一个特定名字的子程序

强制是编译器为了满足外围环境要求，自动将某类型转换为另一类型的值的操作

所以在C中，定义一个计算整数或者浮点数两个值中的最小值的函数

double min(double x, double y);

只要浮点数至少有整数那么多有效二进制位，那么结果就一定会是正确的。因为编译器会对int类型强制转换为double类型

这是强制提供的方法，但是多态性提供的是，它使同一个子程序可以不加转换的接受多种类型的参数。要使这个概念有意义，那么这多种类型肯定要具有共同的特性

显式的参数多态性就叫做泛型，像Ada、C++、Clu、Java和C#都支持泛型机制，像刚才的例子就可以在Ada中用泛型来实现

generic
  type T is private;
  with function "<" (x, y : T) return Boolean;
function min(x, y : T) return T;

function min(x, y : T) return T is
begin
  if x < y then return x;
  else return y;
  end if;
end min

function string_min is new min(string, "<")
function date_min is new min(date, date_precedes);

像List和ML中就可以直接写

(define min (lambda (a b) (if (< a b) a b)))

其中有关类型的任何细节都由解释器处理

引用环境的约束

提到引用环境的约束就有两种方式：浅约束和深约束

推迟到调用时建立约束的方式浅约束。一般动态作用域的语言默认是浅约束，当然动态作用域和深约束也是可以组合到一起的。

执行时依然使用传递时的引用环境，而非执行时的引用环境。那么这种规则称为深约束，一般静态作用域的语言默认是深约束

闭包

为了实现神约束，需要创建引用环境的一种显示表示形式，并将它与对有关子程序的引用捆绑在一起，这样的捆绑叫做闭包

总而言之，如果子程序可以被当作参数传递，那么它的引用环境一样也会被传递过去

一级值和非受限生存期

一般而言，在语言中，如果一个值可以赋值给变量、可以当作参数传递、可以从子程序返回，那么它被称为具有一级状态（和我们在js中说函数是一等公民一个含义）。大多数的语言中数据对象都是一级状态。二级状态是只能当作参数传递；三级值则是连参数也不能做，比如C#中一些+-*/等符号。

在一级子程序会出现一个复杂性，就是它的生存期可能持续到这个子程序的作用域的执行期外。为了避免这一问题，大部分函数式语言都表示局部变量具有非受限的生命周期，它们的生命周期无限延长，直到GC能证明这些对象再也不使用了才会撤销。那么不撤销带来的问题就是这些子程序的存储分配基于栈帧是不行了，只能是基于堆来分配管理。为了维持能基于栈的分配，有些语言会限制一级子程序的能力，比如C++，C#，都是不允许子程序嵌套，也就从根本上不会存在闭包带来的悬空引用问题。