recursion - 为什么 F# 对堆栈大小施加下限？

Question

我想知道是否有将 F# 中的递归深度限制为 10000 左右的根本原因，以及理想情况下如何避免该限制。我认为编写使用 O(n) 堆栈空间的代码是完全合理的，如果不同意的人能解释他们为什么这样做，我将不胜感激。非常感谢。我在下面解释我的想法。

我看不出有任何理由不允许堆栈增长，直到用完整个可用内存。这意味着无限递归需要更长的时间才能注意到，但这并不是说我们已经不能编写消耗无限内存的程序。我知道可以使用延续和尾递归将堆栈使用量减少到 O(1)，但我并不特别明白必须一直这样做对我有什么好处。我也看不出必须知道函数何时可能需要处理“大”输入(嗯，按照 8 位微 Controller 的标准)有什么帮助。

我认为这与必须例如根本不同。使用累积参数来避免二次时间行为。虽然这也涉及到对实现细节的担忧，并且对于“小”输入不需要这样做，但它也非常不同，因为编译器无法自行解决问题。此外，稍微复杂的 O(n) 代码(如果天真地编写会是 O(n^2))比简单、缓慢、易于阅读的版本更有用。相比之下，延续风格的代码与相应的幼稚版本具有完全相同的内存复杂度，只是使用了不同类型的内存。这是编译器不应该让我在这个时代担心的事情吗？

虽然我会“更喜欢”为什么不可能有深堆栈的理论原因，但我们也不妨讨论一下实际方面。在我看来，堆栈是一种比堆更有效的内存管理方式，因为它不需要垃圾收集并且很容易释放？我不确定我什至可以看到允许深筹码是有代价的。诚然，操作系统需要留出足够的虚拟空间来包含您可能想在整个程序中为每个线程堆栈一次使用的所有内存。但那又怎样。不是说我们这样做可能会用完当前常见的 48 位限制，或者硬件制造商不能轻易地将限制增加到 64 位？

这里没有太多特定于 F# 的内容。我希望在 C# 中也适用同样的限制，并且认为那里不再需要它，尽管在以命令式编程时在实践中显然要少很多痛苦。

非常感谢您的任何回复/评论。

编辑:我写了以下答案的摘要。

Answer 1

到目前为止，F# 在这种情况下继承 .NET 限制的最令人信服的原因是兼容性。编译器可以并且确实完全消除了堆栈，例如标准 ML 的 SML/NJ 编译器自动将程序转换为延续传递样式。两个主要缺点是它需要对破坏兼容性的调用约定进行全局更改，并且它的效率大大降低。如果 F# 这样做是为了避免堆栈溢出，那么 C# 的互操作性会更加困难，而 F# 会慢很多。

深堆栈是一个坏主意的另一个原因是垃圾收集器。堆栈被 GC 特殊处理，因为它们保证是线程本地的并且可以在不需要收集的情况下收缩。只要任何线程产生 gen0 集合，.NET GC 就会遍历所有线程堆栈。因此，只有两个具有深堆栈的 sleep 线程可以使另一个线程运行慢 10 倍。想象一下，如果筹码更深，情况会更糟。这可以通过改变 GC 处理堆栈的方式来解决，本质上是将它们变成堆，但这会使堆栈操作变慢很多。