Prolog DCGをtail-recursiveに拡張してこのコードを生成しますか？

Question

次のコードは、Find w/Replaceのすべての数字をRequest &に置き換えるDCGです。答えはResultです。マットのおかげで、コードは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の2番目の定義でreplaceへの再帰呼び出しの後にphraseへの呼び出しがあります。第3の定義replaceのreplaceへの再帰呼び出しの後にE=[F|G]もあります。私は、再帰呼び出しが最後に行われた場合、コードは末尾再帰であると考えました。生成されたコードがtail-recursiveでない場合、Prologにtail-recursiveコードを生成させる方法はありますか？前もって感謝します。

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

これは、どちらかの再帰的な尾ではありませんが、交換することでそうであるようにすることができます2つの目標。 明らかに、ある望ましい特性を保持しており、しばしばより効率的な実行にもつながるので、上記の翻訳は、多くの場合、好ましいと考えられている。