prolog - 此代码是通过扩展 Prolog DCG 尾递归生成的吗？

Question

以下代码是一个 DCG，用于替换 Request 中所有出现的 Find w/Replace 并将答案放入 Result 。感谢 mat，代码，在 this question .

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].

它在许多序言中扩展为:

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

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