recursion - 为什么在 Racket 中是 "there is no such thing as stack overflow"？

Question

以下段落来自The Racket Guide (2.3.4) :

At the same time, recursion does not lead to particularly bad performance in Racket, and there is no such thing as stack overflow; you can run out of memory if a computation involves too much context, but exhausting memory typically requires orders of magnitude deeper recursion than would trigger a stack overflow in other languages.

我很好奇 Racket 是如何设计来避免堆栈溢出的？更何况，为什么像C这样的其他语言也无法避免这样的问题呢？

Answer 1

首先，一些术语:进行非尾调用需要一个上下文框架来存储局部变量、父返回地址等。所以问题是如何表示任意大的上下文。 “堆栈”(或调用堆栈)只是上下文的一种(公认的常见)实现策略。

下面是一些深度递归(即大上下文)的实现策略:

• 在堆上分配上下文框架，让 GC 负责清理它们。 (这很好也很简单，但可能相对较慢，尽管人们会争论这一点。)
• 在堆栈上分配上下文帧。当栈满时，将栈中当前的帧复制到堆中，清空栈，将栈指针重置为栈底。返回时，如果栈为空，则将帧从堆中复制回栈中。 (不过，这意味着您不能拥有指向堆栈分配对象的指针，因为这些对象会四处移动。)
• 在堆栈上分配上下文帧。当堆栈已满时，分配一个新的大块内存，调用新堆栈(即设置堆栈指针)，然后继续。 (这可能需要 mprotect 或其他操作让操作系统相信新的内存块可以作为调用堆栈处理。)
• 在堆栈上分配上下文帧。当栈满时，创建一个新的线程继续计算，等待线程完成并安排从中抓取一个返回值返回到旧线程的栈中。 (此策略在不允许您直接控制堆栈、堆栈指针等的 JVM 等平台上很有用。另一方面，它会使线程本地存储等功能复杂化。)
• ...以及上述策略的更多变体。

对深度递归的支持通常与对一流延续的支持同时发生。一般来说，实现一流的延续意味着你几乎会自动获得对深度递归的支持。有一篇很好的论文叫做 Implementation Strategies for First-class Continuations由 Will Clinger 等人撰写。有更多细节和不同策略之间的比较。