use*_*059 15 recursion f# tail-recursion
我想知道是否有一个根本原因将F#中的递归深度限制在10000左右,理想情况下如何避免该限制.我认为编写使用O(n)堆栈空间的代码是完全合理的,如果不同意的人可以解释他们为什么这样做,我将不胜感激.非常感谢.我在下面解释我的想法.
我没有看到有任何理由不允许堆栈增长,直到整个可用内存耗尽.这意味着无限递归需要更长时间才能注意到,但并不是说我们不能编写消耗无限内存的程序.我知道可以使用continuation和尾递归将堆栈使用减少到O(1),但我并不特别看到我必须一直这样做是有益的.我也没有看到如何知道函数何时需要处理"大"输入(通过8位微控制器的标准).
我认为这与必须例如使用累积参数以避免二次时间行为有根本的不同.虽然这也涉及担心实现细节,并且不需要为"小"输入完成,但它也是非常不同的,因为编译器本身不能轻易地删除问题.进一步的不同之处在于,稍微复杂的O(n)代码如果天真地写入则是O(n ^ 2)比简单,缓慢,易于阅读的版本更有用.相比之下,延续式代码与相应的天真版本具有完全相同的内存复杂性,但只使用不同类型的内存.这是编译器在这个时代不应该让我担心的事情吗？
虽然我"更喜欢"理论上的原因,为什么不可能有一个深层叠加,我们也可以讨论实际方面.在我看来,堆栈是一种比堆更有效的管理内存的方式,因为它不需要垃圾收集并且很容易被释放？我不确定我是否能看到允许深堆栈的成本.不可否认,操作系统需要留出足够的虚拟空间来包含您可能希望在整个程序中为每个线程堆栈一次使用的所有内存.但那是什么呢.通过这样做,或者硬件制造商不能轻易地将该限制增加到64位,这并不是说我们可能会用尽当前常见的48位限制？
F#没有那么具体.我希望在C#中也适用同样的限制,并且没有看到它在那里更加必要,尽管在以命令式方式编程时,实际上显然不那么痛苦.
非常感谢任何回复/评论.
编辑:我写了以下答案的摘要.
到目前为止,F#在这种情况下继承.NET限制的最令人信服的原因是兼容性.编译器可以并且完全消除堆栈,例如标准ML的SML/NJ编译器将程序自动转换为连续传递样式.两个主要缺点是它需要对调用约定进行全局更改,这会破坏兼容性并且效率大大降低.如果F#这样做可以避免堆栈溢出,那么C#的互操作性将会更加困难,而F#会慢得多.
深度堆栈是个坏主意的另一个原因是垃圾收集器.堆栈由GC专门处理,因为它们保证是线程本地的,并且可以在不需要收集的情况下收缩.只要任何线程产生gen0集合,.NET GC就会遍历所有线程堆栈.因此,只有两个具有深堆栈的睡眠线程可以使另一个线程运行速度慢10倍.想象一下,使用更深层次的堆栈会有多糟糕.这可以通过改变GC处理堆栈的方式来解决,实际上将它们变成堆,但这会使堆栈操作慢很多.
从理论上讲,一切皆有可能.您可以编写一个使用堆来管理传统"堆栈"的编译器.
在实践中,性能(特别是对于像'函数调用'这样的基础知识)很重要.我们为有限堆栈内存模型定制/优化了半个世纪的硬件和操作系统.
这是编译器在这个时代不应该让我担心的事情吗？
咩.垃圾收集是一个巨大的胜利; 管理所有内存是一项大多数不必要的工作,许多应用程序可以在这里为程序员的生产力权衡一些性能.但是我认为很少有人觉得堆栈/递归的人工管理是一个大问题,即使在函数式语言中也是如此,因此让程序员摆脱困境的价值是,IMO,边缘.
请注意,在F#中,您可以使用CPS工作流,它将把相当多的堆栈转换为堆和/或尾调用,如果你想去那里,编程风格/语法的变化相对较小(参见例如这里)).