3

以下代码是一个 DCG，用于替换所有出现的Findw/ ReplaceinRequest并将答案放入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([], []).

这段代码是尾递归的吗？在 predicate 的第二个定义中的phrase递归调用之后有一个调用。在第三个定义中的递归调用之后还有. 我认为，如果最后进行递归调用，代码将是尾递归的。如果生成的代码不是尾递归的，有没有办法让 Prolog 生成尾递归代码？提前致谢。replacereplaceE=[F|G]replacereplace

4

1 回答 1

4

上面的代码包含相当复杂的结构，例如对半上下文的非常深远的概括。请注意，以上两者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].

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

于 2011-06-21T18:17:28.923 回答