北航程序设计语言原理教材第04章note.docx
《北航程序设计语言原理教材第04章note.docx》由会员分享，可在线阅读，更多相关《北航程序设计语言原理教材第04章note.docx（39页珍藏版）》请在冰点文库上搜索。
北航程序设计语言原理教材第04章note
第4章存储
如前所述，程序世界、机器世界是同一事物的不同层次描述。
在每个层次上各有自己的术语概念。
我们的目标虽然是为程序世界提供表达程序的术语和语言，因为它们密切相关。
我们也应该了解机器世界里存储对象有哪些，怎样工作，可以实现哪些机制。
这些工作机制反映到程序世界是什么?
在某种意义上说，越能在上层构造出更新、更多的符合软件工程原理的程序对象，越要在下层想出更多的实现办法，如果都能实现，则程序设计语言就进了一步。
有关存储对象的基本术语和机制，我们假定读者已在汇编语言课程学过，此处不重复，只是在涉及到机器世界术语和机制时我们才提到它。
请注意，我们讨论问题的立场是程序世界。
还要注意到，程序对象和存储对象并非一一对应的，赋初值的简单常数一般也是不作为独立的存储对象，直接放在被赋值的变量中。
所以研究存储对象的核心是抓住“变量”。
本章主要讨论变量的时空特性，第二节介绍各种实现计算的存贮模型，第三节讨论因时空关系而出现的悬挂指升问题，第四节讨论各种语言变量更新机制，第五节介绍有副作用的表达式。
4.1程序变量的时、空特性
如前所述，程序世界中的变量不同于数学变量在于它的时、空特性。
我们先从空间特性开始。
我们知道，计算机内的变量的存储空间是随时可变的，它可以在外存磁盘上，也可以在内存的某个地方，而且同一程序两次加载运行变量也不会在一个地方，即非固定地址。
为此，一般目标程序中都采用相对地址的办法，绝对地址就不重要了。
对于程序，我们要找到某个计算对象，永远从该段程序的首地址开始。
为了简化,我们在虚存空间讨论存储对象。
4.1.1引用和指针
由于变量的名值分离，当程序操纵变量时，首先寻址再取内容。
这是两种操作'取地址'（引用）和'取值'（递引用）。
命令式语言两者都要，且有时是隐式的。
自从Pascal,C引入指针变量可显式操纵变量的地址，给程序员带来极大方便。
例如，一个大单位，随机录用上千个员工。
每个员工履历是一复杂记录，现登记现录入无序存放。
我们只要按它的某个属性特征对指向它们的首地址（指针）排序，即可按排好序的指针表次序打印各种报告，而无需将庞大的记录重排多次。
指针本身也是程序对象，它也有地址，于是C语言允许多级指针的机制。
其它语言编译只允许一级指针，除非指向复杂数据结构内嵌的指针。
用↑（Pascal）和*（C）标记指针变量标识符以识别是操纵指针变量的内容（地址），还是操纵指针变量所指对象的内容（值）。
例4-1，C程序中的指针
inti;
int*p，*q;
:
*p=i；//p指向整变量i
p=i；//错误，p中只放地址值
p=&i；//正确，效果同*p=i，&取地址符
q=p；//正确，同类型赋值，q，p都指向i
*q=*p+1；//q指向i，此时i已成为i+1
q=p+1；//'1'仅是名，值取决于所指对象每个单元占多少字节。
所谓寻址即要给出编译（或解释）时程序变量名与地址的对照表。
每当给程序对象分配存储时就在表中填入，这样就创建了引用（reference）。
由于程序对象名字编译后不存在，每次操纵用的是地址，这个在对照表中有的地址即为该对象的别名。
早期语言认为这是属于‘内部’的事，外叫‘变量’，内叫‘地址码’。
而C++语言把这个占据存储的存储对象也上升为程序对象，叫做引用，使用户直接操纵地址。
引用，指针、变量关系的示意图如图4-1。
312（RA）引用
A136（P1）（P2）指针
316（RB）
B140448450
320（RC）136144
C144
500136140144
P14884274.543312.27607.01
504
p2450（A）（B）（C）
图4-1变量、指针、引用示意图
变量A的地址码分配为136放在312中，每当程序中用A的左值，查出136即是，若用A的右值查到136再找136的内容。
既然312也是存储单元地址，则把它对应为一引用名RA。
只是一旦给出136再也不许改变，它成了A的别名，相当于常量指针。
指针P1，P2既是程序对象，它们被分配在448，450存储单元内，地址码448，450同样成为P1，P2的代替物。
如果在448中给予136地址则P1指向A。
给140则指向B。
其内容是可变的，所以和引用RA不一样。
RA虽然也放一个地址，但更强调的是引用内容。
即当RA，A同时出现在赋值号右边，其效果完全一样，这一点和常量指针又不一样。
它和变量A不同之处仅在实现上，效果是相同的，而且引用‘变量’必须赋初值，一旦赋初值则在其作用域在其所在程序单元的范围内不得改动。
C++和C引入引用主要是用于函数调用的传地址。
形、实结合正好相当于引用变量赋初值。
（这在第6章中还要讲）。
4.1.2递引用
一般说来，通过指针变量引用某变量的内容叫做递引用（dereference）。
多层指针则多次递引用。
指针用‘↑’或‘*’显式地表达了它的递引用。
但多数程序设计语言都有隐式的递引用。
例如，下标表达式，除了引用下标变量值再引用该元素的值，即使出现在赋值号的左边的下标表达式也是递引用。
我们称这是自动递引用。
FORTH语言是唯一不容许自动递引用的，它只有显式递引用运算符@：
例4-2FORTH的递引用运算符@
[1]13VARIABLExx（声明变量xx并赋初值13）
[2]0VARIABLEY（声明变量Y并赋初值0）
[3]xx@2*Y!
（相当于Y=xx*2）
如果只写xx2*则为将xx的地址乘以2放在Y之中。
4.1.3变量的时态
除了空间名值分离导出指针、引用、递引用程序世界的概念之外，变量还有时间特性，以它的状态刻划：
（1）.分配/未分配/除分配
为程序对象分配存储就创建了存储对象，程序对象就可以访问了。
如果在编译时做这个工作我们叫静态分配，程序中变量多数如此。
如果在程序运行时刻分配存储，我们叫动态分配，程序中的指针（或访问）类型变量则按动态分配，一般由程序员显式指定（用new操作）。
若程序对象声明了但未分配存储对象即投入运行，此程序对象处于未分配状态。
撤消程序对象即除去已分配的存储对象，我们叫除分配或除配（deallocate）。
除分配可由程序员显式指定（用delete操作），也可以约定由语言的执行系统或操作系统自动实现。
自动将当前无用的程序对象除配，并收回待用称无用单元回收（Garbagecollection）机制。
动态（或无）类型语言一般有此机制，静态类型语言虽然也有动态分配部分，往往不设此机制（如C语言）
（2）.定义/未定义/失去定义
分配的存储单元总是有残值的（上个程序运行后留下的），这些值无任何意义（与本程序无关）。
我们说，变量未定义。
如果通过赋值或赋初值，就是定义变量，除了它的值对本程序计算是有意义的。
如果该变量执行超出了我们指定它有意义的区域（例如，一个局部块的末端），只要它的存储没有撤消，它总是存在，但其内容（值）已失去定义。
以下举例说明。
例4-3变量的状态（Ada）
procedureMAINis
declareBLOCK；
typeCELL；
typeLINKisaccessCELL；
typeCELLisrecord
VALUE:
INTEGER；
NEXT:
LINK；
endrecord；
typeVECTORisarray（INTEGERrange<>）ofFLOAT；
LA:
LINK；--声明访问类型变量LA，但未分配
V:
VECTOR；--声明数组类型变量V，未分配
VB:
VECTOR（1..5）；--声明数组类型变量VB,运行前已分配但未定义
begin
LA:
=newCELL；--动态分配无名CELL对象由LA代名
LA.all:
=（3120，null）；--定义LA所访问对象
V:
=（1=>5.0，2=>4.0；3=>3.0，--分配V为六元素数组，且得到定义，动态完成
4=>2.0，5=>1.0，6=>0.0）--只有VB（3）得到定义，VB的其余元素未定义
VB（3）：
=V
（1）；
endBLOCK；
L：
=LA；--LA值已失去定义，出错
--V，VB（3）的值均失去定义
--Ada有无用单元收集，此处可将失去定义的变量存储回收
endMAIN；
4.1.4可存储值
就变量访问和更新而言，我们把可以直接访问和更新的存储对象的值称为可存储值（storable）。
它们是可访问的最小存储单元。
因此，复合值如果它们的成分不能选择更新，该复合值即为可存储值。
例如，Pascal的集合值，不能单独更新其中某个元素，它是可存储值。
反之，数组元素是可以选择更新的。
整个的记录、文件也都不是可存储值。
所以，Pascal中可存储值是：
·基本类型值
·集合值
·指针值
变量引用、函数过程抽象也不是可存储值，它们本身不是可存储的。
C++语言设置了引用类型变量，变量引用有了名字，它是可存储的。
ML的可存储值有：
·基本类型值
·记录、构造、表
·函数抽象
·变量引用
ML的记录、构造、表是可存储值，因为它们不能选择更新，更新其中一个元素存储要重整一遍。
由于函数抽象和变量引用全部采用类似C++引用类型的办法，借助于引用可以有选择地更新复合值。
事实上除数组而外，ML所有的值均为可存储值。
例4-4ML的函数抽象是可存储值
函数名即函数抽象，在Pascal中，f（x）的f是不能单独存取和更新的，ML中却可写为：
（ifexpthensinelsecos）（x）
这个条件表达式的返回值（sin或cos）是函数抽象，sin（x）是函数定义，也叫型构（signature），sin（a）是函数引用。
后二者都不是可存储值。
4.2组织存储对象的存储模型
存储管理模型是翻译器必须选定的关键部分，各语言不尽相同，但从总体说有三种存储模型，静态存储，堆存储，栈存储。
后二者也称动态存储模型。
4.2.1存储对象的生命期
每个存储对象都有其创建（生）、可用（活着）、撤消（死）的生命期。
每当分配存储即创建存储对象。
当所在程序块或整个程序执行结束，程序对象死亡，存储对象也应自动撤销。
但多数对象生命期不会像程序执行期一样长，也有少量对象的生命期比程序还要长。
我们把寿命和程序一样长的变量称为全局变量；寿命和程序中一个或几个模块一样长的变量称局部变量；寿命大于程序执行期的变量称持久变量。
文件变量即持久变量。
与此对应，程序中变量都叫临时变量（包括全局、局部、静态、堆变量）。
活着的对象必须在内存中才可用。
然而，由于有虚拟存储技术。
外存上虚存中的对象也是活对象，除非所占存储被撤销并分配给其它程序对象。
在程序执行期间，一个存储单元可多次分配给局部变量，甚至同一存储对象可由多个程序对象共享，如C的联合，Pascal、Ada的变体记录。
FORTRAN等价语句指明的各变量。
反过来，一个程序对象可由多个存储对象实现。
如前述的引用、指针。
程序对象死了，对应的存储对象没撤销，此时引用该对象就会引起难以预计的错误。
分配了没有赋（初）值就引用也会引起错误。
这两种错误在程序调试中屡见不鲜。
4.2.2静态存储对象
在程序运行之前分配的程序对象都叫静态存储对象。
编译时分配自不用说。
近代语言有在装入内存后，运行前分配，Ada称之为确立（elaboration）期间（确立除分配某些对象外还计算初值表达式定义初值）。
之所以称静态，因它们在分配之后整个程序执行期间不再改动。
静态分配常伴之以初始化。
所有语言的全局变量都是静态对象。
某些语言（COBOL）只有静态对象；某些语言（Pascal）除全局变量而外没有静态对象；而C和Algol允许程序员把局部变量声明为静态的，即该局部块执行结束静态变量并不失去定义，该块下次还可用，但同一程序其它局部块却不能用。
所以Algol把它叫做OWN（自己的），声明中显式指明。
C则用Static，C的extern变量全局于所在文件也是静态的。
静态存储对象直观易于查错，但它不能支持递归，因为多次递归调用相关的动态参数无法分配（不知道递归几次）。
静态存储对象仅限于全局变量的第二个缺点是被迫使用易引起副作用的全局量。
对于某些问题（如求随机数，输入/出程序指示当前输入/出位置的指针）需要在程序多次执行时值有连续性，因而没有执行后仍保持值的变量（若完全是局部变量执行后自动销毁）无法模型客观世界。
然而，采用全局变量其它无关模块也可使用就会引起副作用，C的静态变量即为局限于一个文件（模块）的局部变量，即保持值的连续性又有保护作用。
静态存储对象，无论是全局量还是局部量的第三个缺点（也是它的优点）是占据的存储不到程序执行完不释放。
对于大程序且有众多只需短寿命变量的应用就浪费了大量存储。
即使有无用单元回收机制不到执行完也收不到它，FORTRAN的等价语句（新一代语言的联合、变体记录）就为（起到）缓解作用而设。
请注意，静态分配的不一定是静态变量，程序中的局部变量（C语言叫自动变量）是静态（编译时）分配的，运行时存贮的地址可变。
4.2.3动态存储对象
动态存储对象在程序执行期间诞生（分配和定义），故名动态。
多数动态对象它们的大小和结构形态往往依赖输入，编译时无法确定。
例如，递归定义的二叉树，其结点、叶子、层数完全由输入值定。
因此，动态存储对象生命期长短不同，大小不同，类型各异，如何使存储管理高效是一个中心问题。
管理不好对程序执行的时、空效率影响极大。
在某种意义上说，它是发展先进语言或软件技术的关键。
例如，Prolog、Smalltalk出现初期都是执行效率难以和传统语言匹敌的，慢5-30倍。
不断改进才能进入实用。
影响最大的因素是动态存储对象的生命期，而不同生命期存储对象搭配使用，恰巧是增加表达能力，减少程序错误的进步。
所以一般语言提供管理不同的生命期对象的模型。
最简单的模型是在内存中开辟一个堆（heap）空间，放入其中的动态对象的寿命完全由程序员控制，语言系统全然不知。
每当创建一新存储对象，存储管理则找出一个足以放下该对象的堆空间。
每当存储管理得知（出了所在程序块）它已死亡，它就记下该对象不再使用。
随来随堆，谁死谁释放，新来的没地方就等到老的死了再存入，故名堆。
一般的指针动态生成的对象即按此型式，故指针变量也叫堆变量。
管理堆型式最大的问题是多次存储后留下存储碎片，因为新对象的大小往往不能填足老对象的空间，时间长了形成星星点点的许多“小洞”，管理很麻烦。
拿出记录该碎片信息所费存储比这些“小洞”本身小不了多少，而且运行时一个到一个链接十分低效。
再者还没有能找出合适的识别算法将“小洞”合并。
这些问题各语言系统都采取了各自的做法。
本节将介绍主要做法。
由于堆型式管理存在着麻烦，人们寻求并得到第二种管理型式：
嵌套生命期型式，按照这种型式任何两同时出现的对象其生命期长短可以不同，但必须完全嵌套，即不能交错。
也就是在时间上一个包容一个，我们就可以把相近寿命变量归成一组,最长寿命组放在堆栈的底部,最短的在顶部，逐级释放和重新占据存储，可以得到成片‘干净’的存储。
如图4-2所示。
块1块2块3块4块5块6
6
4
5
寿6
命5
4
6
图4-2嵌套生命期存储原理图
本例依次分配了6组不同寿命的存储块。
由于块6中对象寿命最短，全部重新分配3次，块4，块5可重新分配两次…而块1的一次生命期还没完。
如同倒下来的堆栈，栈顶的对象生得快死得也快，死了清除再分配第二批。
而栈底的对象一直活着。
事实上，动态对象寿命长短本来就和所在嵌套模块相关，只要把寿命特长的（如文件，全局量）排出来归到栈底的某一组，把寿命特短的（如循环控制变量）另立嵌套组，这个分组的问题也就解决了。
4.2.4动态堆栈存储
按照嵌套生命期存贮原理，对于嵌套块结构的程序设计语言如（Pascal，Ada，C）动态堆栈型管理特别有效，因为多数变量和所在块寿命一样长。
变量生死随所在块的激活和消亡高效自动实现。
所以C语言把局部于块结构的变量叫做auto（自动）变量。
但多数语言（包括C）堆、堆栈管理同时并用（原因见后文）。
4.2.4.1动态堆栈式管理机制
为了说明堆栈式管理，我们再参照图4-2运行时堆栈，结合执行过程，介绍其实现机制，如图4-3所示。
程序代码底
参数全局静态存储
返回地址首先调用块
动态链堆栈帧
静态链第二调用块
返回值栈顶堆栈帧
局部变量……
最新调用块栈顶
堆栈帧
临时变量空间
堆栈帧组织运行时堆栈
图4-3运行时堆栈和堆栈框架实现
运行时堆栈（Run-timestack）是在内存开辟一个空间，如同堆。
首先将程序代码和全局、静态变量装入，示意为图4-3的右图最上一块。
这一块的词法上辈（LexicalParent）是操作系统。
当执行控制开始时，首先执行这一块，当执行到调用时，按编译时生成的嵌套关系，找出被调用的块，将该块的数据（包括实参和局部量）作为新的一帧，记下静态链（连接词法祖先（Lexicalancestor）），压入运行时堆栈后记下动态链（连接执行顺序）。
由于编译时词法祖先块的地址无法确定，静态链要根据祖先块分配存储对象去找，有时要用到局部变量和参数。
动态链指出当前块的动态执行的上辈，以便在块出口时弹出栈内的执行指令。
动态和静态链在压入栈时利用局部分配指针从栈中第一个‘自由’位置逐个向上（下）分配，记下该指针的值，以便以后弹栈。
每个堆栈帧（stackframe）的组织如图4-3的左图，它按以下事件序列压栈：
[1]调用程序将实参值置于新块底部，用局部分配的指针，一般说，最后一个实参先放入，倒数第二个第二…第一个放在最上面。
[2]接着放入新块的返回地址。
[3]把当前栈顶指针值拷贝到栈内，这是新块动态链的一个域（存放当前栈顶地址）。
[4]填写静态链，将编译时生成的标记码拷贝进来，对于调用块静、动态链标记是一样的。
[5]再留足够的位置以放下局部变量的返回值，如已有初始化则拿来就可以了。
[6]控制转回父块代码执行，直至到生成另一个内嵌块的堆栈帧，如此，运行堆栈又生成一层…
如果某块对应的程序代码出口则根据动态链返回父块，再生成复盖的新的一层堆栈帧…
老块被复盖也就是除分配了。
此处为了简化，返回值假定在块内，实际上常用寄存器。
4.2.4.2用堆栈式存储实现递归
显然，递归调用是堆栈存储管理最简单的形式。
因为它的运行栈每次压入的是同一模块新的数据对象版本，静态链自然按逐层递归调用展开直至到达边界，现举例说明。
例4-4Pascal的递归函数
求整数之连乘积
functionproduct（jj：
Integer）：
Integer；
varkk：
Integer;
begin
ifjj<=0thenproduct:
=1
elsebegin
readln（kk）；
product:
=kk*product（jj-1）
end
end；
其执行图示于图4-4.为简化令jj=2，读二次kk=25，7。
DL:
动态链
product函数SL:
静态链
目标代码
jj:
2DL最初调用时堆栈帧
return:
?
kk:
25
jj:
1第一次调用时堆栈帧
return:
?
kk:
7
jj:
0第一次调用时堆栈帧
return:
?
kk:
?
SL临时存储栈顶
图4-4递归函数的堆栈帧
4.2.5动态堆存储
动态堆栈存储虽然解决了碎片问题，但是存储对象寿命只能和堆栈帧同时生死，限制太严。
而且在每一个块的进口处并不知道存储对象的大小和个数，以及要求存储对象比创建它的块的寿命长。
所以堆存储有时是必不可少的。
我们再详细讨论堆存储。
4.2.5.1堆分配
许多语言允许程序员显式分配动态存储，分配语句可以出现在程序中的任何地方，办法是调用操作系统ALLOC函数。
ALLOC将存储对象分配在堆中并返回对该对象的引用。
如前所述堆分配有时在连接的较小的空间上，算法比较复杂。
所以要建立一处自由表登录已死存储对象的空间，并查清相邻的碎片予以合并。
这些算法还必须高效,否则影响性能。
故往往是折衷，追求快速牺牲一些过小碎片（这又是潜在危险，当指针错误地指向这些无用小碎片时，后果极难预料）。
各个语言组织动态堆及分配后的返回值也不完全一样。
现例举说明：
（1）FORTH的堆分配/除配
·分配：
HERE<表达式>ALLOT
FORTH在存放符号表和全局对象的字典中作动态分配。
HERE是系统变量，程序员通过HERE访问字典顶端指针。
先把HERE的当前值放入堆，然后对表达式求值得一整数N，ALLOT将N个字节加到字典指针。
另设一小栈记下新增区域存入，用户只存入指针变量。
·除配无无用单元回收。
重新分配由用户自己写例程。
（2）LISP的分配/除配
·分配：
（cons<表达式1><表达式2>）
见到这个表达式就分配一新表，并返回对新表的引用。
新表左域由表达式1的值填入，右域用表达式2的值填入。
·除配：
由无用单元收集机制自动完成。
（3）C的动态分配/除配
·分配：
malloc（sizeof（T））
malloc（N）
calloc（N，sizeof（basetype））
式中T、basetype是类型名，N是整数。
第1式是分配T类型的一个对象；第2式是N个字节；第3式是分配一个数组，类型为basetype，元素是N个，并初始化为0。
malloc和calloc均返回对新对象的引用。
程序员必须将返回值赋给某个指针类型或强行转成所希望的指针类型。
·除配：
free（ptr）
ptr必须指向已分配过的堆对象。
该对象经此函数即可重用（再分配）。
（4）Pascal动态分配/除配
·分配：
new（<指针名>）
<指针名>必须是声明为指向某类型的指针。
该指针存放引用返回值。
·除配：
Dispose（<指针名>）
<指针名>所指对象置入自由表。
（5）Ada动态分配/除配
·分配：
new'（<表达式>）
分配一TYPE类型的对象，如果提供了可选表达式，对它求值并用以初始化该新对象，new是函数返回对新对象的引用。
该返回值程序员应赋给ACCESS类型变量（即指针）。
·除配：
有无用单元回收，显式除配一般不用，而是所在块执行完自动完成。
4.2.5.2死堆对象处理
死堆对象叫无用单元或垃圾（garbag
升级会员 