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

Question

我正在从Conrad Barski的"Lisp之乡"一书中学习Lisp.现在我遇到了我的第一个绊脚石,作者说:

以这种方式调用自己不仅允许在Lisp中使用,而且经常受到强烈鼓励

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

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

当我my-length用包含一百万个项目的列表调用此函数时,我收到堆栈溢出错误.因此,无论你休想有一个列表,长期在Lisp的(所以也许我用例是没用的),或者还有另一种方法来计算在这么长的列表项.你能否对此有所启发？(顺便说一句,我在Windows上使用GNU CLISP).

Answer 1

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

[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通常由调试级别控制.具有高调试级别,编译器生成的代码使用每个函数调用的堆栈帧.这样,每个调用都可以被跟踪,并且可以在回溯中看到.使用较低的调试级别,编译器可以使用已编译代码中的跳转替换尾调用.然后这些调用将不会出现在回溯中 - 这通常会使调试更加困难.

Answer 2

你正在寻找尾递归.目前您的功能定义为

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

请注意,在my-length调用自身之后,需要在将该值传递给其调用函数之前将结果添加一个.这就需要返回之前修改值意味着你需要分配一个新的堆栈帧每次调用时,使用的空间是成正比的列表的长度.这是导致长列表上的堆栈溢出的原因.

您可以重写它以使用辅助函数

(defun helper (acc list)
  (if list
    (helper (1+ acc) (cdr list))
    acc))

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

该辅助函数有两个参数,一个积累的参数 acc,它存储列表的长度,到目前为止,名单list是我们计算的长名单.

重要的一点是helper递归写尾,这意味着调用自身是它做的最后一件事.这意味着每次函数调用自己时都不需要分配一个新的堆栈帧 - 因为最终的结果只会一直传递到堆栈帧链上,你可以通过覆盖旧的堆栈框架来逃脱使用新的,所以你的递归函数可以在恒定的空间中运行.

这种形式的程序转换 - 从递归(但非尾递归)定义到使用尾递归辅助函数的等效定义,是函数式编程中的一个重要习惯 - 值得花一点时间理解.

Answer 3

在lisp中创建递归函数以对递归数据结构进行操作确实很有用.并且列表(在lisp中)被定义为递归数据结构,所以你应该没问题.

但是,正如您所经历的那样,如果使用递归遍历数百万个深度的数据结构,也会在堆栈上分配一百万个帧,并且除非您特别要求运行时环境分配大量的堆栈空间,否则您可能会发现堆栈溢出(我不知道你是否或如何在gnu clisp中做到这一点......).

首先,我认为这表明list-datastructure对于所有事情来说并不是最好的,在这种情况下,另一个结构可能会更好(但是,你可能还没有找到你的lisp-book中的向量; - )

另一件事是,对于这样的大型递归是有效的,编译器应该优化尾递归并将它们转换为迭代.我不知道clisp是否具有此功能,但您需要将功能更改为实际可更新.(如果"尾递归优化"没有意义,请告诉我,我可以挖掘一些参考资料)

对于其他迭代方法,请查看:

• http://www.lispworks.com/documentation/HyperSpec/Body/c_iterat.htm
• http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm

或其他数据结构:

• http://www.lispworks.com/documentation/HyperSpec/Body/t_vector.htm