CODEWITHSUNDEEP
prologdcg
Ashley
Ashley

Reputation: 829

Is this code generated by expanding a Prolog DCG tail-recursive?

The following code is a DCG to replace all occurences of Find w/ Replace in Request & put the answer in Result. Thanks to mat, for the code, in 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).

In SWI-Prolog, this expands to the following.

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([], []).

Is this code tail-recursive? There is a call to phrase after the recursive call to replace in the 2nd definition of the predicate replace. There's also E=[F|G] after the recursive call to replace in the 3rd definition of replace. I thought that, if the recursive calls were made last, the code would be tail-recursive. If the generated code isn't tail-recursive, is there any way to get Prolog to generate tail-recursive code? Thanks in advance.

Upvotes: 3

Views: 236

Answers (1)

false
false

Reputation: 10120

Above code contains quite complex constructs like a very far reaching generalization of a semicontext. Please note that above, both Find and Replace can be general non-terminals - not only lists.

So let's consider a simpler case:

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

which expands in many Prologs to:

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

This isn't tail recursive either, but it can be made to be so by exchanging the two goals. Still, many consider above translation preferable, since it obviously retains certain desirable properties and also leads to a frequently more efficient execution.

Upvotes: 4

Related Questions