调用栈、de bruijn 索引与堆栈的内存模型

litjohn · 2025-08-26 22:06:58 · 科技·工程

光剑系列的第六作！

（放一个 Gemini 生成的欧比旺的图来解释一下光剑是什么）

前五作：

• 第一篇：Let's build our mathematics by using lambda calculus && church encoding!
• 第二篇：惰性求值、无穷流与发生的魔法
• 第三篇：协程、生成器与 call/cc 的控制流
• 第四篇：动态作用域、词法作用域与表达式求值的环境模型
• 第五篇：基于环境模型的解释器

我们上篇文章写了解释器。在评论区里面可以看到一个非常神秘的东西：https://www.zhihu.com/question/30262900/answer/1943149381

; 嵌套的括号不是 scheme 标准语法。表示定义柯里化的函数，和嵌套 lambda 等价。
(define (Z env)
  (car env))
(define ((S vp) env)
  (vp (cdr env)))
(define ((Lam e) env)
  (lambda (x)
    (e (cons x env))))
(define ((App e1 e2) env)
  ((e1 env) (e2 env)))

; (define global-env '())

顺便，还有人问我为什么不再布置一道习题，那么这就是习题！

这篇文章就是对这个东西的讲解。

看到这个东西，相信大部分人都做不到一眼看懂。不过应该能够看出一点门道：一个变量不再是我们传统解释器中的那个符号，而是一个函数，这个函数的作用是在环境中查找它对应的值。

但是，它究竟是怎么查找的呢？

de Bruijn 索引

答案是，它使用了一种名为 de Bruijn 索引 的技术。

它的核心思想是：用一个自然数来替代变量名，这个数字代表了变量定义距离其使用位置有多少层 lambda 嵌套。

• 0 指代的是最内层（最近）的 lambda 绑定的变量。
• 1 指代的是往外一层的 lambda 绑定的变量。
• 以此类推。

举个例子，在 (lambda (x) (lambda (y) (+ x y))) 这个表达式中，对于 + 表达式而言：

• 变量 y 是由最内层的 lambda (y) 绑定的，所以它的 de Bruijn 索引是 0。
• 变量 x 是由外一层的 lambda (x) 绑定的，所以它的索引是 1。

理解了这一点，我们再来审视那份神秘的代码。这里的“环境” env 不再是符号到值的映射，而是一个从内到外排列的实参列表，完美扮演了调用栈的角色。

• (Z env) 就是 (car env)，它获取列表的第一个元素。这正是查找索引为 0 的变量——“调用栈上最近的那个值”。
• ((S vp) env) 的作用是 (vp (cdr env))。它将环境 env 去掉一层，再用 vp 去查找。这和邱奇编码中的后继函数非常相似，其效果就是让变量查找向外层移动一格。因此，S 操作符就是将变量的索引加一。S(Z) 就代表索引为 1 的变量，S(S(Z)) 代表索引为 2 的变量。

现在，另外两个函数的含义也清晰了：

• ((Lam e) env) 构造了一个 lambda 表达式。它返回一个 Scheme 的 lambda，这个 lambda 接受一个实参 x，然后将 x 通过 cons 压入当前环境 env 的头部，形成一个新的环境，并在这个新环境中执行函数体 e。
• ((App e1 e2) env) 实现了函数应用。它在当前环境 env 中分别对 e1 和 e2 求值，然后直接利用 Scheme 底层的函数应用机制完成调用。

这个实现还有一个极其精妙之处：它利用了 Scheme 的闭包。((Lam e) env) 返回的那个 lambda 自然地捕获了它定义时的环境 env。这使得我们的解释器免费地、正确地实现了词法作用域。

至此，我们用寥寥数行代码，就实现了一个 lambda 演算的解释器。相较于我们在第五作中构建的那个庞大的解释器，这个方案无疑更加简洁、优雅。并且在合理的实现下更加高效。

调用栈

这种函数式的栈模拟，不仅仅是理论上的奇技淫巧。敏锐的你可能已经发现了，它与汇编语言中的函数调用栈如出一辙。

在 x86-64 汇编中，你可能会看到类似这样的代码：

; 函数序言
push rbp        ; 保存旧的栈帧基址
mov rbp, rsp    ; 设置新的栈帧基址
sub rsp, 16     ; 为局部变量分配16字节空间

...

mov rax, [rbp - 8]  ; 访问第一个局部变量 a
add rax, 114514    ; a += 114514
mov [rbp - 8], rax ; 写回 a

这里的 rbp 是栈帧基址指针（Base Pointer），而 rsp 是栈顶指针（Stack Pointer）。在一个函数被调用时，通常会建立一个新的栈帧（Stack Frame），rbp 会指向这个栈帧的固定基址，为函数内部的变量访问提供一个稳定的参考点。

发现了什么？访问局部变量 a 的逻辑 [rbp - 8] 和我们上面的 (S Z) 简直一模一样！

• rbp 就像我们的 env，它为当前函数提供了一个稳定的“环境”基准。
• -8 这个固定的偏移量，就如同 S 操作的次数，是在编译期就确定好的、变量相对于环境基准的“索引”。

这是一种深刻的同构。我们的 Scheme 代码，用纯函数式的方式，模拟了底层指令集架构中基于栈帧的变量访问机制。

理解了这层同构关系后，我们可以进一步探讨一些与调用栈相关的有趣话题。

逃逸分析

我们上面的 Scheme 解释器不需要手动管理内存，GC 会处理一切。同时，闭包中的自由变量也能得到妥善处置，因为列表天生就是可结构共享的。

但是，如果我们把模型切换到汇编中那样的、由连续内存段实现的机械栈上，问题就来了：一个变量的生命周期被严格地限制在它的栈帧之内。当函数返回，栈帧被销毁，其中的所有变量也随之灰飞烟灭。

这在大多数情况下没问题，但当一个变量的生命周期需要比创建它的函数更长时，矛盾就产生了。一个典型的例子是返回闭包：

(define (make-adder add_val)
  ; 下面这个 lambda 捕获了外部的 add_val
  (lambda (x) (+ x add_val)))

(define add5 (make-adder 5))
(add5 10) ; 结果是 15

当 make-adder 函数执行完毕并返回时，它的栈帧理应被销毁。但是，它创建并返回的 lambda（现在被 add5 引用）仍然需要访问 add_val 的值（也就是 5）。这意味着 add_val 这个变量的生命周期，必须比创建它的那个栈帧更长。它从自己的作用域中“逃逸”了。

对于这种情况，简单的栈分配就无能为力了。通用的方法是把 add_val 这样的逃逸变量分配在 堆（Heap） 上，并在闭包中持有指向这块堆内存的引用。

然而，堆分配和间接访问会带来性能开销。因此，现代编译器会进行逃逸分析（Escape Analysis）：如果编译器能证明一个变量绝不会“逃逸”出它的作用域，就可以安全地将它分配在栈上，从而消除开销，提升效率。

堆和栈，动态和静态分配

逃逸分析引出了计算机内存管理中一对最核心的概念：栈与堆。

• 栈（Stack） 的本质是静态内存布局。编译器在编译时就能精确计算出每个函数需要多少空间，以及每个局部变量相对于栈帧基址 rbp 的偏移量。这使得变量访问极其高效，只需要一次地址运算。但它的代价是死板：大小和生命周期必须在编译时确定。

• 堆（Heap） 则是动态内存的舞台。当程序需要在运行时才能确定需要多少内存（例如，读取一个未知大小的文件），或者一个对象的生命周期无法在编译时确定（例如逃逸的闭包变量），就需要从堆上申请。

为了在动态分配的同时不破坏栈的静态布局，常见的做法是在栈上只保存一个固定大小的指针，这个指针指向堆上那块大小不定的内存。这也是为什么 C++ 的 std::vector 或 Java 的所有对象都采用指针/引用的形式——栈上只存放一个引用，而真正的对象数据存放在堆上。

函数调用的实现

那么，硬件层面是如何建立和销毁我们一直在讨论的栈帧的呢？我们来看看 call f 这样一个简单的函数调用背后发生了什么。

1. 调用（call f）：call 指令首先会将返回地址（也就是 call 指令的下一条指令的地址）压入栈顶。然后，它会无条件跳转到函数 f 的代码开头。保存返回地址至关重要，否则函数执行完后就不知道该回到哪里了。

2. 函数序言（Prologue）：函数 f 的开头通常会执行一系列指令来建立自己的新栈帧：

   • push rbp：保存调用者（上一个函数）的 rbp 值。
   • mov rbp, rsp：将当前的栈顶位置设为新栈帧的基址。从此，rbp 在函数执行期间保持稳定。
   • sub rsp, N：在栈上为局部变量预留 N 字节的空间。

3. 函数返回（ret）：当函数 f 执行完毕，它会执行函数尾声（Epilogue）和 ret 指令来拆除栈帧并返回：

   • mov rsp, rbp（或 leave 指令）：释放局部变量空间，将栈顶指针恢复到栈帧基址。
   • pop rbp：从栈中恢复调用者的 rbp。
   • ret：从栈顶弹出之前保存的返回地址，并跳转到该地址，将控制权交还给调用者。

就这样，通过 call 和 ret 的精密配合，以及对 rbp 和 rsp 寄存器的约定用法，程序得以在函数间有序地跳转，同时高效地管理着各自的局部变量。

总结：从 Lambda 到机器码的同构

从一段看似魔法的 Scheme 代码出发，我们踏上了一段奇妙的旅程。我们看到，lambda 演算中的变量绑定，通过 de Bruijn 索引，被转换成了一种基于相对位置的表达。

这种相对位置的表达，与现代计算机体系结构中调用栈通过栈帧指针+偏移量来定位变量的方式，形成了惊人的同构。

进一步地，这个看似简单的内存模型引出了深刻的工程挑战：当函数的生命周期与变量的生命周期不一致时（如闭包导致的变量逃逸），我们就必须引入更灵活的堆内存管理。而栈，作为一种编译期即可确定布局的高效静态模型，则由编译器通过逃逸分析来尽可能地加以利用。

最终我们发现，无论是高级语言的抽象模型，还是底层的机器指令，都在用各自的方式解决同一个核心问题：如何高效、准确地管理和查找变量。抽象的计算理论与具体的硬件实现，在“调用栈”这一点上，达成了深刻的统一。