还剩17页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
第章存储4如前所述，程序世界、机器世界是同一事物的不同层次描述在每个层次上各有自己的术语概念我们的目标虽然是为程序世界提供表达程序的术语和语言，因为它们密切相关我们也应该了解机器世界里存储对象有哪些，怎样工作，可以实现哪些机制这些工作机制反映到程序世界是什么？在某种意义上说，越能在上层构造出更新、更多的符合软件工程原理的程序对象，越要在下层想出更多的实现办法，如果都能实现，则程序设计语言就进了一步有关存储对象的基本术语和机制，我们假定读者已在汇编语言课程学过，此处不重复，只是在涉及到机器世界术语和机制时我们才提到它请注意，我们讨论问题的立场是程序世界还要注意到，程序对象和存储对象并非一一对应的，赋初值的简单常数一般也是不作为独立的存储对象，直接放在被赋值的变量中所以研究存储对象的核心是抓住“变量”本章主要讨论变量的时空特性，第二节介绍各种实现计算的存贮模型，第三节讨论因时空关系而出现的悬挂指升问题，第四节讨论各种语言变量更新机制，第五节介绍有副作用的表达式程序变量的时、空特性
4.1如前所述，程序世界中的变量不同于数学变量在于它的时、空特性我们先从空间特性开始我们知道，计算机内的变量的存储空间是随时可变的，它可以在外存磁盘上，也可以在内存的某个地方，而且同一程序两次加载运行变量也不会在一个地方，即非固定地址为此，一般目标程序中都采用相对地址的办法，绝对地址就不重要了对于程序，我们要找到某个计算对象，永远从该段程序的首地址开始为了简化，我们在虚存空间讨论存储对象
4.
1.1引用和指针由于变量的名值分离，当程序操纵变量时，首先寻址再取内容这是两种操作’取地址（引用）和‘取值’（递引用）命令式语言两者都要，且有时是隐式的自从Pascal,C引入指针变量可显式操纵变量的地址，给程序员带来极大方便例如，一个大单位，随机录用上千个员工每个员工履历是一复杂记录，现登记现录入无序存放我们只要按它的某个属性特征对指向它们的首地址（指针）排序，即可按排好序的指针表次序打印各种报告，而无需将庞大的记录重排多次指针本身也是程序对象，它也有地址，于是C语言允许多级指针的机制其它语言编译只允许一级指针，除非指向复杂数据结构内嵌的指针用t（Pascal）和*（C）标记指针变量标识符以识别是操纵指针变量的内容（地址），还是操纵指针变量所指对象的内容（值）例4-1,C程序中的指针int i;减少堆高指针是不行的要把它们做成登录可重分配存储对象的自由表效率高低全看自由表的设计，曾经有过以下三种办法•忽略死对象，这种表当然最容易实现这看上去近乎胡来的策略还真有实现的，如AOD-VS操作系统上（数据通用公司的MV8000机的Pascal,在其参考手册中明文写出Dispose命令无其它操作该操作系统是有虚存、页式管理和分时的）编译实现者的哲学是页式管理若有浪费充其量不到一页如果一页上的对象全都死了操作系统就不会把这页装入内存事实上，当存储对象的创建时间、寿命大致相差不多时，这种策略能工作得很好否则浪费巨大•保持一个自由表它将所有自由空间连接在一起这样，每个自由空间都要有几个字节记录它的大小并指示链接（多数硬件是8个字节），小于此数的空间也只能放弃了多数C,Pascal编译版本采用这个方案8字节的头部说明是需要的两个指针以构成双向循环链表，一个字节指示该小块是自由还是工作的各小块编排次序和内存地址一致，这样相邻的小块合并就很方便了死对象除配也很方便只要把指示位设成“自由”相邻小块都自由则合并扫描到第一个自由区并接着找到足够大的空间是很费事的，因为多数区域都在工作故扫描从正在工作的顶部开始，倒着来，如果额外增加一些记录信息空间，扫描效率会高些这里有时、空互易问题•保持多个表按类型的长度，每种长度一个表，表的元素可以交换，次序就不重要了这样就不需要标识区域的开销归并、重分配实现起来就容易得多Ada即采用这种办法堆式管理除产生碎片之外仍有悬挂指针问题，其原因是当有多个指针指向同一存储对象时，除配该存储对象及其一个指针而忘掉消除所有指针，其它指针就是悬空（其实是指向无定义存储）了两对象共享一数据结构时更容易出现因为一个死了一个活着，既要除配又不应除配，一除配就产生悬挂指针而识别这种情况比较困难因此，有人主张不要显式的除配（KILL）操作Pascal的Dispose备受攻击，许多版本取消，并有返复LISP语言就是自动处理重用死堆对象没有显式KILL命令，堆对象依然要死的，但存储管理不知道什么时候死它采用无用单元回收机制，每当堆接近满的时候，从头检查起，如果是静态的、堆栈分配的它就认为是活的，凡有一活对象指向的存储也是活的一律作上标记最后将无标记的存储重新分配尽管如此，程序员依然有义务删除对不再需要的对象的引用（无用单元收集只解决最后全部不用了的对象除配）此外，无用单元收集费时低效随着存储廉价可配备大内存，就不致于在一个程序运行期间多次运行它随着机器速度进一步提高，无用单元收集似乎是存储管理有希望的出路悬挂引用
4.3指针指向一个已死或无定义的对象，就称为悬挂引用（Dangling References）,或悬挂指针程序设计语言采用堆式管理，同时提供显式除配命令（KILL）时最容易产生对于堆栈式管理，如果外块的指针指向内块的存储对象时也会产生悬挂指针，因为当内块执行完除配，外块指针依然活着可用，它就指向无意义的单元的悬挂指针是极为有害的它甚至可以无缘无故地修改另一个程序这对另一个程序是无论如何也查不出的错正因为如此，指向堆栈内（即内块）的指针Pascal是不允许的Pascal只限指针为堆对象,构造链表和树数据结构的指针都在堆中分配简单变量和数组在堆栈中分配，不提供地址运算因此，只能用下标处理数组，不能用指针-地址操作快速索引C对指针的使用完全没有限制取地址运算符随处使用当然也可以用到已除配的堆栈对象上即使C不许函数嵌套，主函数对函数的一层调用用堆栈实现时也会产生悬挂引用,试看以下例题例4-4悬挂引用Cint*dangle int**ppp〃参数是指针的指针{int p=5；int m=21；〃传回的指向p的指针〃*ppp=p；返回m的地址returnm；}main{int k=17；〃pk指向kint*pm,*pk=k；pm〃返回时pm,pk均指向已失去定义的指针函数〃=dangle pk；局部量，即p和mmain调用dangle后，堆栈中dangle所据空间可重新分配，而pm,pk指向其中的m,p就成了悬挂引用当然读者会问，既然对指针如此自由使用，为什么不全由堆式管理实现呢？原因是堆栈可实现高效的递归C语言追求高效也支持递归，所以采用栈-堆结合的管理方式只好把悬挂引用的问题留给程序员解决C设计是为系统程序员用的，它的哲学是程序员不需要更多的限制C本来就简单，提供特征不多，限制多了会成为无用的小语言函数抽象作为第一类值是另一个诱发悬挂引用的原因，请看以下示例例4-5假定Pascal将函数扩充成第一类对象var fvInteger fBoolean；procedure P；var VI,V2Real；function fmIntegerBoolean；begin end；beginfv=f〃第一类对象end；beginP;Writein fv0；endP把局部函数抽象f赋给全局函数变量fv执行P后引用fv0时等于间接引用f0然而,此时VI,V2均已失去定义，fv0的返回值成了悬挂引用把局部函数值作为返回值产生的这类引用，在函数式语言把函数作为第一类值时悬挂引用尤其严重所以ML,Miranda采用的方法是把所有变量作为堆变量处理，且不提供强行KILL指令所以在程序块启动结束时，只要直接或间接的引用变量还存在，那么每个变量就继续有效但存储空间利用率就没有堆栈式分配有效了Algol68部分解决了悬挂引用问题对引用赋值作些限制，引用局部变量不赋给比它生命长的变量在对抽象的赋值方面也作了相应限制但实施这些限制是增加运行时的检查增加了开销°变量更新
4.4有了变量的存储我们接着讨论这些存储里的值如何更新变量更新实则是把存储看作一自动机其中状态以共值表征有了改变存储对象更新只有两个途径赋值和初始化也可以用程序运行作界线划分为静态赋值初始化和动态赋值
4.1变量初始化
4.变量分配了没有定义就使用，是程序错误主要来源之一为此早期曾有自动赋初值的做法，即分配了一律赋初值3或某个可区分的位模式事实证明，它不是个好办法，不显式赋初值带来查错困难，再者除数值变量而外，其它类型初值约定也易产生误解变量显式初始化由程序员在变量声明中给出许多语言都有初始化子句以下举出FORTRAN和C两个例子例4-6FORTRAN初始化声明CHARACTER*3EOFLAGDIMENSION A8DATA EOFLAG,ISUM/NO,0/AI,1=1,8/
8.2,
2.6,
3.1,
17.0,4*
0.0/FORTRAN赋初值在DATA语句中完成，用一对‘〃’区分，先写变量再写初值，交替表示按位置对应，AI,1=
1.8是循环表达的数组元素，甚至可以写出更复杂的嵌套循环后面的值是与元素出现次序一一对应的，多个相同连续值用n*表示句中ISUM为隐含声明的整变量例4-7C的初始化声明static charend of_fi1e_f1ag[]={no”}；int isum=0；static floata
[8]={8,2,
2.6,
3.1,
17.0}；这是和上一个FORTRAM例子一样的初始化C语言字符数组第一行的长度可由初始化值表达式长度定第三行只赋了半数初值，也按位对应，其余自动为0C称后者为初始化符initializer,由字面量、常量、常量表达式构成表达式在编译时求值只要复合变量中一个域元素初始化，所有域都要初始化唯一的偷巧是自动为零C语言设计者认为FORTRAN初始化，有不必要的灵活性它们比FORTRAN简单直接FORTRAN有复杂的嵌套循环只能在装载后运行前完成另一个现代风格初始化例子见前述例3-4现代语言支持堆栈式嵌套结构的初始化ANSI C,C++,Ada,即给自动变量初始化，在编译和初装时是无法完成的因为这个堆栈框架还没生成于是由编译算出表达式存在某个地方，并生成儿个装载指令，待帧生成后装入老C版本是不支持这种自动数组初始化的概念上还属于静态初始化
4.
4.2动态更新赋值是以表达式的值强行置换存储对象中的内容正因为如此，才有一个存储对象在不同的时间代表不同的程序对象，这是命令式语言造成语义复杂和混乱的根源我们称强行赋值为破坏性赋值Destructive Assignmento1简单赋值与聚集赋值单个变量、数组元素、记录成分值的改变即通过简单赋值它不涉及新值只涉及两个对象一个引用在赋值号左边，一个值或有值对象多数语言只允许简单赋值，初始化中静态聚集赋值我们已介绍过了近代语言几乎都扩充了动态聚集赋值但仅限于同类型复合变量之间例如，ANSIC中有:typedef struct{int age,weight；char sex；}person；person a,b={10,70,M}；//b有初值，a没有a=b；〃动态聚集赋值，a也有了•••2通过函数赋值除了强行赋值之外，如果通过READ例程把待赋值变量作为返回参数也能实现赋值此时引用作为参数，值由输入介质提供READ实现一系列动作完成赋值，没有返回值在这个意义上，READ仅仅是过程，不是求值的函数然而，真有一些语言赋值按函数实现LISP及所有函数式语言，APL,C就采用函数赋值例4-8C语言赋值的函数实现ttdefine MAXLENGTH100float ar[MAXLENGTH]；int high_sub,num_elements；high_sub=num_element s二MAXLENGTH-1；最后二行=号】□同一般运算符是中缀函数名，前后两个操作数是参数，它返回一个值就是num_elements的值正因为如此，它可以出现在表达式之中LISP的‘赋值’函数是replaca,replacd,返回值是对参数的引用以下将常见语言赋值实现列表如下语言赋值号聚集赋值多重赋值实现机制COBOL MOVE语=在COMPUTE语句中句ADD,SUBTRACT,MULTIPLY DIVIDE可可FORTRAN可*二ALGOL PL/1否*否FORTH可Pascal Ada否1否•否•返回结果函数replace,replaced某些版本可LISP APL•一C1973ANSI C表常见语言赋值的实现机制4-1其中多重赋值指形如a=b=c=
3.0的连接赋值C语言是允许的既然函数可以动态地改变值，则函数式语言每当有破坏性赋值时就用参数束定的函数调用替代每当要把一个计算值存入变量时，函数式语言则把该值作为参数传递给函数赋值例程或函数体内的动作继续以嵌套函数实现，这样就避免了变量参数束定在一个例程入口和出口的语义是不变的因而是可以得到语义清晰的语言有副作用的表达式
4.5我们把赋值V二E称之为赋值命令也就是语句，它对表达式E求值，并以该值强行更新V中的原有值一般表达式在求值过程中是不会更新其中操作数的值的，它只引用各操作数的值它更新的是赋值号左边的值如果E是一个复合的表达式会怎样呢？例如，其中一个子表达式是函数引用，在对E求值时必然要将此函数执行一遍函数体中显然又有许多声明和赋值语句，因此，除了求出函数返回值之外，其中的赋值语句更新了函数体中的变量也就是除了求函数值的主要作用而外，也起了更新变量的副作用side effect如果只更新了函数局部变量，下次求该函数值时并没有影响，如o果更新了全局变量，就会影响到其它表达式求值，这就难于控制了
4.
5.1块表达式块Block是嵌套在程序中的局部程序，由封闭的声明和语句集组成如果表达式包含的子表达式是一个声明或定义，该表达式即为块表达式前述函数引用是隐式的块表达式，函数体中既有声明又有语句如果该函数没有副作用则与变量引用无异，如果有则以块表达式看待有些语言具有显式块表达式，如ML例4-9已知三角形三边a,b,c的长度求三角形的面积let vals=a+b+c*
0.5in sqrts*s-a*s-b*s-cencl抽象形式是let Din Eend,其中D是说明E的表达式，一起叫块表达式D的作用仅限于说明Eo
5.2命令表达式
4.如果没有声明，块中只有命令，嵌入到表达式中则为命令表达式，c语言有显式的命令表达式例4-10C语言读字符常见的表达式c=getchar!=E0F该表达式求真值，若C中读入是EOF,本表达式求值为0假其它字符时值为1真子表达式c二getchar是赋值命令故本表达式是嵌入了命令的表达式这个getchar肯定是有副作用的因为两次同样无参调用可得出不同的字符从当前读的位置移到下一个字符位置就是副作用，但这个副作用正是C程序员希望的块表达式和命令表达式都是具有副作用的表达式，我们扩充它们无非是希望它的副作用能增强表达能力，事实上有了它们程序清晰可读，如上面的例子ML没有全局量不会有什么坏的副作用C语言就靠程序员保证了小结
4.6•程序变量具有时、空特性，故引入存储对象概念它既是程序对象的实现又是独立的存储体•变量名字编译后成为地址码，将此码存放在存储对象中，该存储对象对应的程序对象叫引用（C++）,引用变量是该变量的别名指针可以存放任何程序对象的地址，由程序员操纵•通过指针变量引用程序对象的值叫递引用•变量有分配、未分配、除分配，定义、未定义、失去定义的因时而变的状态•存储模型有两大类静态存储和动态存储静态存储在运行前分配变量的存储，动态存储在运行中分配和除配动态存储模型又分两类堆存储和堆栈存储•堆栈存贮，堆存贮模型是单今多数模块语言模型•存储对象是有其生命周期的一般局限于生成该存储对象所在模块的生命期程序员可显式控制存储对象的生命期，在一模块内使用多生命期对象，以程序运行周期为准，大于此周期为持久变量，等于为全局，小于为局部，局部尚可内嵌局部除持久对象外其余随程序运行终止而销毁，均为临时的•静态存储对象一般由编译分配后在整个程序执行期间不会改变全局的、外部的变量均静态对象也有语言将局部变量定为静态的动态存储对象往往取决于输入值和程序执行情况无法在编译时确定所需存储，只能动态分配/除配堆栈式管理和程序模块执行自然相适应，且天然支持递归，高效堆式管理自由方便，存储利用相对耗费大多数语言是两者相结合指针对象一般是堆对象•显式除配操作易引起悬挂指针，外块指针指向内块对象也易引起悬挂悬挂指针是程序出错根源之一一般认为命令式语言有三大害任意的got语句、悬挂指针、函数副作用，本章涉及一个半函数副作用第6章还要讲•程序中变量更新只有两个途径:赋值和初始化赋值通过赋值命令或调用读例程调用例程或函数是避免破坏性赋值重要途径是函数式语言得以发展的原因•当今语言赋值有按赋值命令模型有按函数调用模型C语言按函数模型故有赋值命令出现在表达式中的命令表达式•如果一个程序块（分程序）嵌入在表达式中则称块表达式函数体是块表达式，嵌有函数引用的表达式是隐式块表达式，ML有显式块表达式•如果块中只有命令没有声明即为命令表达式扩充它们是为了扩大表达能力，但也会带来副作用，故称有副作用的表达式•好的函数副作用使程序简单清晰，一旦放开了函数副作用又易产生难调易出错问题这取决于语言设计的宗旨但目前所有命令式语言都有一定程度的的函数副作用习题
4.1一般变量和指针变量有何不同？引用类型变量与它们又有何不同？答在寻址对照表中，一般变量对应的地址码即为该变量值的存储单元，而指针变量对应的地址码则为该指针所指向的存储单元的地址引用型变量与指针变量的区别在于它是常指针，一旦对照表建立，也就创建了引用，不可改变引用是变量的别名，但它必须赋初值
4.2C语言中数组名的含义是什么，当把数组的地址赋给某指针时是否要用算符，为什么？答C语言中的数组名可以看作是一个指针变量名，它代表数组元素的首地址但其值不可改变，这一点与引用型变量有些类似当把数组的地址赋给某指针时不用运算符，因为数组名本身就是指向数组首地址的指针
4.3现今语言有静态数组、动态定义数组、可变长灵活数组，试说出它们的定义，并举出哪种语言采用它的例子一个语言也行
4.4找一个你所熟悉的语言所写的程序，指出哪些变量应用静态实现？哪些动态实现？该语言真是这样的吗？
4.5试总结存储对象生命期有哪几种，C语言与此对应各叫什么变量？
4.6何谓运行时堆栈？堆栈帧？堆？答运行时堆栈是在内存开辟一个空间，如同堆栈首先将程序代码和全局静态变量装入在执行控制开始时首先执行这一块；当执行调用时，按编译时生成的嵌套关系，结合动态链和静态链来增、减堆栈帧堆栈帧是指在运行时把每次调用所需的数据作为一帧，并包括返回地址、动态链、静态链、返回值和局部变量，压入运行堆栈栈顶当对应的子程序执行完毕，该帧失去定义可为新调用覆盖堆是内存中预留的一片自由空间，当程序在运行过程中需要动态分配空间时;由操作系统从堆中按照一定的算法分配所需的变量的存储空间
4.7堆栈帧中设静、动态链两项的意图是什么？
4.8设计一个程序输入随机的一千个职工记录用悬挂指针的方法，按姓名的字典序，年龄由小到大，按小单位名且姓名字典序，按工资多少由大到小各打印一个报告，即重排的原记录ttinclude stdafx.h〃ttinclude stdio.h〃iiinclude string.h〃struct crew{char name
[20];char unit
[50];int age;float income;crew*next;}*head;void sortbyname;void sortbyunitname;void sortbyincome;void sortbyage;void print;void main{int I;struct crew*p,*sav;head=new crew
[101];forI=0;I100;I++head[I],next=head[I+l];p=head;forI=0;I100;I++{scanf，z%s%s%d%f，z,p-name,p-unit,p-age,p-income;ifI p=sav-next;sav=p;sortbyname;sortbyunitname;sortbyincome;sortbyage;}void sortbyname{int1=0,j=0;crew*tmpl,*tmp2;while K100{for j=I+l;j100;j++ifstrcmphead[I].name,head[j].name0{tmpl=head[I];tmp2二head[j];head[j-l].next=head[j+1];head[I-l].next二tmp2;tmp2-〉next=tmpl;}I++；print;}void sortbyage{int I=0,j=0;struct crew*tmpl,*tmp2;whileKlOO{for j=j+l；j100;j++if head[I].agehead[j].age{tmpl=head[I];tmp2=head[j];head[j-1].next=tmp2;tmp2-next=tmpl;I++；print;void sortbyunitname{int1=0,j=0;struct crew*tmp2;forI=0;I100;I++forj=I+l;j100;j++if strcmphead[I].name,head[j].name0{tmpl=hcad[I];tmp2=head[j];head[j-l].next=head[j+1];head[I-l].next=tmp2;tmp2-next=tmpl;}for99;I=0;I—forj=I-l;j=0;j—if!strcmp head[j].name,head[I].name0{tmpl=head[I];tmp2=head[j];head[j-l].next=head[j+1];head[1-1].next=tmp2;tmp2-next=tmpl;}print;void sortbyincome{int1=0,j=0;crew*tmp2;whileI100{for j=j+l;j100;j++if head[I].income head[j].income{tmpl=head[I];tmp2=head[j];head[j-l],next=head[j+1]；head[Il].next=tmp2;tmp2-next=tmpl;}I++；print;void print{int1=0;for I=0;K=100;I++{printf，，%10s%10s%10d%10d，/,head[I].name,head[I].unit,head[I],age,head[I],income;printf〃\n〃;
4.9全局变量可不可以动态生成，为什么？
4.10设计一个具有悬挂引用的程序见例4—
44.11如果一个语言只支持静态存储行不行？如果只支持动态存储呢？如果都行则指出它们的优缺点按第2章语言设计准则列表说明
4.12想一个办法上机测试C语言寄存器变量、宏变量的生命期，按本章讲述它是静态还是动态的？是局部还是全局的？是临时的还是持久的？
4.13C语言数组和Pascal数组有什么不同可以用函数映射来描述C的数组吗？如果可以又怎样描述
4.14试用汉语写出扩充某个语言具有无用单元收集功能的需求，并给出初步实现原理
4.15指针变量如同语句中的goto,愿意指谁就指谁，没有章法，goto的问题已用结构化解决了，你能想出有效管理指针的方案吗，至少要谈出途径解悬挂引用主要是指指针指向一个已死的或无定义的对象主要出错情况有两种
1.未给一个指针变量分配空间就给它赋值；
2.函数返回局部变量指针解决方案
①在对指针实施运算的地方，检查指针变量是否已赋初值，即指针变量是否已指向合法位置
②在对指针变量赋值的地方，检查指针变量是否先前已指向其他合法位置，避免悬挂引用
③在对指针变量赋值（特别是数组）时，记录其“元素”的个数，以便能在其后的操作中检查是否越界
④在对指针变量赋值的地方，记录引用对象已被哪些指针指向，为此引用对象被除时，提出编译警告，告许程序员哪些指针已悬挂
1.116用图解方式说明
4.
2.
5.2节中以一个自由表、多个自由表处理死堆对象的全过程
4.17函数式语言变量更新是如何实现的？为什么它没有副作用？
4.18试述语言赋值采用函数赋值机制的优缺点int*p,*q;*p=i;〃P指向整变量iP=i;〃错误，p中只放地址值p=i;〃正确，效果同*p=i,取地址符q=p；〃正确，同类型赋值，q,P都指向i*q=*p+1；//q指向i,此时i已成为i+1q=p+l；//l仅是名，值取决于所指对象每个单元占多少字节所谓寻址即要给出编译或解释时程序变量名与地址的对照表每当给程序对象分配存储时就在表中填入，这样就创建了引用reference由于程序对象名字编译后不存在，每次操纵用的是地址，这个在对照表中有的地址即为该对象的别名早期语言认为这是属于‘内部的事，外叫‘变量，内叫地址码而C++语言把这个占据存储的存储对象也上升为程序对象，叫做引用，使用户直接操纵引用A136P2指针P1316RB448450B140320RC136144C1441———1361—140——144—
3312.
274274.
54607.01A B0地址引用，指针、变量关系的示意图如图4-1图4-1变量、指针、引用示意图312RA变量A的地址码分配为136放在312中，每当程序中用A的左值，查出136即是，若用A的右值查到136再找136的内容既然312也是存储单元地址，则把它对应为一引用名RA只是一旦给出136再也不许改变，它成了A的别名，相当于常量指针指针Pl,P2既是程序对象，它们被分配在448,450存储单元内，地址码448,450同样成为Pl,P2的代替物如果在448中给予136地址则P1指向A给140则指向B其内容是可变的,所以和引用RA不一样RA虽然也放一个地址，但更强调的是引用内容即当RA,A同时出现在赋值号右边，其效果完全一样，这一点和常量指针又不一样它和变量A不同之处仅在实现上，效果是相同的，而且引用‘变量必须赋初值，一旦赋初值则在其作用域在其所在程序单元的范围内不得改动C++和C引入引用主要是用于函数调用的传地址形、实结合正好相当于引用变量赋初值这在第6章中还要讲递引用一般说来，通过指针变量引用某变量的内容叫做递引用dereference多层指针则多次递引用指针用‘t或显式地表达了它的递引用但多数程序设计语言都有隐式的递引用例如，下标表达式，除了引用下标变量值再引用该元素的值，即使出现在赋值号的左边的下标表达式也是递引用我们称这是自动递弓I用FORTH语言是唯一不容许自动递引用的，它只有显式递引用运算符皿例4-2FORTH的递引用运算符@
[1]13VARIABLE xx（声明变量xx并赋初值13）
[2]0VARIABLE Y（声明变量Y并赋初值0）
[3]xx@2*Y!（相当于Y=xx*2）如果只写xx2*则为将xx的地址乘以2放在Y之中
4.
1.3变量的时态除了空间名值分离导出指针、引用、递引用程序世界的概念之外，变量还有时间特性，以它的状态刻划
（1）.分配/未分配/除分配为程序对象分配存储就创建了存储对象，程序对象就可以访问了如果在编译时做这个工作我们叫静态分配，程序中变量多数如此如果在程序运行时刻分配存储，我们叫动态分配,程序中的指针（或访问）类型变量则按动态分配，一般由程序员显式指定（用new操作）若程序对象声明了但未分配存储对象即投入运行，此程序对象处于未分配状态撤消程序对象即除去已分配的存储对象，我们叫除分配或除配（deallocate）除分配可由程序员显式指定（用delete操作），也可以约定由语言的执行系统或操作系统自动实现自动将当前无用的程序对象除配，并收回待用称无用单元回收（Garbage collection）机制动态（或无）类型语言一般有此机制，静态类型语言虽然也有动态分配部分，往往不设此机制（如C语言）
（2）.定义/未定义/失去定义分配的存储单元总是有残值的（上个程序运行后留下的），这些值无任何意义（与本程序无关）我们说，变量未定义如果通过赋值或赋初值，就是定义变量，除了它的值对本程序计算是有意义的如果该变量执行超出了我们指定它有意义的区域（例如，一个局部块的末端），只耍它的存储没有撤消，它总是存在，但其内容（值）已失去定义以下举例说明例4-3变量的状态（Ada）procedure MAINis declareBLOCK；type CELL；type LINKis accessCELL；type CELLis recordVALUE:INTEGER；NEXT:LINK；end record；type VECTORis arrayINTEGER rangeof FLOAT；LA:LINK；--声明访问类型变量LA,但未分配V:VECTOR；--声明数组类型变量V,未分配VB:VECT0Rl..5；--声明数组类型变量VB,运行前已分配但未定义begin LA:=new CELL；--动态分配无名CELL对象由LA代名LA.all:=3120,null；--定义LA所访问对象V:=l=5,0,2=
4.0；3二〉
3.0,--分配V为六元素数组，且得到定义，动态完成4二2,0,5=
1.0,6=
0.0--只有VB⑶得到定义，VB的其余元素未定义VB3=Vl；end BLOCK；L-LA；--LA值已失去定义，出错--V,VB3的值均失去定义-Ada有无用单元收集，此处可将失去定义的变量存储回收end MAIN；可存储值就变量访问和更新而言，我们把可以直接访问和更新的存储对象的值称为可存储值storableo它们是可访问的最小存储单元因此，复合值如果它们的成分不能选择更新，该复合值即为可存储值例如，Pascal的集合值，不能单独更新其中某个元素，它是可存储值反之，数组元素是可以选择更新的整个的记录、文件也都不是可存储值所以，Pascal中可存储值是•基本类型值•集合值•指针值变量引用、函数过程抽象也不是可存储值，它们本身不是可存储的C++语言设置了引用类型变量，变量引用有了名字，它是可存储的ML的可存储值有•基本类型值•记录、构造、表•函数抽象•变量引用ML的记录、构造、表是可存储值，因为它们不能选择更新，更新其中一个元素存储要重整一遍由于函数抽象和变量引用全部采用类似C++引用类型的办法，借助于引用可以有选择地更新复合值事实上除数组而外，ML所有的值均为可存储值例4-4ML的函数抽象是可存储值函数名即函数抽象，在Pascal中，fx的f是不能单独存取和更新的，ML中却可写为if expthen sinelse cosx这个条件表达式的返回值sin或cos是函数抽象,sinx是函数定义，也叫型构signature,sina是函数引用后二者都不是可存储值组织存储对象的存储模型
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语言叫自动变量）是静态（编译时）分配的，运行时存贮的地址可变3动态存储对象
4.
2.动态存储对象在程序执行期间诞生（分配和定义），故名动态多数动态对象它们的大小和结构形态往往依赖输入，编译时无法确定例如，递归定义的二叉树，其结点、叶子、层数完全由输入值定因此，动态存储对象生命期长短不同，大小不同，类型各异，如何使存储管理高效是一个中心问题管理不好对程序执行的时、空效率影响极大在某种意义上说，它是发展先进语言或软件技术的关键例如，Prolog.Smalltalk出现初期都是执行效率难以和传统语言匹敌的，慢5-30倍不断改进才能进入实用影响最大的因素是动态存储对象的生命期,而不同生命期存储对象搭配使用，恰巧是增加表达能力，减少程序错误的进步所以一般语言提供管理不同的生命期对象的模型最简单的模型是在内存中开辟一个堆（heap）空间，放入其中的动态对象的寿命完全由程序员控制，语言系统全然不知每当创建一新存储对象，存储管理则找出一个足以放下该对象的堆空间每当存储管理得知（出了所在程序块）它已死亡，它就记下该对象不再使用随来随堆，谁死谁释放，新来的没地方就等到老的死了再存入，故名堆一般的指针动态生成的对象即按此型式，故指针变量也叫堆变量管理堆型式最大的问题是多次存储后留下存储碎片，因为新对象的大小往往不能填足老对象的空间，时间长了形成星星点点的许多“小洞”，管理很麻烦拿出记录该碎片信息所费存储比这些“小洞”本身小不了多少，而且运行时一个到一个链接十分低效再者还没有能找出合适的识别算法将“小洞”合并这些问题各语言系统都采取了各自的做法本节将介绍主要做法由于堆型式管理存在着麻烦，人们寻求并得到第二种管理型式嵌套生命期型式，按照这种型式任何两同时出现的对象其生命期长短可以不同，但必须完全嵌套，即不能交错也就是在时间上一个包容一个，我们就可以把相近寿命变量归成一组,最长寿命组放在堆栈的底部，最短的在顶部，逐级释放和重新占据存储，可以得到成片干净’的存储如图4-2所示本例依次分配了6组不同寿命的存储块由于块6中对象寿命最短，全部重新分配3次，块4,块5可重新分配两次…而块1的一次生命期还没完如同倒下来的堆栈，栈顶的对象生得快死得也快，死了清除再分配第二批而栈底的对象一直活着事实上，动态对象寿命长短本来就和所在嵌套模块相关，只要把寿命特长的（如文件，全局量）排出来归到栈底的某一组，把寿命特短的（如循环控制变量）另立嵌套组，这个分组的问题也就解决了4动态堆栈存储
4.
2.按照嵌套生命期存贮原理，对于嵌套块结构的程序设计语言如（Pascal,Ada,C）动态堆栈型管理特别有效，因为多数变量和所在块寿命一样长变量生死随所在块的激活和消亡高效自动实现所以C语言把局部于块结构的变量叫做auto（自动）变量但多数语言（包括C）堆、堆栈管理同时并用（原因见后文）
4.
2.
4.1动态堆栈式管理机制为了说明堆栈式管理，我们再参照图4-2运行时堆栈，结合执行过程，介绍其实现机制，如图4-3所示参.数返回地址（首先调用块:二二动卷锭二二:堆栈帧第二二调用块静态链返回值堆栈帧……扃就变量’…一栈顶最新调用块\/片堆栈帧程序代码栈顶\临时变量空间,全局静态存储堆栈帧组织运行时堆栈图4-3运行时堆栈和堆栈框架实现运行时堆栈（Run-time stack）是在内存开辟一个空间，如同堆首先将程序代码和全局、静态变量装入，示意为图4-3的右图最上一块这一块的词法上辈（Lexical Parent）是操作系统当执行控制开始时，首先执行这一块，当执行到调用时，按编译时生成的嵌套关系，找出被调用的块，将该块的数据（包括实参和局部量）作为新的一帧，记下静态链（连接词法祖先（Lexical ancestor））,压入运行时堆栈后记下动态链（连接执行顺序）由于编译时词法祖先块的地址无法确定，静态链要根据祖先块分配存储对象去找，有时要用到局部变量和参数动态链指出当前块的动态执行的上辈，以便在块出口时弹出栈内的执行指令动态和静态链在压入栈时利用局部分配指针从栈中第一个‘自由位置逐个向上（下）分配，记下该指针的值，以便以后弹栈每个堆栈帧（stack frame）的组织如图4-3的左图，它按以下事件序列压栈
[1]调用程序将实参值置于新块底部，用局部分配的指针，一般说，最后一个实参先放入，倒数第二个第二…第一个放在最上面
[2]接着放入新块的返回地址
[3]把当前栈顶指针值拷贝到栈内，这是新块动态链的一个域（存放当前栈顶地址）
[4]填写静态链，将编译时生成的标记码拷贝进来，对于调用块静、动态链标记是一样的
[5]再留足够的位置以放下局部变量的返回值，如已有初始化则拿来就可以了
[6]控制转回父块代码执行，直至到生成另一个内嵌块的堆栈帧，如此，运行堆栈又生成一层…如果某块对应的程序代码出口则根据动态链返回父块，再生成复盖的新的一层堆栈帧…老块被复盖也就是除分配了此处为了简化，返回值假定在块内，实际上常用寄存器
4.
2.
4.2用堆栈式存储实现递归显然，递归调用是堆栈存储管理最简单的形式因为它的运行栈每次压入的是同一模块新的数据对象版本，静态链自然按逐层递归调用展开直至到达边界，现举例说明例4-4Pascal的递归函数求整数之连乘积function productjjIntegerInteger；var kkInteger;beginif jj=0then product:=1else beginreadlnkk；product:=kk*product jjlendend；其执行图示于图4-
4.为简化令jj=2,读二次kk二25,7oDL:动态链product函数SL:静态链目标代码\/—ZDL最初调用时堆栈帧jj2return:—J.nr___rjj:l第一次调用时堆栈帧return:—kk:7第一次调用时堆栈帧J,J Oreturn:k:-J栈顶图4-4递归函数的堆栈帧5动态堆存储
4.
2.动态堆栈存储虽然解决了碎片问题，但是存储对象寿命只能和堆栈帧同时生死，限制太严而且在每一个块的进口处并不知道存储对象的大小和个数，以及要求存储对象比创建它的块的寿命长所以堆存储有时是必不可少的我们再详细讨论堆存储
4.
2.
5.1堆分配许多语言允许程序员显式分配动态存储，分配语句可以出现在程序中的任何地方，办法是调用操作系统ALLOC函数ALLOC将存储对象分配在堆中并返回对该对象的引用如前所述堆分配有时在连接的较小的空间上，算法比较复杂所以要建立一处自由表登录已死存储对象的空间，并查清相邻的碎片予以合并这些算法还必须高效，否则影响性能故往往是折衷，追求快速牺牲一些过小碎片这又是潜在危险，当指针错误地指向这些无用小碎片时，后果极难预料各个语言组织动态堆及分配后的返回值也不完全一样现例举说明1FORTH的堆分配/除配•分配HERE〈表达式〉ALLOTFORTH在存放符号表和全局对象的字典中作动态分配HERE是系统变量，程序员通过HERE访问字典顶端指针先把HERE的当前值放入堆，然后对表达式求值得一整数N,ALLOT将N个字节加到字典指针另设一小栈记下新增区域存入，用户只存入指针变量•除配无无用单元回收重新分配由用户自己写例程2LISP的分配/除配•分配cons〈表达式1*表达式2见到这个表达式就分配一新表，并返回对新表的引用新表左域由表达式1的值填入，右域用表达式2的值填入•除配由无用单元收集机制自动完成3C的动态分配/除配•分配malloc sizeofTmallocNcallocN,sizeof basetype式中T、basetype是类型名，N是整数第1式是分配T类型的一个对象；第2式是N个字节；第3式是分配一个数组，类型为basetype,元素是N个，并初始化为0malloc和calloc均返回对新对象的引用程序员必须将返回值赋给某个指针类型或强行转成所希望的指针类型•除配free ptrptr必须指向已分配过的堆对象该对象经此函数即可重用再分配4Pascal动态分配/除配•分配new〈指针名〉〈指针名》必须是声明为指向某类型的指针该指针存放引用返回值•除配Dispose〈指针名〉〈指针名》所指对象置入自由表5Ada动态分配/除配•分配new〈TYPE〉〈表达式〉分配一TYPE类型的对象，如果提供了可选表达式，对它求值并用以初始化该新对象，new是函数返回对新对象的引用该返回值程序员应赋给ACCESS类型变量即指针•除配有无用单元回收，显式除配一般不用，而是所在块执行完自动完成
4.
2.
5.2死堆对象处理死堆对象叫无用单元或垃圾garbage堆对象死亡是当它引用的对象已失去定义即出了创建该对象的块，我们称这种死亡是自然死亡强行用或类似操作系统KILL命令也能显式使之死亡自然死亡一般程序员和运算支持系统都是察觉不到的，不知不觉在一个未知的地方留下垃圾KILL命令在除配之后将该对象的引用地址置入自由表在语言中实现KILL并拿出大量存储以便追踪，一直存在着很大的争议回收死堆对象的存储比堆存储复杂得多死堆对象往往不在堆的末端而在中间，简单地。
个人认证
优秀文档
获得点赞 0
