13

我正在通过“Learn Prolog now”在线书籍来寻找乐趣。

我正在尝试使用累加器编写一个谓词，该谓词遍历列表的每个成员并向其添加一个。我已经很容易做到了，没有尾递归。

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

但我读过，出于性能原因，最好避免这种类型的递归。这是真的？总是使用尾递归是否被认为是“好习惯”？使用蓄能器来养成一个好习惯值得吗？

我试图将此示例更改为使用累加器，但它反转了列表。我怎样才能避免这种情况？

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).
4

5 回答 5

12

简短的回答：尾递归是可取的，但不要过分强调它。

您的原始程序与 Prolog 中的尾递归程序一样。但还有更重要的问题：正确性和终止。

事实上，许多实现更愿意为他们认为更重要的其他属性牺牲尾递归。例如坚定不移。

但是您尝试的优化有一定的意义。至少从历史的角度来看。

早在 1970 年代，主要的 AI 语言是 LISP。相应的定义是

(defun 插件 (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs)))
         （添加（cdr xs））））））

这不是直接的尾递归：原因是cons：在那个时候的实现中，它的参数首先被评估，然后才cons可以执行。因此，按照您的指示重写（并反转结果列表）是一种可能的优化技术。

然而，在 Prolog 中，由于逻辑变量，您可以在知道实际值之前创建缺点。这么多在 LISP 中不是尾递归的程序，在 Prolog 中被翻译成尾递归程序。

在许多 Prolog 教科书中仍然可以找到这种影响。

于 2012-12-31T10:33:15.123 回答
7

您的 addOne 过程已经是尾递归的。

在头和最后一个递归调用之间没有选择点，因为 is/2 是确定性的。

有时会添加累加器以允许尾递归，我能想到的更简单的例子是 reverse/2。这是一个朴素的反向（nreverse/2），非尾递归

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

如果我们添加一个累加器

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

现在 reverse/3 是尾递归：递归调用是最后一个，没有选择点。

于 2012-12-31T07:12:51.200 回答
4

OP 说：

但是我已经读过，出于性能原因，最好避免 [tail] 递归。这是真的？总是使用尾递归是否被认为是“好习惯”？使用蓄能器来养成一个好习惯值得吗？

将尾递归构造转换为迭代（循环）是一种相当简单的优化。由于尾部（递归）调用是最后完成的事情，因此堆栈帧可以在递归调用中重用，通过简单地跳转到谓词/函数/方法的开头，就所有意图和目的而言，使递归成为一个循环/子程序。因此，尾递归谓词不会溢出堆栈。应用了优化的尾递归构造具有以下优点：

  • 由于不需要分配/释放新的堆栈帧，因此执行速度稍快；此外，您可以获得更好的参考位置，因此可以说分页更少。
  • 递归深度没有上限。
  • 没有堆栈溢出。

可能的缺点？

  • 有用的堆栈跟踪丢失。如果 TRO 仅应用于发布/优化版本而不是调试版本，则不是问题，但是...
  • 开发人员将编写依赖于 TRO 的代码，这意味着应用 TRO 的代码将运行良好，如果不应用 TRO，代码将失败。这意味着在上述情况下（TRO 仅在发布/优化构建中），发布和调试构建之间存在功能更改，本质上意味着一个人选择的编译器选项会从相同的源代码生成两个不同的程序。

当语言标准要求尾递归优化时，这当然不是问题。

引用维基百科：

尾调用很重要，因为它们可以在不向调用堆栈添加新堆栈帧的情况下实现。当前过程的大部分框架都不再需要了，可以用尾调用的框架代替，并酌情修改（类似于进程的覆盖，但用于函数调用）。然后程序可以跳转到被调用的子程序。生成这样的代码而不是标准调用序列称为尾调用消除或尾调用优化。

也可以看看：

我一直不明白为什么更多的语言不实现尾递归优化

于 2012-12-31T18:20:05.203 回答
2

我不认为第一个版本会addone导致代码效率降低。它也更具可读性，所以我认为没有理由避免它是一种好的做法。

在更复杂的示例中，编译器可能无法自动将代码转换为尾递归。那么将其重写为优化可能是合理的，但前提是确实有必要。

那么，如何实现一个有效的尾递归版本addone？它可能是作弊，但假设它reverse是通过尾递归实现的（例如，请参见此处），那么它可以用来解决您的问题：

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],Acc,Result) :- reverse(Acc, Result).
addone(List,Result) :- accAddOne(List,[],Result).

不过，这非常笨拙。:-)

顺便说一句，我找不到更简单的解决方案。可能由于与 Haskell 中相同的原因，foldr通常不使用尾递归定义。

于 2012-12-31T02:36:28.193 回答
0

与其他一些编程语言相比，某些 Prolog 实现非常适合尾递归程序。尾递归可以作为最后调用优化 (LCO) 的一种特殊情况来处理。例如，这里在 Java 中不起作用：

public static boolean count(int n) {
    if (n == 0) {
        return true;
    } else {
        return count(n-1);
    }
}

public static void main(String[] args) {
    System.out.println("count(1000)="+count(1000));
    System.out.println("count(1000000)="+count(1000000));
}

结果将是：

count(1000)=true
Exception in thread "main" java.lang.StackOverflowError
    at protect.Count.count(Count.java:9)
    at protect.Count.count(Count.java:9)

另一方面，主要的 Prolog 实现对此没有任何问题：

 ?- [user].
 count(0) :- !.
 count(N) :- M is N-1, count(M).
 ^D

结果将是：

?- count(1000).
true.
?- count(1000000).
true.

Prolog 系统可以做到这一点的原因是，它们的执行通常是蹦床式的，最后调用优化是选择点消除和环境修剪的问题。早期的WAM中已经记录了环境修整。

但是，是的，调试可能是个问题。

于 2020-02-17T11:52:06.740 回答