名字、绑定和作用域
1.程序设计语言 ——实践之路
Michael L,Scott,Programming Languages Pragmatics,
Morgan Kaufmann,2000,2005）
中文版由裘宗燕译,电子工业出版社出版,2005
2.编译原理及实践,Kenneth C.Louden.机械工业出版社,1997
本节要点
名字、绑定、静态绑定、动态绑定
对象的生存期
典型的存储分配方式
作用域名字和绑定
名字
助记符，如：标识符，符号（＋）
是程序语言里最基本的抽象机制
用来指称程序中出现的各种,东西,,变量、常量、过程 /函数、
结构 /记录的成分、类型等等。
绑定（ binding）是两个东西之间的关联，如一个名字和它所指的东西。
注：不是所有的数据都有名字，例,C,Ada 95和 Fortran 90用指针来引用动态存储；类似的,Java和 C#用引用来间接访问。
声明和定义名字与事物（包括程序对象）之间的约束关系由定义或声明建立。
一个定义或声明引进一个名字，被定义 /声明的事物及相关属性就是该名字的意义。这个声明 /定义建立了名字与相关事物和属性之间的约束关系。
例,C 声明 const double x = 3.876;
将名字 x 约束于一个 double 类型的变量,const 和值
3.876 为其属性例,C 声明 int fun (int,double);
使名字 fun 约束于函数类型 int× double → int。这个函数的定义应该具有这种类型，它的使用必须符合这一类型。
绑定时间 (约束时间）
绑定时间指一个绑定的活跃时间。
与高级语言和程序有关的重要时间概念：
语言设计时。如：程序结构、类型。
语言实现时。如,I/O,算术溢出，类型等价
编程时。如：算法和名字
编译时。数据对象的布局，从程序中高级结构到机器代码的映射。
连接时。整个程序在内存的布局，如：静态数据对象分配，跨模块对象约束，库对象约束
装载时。物理地址的选择，完成虚地址到实地址的映射
运行时。变量的值绑定，运行时的其他事项静态绑定和动态绑定
静态绑定：在程序运行前建立的约束
动态绑定：在程序执行过程中建立的约束
哪些特征能静态绑定，或者必须动态绑定，不同语言之间差别很大
一般而言，静态绑定效率高、意义清晰，动态绑定更灵活
静态绑定的语言一般是编译执行
动态绑定的语言一般是解释执行
下面重点讨论变量的绑定，以下用对象表示任何有名字的东西。
生存期和作用域
绑定的生存期是一个绑定从创建到销毁的时间。
创建和销毁可能伴有特定的动作（例：常量创建时需要给定值）
绑定的作用域是一个绑定在程序中活跃的文本区域。
作用域本身指程序中没有绑定被销毁的一段最大的程序区域。 （后面再讨论）
常见作业域
子程序 (函数和过程）
模块
模块类型
类
块子程序
在大多数带子程序的语言中，子程序入口打开一个新的作用域。
在子程序入口，为局部变量创建绑定，使被重复声明的全局变量的绑定无效，然后建立到局部变量的索引。
在子程序出口，销毁局部变量的绑定，激活那些被变无效的非局部变量的绑定。
对象的创建和销毁
对象的创建（ creation）可能是
静态创建，包括编译时完成，连接时完成，或者装载时完成
动态创建，运行中创建
对象的销毁可能在
运行中完成
程序终止时完成
生存期跨越程序运行期的对象称为永久（ persistent）
对象静态对象和非静态对象
静态对象：静态创建，程序终止时销毁。
非静态对象：程序运行中创建和销毁。
Fortran 中的所有变量都是静态对象。
C 中的外部变量（用 extern声明）和局部 static 变量是静态对象，自动变量（用 auto声明或默认）是非静态对象。
创建和初始化动作完全可能不同时做。例如 C++ 的局部 static 变量是静态创建的，但在执行首次进入变量所在函数时进行初始化。
生存的对象通常有一个固定标识，最常见的就是用对象的存储位置表示。对象总占据着一块存储空间，在其中保存自己的,值,。
因此，对象创建有时也称为分配（ allocation）
存储位置 值对象：生存期
静态创建的对象在程序执行过程中始终存在，生存期是程序整个执行过程
例,C语言的全局变量
动态创建的对象具有较短的生存期
例,C的局部自动变量，生存期是它所在的函数的执行期间
程序对象创建时可能需要执行一些动作，销毁时也可能需要执行一些动作
例,C 标准函数 fopen 创建一个 FILE 对象，建立文件链接（执行一些操作系统动作），分配数据缓冲区和附属结构。该对象生存到相应的 fclose 操作，销毁时需要清理缓冲区，释放相关存储，
释放文件链接
C++ 等语言允许程序员为对象的创建和销毁定义特定的动作
（构造函数和析构函数）
典型的存储分配方式
创建对象首先需要为其存储分配。典型的存储分配有三种情况：
静态分配：给定一个绝对地址，执行中保持不变
栈分配：如果对象具有后创建先销毁的性质，可采用栈分配,如过程的调用和返回
堆分配：不能采用上述方式分配的对象，只能在堆里分配
程序的存储区通常分为三部分：静态区，栈区（程序运行栈）
和堆区（动态管理区），分别对应上面的三种分配
静态区可能还分为只读区和读写区（依赖于操作系统支持）：
代码放在只读区，常量对象也可能放在只读区
静态分配的变量放在静态区里的可读写区问题
例：试判断下面的 c程序是否正确？
char *p = "a string";
*p = 'A';
答,C语言不允许修改字符串常量,因此上面程序是错误的，
可能导致程序崩溃 ！！
调用序列
运行时环境依靠调用序列来进行维护。
调用序列 (calling sequence)：当调用过程或函数时，
运行时环境必须发生的操作序列。
包括：过程活动记录的存储器分配、计算和保存参数，
必要的寄存器的保存和设置，放置可由调用程序访问的返回值，以及活动记录存储器的释放。
调用时执行的操作称为调用序列 (call sequence)。返回时执行的操作称为返回序列 (return sequence)。
哪些对象可以静态分配能静态确定所有性质（包括大小）的对象才能静态分配。常见的有：
全局变量
有些语言没有全局变量，如 Java
子程序代码（翻译结果）
需要建立对象的常量，包括：
一些全局的常量
字符串和浮点数（可能还有一些整数）
局部静态变量。如 C 函数的 static 变量,C++/Java 类的 static 数据成员
编译系统可能在静态区建立一些支持程序运行所需的静态数据结构，
例如为支持动态检查和执行的表格（例如数组的维数和上下界越界检 查,OO 语言里类的虚表），支持存储管理和异常处理的数据结构等子程序代码、常量、字符串对象有可能分配在只读区域，修改它们将产生动态运行错误（相关检查通常需要操作系统支持）
生存期：静态分配无递归的语言，局部变量可以静态分配在 Fortran 90 之前,Fortran 的许多实现里，所有对象都静态分配，程序运行中没有堆栈和堆区
Fortran 不允许子程序的递归调用，子程序里的局部变量只需要一份
程序里所有的变量访问都编译为直接的地址访问
程序运行前完成所有对象的创建，运行中不做任何对象分配和释放工作这些情况使 Fortran 程序具有很高的效率
Fortran 不支持下列程序设计技术：
递归
变长度数组或字符串
动态存储分配和动态数据结构（如链表），等等
Fortran 90 加入了递归和动态存储分配，语言的实现模型必须改变静态分配例：程序清单 1 一个 FORTRAN77示例程序
PROGRAM TEST
COMMON MAXIZE
INTEGER MAXSIZE
REAL TABLE(10),TEMP
MAXSIZE=10
READ *,TABLE(1),TABLE(2),TABLE(3)
CALL QUADMEAN(TABLE,3,TEMP)
PRINT *,TEMP
END
静态分配举例
SUBROTINE QUADMEAN(A,SIZE,
QMEAN)
COMMON MAXSIZE
INTEGER MAXSIZE,SIZE
REAL A(SIZE),QMEAN,TEMP
INTEGER K
TEMP=0.0
IF ((SIZE,GT,MAXSIZE),OR,
(SIZE,LT,1)) GOTO 99
DO 10 K=1,SIZE
TEMP=TEMP+A(K)*A(K)
10 CONTINUE
99 QMEAN=SQRT(TEMP/SIZE)
RETURN
END
可变数组
MAXSIZE
TABLE (1)
(2)
…
(10)
TEMP
3
A
SIZE
QMEAN
返回地址
TEMP
K
全局区主过程的活动记录过程 QUADMEAN
的活动记录图 程序清单 1中程序的运行时环境生存期：栈分配在允许递归的语言里，子程序里的局部对象不能静态分配
一个局部对象可能同时存在多个活动的副本（可能存在递归）
由于子程序调用有后进先出性质，因此其局部对象可以采用堆栈分配栈的分配和使用
编译时为每个子程序安排一个栈框架，算出各个局部对象所需存储量，
在框架里为它们安排位置，算出各对象相对于框架起始位置的偏移量
运行进入一个子程序时，在栈里为这个子程序的框架分配空间
设置框架指针（通常是一个寄存器）指向当前子程序的框架
子程序局部对象的访问都通过框架指针加偏移量进行子程序结束时释放对应的栈框架，所有局部对象都销毁（有些语言在销毁前执行一些特定销毁动作。如 C++ 可以定义销毁动作）
生存期：栈分配例 2 利用 Euclid算法的简单递归算法，
计算两个非负整数的最大公约数。
程序清单 2 例 2的 C代码
#include <stdio.h>
int x,y;
int gcd(int u,int v)
{ if (v==0) return u;
else return gcd(v,u%v);
}
main()
{ scanf(“%d%d”,&x,&y);
printf(“%d\n”,gcd(x,y));
return 0;
}
假设输入 15、
10，则 main
调用
gcd(15,10)。
它递归调用
gcd(10,5)。
它再递归调用 gcd(5,0)。
它返回 5。
第 3个调用时的环境如图 2
所示。
x:15
y:10
u:15
v:10
控制链返回地址
u:10
v:5
控制链返回地址
u:5
v:0
控制链返回地址自由空间
fp
sp
全局／静态区域
main的活动记录第一次调用 gcd时的活动记录第二次调用 gcd时的活动记录第三次调用 gcd时的活动记录栈的生长方向图 2 例 2的基于栈的环境在允许嵌套定义的语言中，还要加上静态链（访问链）来描述一个过程的定义环境。
生存期：堆分配只要对象的生存期有后创建先销毁的性质，就可以在运行栈里分配。
没有这种性质的对象只能在堆里分配。
堆是一块存储区域，其中的存储块可以在任何时间分配和释放。
堆管理就是常说的,动态存储管理,。
动态存储管理子系统是程序运行系统的一部分，它管理一片存储区。
如果有存储申请，管理系统就从当前可用的空闲区里分配一块；
如果无法满足要求，管理系统可能向操作系统申请新存储块，或者直接返回分配失败的信息
C 标准库的 malloc,calloc,Pascal 的 new 都是调用动态存管系统的界面操作。
堆的一个场景：
堆存储分配算法
维护堆中当前尚未使用的存储块的一个链表，称为 自由表 。
堆存储的常用算法
分配代价与自由块的数目成线性关系的
最先适配 算法：选择表中第一个能满足请求的足够大的块。
最佳适配 算法：选择表中能满足请求的最小的块。
如块比请求大得多，两算法都将块划为两块，不用的返回
分配代价为常数级
将不同大小的块分别维护在不同的自由表 (存储池）中，将分配请求向上归约到一种块的大小，并从相应的表中进行划分。
动态调整的算法：伙伴系统和斐波那契堆堆存储分配算法
伙伴系统：标准块的大小是 2的幂。如果需要一个 2K的块而没有，则把一个 2k+1的块一分为二，一半用于满足本次需求，一半放在第 K个自由表中。在释放时，如果它的伙伴（创建时与它分开的另一半）也是自由的，则合并它们。
斐不那契堆与之类似，只不过标准块的大小采用的是斐波那契数。
垃圾回收机制
堆的存储空间释放分为显式释放和自动回收两种
一些语言提供了动态存储块的释放机制，程序员可以根据需要释放以前分配的块。存管系统回收存储块，将其恢复为空闲空间。
如,C语言的 fclose和 free。
回收时通常需要合并释放块和相邻空闲块，以便满足以后的大块请求。
人工释放的问题在于确定正确的释放时刻。
在复杂程序里弄清合适时刻可能成为程序员的巨大负担。如果程序设计得不好，就可能无法确定何时释放某对象。堆分配对象的使用错误是复杂程序中一类最常见错误，不但很容易出现，而且很难排除。
垃圾回收机制自动释放技术方面，目前主要有两种想法：
把堆对象约束于适当的栈对象，借助栈对象的销毁自动释放堆对象
设计某种自动机制，自动回收不再有用的堆分配块（ garbage
collection）
C语言实际没有垃圾回收机制，一切依赖程序员和操作系统。
C++语言在类的析构函数中提供垃圾回收，由程序员决定释放那些资源，当程序调用某个类的析构函数时，垃圾回收工作执行并完成。
Java则提供了独立的垃圾回收机制，无需程序员介入，由 Java虚拟机来决定何时进行垃圾回收。当然程序员在一定情况下可以强制垃圾 回收机制立即工作，方法是调用 system.gc下面的几个方法 。
垃圾回收机制垃圾回收（ GC）技术起源于 Lisp，最早是由
McCarthy 等为实现 Lisp 而开发的。
垃圾回收的主要技术：
标记 -清扫式：通过引用关系标出堆里全部的活跃对象，收集其余对象。
复制式：把活跃对象及其连接关系复制到另一存储区，原区全部收回。
分代式：复制式的改进，利用对象的生存特性提高 GC效率。
分代式垃圾回收
目前客户端虚拟机垃圾回收技术的主流,Java和,Net都采用
分代假设
弱分代假设：大多数对象在年轻时死亡（广泛成立）
强分代假设：越老的对象越不可能死亡（不普遍成立）
分代式收集策略
将对象按照年龄存放到堆中的不同区域（分代），年轻的分代被收集频率高，年老的则收集频率低。
垃圾回收机制
GC 一直受到实际程序员的排斥，认为其（时间和空间）开销太大，可能导致程序执行的时间特征无法预期。典型：
C++ 设计者很反对垃圾回收。
近年，由于：
处理器速度提高，内存、垃圾回收的开销已经不是大问题
系统开发中良好正确地管理存储，已经成为程序员最大的负担之一
OO 的广泛应用，没有垃圾回收，开发 OO 程序的代价会大大提高最新的程序语言都提供了自动垃圾回收。
作用域
定义（声明）建立名字与对象之间的约束，在存续期间固定不变
约束在源程序里的作用范围称为该约束的作用域
（ scope），也说是这个定义或声明的作用域
作用域：解决由名字确定程序对象的问题
例,C 局部变量在其定义所在的复合语句里可用（从定义位置开始）
作业域类型
静态作业域（词法作业域）
约束在编译时确定，大多数语言采用，如,C，
Ada
在允许子程序嵌套的语言中，通常采用最近嵌套原则，如,pascal
动态作业域
约束依赖于程序的执行，如,Lisp
static vs dynamic scope rules
例：试分别给出下列程序在静态和动态作用域的输出。
int a
proc first:
a,= 1
proc second:
int a
first()
a,= 2; second(); write(a)
静态作业域,1
动态作用域,2
一个动态作用域的问题引入动态作用域的原因可能是因为它容易让解释器弄清楚名字的含义，但是它的运行时代价高，也容易让程序难以理解。
例：判断下列程序是否能够正常工作？
作用域单位与语言
最简单的作业域是 BASIC，只有一个全局作业域。
早期 Fortran 的作用域结构很简单，只区分全局变量和局部变量。全局变量放在 COMMON块中。
后来人们认识到信息局部化的重要性，慢慢地引进了许多作用域单位。
Algol 60 引进块（ block）结构作为基本作用域单位，允许任意嵌套的局部作用域，子程序被看作是是有名字可调用的块。
现在一般语言都以子程序（过程 /函数）作为作用域单位，一些语言允许子程序体内部的嵌套作用域（如 C 的复合语句）。
其他作用域单位：
结构 /记录的声明,OO语言里的类定义（声明）
模块结构（如 C++ 的名字空间,Ada 的包）
其他，如 C 源文件是一种作用域单位（ static 外部函数和变量的作用域）
学习语言时，需要弄清语言的作用域单位。
作用域单位不同语言对于作用域单位的规定不同
一些语言有全局作用域，供定义全局的标识符 /对象约束。除全局作用域外的其他作用域都是局部的
C 语言的全局作用域里可以定义 /声明变量、函数等。函数只允许定义在全局作用域里（不允许函数的嵌套定义）
C 语言的局部作用域是复合语句（函数体也是复合语句）。 C++ 对 C
的作用域做了许多扩充
在 Java 语言的全局作用域里只能定义类，其他实体都只能在局部作用域里定义
Fortran 只有全局作用域和子程序作用域，子程序内部没有嵌套作用域
Basic（老的）只有一个全局作用域，所有变量约束都在一个作用域里。
定义在子程序里的变量也具有全局作用域（难以编写大程序）
作用域作用域：冲突和嵌套通常规定：
在一个作用域里同一个名字不能有多个约束（名字冲突）
不同作用域里的名字相互无关作用域可能嵌套,局部作用域位于全局作用域里，局部作用域里可能还有内部的作用域。
同一名字的不同定义有可能出现作用域重叠的情况。此时就出现了作用域里的,空洞,现象（见图）
内层的定义,遮蔽,外层的定义为了程序容易理解，应尽量避免同名对象的作用域嵌套
int n;
int p (int n) {
double x;
… n … x …
}
int main () {
int x; double y;
… n … x … y …
if (…) {
int n = 3;
… n … x … y …
for (… …) {
int n; int y;
… n … x … y …
}
… n … x … y …
}
… n … x … y …
}
作用域：嵌套在作用域空洞里，（被遮蔽的）外层定义的约束不可见，直接写出一个名字，总是表示当时的最内层约束。
为了编程方便，一些语言提供了,带修饰的,名字形式，通过名字的前缀修饰指定对外层（定义）约束的访问（有些语言的机制有限制）。
例,C++ 的,,是作用域解析运算符，可以用,:nm 的形式表示引用全局定义，用 cn::nm 的方式引用特定 namespace
或者类里的定义。
在 Ada 里，每个块（ block）都可以命名，利用块名作为前缀，可以引用外围块定义的约束（就像引用结构 /记录的成员）。
静态和动态作用域规则
作用域规则（ Scope rule | Static,
Dynamic）：规定在程序中任一特定位置，
从一个名字确定与之约束的对象的方法。
局部定义的约束容易确定，关键是非局部定义（非局部约束的）的名字
静态作用域规则：非局部名字的约束由名字出现位置的静态正文环境确定
动态作用域规则：非局部名字的约束由动态运行环境确定
常规语言都采用静态作用域规则，函数 f
中非局部的 y 约束于函数的静态环境里的
y
一些函数式语言采用动态约束规则。
子程序中非局部变量的静态约束，语义清晰，但实现比较复杂
int y = 3;
#define f(x) \
printf("%d",x+y)
...
{
int y = 4;
f(2);
...,..
}
作用域：实例不同语言采用的作用域设计可能不同，每个语言有一套规定
Pascal 语言：
program 作用域（类似全局作用域）
允许任意嵌套的子程序（函数 /过程）作用域
只有子程序是局部的作用域单位
C 语言：
全局的外部作用域
子程序定义的局部作用域（不允许嵌套定义的子程序）
子程序里任意嵌套的复合语句作用域
文件为单位的全局 static 作用域（只是为了信息的局部化）
作用域：实例
C++ 语言
C 语言的各种作用域
类定义形成的作用域
继承关系形成的作用域嵌套
方法的作用域嵌套在类作用域里
namespace 定义的模块作用域
Java 语言
全局作用域里只能定义类（全局作用域里没有对象名）
类定义形成作用域
方法作用域嵌套在类作用域里
package 形成的模块作用域作用域举例（ 1）
Pascal says the scope of an identifier is its entire block,excluding
sub-blocks in which the identifier is reclared,Within its block,the
identifier must be declared before it is used,Consider this:
const A = 10;
,..
procedure P;
const
B = A;
,..
A = 15;
Pascal rules say the second declaration of A covers all of P,so
the declaration of B refers to A before it is declared,Where should
you report the error?
作用域举例（ 2）
const foo = 10;
,..
procedure P1;
,..
procedure P2;
var A,integer;
begin
,..
A = foo; {illegal,because of dec,below!}
,..
end {P2};
,..
procedure foo;
作用域：细节一个定义 /声明的作用域，常见的有两种规定：
定义的作用域从定义出现的位置到当前作用域结束
定义的作用域包括整个当前作用域两个例子：
int n = 2;
int f (…) {
int n = n+1,m = n+1;
… …
}
C：作用域从声明结束点开始
C++：类成员的作用域是整个类定义语言对于声明的作用域的范围都有明确规定，详见语言手册。
int n = 2;
class C {
int f() { n++; }
… …
int n;
}
作用域和可见性
作用域进入和退出的特殊描述方式：
,运算符（许多语言）
:,运算符（ C++ 等面向对象语言）
Pascal 和 VB的 with 语句其他实体：定义和使用程序里的命名实体还很多，例如类型、标号。
类型通常只在静态处理过程中有效，采用通用的静态作用域规则。
类型定义也可能由于嵌套作用域里的重新定义而被覆盖。
标号，标明代码中的一个位置，作为 goto 的目标。
有些语言里，标号的作用域有特殊规定。
C 语言的标号，作用域是整个函数，允许向前或向后跳到标号。允许跳入跳出嵌套的复合语句、内层控制结构（对于由跳入位置引起的语义不清情况，语言没有定义）
Fortran 标号的作用域是整个子程序。存在与 C 语言类似的问题
Pascal 标号需要首先声明，用无符号的整数表示，其作用域是定义所在的整个子程序（包括嵌套定义的子程序）。不允许转入嵌套的控制结构，但允许从内层子程序里跳回外层子程序（非局部转跳）
名字分类程序里存在多种命名的事物（包括命名对象、类型、结构的成分名，标号等等），
有些语言对名字做了某种分类。在同一作用域里，属于不同类别的名字互不冲突（允许不同类别的同名事物）。
一般规定（在一个作用域里）同类事物的名字不能冲突。
例,C 语言规定了三个名字类（称为,名字空间,）
标号名
struct/union/enum 标志
变量名、函数名、类型名,typedef 名、枚举常量名
每个结构或者联合声明是一个,名字空间,（包含各成分名）
规定程序里的名字分属不同类别，要求语言的实现能区分它们。
采用怎样的规定，与语言里各种特征的设计有关。
1.程序设计语言 ——实践之路
Michael L,Scott,Programming Languages Pragmatics,
Morgan Kaufmann,2000,2005）
中文版由裘宗燕译,电子工业出版社出版,2005
2.编译原理及实践,Kenneth C.Louden.机械工业出版社,1997
本节要点
名字、绑定、静态绑定、动态绑定
对象的生存期
典型的存储分配方式
作用域名字和绑定
名字
助记符，如：标识符，符号（＋）
是程序语言里最基本的抽象机制
用来指称程序中出现的各种,东西,,变量、常量、过程 /函数、
结构 /记录的成分、类型等等。
绑定（ binding）是两个东西之间的关联，如一个名字和它所指的东西。
注：不是所有的数据都有名字，例,C,Ada 95和 Fortran 90用指针来引用动态存储；类似的,Java和 C#用引用来间接访问。
声明和定义名字与事物（包括程序对象）之间的约束关系由定义或声明建立。
一个定义或声明引进一个名字，被定义 /声明的事物及相关属性就是该名字的意义。这个声明 /定义建立了名字与相关事物和属性之间的约束关系。
例,C 声明 const double x = 3.876;
将名字 x 约束于一个 double 类型的变量,const 和值
3.876 为其属性例,C 声明 int fun (int,double);
使名字 fun 约束于函数类型 int× double → int。这个函数的定义应该具有这种类型，它的使用必须符合这一类型。
绑定时间 (约束时间）
绑定时间指一个绑定的活跃时间。
与高级语言和程序有关的重要时间概念：
语言设计时。如：程序结构、类型。
语言实现时。如,I/O,算术溢出，类型等价
编程时。如：算法和名字
编译时。数据对象的布局，从程序中高级结构到机器代码的映射。
连接时。整个程序在内存的布局，如：静态数据对象分配，跨模块对象约束，库对象约束
装载时。物理地址的选择，完成虚地址到实地址的映射
运行时。变量的值绑定，运行时的其他事项静态绑定和动态绑定
静态绑定：在程序运行前建立的约束
动态绑定：在程序执行过程中建立的约束
哪些特征能静态绑定，或者必须动态绑定，不同语言之间差别很大
一般而言，静态绑定效率高、意义清晰，动态绑定更灵活
静态绑定的语言一般是编译执行
动态绑定的语言一般是解释执行
下面重点讨论变量的绑定，以下用对象表示任何有名字的东西。
生存期和作用域
绑定的生存期是一个绑定从创建到销毁的时间。
创建和销毁可能伴有特定的动作（例：常量创建时需要给定值）
绑定的作用域是一个绑定在程序中活跃的文本区域。
作用域本身指程序中没有绑定被销毁的一段最大的程序区域。 （后面再讨论）
常见作业域
子程序 (函数和过程）
模块
模块类型
类
块子程序
在大多数带子程序的语言中，子程序入口打开一个新的作用域。
在子程序入口，为局部变量创建绑定，使被重复声明的全局变量的绑定无效，然后建立到局部变量的索引。
在子程序出口，销毁局部变量的绑定，激活那些被变无效的非局部变量的绑定。
对象的创建和销毁
对象的创建（ creation）可能是
静态创建，包括编译时完成，连接时完成，或者装载时完成
动态创建，运行中创建
对象的销毁可能在
运行中完成
程序终止时完成
生存期跨越程序运行期的对象称为永久（ persistent）
对象静态对象和非静态对象
静态对象：静态创建，程序终止时销毁。
非静态对象：程序运行中创建和销毁。
Fortran 中的所有变量都是静态对象。
C 中的外部变量（用 extern声明）和局部 static 变量是静态对象，自动变量（用 auto声明或默认）是非静态对象。
创建和初始化动作完全可能不同时做。例如 C++ 的局部 static 变量是静态创建的，但在执行首次进入变量所在函数时进行初始化。
生存的对象通常有一个固定标识，最常见的就是用对象的存储位置表示。对象总占据着一块存储空间，在其中保存自己的,值,。
因此，对象创建有时也称为分配（ allocation）
存储位置 值对象：生存期
静态创建的对象在程序执行过程中始终存在，生存期是程序整个执行过程
例,C语言的全局变量
动态创建的对象具有较短的生存期
例,C的局部自动变量，生存期是它所在的函数的执行期间
程序对象创建时可能需要执行一些动作，销毁时也可能需要执行一些动作
例,C 标准函数 fopen 创建一个 FILE 对象，建立文件链接（执行一些操作系统动作），分配数据缓冲区和附属结构。该对象生存到相应的 fclose 操作，销毁时需要清理缓冲区，释放相关存储，
释放文件链接
C++ 等语言允许程序员为对象的创建和销毁定义特定的动作
（构造函数和析构函数）
典型的存储分配方式
创建对象首先需要为其存储分配。典型的存储分配有三种情况：
静态分配：给定一个绝对地址，执行中保持不变
栈分配：如果对象具有后创建先销毁的性质，可采用栈分配,如过程的调用和返回
堆分配：不能采用上述方式分配的对象，只能在堆里分配
程序的存储区通常分为三部分：静态区，栈区（程序运行栈）
和堆区（动态管理区），分别对应上面的三种分配
静态区可能还分为只读区和读写区（依赖于操作系统支持）：
代码放在只读区，常量对象也可能放在只读区
静态分配的变量放在静态区里的可读写区问题
例：试判断下面的 c程序是否正确？
char *p = "a string";
*p = 'A';
答,C语言不允许修改字符串常量,因此上面程序是错误的，
可能导致程序崩溃 ！！
调用序列
运行时环境依靠调用序列来进行维护。
调用序列 (calling sequence)：当调用过程或函数时，
运行时环境必须发生的操作序列。
包括：过程活动记录的存储器分配、计算和保存参数，
必要的寄存器的保存和设置，放置可由调用程序访问的返回值，以及活动记录存储器的释放。
调用时执行的操作称为调用序列 (call sequence)。返回时执行的操作称为返回序列 (return sequence)。
哪些对象可以静态分配能静态确定所有性质（包括大小）的对象才能静态分配。常见的有：
全局变量
有些语言没有全局变量，如 Java
子程序代码（翻译结果）
需要建立对象的常量，包括：
一些全局的常量
字符串和浮点数（可能还有一些整数）
局部静态变量。如 C 函数的 static 变量,C++/Java 类的 static 数据成员
编译系统可能在静态区建立一些支持程序运行所需的静态数据结构，
例如为支持动态检查和执行的表格（例如数组的维数和上下界越界检 查,OO 语言里类的虚表），支持存储管理和异常处理的数据结构等子程序代码、常量、字符串对象有可能分配在只读区域，修改它们将产生动态运行错误（相关检查通常需要操作系统支持）
生存期：静态分配无递归的语言，局部变量可以静态分配在 Fortran 90 之前,Fortran 的许多实现里，所有对象都静态分配，程序运行中没有堆栈和堆区
Fortran 不允许子程序的递归调用，子程序里的局部变量只需要一份
程序里所有的变量访问都编译为直接的地址访问
程序运行前完成所有对象的创建，运行中不做任何对象分配和释放工作这些情况使 Fortran 程序具有很高的效率
Fortran 不支持下列程序设计技术：
递归
变长度数组或字符串
动态存储分配和动态数据结构（如链表），等等
Fortran 90 加入了递归和动态存储分配，语言的实现模型必须改变静态分配例：程序清单 1 一个 FORTRAN77示例程序
PROGRAM TEST
COMMON MAXIZE
INTEGER MAXSIZE
REAL TABLE(10),TEMP
MAXSIZE=10
READ *,TABLE(1),TABLE(2),TABLE(3)
CALL QUADMEAN(TABLE,3,TEMP)
PRINT *,TEMP
END
静态分配举例
SUBROTINE QUADMEAN(A,SIZE,
QMEAN)
COMMON MAXSIZE
INTEGER MAXSIZE,SIZE
REAL A(SIZE),QMEAN,TEMP
INTEGER K
TEMP=0.0
IF ((SIZE,GT,MAXSIZE),OR,
(SIZE,LT,1)) GOTO 99
DO 10 K=1,SIZE
TEMP=TEMP+A(K)*A(K)
10 CONTINUE
99 QMEAN=SQRT(TEMP/SIZE)
RETURN
END
可变数组
MAXSIZE
TABLE (1)
(2)
…
(10)
TEMP
3
A
SIZE
QMEAN
返回地址
TEMP
K
全局区主过程的活动记录过程 QUADMEAN
的活动记录图 程序清单 1中程序的运行时环境生存期：栈分配在允许递归的语言里，子程序里的局部对象不能静态分配
一个局部对象可能同时存在多个活动的副本（可能存在递归）
由于子程序调用有后进先出性质，因此其局部对象可以采用堆栈分配栈的分配和使用
编译时为每个子程序安排一个栈框架，算出各个局部对象所需存储量，
在框架里为它们安排位置，算出各对象相对于框架起始位置的偏移量
运行进入一个子程序时，在栈里为这个子程序的框架分配空间
设置框架指针（通常是一个寄存器）指向当前子程序的框架
子程序局部对象的访问都通过框架指针加偏移量进行子程序结束时释放对应的栈框架，所有局部对象都销毁（有些语言在销毁前执行一些特定销毁动作。如 C++ 可以定义销毁动作）
生存期：栈分配例 2 利用 Euclid算法的简单递归算法，
计算两个非负整数的最大公约数。
程序清单 2 例 2的 C代码
#include <stdio.h>
int x,y;
int gcd(int u,int v)
{ if (v==0) return u;
else return gcd(v,u%v);
}
main()
{ scanf(“%d%d”,&x,&y);
printf(“%d\n”,gcd(x,y));
return 0;
}
假设输入 15、
10，则 main
调用
gcd(15,10)。
它递归调用
gcd(10,5)。
它再递归调用 gcd(5,0)。
它返回 5。
第 3个调用时的环境如图 2
所示。
x:15
y:10
u:15
v:10
控制链返回地址
u:10
v:5
控制链返回地址
u:5
v:0
控制链返回地址自由空间
fp
sp
全局／静态区域
main的活动记录第一次调用 gcd时的活动记录第二次调用 gcd时的活动记录第三次调用 gcd时的活动记录栈的生长方向图 2 例 2的基于栈的环境在允许嵌套定义的语言中，还要加上静态链（访问链）来描述一个过程的定义环境。
生存期：堆分配只要对象的生存期有后创建先销毁的性质，就可以在运行栈里分配。
没有这种性质的对象只能在堆里分配。
堆是一块存储区域，其中的存储块可以在任何时间分配和释放。
堆管理就是常说的,动态存储管理,。
动态存储管理子系统是程序运行系统的一部分，它管理一片存储区。
如果有存储申请，管理系统就从当前可用的空闲区里分配一块；
如果无法满足要求，管理系统可能向操作系统申请新存储块，或者直接返回分配失败的信息
C 标准库的 malloc,calloc,Pascal 的 new 都是调用动态存管系统的界面操作。
堆的一个场景：
堆存储分配算法
维护堆中当前尚未使用的存储块的一个链表，称为 自由表 。
堆存储的常用算法
分配代价与自由块的数目成线性关系的
最先适配 算法：选择表中第一个能满足请求的足够大的块。
最佳适配 算法：选择表中能满足请求的最小的块。
如块比请求大得多，两算法都将块划为两块，不用的返回
分配代价为常数级
将不同大小的块分别维护在不同的自由表 (存储池）中，将分配请求向上归约到一种块的大小，并从相应的表中进行划分。
动态调整的算法：伙伴系统和斐波那契堆堆存储分配算法
伙伴系统：标准块的大小是 2的幂。如果需要一个 2K的块而没有，则把一个 2k+1的块一分为二，一半用于满足本次需求，一半放在第 K个自由表中。在释放时，如果它的伙伴（创建时与它分开的另一半）也是自由的，则合并它们。
斐不那契堆与之类似，只不过标准块的大小采用的是斐波那契数。
垃圾回收机制
堆的存储空间释放分为显式释放和自动回收两种
一些语言提供了动态存储块的释放机制，程序员可以根据需要释放以前分配的块。存管系统回收存储块，将其恢复为空闲空间。
如,C语言的 fclose和 free。
回收时通常需要合并释放块和相邻空闲块，以便满足以后的大块请求。
人工释放的问题在于确定正确的释放时刻。
在复杂程序里弄清合适时刻可能成为程序员的巨大负担。如果程序设计得不好，就可能无法确定何时释放某对象。堆分配对象的使用错误是复杂程序中一类最常见错误，不但很容易出现，而且很难排除。
垃圾回收机制自动释放技术方面，目前主要有两种想法：
把堆对象约束于适当的栈对象，借助栈对象的销毁自动释放堆对象
设计某种自动机制，自动回收不再有用的堆分配块（ garbage
collection）
C语言实际没有垃圾回收机制，一切依赖程序员和操作系统。
C++语言在类的析构函数中提供垃圾回收，由程序员决定释放那些资源，当程序调用某个类的析构函数时，垃圾回收工作执行并完成。
Java则提供了独立的垃圾回收机制，无需程序员介入，由 Java虚拟机来决定何时进行垃圾回收。当然程序员在一定情况下可以强制垃圾 回收机制立即工作，方法是调用 system.gc下面的几个方法 。
垃圾回收机制垃圾回收（ GC）技术起源于 Lisp，最早是由
McCarthy 等为实现 Lisp 而开发的。
垃圾回收的主要技术：
标记 -清扫式：通过引用关系标出堆里全部的活跃对象，收集其余对象。
复制式：把活跃对象及其连接关系复制到另一存储区，原区全部收回。
分代式：复制式的改进，利用对象的生存特性提高 GC效率。
分代式垃圾回收
目前客户端虚拟机垃圾回收技术的主流,Java和,Net都采用
分代假设
弱分代假设：大多数对象在年轻时死亡（广泛成立）
强分代假设：越老的对象越不可能死亡（不普遍成立）
分代式收集策略
将对象按照年龄存放到堆中的不同区域（分代），年轻的分代被收集频率高，年老的则收集频率低。
垃圾回收机制
GC 一直受到实际程序员的排斥，认为其（时间和空间）开销太大，可能导致程序执行的时间特征无法预期。典型：
C++ 设计者很反对垃圾回收。
近年，由于：
处理器速度提高，内存、垃圾回收的开销已经不是大问题
系统开发中良好正确地管理存储，已经成为程序员最大的负担之一
OO 的广泛应用，没有垃圾回收，开发 OO 程序的代价会大大提高最新的程序语言都提供了自动垃圾回收。
作用域
定义（声明）建立名字与对象之间的约束，在存续期间固定不变
约束在源程序里的作用范围称为该约束的作用域
（ scope），也说是这个定义或声明的作用域
作用域：解决由名字确定程序对象的问题
例,C 局部变量在其定义所在的复合语句里可用（从定义位置开始）
作业域类型
静态作业域（词法作业域）
约束在编译时确定，大多数语言采用，如,C，
Ada
在允许子程序嵌套的语言中，通常采用最近嵌套原则，如,pascal
动态作业域
约束依赖于程序的执行，如,Lisp
static vs dynamic scope rules
例：试分别给出下列程序在静态和动态作用域的输出。
int a
proc first:
a,= 1
proc second:
int a
first()
a,= 2; second(); write(a)
静态作业域,1
动态作用域,2
一个动态作用域的问题引入动态作用域的原因可能是因为它容易让解释器弄清楚名字的含义，但是它的运行时代价高，也容易让程序难以理解。
例：判断下列程序是否能够正常工作？
作用域单位与语言
最简单的作业域是 BASIC，只有一个全局作业域。
早期 Fortran 的作用域结构很简单，只区分全局变量和局部变量。全局变量放在 COMMON块中。
后来人们认识到信息局部化的重要性，慢慢地引进了许多作用域单位。
Algol 60 引进块（ block）结构作为基本作用域单位，允许任意嵌套的局部作用域，子程序被看作是是有名字可调用的块。
现在一般语言都以子程序（过程 /函数）作为作用域单位，一些语言允许子程序体内部的嵌套作用域（如 C 的复合语句）。
其他作用域单位：
结构 /记录的声明,OO语言里的类定义（声明）
模块结构（如 C++ 的名字空间,Ada 的包）
其他，如 C 源文件是一种作用域单位（ static 外部函数和变量的作用域）
学习语言时，需要弄清语言的作用域单位。
作用域单位不同语言对于作用域单位的规定不同
一些语言有全局作用域，供定义全局的标识符 /对象约束。除全局作用域外的其他作用域都是局部的
C 语言的全局作用域里可以定义 /声明变量、函数等。函数只允许定义在全局作用域里（不允许函数的嵌套定义）
C 语言的局部作用域是复合语句（函数体也是复合语句）。 C++ 对 C
的作用域做了许多扩充
在 Java 语言的全局作用域里只能定义类，其他实体都只能在局部作用域里定义
Fortran 只有全局作用域和子程序作用域，子程序内部没有嵌套作用域
Basic（老的）只有一个全局作用域，所有变量约束都在一个作用域里。
定义在子程序里的变量也具有全局作用域（难以编写大程序）
作用域作用域：冲突和嵌套通常规定：
在一个作用域里同一个名字不能有多个约束（名字冲突）
不同作用域里的名字相互无关作用域可能嵌套,局部作用域位于全局作用域里，局部作用域里可能还有内部的作用域。
同一名字的不同定义有可能出现作用域重叠的情况。此时就出现了作用域里的,空洞,现象（见图）
内层的定义,遮蔽,外层的定义为了程序容易理解，应尽量避免同名对象的作用域嵌套
int n;
int p (int n) {
double x;
… n … x …
}
int main () {
int x; double y;
… n … x … y …
if (…) {
int n = 3;
… n … x … y …
for (… …) {
int n; int y;
… n … x … y …
}
… n … x … y …
}
… n … x … y …
}
作用域：嵌套在作用域空洞里，（被遮蔽的）外层定义的约束不可见，直接写出一个名字，总是表示当时的最内层约束。
为了编程方便，一些语言提供了,带修饰的,名字形式，通过名字的前缀修饰指定对外层（定义）约束的访问（有些语言的机制有限制）。
例,C++ 的,,是作用域解析运算符，可以用,:nm 的形式表示引用全局定义，用 cn::nm 的方式引用特定 namespace
或者类里的定义。
在 Ada 里，每个块（ block）都可以命名，利用块名作为前缀，可以引用外围块定义的约束（就像引用结构 /记录的成员）。
静态和动态作用域规则
作用域规则（ Scope rule | Static,
Dynamic）：规定在程序中任一特定位置，
从一个名字确定与之约束的对象的方法。
局部定义的约束容易确定，关键是非局部定义（非局部约束的）的名字
静态作用域规则：非局部名字的约束由名字出现位置的静态正文环境确定
动态作用域规则：非局部名字的约束由动态运行环境确定
常规语言都采用静态作用域规则，函数 f
中非局部的 y 约束于函数的静态环境里的
y
一些函数式语言采用动态约束规则。
子程序中非局部变量的静态约束，语义清晰，但实现比较复杂
int y = 3;
#define f(x) \
printf("%d",x+y)
...
{
int y = 4;
f(2);
...,..
}
作用域：实例不同语言采用的作用域设计可能不同，每个语言有一套规定
Pascal 语言：
program 作用域（类似全局作用域）
允许任意嵌套的子程序（函数 /过程）作用域
只有子程序是局部的作用域单位
C 语言：
全局的外部作用域
子程序定义的局部作用域（不允许嵌套定义的子程序）
子程序里任意嵌套的复合语句作用域
文件为单位的全局 static 作用域（只是为了信息的局部化）
作用域：实例
C++ 语言
C 语言的各种作用域
类定义形成的作用域
继承关系形成的作用域嵌套
方法的作用域嵌套在类作用域里
namespace 定义的模块作用域
Java 语言
全局作用域里只能定义类（全局作用域里没有对象名）
类定义形成作用域
方法作用域嵌套在类作用域里
package 形成的模块作用域作用域举例（ 1）
Pascal says the scope of an identifier is its entire block,excluding
sub-blocks in which the identifier is reclared,Within its block,the
identifier must be declared before it is used,Consider this:
const A = 10;
,..
procedure P;
const
B = A;
,..
A = 15;
Pascal rules say the second declaration of A covers all of P,so
the declaration of B refers to A before it is declared,Where should
you report the error?
作用域举例（ 2）
const foo = 10;
,..
procedure P1;
,..
procedure P2;
var A,integer;
begin
,..
A = foo; {illegal,because of dec,below!}
,..
end {P2};
,..
procedure foo;
作用域：细节一个定义 /声明的作用域，常见的有两种规定：
定义的作用域从定义出现的位置到当前作用域结束
定义的作用域包括整个当前作用域两个例子：
int n = 2;
int f (…) {
int n = n+1,m = n+1;
… …
}
C：作用域从声明结束点开始
C++：类成员的作用域是整个类定义语言对于声明的作用域的范围都有明确规定，详见语言手册。
int n = 2;
class C {
int f() { n++; }
… …
int n;
}
作用域和可见性
作用域进入和退出的特殊描述方式：
,运算符（许多语言）
:,运算符（ C++ 等面向对象语言）
Pascal 和 VB的 with 语句其他实体：定义和使用程序里的命名实体还很多，例如类型、标号。
类型通常只在静态处理过程中有效，采用通用的静态作用域规则。
类型定义也可能由于嵌套作用域里的重新定义而被覆盖。
标号，标明代码中的一个位置，作为 goto 的目标。
有些语言里，标号的作用域有特殊规定。
C 语言的标号，作用域是整个函数，允许向前或向后跳到标号。允许跳入跳出嵌套的复合语句、内层控制结构（对于由跳入位置引起的语义不清情况，语言没有定义）
Fortran 标号的作用域是整个子程序。存在与 C 语言类似的问题
Pascal 标号需要首先声明，用无符号的整数表示，其作用域是定义所在的整个子程序（包括嵌套定义的子程序）。不允许转入嵌套的控制结构，但允许从内层子程序里跳回外层子程序（非局部转跳）
名字分类程序里存在多种命名的事物（包括命名对象、类型、结构的成分名，标号等等），
有些语言对名字做了某种分类。在同一作用域里，属于不同类别的名字互不冲突（允许不同类别的同名事物）。
一般规定（在一个作用域里）同类事物的名字不能冲突。
例,C 语言规定了三个名字类（称为,名字空间,）
标号名
struct/union/enum 标志
变量名、函数名、类型名,typedef 名、枚举常量名
每个结构或者联合声明是一个,名字空间,（包含各成分名）
规定程序里的名字分属不同类别，要求语言的实现能区分它们。
采用怎样的规定，与语言里各种特征的设计有关。
