compiler-construction - 堆栈跟踪与 TCO : Do non-tail recursive languages generally have efficient stack frames?

Question

我听说某些语言不支持尾调用优化 (TCO) 的原因之一是 this optimization comes at the cost of obfuscating the call stack如果/何时调试应该需要查看堆栈跟踪。 (我听说过其他原因，例如“虚拟机不支持它”，但暂时先忽略 Java。)

那么似乎对于某些语言中的某些情况，TCO 是可能的，但如果不执行它，堆栈帧的唯一目的是维护要生成的任何最终堆栈跟踪的元数据。即，堆栈帧可能是最小的，只包含足够的信息来生成堆栈跟踪。

问题:最小化这种堆栈帧的大小没有意义吗？它不会最小化堆栈空间的使用，从而在空间用完之前允许更深层次的递归吗？这是在这种思想适用的语言中尝试过的吗？ (我特别在想 Python。)或者这是在节省的实际空间方面失去的努力？ (我想，与通常在堆栈帧中的数据相比，生成良好堆栈跟踪所需的元数据实际上要多得多。)

简而言之:最小化堆栈帧的大小作为 TCO 的替代方案。

附注。我的想法不是基于任何实际的基准。我可能会离开这里。

Answer 1

如果正在调试，除非您正在调试优化本身，否则并非所有优化都需要打开。所以尾递归优化 (TRO) 不必在调试期间禁用回溯，除非开发环境是脑残的(例如，没有“禁用优化”选项)。

如果您确实记录了元数据，它所占用的空间非常小；基本上它说，“进行了递归调用”。具有少量字节元素的链表可以解决问题。但我认为在 TRO 面前记录回溯元数据是没有意义的；如果您正在优化，您可能也不想支付记录元数据的额外时间成本，因为有人可能想稍后进行调试。

我不确定“最小化堆栈帧的大小”是什么意思，因为您是在 TRO 的上下文中询问的。一般来说，一个好的编译器会通过只分配足够的空间来自动地最小化大小来完成堆栈帧实例所代表的(子)例程的整个计算。一种标准优化是让具有非重叠生命周期的变量共享堆栈帧中的相同空间。可以通过几种不同的方式做到这一点:a) 子程序主体内不重叠的嵌套作用域可以在类似堆栈的规则中轻松共享它们的空间，并且 b) 处理“堆栈框架”而不是像一个堆栈，但作为一组用于存储溢出值的寄存器；寄存器着色算法可以很好地处理这个问题。

有时堆栈帧最小化会因操作系统(缺乏)支持而受损。见 this讨论 Windows 如何捕获大量损坏堆栈帧大小。