这段代码是通过扩展 Prolog DCG 尾递归生成的吗？

Question

以下代码是一个 DCG，用于替换 Request 中所有出现的 Find 和 Replace 。将答案放入 Result 中。感谢 mat 在这个问题。

eos([], []).

replace(_, _) --> call(eos), !.
replace(Find, Replace), Replace -->
        Find,
        !,
        replace(Find, Replace).
replace(Find, Replace), [C] -->
        [C],
        replace(Find, Replace).

substitute(Find, Replace, Request, Result):-
        phrase(replace(Find, Replace), Request, Result).

在 SWI-Prolog 中，这扩展到以下内容。

replace(_, _, A, B) :-
        call(eos, A, C), !,
        B=C.
replace(A, D, B, F) :-
        phrase(A, B, C), !,
        E=C,
        replace(A, D, E, G),
        phrase(D, F, G).
replace(B, C, A, E) :-
        A=[F|D],
        replace(B, C, D, G),
        E=[F|G].

substitute(A, B, C, D) :-
        phrase(replace(A, B), C, D).

eos([], []).

这段代码是尾递归的吗？在谓词 replace 的第二个定义中递归调用 replace 后，调用了 phrase。在 replace 的第三个定义中，在递归调用 replace 后还有 E=[F|G]。我认为，如果最后进行递归调用，代码将是尾递归的。如果生成的代码不是尾递归的，有什么办法让Prolog生成尾递归代码吗？提前致谢。

Answer 1

上面的代码包含相当复杂的构造，例如半上下文的非常深远的概括。请注意，上面的 Find 和 Replace 都可以是一般的非终结符 - 不仅仅是列表。

因此，让我们考虑一个更简单的情况：

iseq([]) --> [].
iseq([E|Es]) --> iseq(Es), [E].

它在许多 Prolog 中扩展为：

iseq([], Xs, Xs).
iseq([E|Es], Xs0,Xs) :-
   iseq(Es, Xs0,Xs1),
   Xs1 = [E|Xs].

这也不是尾递归，但可以通过交换两个目标来实现尾递归。
尽管如此，许多人认为上述翻译更可取，因为它显然保留了某些所需的属性，并且还导致通常更有效的执行。