`append`谓词是尾递归的吗？

Question

Prolog中列表处理的典型代码示例是append:

append([], Ys, Ys).
append([X | Xs], Ys, [X | Zs]) :- append(Xs, Ys, Zs).

我的问题是这个程序是否是尾递归的.我想不是我在函数式语言方面的经验.但是,我觉得判断Prolog程序更加困难.我们似乎必须考虑统一.

Answer 1

是的,您的(因此Prolog"标准"版本)append/3是尾递归的.您可以轻松地看到这一点,因为最终目标是呼唤append/3自己.请注意,append函数式语言的典型实现不是尾递归,因为最终调用是一个等效cons于Lisp 的操作,例如对应于:

lisp_append([], Ys, Ys).
lisp_append([X|Xs], Ys, Zs) :-
        lisp_append(Xs, Ys, Zs0),
        Zs = [X|Zs0].

示例查询,产生本地堆栈溢出,因为无法应用尾调用优化:

?- length(Ls, 10_000_000), lisp_append(Ls, [], _).
ERROR: Out of local stack

而你的自然Prolog版本的append/3作品:

?- length(Ls, 10_000_000), append(Ls, [], _).
Ls = [_G8, _G11, _G14, _G17, _G20, _G23, _G26, _G29, _G32|...].

请注意,由于统一的强大功能允许您在尾部调用之前提取部分结果的描述,因此更多谓词在Prolog中比在函数语言中自然是尾递归的.给一个好问题+1.