堆栈跟踪与TCO:非尾递归语言通常具有有效的堆栈框架吗？

Question

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

那么，对于某些语言中的一些情况，TCO是可能的，但在不执行TCO的情况下，堆栈帧的唯一目的是为生成的任何最终堆栈跟踪维护元数据。也就是说，堆栈帧可以是最小的，只包含足够的信息来生成堆栈跟踪。

问题：将这样的堆栈帧的大小最小化难道没有意义吗？它会不会最小化堆栈空间的使用，从而允许在耗尽空间之前进行更深层次的递归？这种想法适用的语言中是否尝试过这种方法？(我特别想到Python。)还是说这是在节省实际空间方面失败的努力？(我认为生成良好堆栈跟踪所需的元数据实际上与堆栈框架中的正常情况相比相当多。)

简而言之，的思想是：最小化堆栈帧的大小，作为TCO的替代方案。

PS。我的想法不是基于任何实际的基准。我可能离这里很远。

Answer 1

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

元数据占用的空间(如果您确实记录了它)非常小；基本上它的意思是“进行了递归调用”。一个包含少量字节元素的链接列表就能做到这一点。但是，我认为在面对TRO的情况下记录回溯元数据是没有意义的；如果您正在进行优化，您可能也不想支付记录元数据的额外时间成本，因为有人可能希望稍后进行调试。

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

有时，堆栈帧最小化会因操作系统缺乏支持而受损。有关Windows陷阱如何严重损害堆栈帧大小的讨论，请参见this。

Answer 2

基本上，您可以在“优化”尾递归还是维护“精确”调用堆栈之间进行选择。您要么维护某种“面包屑”，而不完全优化尾递归，要么在丢失堆栈跟踪的同时优化尾递归。

每个设计良好的语言实现(对运行时性能和“占用”感兴趣)“最小化”堆栈帧大小。

但是，就像计算中几乎所有的东西一样，在竞争因素之间也有一种权衡--性能、“足迹”、实现的简单性/可靠性、灵活性(例如多种语言)、可调试性等。