OCaml 中的尾调用与局部区域

本集继续介绍 Jane Street 正在开发的 OCaml 编译器分支中的 local 模式。我将用一个小型列表处理示例，展示局部值与尾调用如何相互影响。

示例统计列表首元素出现的次数。对于 [3; 1; 3; 8; 3; 3; 4]，结果应为 4。我们先用普通方式实现，再引入局部值并检查产生的错误。

对于空列表，count_firsts 返回零。否则，它将表头绑定为 x，并定义递归函数 count_occs 来处理尾部。空尾部返回一，计入原来的表头；之后每次匹配加一，不匹配则继续递归而不增加计数。

递归函数捕获 x，外层函数用剩余列表调用它。编译并运行程序会输出 4。这个特定示例的列表完全由常量构成，所以 OCaml 已能避免堆分配；一般列表则可能需要分配。

我给 count_firsts 添加注解，让它接收局部列表并返回 int。此时编译器报告局部值逃离了其区域，并提示由于这是尾调用，该函数不能是局部的。乍看之下这很奇怪：返回的整数不可能包含列表，我们也没有把列表存入任何引用。

在本例中，对局部列表进行模式匹配会使 x 和 xs 都成为局部值。由于 count_occs 捕获 x，它的闭包也必须是局部的：如果将闭包放在堆上，局部区域结束后，堆中可能留下指向栈数据的指针。

把捕获的 x 换成常量 3 后，错误消失，这证实正是捕获的局部变量迫使闭包成为局部值。但我们实际要统计 x 的出现次数，因此需要弄清楚尾调用。

如果我先将 count_occs 的结果绑定到变量，再返回该变量，调用就不再处于尾位置，程序也能编译运行。区别源于尾调用优化。

当函数的最后一个操作是调用另一个函数时，尾调用优化可以直接把控制权交给被调用函数，而不必先返回调用函数。被调用函数最终返回给原始调用者，从而省去一个之后没有工作可做的调用帧。

函数的局部区域在其尾调用之前立即结束，如果存在尾调用的话。因此，局部 count_occs 闭包属于 count_firsts 的区域，但在尾调用中使用它会让它逃离该区域。先绑定整数结果则可行，因为返回的整数不保留闭包或列表。

这个编译器分支提供了明确的替代办法：用 [@nontail] 标记调用。它会在该调用点阻止尾调用优化，使局部区域在普通调用期间保持可用，从而让程序通过编译。

这个注解会改变运行时行为：普通调用会增加一个调用栈帧。讲者说，对于这一次调用，额外分配耗时很少，但它确实会额外使用栈空间。

还有一个更微妙的问题：ys 来自局部列表，为什么 count_occs 仍能用它进行尾递归调用？其局部参数得到了正确推断，而且调用无需 nontail 注解就能通过。

原因是一个隐藏模式 regional，它介于 global 和 local 之间：global 是 regional 的子模式，regional 又是 local 的子模式。局部参数来自当前函数区域之外，因此可以逃离这一个区域。对参数进行匹配得到的尾部 ys 是 regional，所以允许尾调用。

为了演示，我定义恒等函数 lid，接收并返回局部值。将 ys 传入 lid，再把结果绑定为 zs，会丢失该值原本是 regional 的信息：类型允许这次调用，但只知道其结果是 local。

此时在尾递归调用中使用 zs 就会产生局部值逃逸错误。用 [@nontail] 标记该调用可使其通过编译，但在长列表的递归中反复这样做，可能多消耗 O(n) 的调用栈空间。保留 regional 信息可让尾递归分支避免这一成本。

递归调用后还要加一的分支则不同：1 + count_occs zs 不是尾调用，因为还要执行加法。因此，即使没有 nontail 注解，也可以在那里传入局部值。

需要记住的规则是：函数区域在尾调用之前结束。显式使用 [@nontail] 注解，或在返回之前绑定调用结果，都能阻止该调用点按尾调用处理。

实践中，当前方法可能需要许多 nontail 注解。我认为在将这项工作合入上游之前，需要找到更好的方案；我们有一些启发式方法的想法，但未来如何发展仍未确定。