recursion - 读取深度嵌套的树会导致堆栈溢出

Question

我正在尝试将大量 sexp 从文件读取到内存中，对于较小的输入似乎效果很好，但对于嵌套更深的输入，sbcl 会因堆栈耗尽而崩溃。似乎有一个 sbcl 根本无法超越的硬递归限制(在 1000 个函数深度)(奇怪的是，即使它的堆栈大小增加)。示例(代码为 here):make check-c 有效，但 make check-cpp 耗尽堆栈，如下所示:

INFO: Control stack guard page unprotected
Control stack guard page temporarily disabled: proceed with caution
Unhandled SB-KERNEL::CONTROL-STACK-EXHAUSTED in thread #<SB-THREAD:THREAD
                                                         "main thread" RUNNING
                                                          {10034E6DE3}>:
  Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Backtrace for: #<SB-THREAD:THREAD "main thread" RUNNING {10034E6DE3}>
0: ((LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX))
1: (SB-IMPL::CALL-WITH-SANE-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100FC9006B}>)
2: (SB-IMPL::%WITH-STANDARD-IO-SYNTAX #<CLOSURE (LAMBDA NIL :IN SB-DEBUG::FUNCALL-WITH-DEBUG-IO-SYNTAX) {100FC9003B}>)
...

那我为什么要使用递归呢？实际上，我不是，但不幸的是内置的 (read) 使用递归，这就是堆栈溢出发生的地方。另一个选项(我已经开始研究)是编写 read 的迭代版本，它依赖于我从一个单独的程序中输入的更有限的语法，以避免复杂性重新实现读取(我的(当前失败的)尝试在上述存储库的 lisp 分支中)。

但是，我更喜欢更规范的解决方案。除了可以通过避免递归来解析深层嵌套结构的内置 read 之外，还有其他替代方法吗？

编辑:这似乎是 sbcl 本身无法克服的问题，而不是输入数据。举个简单的例子，尝试运行:

(for i in $(seq 1 2000); do
echo -n "("
done; echo -n "2"; for i in $(seq 1 2000); do
echo -n ")"
done; echo) > file

然后在 sbcl 中:

(with-open-file (file "file" :direction :input) (read file))

出现同样的故障。

编辑:在 #sbcl 上询问，显然控制堆栈大小实际上仅适用于新线程，并且主线程的堆栈大小也受到许多其他因素的影响.所以我尝试将读取放在一个单独的线程中。仍然没有用。结帐this repo如果您感兴趣，请运行 make check。

Answer 1

我不知道你做了什么(因为你没有准确显示)，但是当我按如下方式启动 sbcl 时，你的示例对我来说工作正常:

sbcl --control-stack-size 100

当然，我推荐 GNU CLISP 和 Embedded Common Lisp，因为它们对于您的示例也可以正常工作。

我将为 future 的读者添加对此答案的引用:https://stackoverflow.com/a/9002973/816536

我还会提到，在许多 CL 实现中可能需要使用适当的优化选项编译代码，以便从尾调用优化中获益。