刚学编译原理的时候我最头大的模块就是运行时存储空间管理尤其是其中的变量访问环境。教材堆了一堆术语——过程活动记录、动态链、访问链、显示表——每个字都认识连起来就看不懂。后来自己对照汇编逐步调又动手写了个C方言小编译器才真正把这部分打通。这篇博文就按我自己的学习路径整理一遍先讲清楚运行时存储空间管理到底在管什么、过程活动记录长什么样再重点拆解变量访问环境里的两条主线——局部变量怎么访问、嵌套过程里的非局部变量怎么访问最后聊参数传递和过程作为参数时的环境问题。正在学编译原理、准备编译器方向面试或者想弄明白JavaScript闭包底层原理的人这篇能帮你一次性把这些概念串起来。1. 运行时存储空间管理到底在管什么1.1 程序运行时的内存长什么样写代码的时候变量是一个抽象的名字程序跑起来之后每个变量都要落到真实的内存地址上。运行时存储空间管理的第一个任务就是决定这些变量各放哪里、怎么组织、怎么回收。按经典的进程内存布局一块虚拟内存空间大致分成四个区域代码区、静态数据区、栈区和堆区。代码区存放编译器生成的目标指令。它通常是只读的程序执行时从这里不断取指令。静态数据区存放全局变量、静态变量、字符串常量等。这些变量的地址在编译期就能确定整个程序生命周期里一直存活。栈区存放目前正在执行的过程函数的活动记录。每个过程调用发生时就往栈顶压入一条记录过程返回时弹出。栈在主流x86-64体系上通常向下增长也就是从高地址往低地址长。堆区存放动态分配的数据比如C语言里malloc、C里new出来的对象。堆一般向上增长和栈相向而行。把这几个区域想清楚很多初学者常见的困惑就消失了。比如有人问全局变量和局部变量的区别到底是啥从存储管理角度看区别就是全局变量在静态区、地址固定、生命周期是整个程序局部变量在栈上、地址是运行时算出来的、生命周期是当前过程这次调用的期限。1.2 为什么过程活动记录要放栈上栈这个数据结构天然匹配过程调用的嵌套特性。一个过程一旦调用了另一个过程被调用的过程必须先执行完并返回调用者才能继续往下走。这个最后被调用的过程最先返回的规律正好是栈的后进先出特性。想象一个调用序列主程序调用AA调用BB调用C。C返回B返回A返回。程序的执行轨迹就是一层层套进去、再一层层解出来。每层套进去时栈顶多一块活动记录每层解出来时栈顶少一块活动记录。这个过程完全不需要额外管理压栈弹栈的开销极小。栈还有一个重要优势递归调用时同一个过程的多个活动记录可以同时存在于栈上互不干扰。比如计算阶乘的fact函数递归调用5次栈上就有5份fact的活动记录每份里都有自己独立的参数n和局部变量。这就是变量局部性在运行时最直观的体现。每个调用实例看到的n都不一样但编译器生成的目标代码只用一套区别只在于当前访问的是哪一份活动记录。1.3 堆区为什么不能替代栈区可能有人会问为什么不把所有过程局部变量都放堆里现代语言的闭包不就这么干吗放堆当然可以但代价很大。堆的分配和回收通常比栈复杂得多分配时可能有空闲链表查找、内存碎片整理回收时可能有垃圾回收器介入。而栈区的分配就是一条指令——把栈指针减去一个偏移量释放就是加回去几乎零成本。所以经典编译器处理局部变量的默认策略是尽量放栈上。只有那些在过程返回后还需要存活的数据比如逃逸的闭包环境才考虑提升到堆上。这个判断在编译原理里叫逃逸分析。2. 过程活动记录一个过程调用的一份“档案”2.1 活动记录里到底装了哪些东西过程活动记录Activation Record简称AR也叫栈帧。它就是一次过程调用在栈上的全部私有数据。不同编译器实现的AR布局不完全一样但核心成员通常包括这几块。返回地址过程执行完之后CPU回到哪里继续执行。通常是调用点下一条指令的地址。动态链Dynamic Link保存调用者的帧指针fp值。它把当前AR和调用者的AR串起来形成一条谁调用了谁的链过程返回时靠它恢复现场。访问链Access Link保存静态外层过程的最新AR地址。支持嵌套过程的语言需要它来访问非局部变量像C这种不支持嵌套函数的语言AR里可以没有这项。参数区存放调用者传入的实参。有些调用约定用寄存器传参但编译器通常会把寄存器参数再保存到AR的统一位置方便后续统一访问。局部变量区存放过程内部声明的局部变量。临时变量区存放编译生成的中间结果比如表达式求值时产生的临时值。这里最容易被误解的就是动态链和访问链。动态链跟着调用历史走访问链跟着词法定义结构走。两个链在大多数情况下指向不同的位置这两个概念的区别是整个运行时存储管理的核心之一后面我会专门展开。2.2 活动记录的一生从入口序列到出口序列一段过程调用在汇编层面长什么样我直接用一个add函数来看。假设有C代码int add(int a, int b) { int c a b; return c; }用x86-64 GCC编译不优化时函数的开头和结尾大概长这样# 函数开头也叫入口序列 prologue pushq %rbp # 保存调用者的帧指针到栈上这就是动态链 movq %rsp, %rbp # 把当前栈顶设为新帧指针 subq $16, %rsp # 给局部变量和临时变量分配16字节空间 # 函数体... movl %edi, -8(%rbp) # 把寄存器参数a保存到栈上局部区 movl %esi, -12(%rbp) # 把寄存器参数b保存到栈上局部区 movl -8(%rbp), %eax # 读取a到eax addl -12(%rbp), %eax # 加上b结果在eax movl %eax, -4(%rbp) # 存到局部变量c的槽位 movl -4(%rbp), %eax # 把c的值作为函数返回值放到eax # 函数结尾出口序列 epilogue movq %rbp, %rsp # 栈顶回到帧指针位置等价于撤销局部空间 popq %rbp # 恢复调用者的帧指针 ret # 返回地址出栈程序跳回调用点这里有两对关键指针栈指针sp汇编里是rsp和帧指针fp汇编里是rbp。sp始终指向当前栈顶压栈弹栈都跟着它走fp指向当前活动记录的固定基准点局部变量和参数的访问都通过它加上一个编译期算好的偏移量来完成。上面代码里的-4(%rbp)就是通过fp偏移访问局部变量c-8(%rbp)是参数a-12(%rbp)是参数b。为什么非要用fp而不直接拿sp偏移因为sp在函数体内会不断变化每压一次栈、调一次函数sp都在动。如果所有变量都基于sp偏移编译器必须精确跟踪每个时刻sp变化了多少非常麻烦。fp在函数体执行期间是固定的编译器只需要在函数开头设置一次后面所有访问都基于fp省心得多。这也是为什么调试信息里到处是rbp的影子。2.3 局部变量的访问帧指针加偏移局部变量在AR里的位置是编译期就能确定的。编译器遍历一遍语法树为每个局部变量分配一个在AR内的偏移量然后生成一条mov指令用fp 偏移量去访问。这里我加一句提醒很多初学者以为变量一定在内存里。实际上经过优化之后大量局部变量被分配到了寄存器里根本不进栈。寄存器是CPU内部的高速存储单元读写比内存快一个数量级编译器会想方设法把变量放寄存器。但有些情况变量必须要放到栈上变量被取地址x后续可能通过指针访问。变量是数组或者结构体寄存器装不下。变量被声明为volatile编译器不能随便缓存它的值。调试模式下关闭优化方便和源码行号对应。所以运行时存储空间管理并不等于所有变量都在栈上而是说栈是那些不能进寄存器的临时数据的默认归宿。看汇编时如果发现某个局部变量根本没出现在栈上不用奇怪它可能在寄存器里活完了整个生命周期。3. 非局部变量的访问访问链和显示表3.1 嵌套过程带来真正的麻烦如果一门语言只有全局变量和局部变量两种变量那运行时存储管理其实很简单全局变量用固定地址访问局部变量用fp加偏移访问完事。C语言就是这种模式所以学C的时候大多数人根本不会意识到变量访问环境是个需要专门研究的问题。但Pascal、Ada这类语言支持嵌套过程定义。内层过程可以访问外层过程的局部变量。这种能力在词法分析、语法分析阶段没什么问题一个变量引用是声明在哪一层的编译期就能算清楚。真正难的是运行时怎么找到它。举个例子program Main; var x: integer; procedure A; var a: integer; procedure B; var b: integer; begin b : a x; // b局部a来自Ax来自Main end; begin a : 1; B; end; begin x : 0; A; end.执行到B内部时栈上的AR自底向上是Main、A、B。变量a在A的AR里变量x在Main的AR里。B的AR里没有它们直接拿fp偏移是访问不到的。而且A的AR在栈上的具体位置只有在运行时才知道——如果Main先调用A一次A返回后再调用A一次两次A的AR地址完全不同。这里的核心问题就是当前正在执行的过程如何访问到静态外层某个过程的局部变量这就要用到访问链或者显示表。在展开这两种方案之前先说清楚静态作用域规则。编译原理里定义嵌套深度主程序是0定义在深度0里的过程是1定义在深度1里的过程是2以此类推。变量x定义在深度0a定义在深度1b定义在深度2。当前过程深度为cur访问定义在深度d的变量需要从当前AR出发沿某种机制回溯到深度d对应的外层AR。3.2 访问链方案沿着定义链往上跳访问链的思路很直白每个活动记录里保存一个指针指向静态直接外围过程的最新活动记录。B的定义在A内部所以B的AR的访问链就指向A的ARA的定义在Main内部所以A的AR的访问链指向Main的AR。这个链不是调用历史链而是词法定义链。无论B是被谁调用的——哪怕是被一个和A同级的C调用——B的访问链都指向A的AR因为B在词法上定义在A里面。那么调用发生时访问链怎么建立设当前过程为p调用过程为qp深度npq深度nq。关键是找到q的静态父过程的深度也就是nq - 1。如果q直接定义在当前过程p里即nq np 1那么q的访问链就直接指向p的AR。比如A调用BB定义在A里B的访问链就是A的AR。否则需要从p的AR出发沿着p的访问链往前找。目标是找到深度为nq - 1的那个过程的AR。总共需要走的步数是np - (nq - 1)。举个具体的例子program P; // 深度0 var x: integer; procedure A; // 深度1 var a: integer; begin a : 10; end; procedure C; // 深度1 begin A; // C调用A end; begin x : 1; C; end.执行序列是P调用CC调用A。C的访问链好算C定义在P里nq1np0nqnp1C的访问链指向P的AR。A呢A定义在P里但它是被C调用的不是被P调用的。当前过程p是Cnp1q是Anq1。A的静态父过程是P深度0也就是nq-10。从C出发找目标深度0的AR需要走np-(nq-1)1步。C的访问链指向P的AR所以A的访问链也指向P的AR。这个结论对吗对因为A的词法外层就是P和C是谁无关。访问变量时也是一样的逻辑。当前过程深度是cur目标变量定义的深度是d需要走cur - d步访问链。在刚才那个Pascal例子中B内部访问a时cur2d1走1步访问链到达A的AR然后加a的偏移量就能拿到a。访问x时cur2d0走2步B的AR到A的AR再沿A的访问链到Main的AR再加x的偏移。这个方案优点是好懂、内存开销小每个AR只多一个指针。缺点是随着嵌套层数变深访问一次非局部变量要走很多步效率低。如果一个深度10的过程频繁访问全局变量每次都要跳10次指针才能拿到地址这在追求极致性能的编译器里是不可接受的。3.3 显示表方案所有深度一表打尽显示表的思路是不用沿链一个个跳了直接用一张全局表把所有深度的外层AR指针都存起来。这张表叫display数组一般是从0到最大嵌套深度。它始终维护着当前所有活跃层的最新AR指针。比如当前执行到深度3的过程Cdisplay[0]指向主程序的ARdisplay[1]指向A的ARdisplay[2]指向B的ARdisplay[3]指向C的AR。任何一级外层过程只要按深度索引查一下display立刻就能拿到它的AR地址。进入一个新过程q时display[nq]要被设置为q的AR。但同时原来的display[nq]里存的可能是某个还在等待恢复的外层同层过程的AR所以q的AR里必须保存display[nq]的旧值等q返回时再恢复。这就是显示表方案里保存/恢复动作的来源。用显示表访问非局部变量效率极高。访问定义在深度d的变量指令序列就是mov %display[d], %reg; mov offset(%reg), %target不再需要链式循环。无论嵌套多深开销都是常数级的。但显示表也不是没有代价。第一它需要在全局数据区维护一个数组并且每个过程调用和返回时都要处理保存/恢复。第二如果显示表实现不当频繁的过程调用会带来额外的内存读写。第三过程作为参数传递时环境指针的打包同样要考虑display的同步问题。从教学角度看我觉得访问链更适合建立直觉它把词法嵌套直接翻译成了指针链显示表则更适合理解空间换时间的优化思想。3.4 两种方案怎么选很多教材把访问链和显示表放在一起讲但没有说清楚选择依据。我总结一下我自己的理解。对比维度访问链显示表访问非局部变量开销O(深度差)嵌套越深越慢O(1)固定两三次访存调用/返回额外开销建立访问链只需一两条指令需要更新并保存/恢复display项内存开销每个AR多一个指针全局数组加每个AR可能保存的旧表项实现难度简单直观容易调试稍复杂但也不难典型应用教学编译器、嵌套层数浅的语言嵌套过程频繁访问外层变量的语言我记得早期有些Pascal编译器的实现就偏爱显示表因为Pascal程序里嵌套过程访问外层变量太常见了用访问链会让生成的代码包含大量的指针跳转循环。现代很多函数式语言实现采用了更激进的方案干脆把捕获的变量提升到堆上的闭包对象里按对象字段访问效率也不差。说到底没有放之四海而皆准的最优解只有适合当前语言特征和目标平台的折中。学的时候把两种方案都亲手模拟一遍比只看结论有用得多。4. 参数传递与过程参数的环境问题4.1 值传递、引用传递、值-结果传递的底层差异参数传递也属于变量访问环境的范畴。调用一个过程时实参的值或者地址是要放在新AR的参数区里的被调用过程再通过自己的fp偏移来访问它们。传值是最常见的。调用者把实参的值拷贝到被调用者AR的参数区被调用者把形参当普通局部变量用修改形参不影响实参。C语言默认这种方式Java的基本类型也是。传引用传的是实参的地址。被调用者拿到地址之后对形参的任何读写都直接作用于实参本体的内存单元。C的引用参数、C#的ref参数、Pascal的var参数都是这个模式。访问形参变量时需要多一次间接寻址先从参数区取出地址再根据地址访问内存。值-结果传递是一种折中过程刚开始时把实参的值拷贝到形参这像是传值过程返回前再把形参的最终值拷贝回实参。从语义上看它在过程体内完全操作自己的私有一份数据只是返回时把结果同步回去。Ada的out参数就是这样的思路。实现上编译器在参数区里通常会放一个指向实参的地址过程开始时按地址读取初始值返回时按地址写回最终结果。4.2 传名调用是怎么回事还有一个很特别的传参方式是传名call by nameAlgol 60里比较有名。它的做法是不计算实参的值而是把实参的表达式和它的求值环境整体传给被调用者。每次在函数体内用到这个形参都现场重新求值一次。最经典的案例是Jensens Device一段用Algol 60写的求和过程用传名参数一次性实现了微积分里那种把表达式代进去的求和功能。传名的实现机制就是生成一个thunk也就是一段小函数它知道怎么在原来的环境中计算实参表达式。被调用者的AR参数区里存的是thunk的入口地址和环境指针每次访问形参就调用一次thunk。传名的语义非常强大但也非常难以预测容易造成重复计算。后面大多数语言都放弃了它只在宏展开之类的地方保留了类似思想。学它主要是为了理解名字和值分离这件事一个形参名背后到底绑定的是什么求值时机是我们在编译器设计时必须明确的问题。4.3 过程作为参数传递为什么C的函数指针不需要闭包如果语言支持嵌套过程并且允许把过程作为参数传递就会引出变量访问环境里最绕的一个问题怎么把一个过程的环境一起传过去。假设有下面的Pascal风格代码program P; var x: integer; procedure A; var a: integer; procedure B; begin a : a x; end; begin a : 1; Apply(B); // 把过程B作为参数传出去 end; procedure Apply(paramProc: procedure); begin paramProc; end;当A调用Apply时Apply的AR里收到的如果只是B的代码入口地址等Apply执行paramProc去调用B的时候B的AR里的访问链该指向谁按正常的访问链建立规则当前过程是ApplyB定义在A里应该让B的访问链指向A的AR但Apply自己并不知道A的AR在哪。结果就是B内部的a : a x会访问到一个完全错误的地址。正确方案是把过程作为参数传递时必须同时传入口地址和环境指针。这个入口地址环境指针的组合就是现在说的闭包。Apply执行paramProc时用它收到的环境指针直接作为B的AR的访问链B内部访问a和x时才能找到正确的AR。JavaScript闭包就是这个原理。再看一个经典问题for (var i 0; i 3; i) { setTimeout(function() { console.log(i); }, 100); }输出是三个3不是0、1、2。原因就是三个匿名函数捕获的是同一个i的绑定、同一个环境循环结束时i已经变成了3。改成let i之后每次循环都会创建一个新的绑定三个闭包分别捕获各自迭代环境里的i输出才是0、1、2。理解了闭包函数环境指针这个问题就不需要死记结论了。C语言就没有这个问题因为C不支持嵌套函数所有函数都定义在顶层。函数内部能访问的非局部变量只有全局变量而全局变量在静态数据区有固定地址根本不需要环境指针。所以C的函数指针只传地址就够了。这也解释了为什么C语言老手第一次接触JavaScript闭包时往往一头雾水本质上就是运行时存储模型不一样。5. 常见问题与排查技巧实录5.1 动态链和访问链的终极区分动态链和访问链的混淆是学生里出现频率最高的问题。我提供一个我自己用的判断口诀动态链回答我是被谁调进来的访问链回答我词法上定义在哪个过程里面。动态链用于过程返回时恢复调用者的帧指针。栈上每压入一条AR动态链就指向调用者的AR一路回溯正好还原当初逐层调用的轨迹。如果没有它过程执行完就找不到回去的路了。访问链用于变量访问。过程内部的非局部变量要在静态外层过程的活动记录里找而静态外层过程可能和调用路径完全没关系。比如B定义在A里面但B是被和A同级的C调用的那么B的动态链指向C的AR访问链却指向A的AR。两条链南辕北辙一点都不奇怪。5.2 栈上局部变量的几个典型坑局部变量在栈上分配的模型也衍生出不少经典问题。最典型的就是返回局部变量地址的悬垂指针int* bad() { int x 42; return x; }bad返回后x所在的AR被弹出栈但栈上那块内存并没有被清零。调用者拿到这个指针之后再访问读到的值可能还是42也可能已经被后续的函数调用覆盖成了别的垃圾。这是未定义行为和残留数据有关。理解AR的生命周期就能理解为什么这种代码危险。还有一个坑是未初始化局部变量的读取。栈上放着一堆历史调用留下的残留数据如果某个局部变量忘记初始化读到的就是那块位置上一次使用它的过程留下的内容。这不是随机数而是有规律可循的残留数据在安全领域经常被利用来泄漏信息。递归太深导致的栈溢出也一样。每个活动记录都要占栈空间递归深度过大AR越压越多栈顶迟早撞上堆区或者超出系统限制程序直接崩溃。某些语言允许调大栈大小比如Go的goroutine栈可以动态增长但大多数C/C程序只能靠减小递归深度或者改迭代来规避。5.3 一个嵌套访问的完整手推我设计一个自测题读者可以自己推一遍再对照。program Main; // 深度0 var g: integer; procedure A; // 深度1 var a: integer; procedure B; // 深度2 var b: integer; procedure C; // 深度3 var c: integer; begin c : b a g; end; begin C; end; begin a : 1; B; end; procedure D; // 深度1 begin A; end; begin g : 0; D; end.执行到C内部时栈上从低到高是Main、D、A、B、C。用访问链方案去推D的访问链D定义在Main里直接指向Main的AR。A的访问链D调用AA定义在Main里target深度是0从D的访问链走1步还是Main的AR。B的访问链A调用BB定义在A里target深度是1从A的AR出发走0步就是A的AR所以B的访问链指向A的AR。C的访问链B调用CC定义在B里C的访问链指向B的AR。C内部访问b、a、g分别要跳几步访问bb定义在深度2当前深度3跳1步。C的访问链指向B的AR一次命中。访问aa定义在深度1跳2步。C→BB的ARB→AA的AR两次命中。访问gg定义在深度0跳3步。C→B→A→Main。这样的手推练习做上两三次对访问链的理解就扎实了。考试和面试里这类题的套路基本一致先判断每个AR的访问链指向谁再数访问目标变量需要跳几步。常见问题速查表现象可能原因排查思路局部变量值神秘变化返回了局部变量地址检查是否返回局部指针访问嵌套外层变量结果不对访问链建立错误手推一遍调用路径和词法深度函数指针调用崩溃过程参数没带环境改成闭包结构传递入口环境递归几万次栈溢出AR过大或递归过深看资源占用、尝试改迭代未初始化变量有奇怪值栈残留数据初始化变量并检查代码路径6. 把这部分学扎实的实操建议6.1 用gdb和汇编把活动记录看穿如果总觉得AR是个抽象概念那就打开调试器亲眼看一次。写一个简单的C程序#include stdio.h int sum(int a, int b) { int c a b; return c; } int main() { int x 1; int y 2; int z sum(x, y); printf(%d\n, z); return 0; }用gcc -g -fno-omit-frame-pointer编译。加-fno-omit-frame-pointer是为了让编译器保留帧指针方便调试观察。然后用gdb调试break sum在sum函数入口打断点运行到sum函数里执行info framegdb会显示这个帧的返回地址、保存的帧指针、局部变量地址等信息。执行bt看整个调用栈能看到main调用sum的完整轨迹。这就是动态链的直观体现。执行objdump -d看sum函数的汇编代码找到push %rbp; mov %rsp, %rbp这样的入口序列再看局部变量是怎么通过-4(%rbp)访问的。看完一遍原来课本上那些概念就落到具体的指令上了。以后看到任何关于活动记录的说法脑子里会自动浮现出栈的推拉画面。6.2 动手写一个带嵌套过程的小编译器学习编译原理光看书永远隔着一层。我最推荐的实操项目是用Yacc/Lex写一个支持嵌套过程的Pascal子集编译器后端只生成简单的栈机中间代码。一开始不用做完整的优化能编译运行一段定义嵌套过程、内层访问外层变量的代码就行。做的时候会强迫你处理符号表如何区分不同层级的同名变量。为每个过程计算嵌套深度。过程调用时生成建立访问链的指令。变量引用时生成沿访问链查找的指令。做完第一版之后再把访问链方案换成显示表方案对比生成的中间代码有什么变化。这个过程比做十套题都有用。我当时做完之后很多原先模模糊糊的概念一下子都通了。6.3 面试里最常见的几种变体题编译器方向面试或者编译原理期末考试里运行时存储空间管理的题目就那么几类提前刷一遍很有帮助。给一段Pascal代码让你求某个过程内部访问某个变量时的访问链接路径。给一个过程作为参数传递的场景让你指出闭包的环境指针应该指向哪里。给一段静态作用域和动态作用域的代码让你写出两种规则下分别输出什么。画出程序执行到某个断点时的栈状态标出动态链和访问链。解释C函数指针和JavaScript闭包在环境处理上的根本差异。本质上都在考一件事你有没有真正理解变量名到存储位置的绑定关系是怎么建立和维护的。结尾我个人在学习这一块时体会最深的一点是运行时存储空间管理不是一个孤立的主题它把语法分析、符号表、代码生成、甚至操作系统里的栈机制全部串在了一起。弄懂活动记录和变量访问环境之后再看任何语言里的函数调用、回调、函子、闭包、装饰器都会觉得它们骨子里是同一件事在某个执行时刻程序要能找到一个变量对应的存储位置而这个位置是由词法结构、调用路径和存储布局共同决定的。最后再分享一个小技巧手推题目的时候动态链用一条虚线画访问链用一条实线画颜色区分开一张图推完很多混淆自然就消失了。这个习惯我保留到现在看回溯类代码时都还在用。
编译原理：运行时存储管理与变量访问环境深度拆解（过程活动记录/访问链）
刚学编译原理的时候我最头大的模块就是运行时存储空间管理尤其是其中的变量访问环境。教材堆了一堆术语——过程活动记录、动态链、访问链、显示表——每个字都认识连起来就看不懂。后来自己对照汇编逐步调又动手写了个C方言小编译器才真正把这部分打通。这篇博文就按我自己的学习路径整理一遍先讲清楚运行时存储空间管理到底在管什么、过程活动记录长什么样再重点拆解变量访问环境里的两条主线——局部变量怎么访问、嵌套过程里的非局部变量怎么访问最后聊参数传递和过程作为参数时的环境问题。正在学编译原理、准备编译器方向面试或者想弄明白JavaScript闭包底层原理的人这篇能帮你一次性把这些概念串起来。1. 运行时存储空间管理到底在管什么1.1 程序运行时的内存长什么样写代码的时候变量是一个抽象的名字程序跑起来之后每个变量都要落到真实的内存地址上。运行时存储空间管理的第一个任务就是决定这些变量各放哪里、怎么组织、怎么回收。按经典的进程内存布局一块虚拟内存空间大致分成四个区域代码区、静态数据区、栈区和堆区。代码区存放编译器生成的目标指令。它通常是只读的程序执行时从这里不断取指令。静态数据区存放全局变量、静态变量、字符串常量等。这些变量的地址在编译期就能确定整个程序生命周期里一直存活。栈区存放目前正在执行的过程函数的活动记录。每个过程调用发生时就往栈顶压入一条记录过程返回时弹出。栈在主流x86-64体系上通常向下增长也就是从高地址往低地址长。堆区存放动态分配的数据比如C语言里malloc、C里new出来的对象。堆一般向上增长和栈相向而行。把这几个区域想清楚很多初学者常见的困惑就消失了。比如有人问全局变量和局部变量的区别到底是啥从存储管理角度看区别就是全局变量在静态区、地址固定、生命周期是整个程序局部变量在栈上、地址是运行时算出来的、生命周期是当前过程这次调用的期限。1.2 为什么过程活动记录要放栈上栈这个数据结构天然匹配过程调用的嵌套特性。一个过程一旦调用了另一个过程被调用的过程必须先执行完并返回调用者才能继续往下走。这个最后被调用的过程最先返回的规律正好是栈的后进先出特性。想象一个调用序列主程序调用AA调用BB调用C。C返回B返回A返回。程序的执行轨迹就是一层层套进去、再一层层解出来。每层套进去时栈顶多一块活动记录每层解出来时栈顶少一块活动记录。这个过程完全不需要额外管理压栈弹栈的开销极小。栈还有一个重要优势递归调用时同一个过程的多个活动记录可以同时存在于栈上互不干扰。比如计算阶乘的fact函数递归调用5次栈上就有5份fact的活动记录每份里都有自己独立的参数n和局部变量。这就是变量局部性在运行时最直观的体现。每个调用实例看到的n都不一样但编译器生成的目标代码只用一套区别只在于当前访问的是哪一份活动记录。1.3 堆区为什么不能替代栈区可能有人会问为什么不把所有过程局部变量都放堆里现代语言的闭包不就这么干吗放堆当然可以但代价很大。堆的分配和回收通常比栈复杂得多分配时可能有空闲链表查找、内存碎片整理回收时可能有垃圾回收器介入。而栈区的分配就是一条指令——把栈指针减去一个偏移量释放就是加回去几乎零成本。所以经典编译器处理局部变量的默认策略是尽量放栈上。只有那些在过程返回后还需要存活的数据比如逃逸的闭包环境才考虑提升到堆上。这个判断在编译原理里叫逃逸分析。2. 过程活动记录一个过程调用的一份“档案”2.1 活动记录里到底装了哪些东西过程活动记录Activation Record简称AR也叫栈帧。它就是一次过程调用在栈上的全部私有数据。不同编译器实现的AR布局不完全一样但核心成员通常包括这几块。返回地址过程执行完之后CPU回到哪里继续执行。通常是调用点下一条指令的地址。动态链Dynamic Link保存调用者的帧指针fp值。它把当前AR和调用者的AR串起来形成一条谁调用了谁的链过程返回时靠它恢复现场。访问链Access Link保存静态外层过程的最新AR地址。支持嵌套过程的语言需要它来访问非局部变量像C这种不支持嵌套函数的语言AR里可以没有这项。参数区存放调用者传入的实参。有些调用约定用寄存器传参但编译器通常会把寄存器参数再保存到AR的统一位置方便后续统一访问。局部变量区存放过程内部声明的局部变量。临时变量区存放编译生成的中间结果比如表达式求值时产生的临时值。这里最容易被误解的就是动态链和访问链。动态链跟着调用历史走访问链跟着词法定义结构走。两个链在大多数情况下指向不同的位置这两个概念的区别是整个运行时存储管理的核心之一后面我会专门展开。2.2 活动记录的一生从入口序列到出口序列一段过程调用在汇编层面长什么样我直接用一个add函数来看。假设有C代码int add(int a, int b) { int c a b; return c; }用x86-64 GCC编译不优化时函数的开头和结尾大概长这样# 函数开头也叫入口序列 prologue pushq %rbp # 保存调用者的帧指针到栈上这就是动态链 movq %rsp, %rbp # 把当前栈顶设为新帧指针 subq $16, %rsp # 给局部变量和临时变量分配16字节空间 # 函数体... movl %edi, -8(%rbp) # 把寄存器参数a保存到栈上局部区 movl %esi, -12(%rbp) # 把寄存器参数b保存到栈上局部区 movl -8(%rbp), %eax # 读取a到eax addl -12(%rbp), %eax # 加上b结果在eax movl %eax, -4(%rbp) # 存到局部变量c的槽位 movl -4(%rbp), %eax # 把c的值作为函数返回值放到eax # 函数结尾出口序列 epilogue movq %rbp, %rsp # 栈顶回到帧指针位置等价于撤销局部空间 popq %rbp # 恢复调用者的帧指针 ret # 返回地址出栈程序跳回调用点这里有两对关键指针栈指针sp汇编里是rsp和帧指针fp汇编里是rbp。sp始终指向当前栈顶压栈弹栈都跟着它走fp指向当前活动记录的固定基准点局部变量和参数的访问都通过它加上一个编译期算好的偏移量来完成。上面代码里的-4(%rbp)就是通过fp偏移访问局部变量c-8(%rbp)是参数a-12(%rbp)是参数b。为什么非要用fp而不直接拿sp偏移因为sp在函数体内会不断变化每压一次栈、调一次函数sp都在动。如果所有变量都基于sp偏移编译器必须精确跟踪每个时刻sp变化了多少非常麻烦。fp在函数体执行期间是固定的编译器只需要在函数开头设置一次后面所有访问都基于fp省心得多。这也是为什么调试信息里到处是rbp的影子。2.3 局部变量的访问帧指针加偏移局部变量在AR里的位置是编译期就能确定的。编译器遍历一遍语法树为每个局部变量分配一个在AR内的偏移量然后生成一条mov指令用fp 偏移量去访问。这里我加一句提醒很多初学者以为变量一定在内存里。实际上经过优化之后大量局部变量被分配到了寄存器里根本不进栈。寄存器是CPU内部的高速存储单元读写比内存快一个数量级编译器会想方设法把变量放寄存器。但有些情况变量必须要放到栈上变量被取地址x后续可能通过指针访问。变量是数组或者结构体寄存器装不下。变量被声明为volatile编译器不能随便缓存它的值。调试模式下关闭优化方便和源码行号对应。所以运行时存储空间管理并不等于所有变量都在栈上而是说栈是那些不能进寄存器的临时数据的默认归宿。看汇编时如果发现某个局部变量根本没出现在栈上不用奇怪它可能在寄存器里活完了整个生命周期。3. 非局部变量的访问访问链和显示表3.1 嵌套过程带来真正的麻烦如果一门语言只有全局变量和局部变量两种变量那运行时存储管理其实很简单全局变量用固定地址访问局部变量用fp加偏移访问完事。C语言就是这种模式所以学C的时候大多数人根本不会意识到变量访问环境是个需要专门研究的问题。但Pascal、Ada这类语言支持嵌套过程定义。内层过程可以访问外层过程的局部变量。这种能力在词法分析、语法分析阶段没什么问题一个变量引用是声明在哪一层的编译期就能算清楚。真正难的是运行时怎么找到它。举个例子program Main; var x: integer; procedure A; var a: integer; procedure B; var b: integer; begin b : a x; // b局部a来自Ax来自Main end; begin a : 1; B; end; begin x : 0; A; end.执行到B内部时栈上的AR自底向上是Main、A、B。变量a在A的AR里变量x在Main的AR里。B的AR里没有它们直接拿fp偏移是访问不到的。而且A的AR在栈上的具体位置只有在运行时才知道——如果Main先调用A一次A返回后再调用A一次两次A的AR地址完全不同。这里的核心问题就是当前正在执行的过程如何访问到静态外层某个过程的局部变量这就要用到访问链或者显示表。在展开这两种方案之前先说清楚静态作用域规则。编译原理里定义嵌套深度主程序是0定义在深度0里的过程是1定义在深度1里的过程是2以此类推。变量x定义在深度0a定义在深度1b定义在深度2。当前过程深度为cur访问定义在深度d的变量需要从当前AR出发沿某种机制回溯到深度d对应的外层AR。3.2 访问链方案沿着定义链往上跳访问链的思路很直白每个活动记录里保存一个指针指向静态直接外围过程的最新活动记录。B的定义在A内部所以B的AR的访问链就指向A的ARA的定义在Main内部所以A的AR的访问链指向Main的AR。这个链不是调用历史链而是词法定义链。无论B是被谁调用的——哪怕是被一个和A同级的C调用——B的访问链都指向A的AR因为B在词法上定义在A里面。那么调用发生时访问链怎么建立设当前过程为p调用过程为qp深度npq深度nq。关键是找到q的静态父过程的深度也就是nq - 1。如果q直接定义在当前过程p里即nq np 1那么q的访问链就直接指向p的AR。比如A调用BB定义在A里B的访问链就是A的AR。否则需要从p的AR出发沿着p的访问链往前找。目标是找到深度为nq - 1的那个过程的AR。总共需要走的步数是np - (nq - 1)。举个具体的例子program P; // 深度0 var x: integer; procedure A; // 深度1 var a: integer; begin a : 10; end; procedure C; // 深度1 begin A; // C调用A end; begin x : 1; C; end.执行序列是P调用CC调用A。C的访问链好算C定义在P里nq1np0nqnp1C的访问链指向P的AR。A呢A定义在P里但它是被C调用的不是被P调用的。当前过程p是Cnp1q是Anq1。A的静态父过程是P深度0也就是nq-10。从C出发找目标深度0的AR需要走np-(nq-1)1步。C的访问链指向P的AR所以A的访问链也指向P的AR。这个结论对吗对因为A的词法外层就是P和C是谁无关。访问变量时也是一样的逻辑。当前过程深度是cur目标变量定义的深度是d需要走cur - d步访问链。在刚才那个Pascal例子中B内部访问a时cur2d1走1步访问链到达A的AR然后加a的偏移量就能拿到a。访问x时cur2d0走2步B的AR到A的AR再沿A的访问链到Main的AR再加x的偏移。这个方案优点是好懂、内存开销小每个AR只多一个指针。缺点是随着嵌套层数变深访问一次非局部变量要走很多步效率低。如果一个深度10的过程频繁访问全局变量每次都要跳10次指针才能拿到地址这在追求极致性能的编译器里是不可接受的。3.3 显示表方案所有深度一表打尽显示表的思路是不用沿链一个个跳了直接用一张全局表把所有深度的外层AR指针都存起来。这张表叫display数组一般是从0到最大嵌套深度。它始终维护着当前所有活跃层的最新AR指针。比如当前执行到深度3的过程Cdisplay[0]指向主程序的ARdisplay[1]指向A的ARdisplay[2]指向B的ARdisplay[3]指向C的AR。任何一级外层过程只要按深度索引查一下display立刻就能拿到它的AR地址。进入一个新过程q时display[nq]要被设置为q的AR。但同时原来的display[nq]里存的可能是某个还在等待恢复的外层同层过程的AR所以q的AR里必须保存display[nq]的旧值等q返回时再恢复。这就是显示表方案里保存/恢复动作的来源。用显示表访问非局部变量效率极高。访问定义在深度d的变量指令序列就是mov %display[d], %reg; mov offset(%reg), %target不再需要链式循环。无论嵌套多深开销都是常数级的。但显示表也不是没有代价。第一它需要在全局数据区维护一个数组并且每个过程调用和返回时都要处理保存/恢复。第二如果显示表实现不当频繁的过程调用会带来额外的内存读写。第三过程作为参数传递时环境指针的打包同样要考虑display的同步问题。从教学角度看我觉得访问链更适合建立直觉它把词法嵌套直接翻译成了指针链显示表则更适合理解空间换时间的优化思想。3.4 两种方案怎么选很多教材把访问链和显示表放在一起讲但没有说清楚选择依据。我总结一下我自己的理解。对比维度访问链显示表访问非局部变量开销O(深度差)嵌套越深越慢O(1)固定两三次访存调用/返回额外开销建立访问链只需一两条指令需要更新并保存/恢复display项内存开销每个AR多一个指针全局数组加每个AR可能保存的旧表项实现难度简单直观容易调试稍复杂但也不难典型应用教学编译器、嵌套层数浅的语言嵌套过程频繁访问外层变量的语言我记得早期有些Pascal编译器的实现就偏爱显示表因为Pascal程序里嵌套过程访问外层变量太常见了用访问链会让生成的代码包含大量的指针跳转循环。现代很多函数式语言实现采用了更激进的方案干脆把捕获的变量提升到堆上的闭包对象里按对象字段访问效率也不差。说到底没有放之四海而皆准的最优解只有适合当前语言特征和目标平台的折中。学的时候把两种方案都亲手模拟一遍比只看结论有用得多。4. 参数传递与过程参数的环境问题4.1 值传递、引用传递、值-结果传递的底层差异参数传递也属于变量访问环境的范畴。调用一个过程时实参的值或者地址是要放在新AR的参数区里的被调用过程再通过自己的fp偏移来访问它们。传值是最常见的。调用者把实参的值拷贝到被调用者AR的参数区被调用者把形参当普通局部变量用修改形参不影响实参。C语言默认这种方式Java的基本类型也是。传引用传的是实参的地址。被调用者拿到地址之后对形参的任何读写都直接作用于实参本体的内存单元。C的引用参数、C#的ref参数、Pascal的var参数都是这个模式。访问形参变量时需要多一次间接寻址先从参数区取出地址再根据地址访问内存。值-结果传递是一种折中过程刚开始时把实参的值拷贝到形参这像是传值过程返回前再把形参的最终值拷贝回实参。从语义上看它在过程体内完全操作自己的私有一份数据只是返回时把结果同步回去。Ada的out参数就是这样的思路。实现上编译器在参数区里通常会放一个指向实参的地址过程开始时按地址读取初始值返回时按地址写回最终结果。4.2 传名调用是怎么回事还有一个很特别的传参方式是传名call by nameAlgol 60里比较有名。它的做法是不计算实参的值而是把实参的表达式和它的求值环境整体传给被调用者。每次在函数体内用到这个形参都现场重新求值一次。最经典的案例是Jensens Device一段用Algol 60写的求和过程用传名参数一次性实现了微积分里那种把表达式代进去的求和功能。传名的实现机制就是生成一个thunk也就是一段小函数它知道怎么在原来的环境中计算实参表达式。被调用者的AR参数区里存的是thunk的入口地址和环境指针每次访问形参就调用一次thunk。传名的语义非常强大但也非常难以预测容易造成重复计算。后面大多数语言都放弃了它只在宏展开之类的地方保留了类似思想。学它主要是为了理解名字和值分离这件事一个形参名背后到底绑定的是什么求值时机是我们在编译器设计时必须明确的问题。4.3 过程作为参数传递为什么C的函数指针不需要闭包如果语言支持嵌套过程并且允许把过程作为参数传递就会引出变量访问环境里最绕的一个问题怎么把一个过程的环境一起传过去。假设有下面的Pascal风格代码program P; var x: integer; procedure A; var a: integer; procedure B; begin a : a x; end; begin a : 1; Apply(B); // 把过程B作为参数传出去 end; procedure Apply(paramProc: procedure); begin paramProc; end;当A调用Apply时Apply的AR里收到的如果只是B的代码入口地址等Apply执行paramProc去调用B的时候B的AR里的访问链该指向谁按正常的访问链建立规则当前过程是ApplyB定义在A里应该让B的访问链指向A的AR但Apply自己并不知道A的AR在哪。结果就是B内部的a : a x会访问到一个完全错误的地址。正确方案是把过程作为参数传递时必须同时传入口地址和环境指针。这个入口地址环境指针的组合就是现在说的闭包。Apply执行paramProc时用它收到的环境指针直接作为B的AR的访问链B内部访问a和x时才能找到正确的AR。JavaScript闭包就是这个原理。再看一个经典问题for (var i 0; i 3; i) { setTimeout(function() { console.log(i); }, 100); }输出是三个3不是0、1、2。原因就是三个匿名函数捕获的是同一个i的绑定、同一个环境循环结束时i已经变成了3。改成let i之后每次循环都会创建一个新的绑定三个闭包分别捕获各自迭代环境里的i输出才是0、1、2。理解了闭包函数环境指针这个问题就不需要死记结论了。C语言就没有这个问题因为C不支持嵌套函数所有函数都定义在顶层。函数内部能访问的非局部变量只有全局变量而全局变量在静态数据区有固定地址根本不需要环境指针。所以C的函数指针只传地址就够了。这也解释了为什么C语言老手第一次接触JavaScript闭包时往往一头雾水本质上就是运行时存储模型不一样。5. 常见问题与排查技巧实录5.1 动态链和访问链的终极区分动态链和访问链的混淆是学生里出现频率最高的问题。我提供一个我自己用的判断口诀动态链回答我是被谁调进来的访问链回答我词法上定义在哪个过程里面。动态链用于过程返回时恢复调用者的帧指针。栈上每压入一条AR动态链就指向调用者的AR一路回溯正好还原当初逐层调用的轨迹。如果没有它过程执行完就找不到回去的路了。访问链用于变量访问。过程内部的非局部变量要在静态外层过程的活动记录里找而静态外层过程可能和调用路径完全没关系。比如B定义在A里面但B是被和A同级的C调用的那么B的动态链指向C的AR访问链却指向A的AR。两条链南辕北辙一点都不奇怪。5.2 栈上局部变量的几个典型坑局部变量在栈上分配的模型也衍生出不少经典问题。最典型的就是返回局部变量地址的悬垂指针int* bad() { int x 42; return x; }bad返回后x所在的AR被弹出栈但栈上那块内存并没有被清零。调用者拿到这个指针之后再访问读到的值可能还是42也可能已经被后续的函数调用覆盖成了别的垃圾。这是未定义行为和残留数据有关。理解AR的生命周期就能理解为什么这种代码危险。还有一个坑是未初始化局部变量的读取。栈上放着一堆历史调用留下的残留数据如果某个局部变量忘记初始化读到的就是那块位置上一次使用它的过程留下的内容。这不是随机数而是有规律可循的残留数据在安全领域经常被利用来泄漏信息。递归太深导致的栈溢出也一样。每个活动记录都要占栈空间递归深度过大AR越压越多栈顶迟早撞上堆区或者超出系统限制程序直接崩溃。某些语言允许调大栈大小比如Go的goroutine栈可以动态增长但大多数C/C程序只能靠减小递归深度或者改迭代来规避。5.3 一个嵌套访问的完整手推我设计一个自测题读者可以自己推一遍再对照。program Main; // 深度0 var g: integer; procedure A; // 深度1 var a: integer; procedure B; // 深度2 var b: integer; procedure C; // 深度3 var c: integer; begin c : b a g; end; begin C; end; begin a : 1; B; end; procedure D; // 深度1 begin A; end; begin g : 0; D; end.执行到C内部时栈上从低到高是Main、D、A、B、C。用访问链方案去推D的访问链D定义在Main里直接指向Main的AR。A的访问链D调用AA定义在Main里target深度是0从D的访问链走1步还是Main的AR。B的访问链A调用BB定义在A里target深度是1从A的AR出发走0步就是A的AR所以B的访问链指向A的AR。C的访问链B调用CC定义在B里C的访问链指向B的AR。C内部访问b、a、g分别要跳几步访问bb定义在深度2当前深度3跳1步。C的访问链指向B的AR一次命中。访问aa定义在深度1跳2步。C→BB的ARB→AA的AR两次命中。访问gg定义在深度0跳3步。C→B→A→Main。这样的手推练习做上两三次对访问链的理解就扎实了。考试和面试里这类题的套路基本一致先判断每个AR的访问链指向谁再数访问目标变量需要跳几步。常见问题速查表现象可能原因排查思路局部变量值神秘变化返回了局部变量地址检查是否返回局部指针访问嵌套外层变量结果不对访问链建立错误手推一遍调用路径和词法深度函数指针调用崩溃过程参数没带环境改成闭包结构传递入口环境递归几万次栈溢出AR过大或递归过深看资源占用、尝试改迭代未初始化变量有奇怪值栈残留数据初始化变量并检查代码路径6. 把这部分学扎实的实操建议6.1 用gdb和汇编把活动记录看穿如果总觉得AR是个抽象概念那就打开调试器亲眼看一次。写一个简单的C程序#include stdio.h int sum(int a, int b) { int c a b; return c; } int main() { int x 1; int y 2; int z sum(x, y); printf(%d\n, z); return 0; }用gcc -g -fno-omit-frame-pointer编译。加-fno-omit-frame-pointer是为了让编译器保留帧指针方便调试观察。然后用gdb调试break sum在sum函数入口打断点运行到sum函数里执行info framegdb会显示这个帧的返回地址、保存的帧指针、局部变量地址等信息。执行bt看整个调用栈能看到main调用sum的完整轨迹。这就是动态链的直观体现。执行objdump -d看sum函数的汇编代码找到push %rbp; mov %rsp, %rbp这样的入口序列再看局部变量是怎么通过-4(%rbp)访问的。看完一遍原来课本上那些概念就落到具体的指令上了。以后看到任何关于活动记录的说法脑子里会自动浮现出栈的推拉画面。6.2 动手写一个带嵌套过程的小编译器学习编译原理光看书永远隔着一层。我最推荐的实操项目是用Yacc/Lex写一个支持嵌套过程的Pascal子集编译器后端只生成简单的栈机中间代码。一开始不用做完整的优化能编译运行一段定义嵌套过程、内层访问外层变量的代码就行。做的时候会强迫你处理符号表如何区分不同层级的同名变量。为每个过程计算嵌套深度。过程调用时生成建立访问链的指令。变量引用时生成沿访问链查找的指令。做完第一版之后再把访问链方案换成显示表方案对比生成的中间代码有什么变化。这个过程比做十套题都有用。我当时做完之后很多原先模模糊糊的概念一下子都通了。6.3 面试里最常见的几种变体题编译器方向面试或者编译原理期末考试里运行时存储空间管理的题目就那么几类提前刷一遍很有帮助。给一段Pascal代码让你求某个过程内部访问某个变量时的访问链接路径。给一个过程作为参数传递的场景让你指出闭包的环境指针应该指向哪里。给一段静态作用域和动态作用域的代码让你写出两种规则下分别输出什么。画出程序执行到某个断点时的栈状态标出动态链和访问链。解释C函数指针和JavaScript闭包在环境处理上的根本差异。本质上都在考一件事你有没有真正理解变量名到存储位置的绑定关系是怎么建立和维护的。结尾我个人在学习这一块时体会最深的一点是运行时存储空间管理不是一个孤立的主题它把语法分析、符号表、代码生成、甚至操作系统里的栈机制全部串在了一起。弄懂活动记录和变量访问环境之后再看任何语言里的函数调用、回调、函子、闭包、装饰器都会觉得它们骨子里是同一件事在某个执行时刻程序要能找到一个变量对应的存储位置而这个位置是由词法结构、调用路径和存储布局共同决定的。最后再分享一个小技巧手推题目的时候动态链用一条虚线画访问链用一条实线画颜色区分开一张图推完很多混淆自然就消失了。这个习惯我保留到现在看回溯类代码时都还在用。
与show()方法深度解析与应用实践)
