Генерируется ли этот код путем расширения хвостовой рекурсии Prolog DCG? - PullRequest
Новая
       3

Генерируется ли этот код путем расширения хвостовой рекурсии Prolog DCG?

3 голосов
/ 21 июня 2011

Следующий код является DCG, чтобы заменить все вхождения Find w / Replace в Request и поместить ответ в 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 во 2-м определении предиката replace происходит вызов phrase.Также есть E=[F|G] после рекурсивного вызова replace в 3-м определении replace.Я думал, что если бы рекурсивные вызовы были сделаны последними, код был бы рекурсивным.Если сгенерированный код не является хвост-рекурсивным, есть ли способ заставить Prolog сгенерировать хвост-рекурсивный код?Заранее спасибо.

1 Ответ

4 голосов
/ 21 июня 2011

Вышеупомянутый код содержит довольно сложные конструкции, такие как очень далеко идущее обобщение полуконтекста. Обратите внимание, что выше, Find и Replace могут быть общими терминалами, а не только списками.

Итак, давайте рассмотрим более простой случай: 

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

, который расширяется во многих Прологах до: 

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

Это не хвостовая рекурсия, но это можно сделать, обменяв две цели. Тем не менее, многие считают приведенный выше перевод предпочтительным, поскольку он, очевидно, сохраняет определенные желательные свойства, а также приводит к зачастую более эффективному выполнению.

...