3

次のコードは、Findw / Replaceinのすべての出現を置き換えRequest、答えをに入れるDCGResultです。この質問のコードについては、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([], []).

このコードは末尾再帰ですか？述語の2番目の定義のphraseへの再帰呼び出しの後にへの呼び出しがあります。の3番目の定義には、への再帰呼び出しの後にもあります。再帰呼び出しが最後に行われた場合、コードは末尾再帰になると思いました。生成されたコードが末尾再帰でない場合、Prologに末尾再帰コードを生成させる方法はありますか？前もって感謝します。replacereplaceE=[F|G]replacereplace

4

1 に答える 1

4

上記のコードには、セミコンテキストの非常に広範囲にわたる一般化のような非常に複雑な構造が含まれています。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つの目標を交換することで末尾再帰にすることができます。それでも、多くの人は上記の翻訳が好ましいと考えています。なぜなら、それは明らかに特定の望ましい特性を保持し、また頻繁により効率的な実行につながるからです。

于 2011-06-21T18:17:28.923 に答える