10

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

以这种方式称呼自己不仅在 Lisp 中是允许的,而且经常被强烈鼓励

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

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

my-length当我使用包含一百万个项目的列表调用此函数时,出现堆栈溢出错误。因此,要么您永远不会期望在 Lisp 中有这么长的列表(所以也许我的用例没用),或者还有另一种方法可以计算如此长的列表中的项目。你能对此有所启发吗?(顺便说一下,我在 Windows 上使用 GNU CLISP)。

4

4 回答 4

24

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

于 2013-03-07T12:54:45.613 回答
12

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

(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另一个是我们正在计算长度的列表。

重要的一点是helpertail是递归写的,这意味着调用自己是它做的最后一件事。这意味着您不需要在每次函数调用自身时分配新的堆栈帧 - 因为最终结果无论如何都会一直传递回堆栈帧链,您可以避免覆盖旧的堆栈帧使用新的,因此您的递归函数可以在恒定空间中运行。

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

于 2013-03-07T11:05:11.307 回答
8

在 lisp 中创建递归函数来操作递归数据结构确实有好处。列表(在 lisp 中)被定义为递归数据结构,所以你应该没问题。

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

首先,我认为这表明列表数据结构并不是对所有事情都是最好的,在这种情况下,另一种结构可能会更好(但是,你可能还没有在你的 lisp 书中找到向量;- )

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

有关其他迭代方式,请查看:

或其他数据结构:

于 2013-03-07T10:58:14.283 回答
0
(DEFUN nrelem(l) 
    (if (null l)
        0
       (+ (nrelem (rest l)) 1)
))
于 2015-03-29T17:04:56.253 回答