lisp - Lisp中递归函数调用的堆栈溢出

Question

我正在从 Conrad Barski 的“The Land of Lisp”一书中学习 Lisp。现在我遇到了我的第一个绊脚石，作者说:

Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged

在显示以下示例函数以计算列表中的项目之后:

(defun my-length (list)
  (if list
    (1+ (my-length (cdr list)))
    0))

当我使用包含一百万个项目的列表调用此函数 my-length 时，我收到堆栈溢出错误。因此，要么你永远不会期望 Lisp 中有这么长的列表(所以我的用例可能没用)，要么有另一种方法来计算这么长的列表中的项目。你能不能对此有所启发？ (顺便说一句，我在 Windows 上使用 GNU CLISP)。

Answer 1

CLISP 中的 TCO(尾调用优化)使用 Chris Taylor 的示例:

[1]> (defun helper (acc list)
       (if list
           (helper (1+ acc) (cdr list))
           acc))

(defun my-length (list)
  (helper 0 list))

HELPER

现在编译它:

[2]> (compile 'helper)
MY-LENGTH
[3]> (my-length (loop repeat 100000 collect t))

*** - Program stack overflow. RESET

现在，以上不起作用。让我们将调试级别设置为低。这允许编译器执行 TCO。

[4]> (proclaim '(optimize (debug 1)))
NIL

再次编译。

[5]> (compile 'helper)
HELPER ;
NIL ;
NIL
[6]> (my-length (loop repeat 100000 collect t))
100000
[7]> 

有效。

允许 Common Lisp 编译器执行 TCO 通常由调试级别控制。对于高调试级别，编译器生成的代码会为每个函数调用使用堆栈帧。这样每个调用都可以被跟踪并且可以在回溯中看到。对于较低的调试级别，编译器可能会在编译后的代码中用跳转替换尾部调用。然后，这些调用将不会在回溯中看到 - 这通常会使调试变得更加困难。