WebKit 中的 ECMAScript 6 严格尾调用
严格尾调用 (Proper Tail Calls, 简称 PTC) 是 ECMAScript 6 语言中的一项新特性。添加此特性旨在促进直接和间接递归的编程模式。许多其他设计模式也能从 PTC 中受益，例如封装某些功能的代码，其中封装代码直接返回其所封装功能的结果。通过使用 PTC，运行代码所需的内存量得以减少。在深度递归的代码中，PTC 使得原本会抛出堆栈溢出异常的代码得以运行。
什么是严格尾调用？
通常，当调用一个函数时，会为与函数调用相关的数据分配堆栈空间。这些数据包括返回地址、前一个堆栈指针、函数参数以及函数局部值的空间。这个空间被称为堆栈帧。在尾部位置对函数进行的调用将重用调用函数的堆栈空间。如果满足以下条件，则函数调用处于尾部位置：
- 调用函数处于严格模式下。
- 调用函数是普通函数或箭头函数。
- 调用函数不是生成器函数。
- 被调用函数的返回值由调用函数返回。
当函数调用处于尾部位置时，ECMAScript 6 规定此类调用必须重用其自身帧的堆栈空间，而不是将另一个帧压入调用堆栈。需要强调的是，ECMAScript 6 要求处于尾部位置的调用将重用调用者的堆栈空间。调用函数的帧被称为尾删除帧，因为它一旦进行尾调用就不再位于堆栈上。这意味着尾删除函数不会出现在堆栈跟踪中。需要注意的是，PTC 与尾调用优化不同，后者是许多优化编译器出于各种性能原因可能进行的自由裁量优化。
严格尾调用的好处
PTC 被添加到 ECMAScript 中的主要目的是重用堆栈空间。堆栈内存的重用允许递归和尾调用编码模式，这在函数式编程和其他编程范式中很常见。通过使用 PTC，程序可以进行无限数量的连续尾调用，而不会无限地增长堆栈。
PTC 还提供了其他好处。利用 PTC 的程序可以减少内存占用，因为垃圾回收器更有可能回收某些局部对象。利用 PTC 的程序还可以看到速度提升，因为从尾调用函数返回时所需的处理更少。
堆栈空间
减少堆栈使用也能以其他方式带来好处。现代计算设备包含分层内存缓存，以减少内存访问延迟。尽管这些缓存容量很大，但它们仍然是有限的。通过使用 PTC 减少堆栈使用还可以减少所需的缓存空间量，从而为其他内存访问释放缓存空间。
局部分配对象
考虑一个分配局部对象的函数，但该对象从未对其他代码可见。对此类局部对象的唯一引用将通过函数堆栈帧中的指针或函数正在使用的寄存器进行。如果 JavaScript 虚拟机需要进行垃圾回收，它将通过扫描堆栈和 CPU 寄存器的内容来查找对此类局部对象的引用。如果该函数调用另一个函数且该调用不是尾调用，则调用函数的任何局部对象将不会被回收，直到调用函数本身返回。但是，如果一个函数对另一个函数进行尾调用，则调用函数的所有局部对象都可以被垃圾回收，因为不再有对该对象的堆栈引用。
从尾调用函数返回
PTC 的另一个好处是，当叶函数返回时，它会绕过所有中间尾调用函数，直接返回到第一个未进行尾调用的调用者。这消除了这些中间函数的所有返回处理。连续尾调用链越深，所带来的性能优势就越大。这适用于直接递归和相互递归。
示例
有许多算法最适合使用递归编写。其中许多算法自然地利用了 PTC，而另一些可能需要一些修改。考虑编写一个程序，使用欧几里得算法来计算最大公约数 (GCD) 函数。将欧几里得算法转换为利用 PTC 的程序是简单、优雅且自然的：
"use strict";
function gcd(m, n)
{
if (!n)
return m;
return gcd(n, m % n);
}
其他递归数学函数的自然转换可能导致不在尾部位置的递归调用。例如，计算阶乘 (N!) 的程序通常写成：
"use strict";
function factorial(n)
{
if (!n)
return 1;
return n * factorial(n - 1);
}
在此函数中，对 factorial() 的递归调用不在尾部位置，因为 return 语句计算并返回 n 与递归调用结果的乘积。提醒一下，要处于尾部位置，被调用函数的返回值必须是调用函数返回的唯一内容。稍加修改，我们可以将 factorial 重写为如下所示，以利用 PTC：
"use strict";
function factorial(n, partialFactorial = 1)
{
if (!n)
return partialFactorial;
return factorial(n - 1, n * partialFactorial);
}
此更改将对 factorial 的递归调用置于尾部位置，从而使函数能够利用 PTC。两个版本的递归调用次数和算术运算次数相同。
下一个示例涉及函数 computeSquareRoot()、computePositiveSquareRoot() 和 iterativeSquareRoot()，它们用于使用牛顿迭代法计算数字的平方根：
"use strict";
function computeSquareRoot(x)
{
if (!x)
return "0";
let imaginaryPart = "";
if (x < 0) {
x = -x;
imaginaryPart = "i";
}
return computePositiveSquareRoot(x).toString() + imaginaryPart;
}
function computePositiveSquareRoot(x)
{
let targetEpsilon = x / 10000000000;
return iterativeSquareRoot(x, x / 2, targetEpsilon);
}
function iterativeSquareRoot(x, estimate, targetEpsilon)
{
let newEstimate = ((x / estimate) + estimate) / 2;
let delta = Math.abs(estimate - newEstimate);
if (delta <= targetEpsilon)
return newEstimate;
return iterativeSquareRoot(x, newEstimate, targetEpsilon);
}
最顶层的函数 computeSquareRoot() 确定结果是实数还是虚数，然后调用 computePositiveSquareRoot()，后者设置迭代平方过程并返回 iterativeSquareRoot() 的结果。computeSquareRoot() 中对 computePositiveSquareRoot() 的调用不在尾部位置，因为对调用结果进行了额外的处理。所有其他函数调用都处于尾部位置。
假设 computeSquareRoot() 以 99 作为参数被调用。它将调用 computePositiveSquareRoot(99)，后者随后将调用 iterativeSquareRoot(99, ...)。使用 Web Inspector，我们观察到 iterativeSquareRoot() 在返回结果之前调用自身 6 次。该结果直接返回到 computeSquareRoot，并在那里转换为字符串，节省了 7 次返回的处理开销。
最后一个示例展示了 PTC 启用的函数式编程类型：
"use strict";
function newList(count)
{
let head = { value: count, next: null };
while (--count)
head = { value: count, next: head };
return head;
}
let count = 100000;
let list = newList(count);
function contains(list, x)
{
if (!list)
return false;
if (list.value == x)
return true;
return contains(list.next, x);
}
...
if (contains(list, someValue))
...
函数 contains() 使用尾递归搜索列表。对于本例中给出的 100,000 个元素大小的列表，大多数浏览器会耗尽堆栈内存并抛出异常。在严格模式下，contains() 可以利用 PTC，程序运行良好。值得注意的是，即使列表大小小到足以让此代码在没有 PTC 的情况下运行，使用 PTC 也能使代码运行速度提高 2.5 倍。
注意事项
在使用 PTC 时，有一些细微但次要的问题需要注意。请记住，PTC 仅在严格模式下可用，并且仅适用于从尾部位置进行的调用。另一个显著的变化涉及堆栈跟踪的生成。JavaScript 中有一些非标准的 ECMAScript 功能，在 PTC 存在时表现不同。这些功能包括 Error.stack 和 Console 对象的堆栈跟踪。例如，假设一个尾调用函数 gonnaThrowAnError() 抛出一个 Error 对象；捕获该 Error 的函数将不会在 Error 对象的堆栈跟踪中看到调用 gonnaThrowAnError() 的函数。通常，Console 对象的堆栈跟踪不会包含对另一个函数进行尾调用的函数。我们将此类帧称为尾删除帧，因为它们在进行调用时就好像从堆栈中被删除了。
使用 ShadowChicken 调试 PTC
由于 PTC 对堆栈使用施加了严格的资源保证，JavaScriptCore 无法保留所有尾删除帧的信息。为无限数量的尾删除帧保留任何额外资源（无论多小）都是不可能的，因为它可能使用无限量的内存并最终耗尽程序的内存限制。鉴于尾调用在程序的执行状态中不保留任何信息，在使用交互式调试工具时调试尾调用可能具有挑战性。如果没有添加任何额外机制，调试器将无法知道是否发生了尾调用。因为我们希望在 Web Inspector 中提供出色的尾调用调试体验，我们在 JavaScriptCore 内部实现了机制，以保留一个影子堆栈，该堆栈将显示有限数量（目前为 128 个）的尾删除帧。这使我们既能提供严格的内存使用保证，又能让 PTC 用户受益于在 Web Inspector 中查看程序中最重要的堆栈帧。
我们将我们的影子堆栈实现称为 ShadowChicken。这个名字是为了致敬 CHICKEN scheme 解释器。ShadowChicken 使用日志记录机制来构建其影子堆栈。日志工作方式如下：
- 进入函数时，函数的被调用者将记录一个序言包。
- 进行尾调用时，调用者将在尾调用发生前记录一个尾部包。
- 抛出异常时，ShadowChicken 将记录一个抛出包。
为了构建影子堆栈，ShadowChicken 接受两个输入：
- 包含一系列序言、尾部和抛出包的日志。
- 机器堆栈的当前顶部（请注意，机器堆栈不包含任何尾删除的帧）。
给定这两个输入，ShadowChicken 能够构建一个包含尾删除帧的影子堆栈。它将将机器堆栈与其日志进行协调。由于日志中包含尾调用发生时的尾部包，它能够使用日志将尾删除堆栈帧插入到影子堆栈中，以表示在尾调用发生之前仅存在于机器堆栈上的帧。ShadowChicken 在您程序已使用的内存之外，使用恒定量的内存。日志大小是固定的。每当 ShadowChicken 日志空间不足时，它将执行其协调算法来更新其关于影子堆栈状态的内部数据结构。影子堆栈最多将包含 128 个尾删除帧，我们认为这个数字在有意利用 PTC 的程序和偶然使用 PTC 但没有明确意图的程序之间取得了很好的平衡。
将 ShadowChicken 连接到 Web Inspector
由于 JavaScriptCore 具有构建影子堆栈的机制，Web Inspector 可以在其调试器中使用 JavaScriptCore 的影子堆栈。这使得 Web Inspector 用户可以与尾删除堆栈帧进行交互，就好像它们是当前机器堆栈上的真实堆栈帧一样。
让我们看看 Web Inspector 与迭代平方根代码的交互，以计算 99 的平方根。在 iterativeSquareRoot() 中设置断点并调用 computeSquareRoot(99) 后，Web Inspector 显示我们已暂停，准备返回结果。
Web Inspector 不仅显示我们停止的帧和原始调用者 computeSquareRoot()，还显示了七个尾删除帧。这些在上面的图像中高亮显示。Web Inspector 中的尾删除帧左侧会显示一个灰色的 ƒ 图标。如下图所示，尾删除帧中的变量可以像普通帧一样进行检查。下一张图片显示了 Web Inspector 正在检查叶帧上方一级的尾删除帧。
在此图像中，可以检查局部变量（圈起来的部分）。程序中突出显示的行也显示了尾删除帧进行尾调用的位置。
下一张图片显示了从断点单步执行时发生的情况。
点击“步入”按钮后，Web Inspector 现在显示我们已直接返回到 computeSquareRoot() 第一次进行尾调用的位置。
总结
WebKit 已经支持 ECMAScript 6 严格尾调用，鼓励 Web 开发人员利用它们来设计以前不可能实现的程序。现有代码也能从中受益。Web Inspector 使使用 PTC 进行开发和调试变得简单直观。
当前的Safari 技术预览版 4 支持 PTC。然而，Web Inspector 最近才与 ShadowChicken 联用，因此它不包含在 Safari 技术预览版 4 中。预计将在下一个 Safari 技术预览版中提供。您也可以通过使用WebKit 每夜版在 Web Inspector 中试用 ShadowChicken。
致谢
本文与 JavaScriptCore 团队的 Saam Barati 共同撰写。我们欢迎对 WebKit 的 PTC 实现提出评论和反馈。请随时通过 Twitter 联系@msaboff、@saambarati 和@jonathandavis。