13

私は楽しみのために「Learn Prolog now」オンラインブックに取り組んでいます。

アキュムレータを使用して、リストの各メンバーを通過し、リストに追加する述語を作成しようとしています。末尾再帰なしで簡単に実行できました。

addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).

しかし、パフォーマンス上の理由から、このタイプの再帰は避ける方がよいと読みました。これは本当ですか？常に末尾再帰を使用することは「良い習慣」と見なされますか? 良い習慣を身につけるためにアキュムレータを使用する価値はありますか?

この例をアキュムレータを使用するように変更しようとしましたが、リストが逆になります。どうすればこれを回避できますか?

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).
4

5 に答える 5

12

簡単な答え: 末尾再帰は望ましいですが、強調しすぎないでください。

あなたの元のプログラムは、Prolog で得られるのと同じくらい末尾再帰的です。しかし、もっと重要な問題があります: 正確性と終了です。

実際、多くの実装は、より重要と考える他のプロパティのために末尾再帰性を犠牲にすることを厭いません。たとえば不動。

しかし、試みた最適化にはいくつかのポイントがあります。少なくとも歴史的な観点から。

1970 年代には、主要な AI 言語は LISP でした。そして対応する定義は

(defun addone (xs)
  (cond ((null xs) nil)
    (t (cons (+ 1 (car xs))
         (addone (cdr xs))))))

これは直接の末尾再帰ではありません: その理由はcons: 当時の実装では、その引数が最初に評価され、その後で初めてcons実行されました。したがって、これをあなたが示したように書き直す（そして結果のリストを逆にする）ことは、可能な最適化手法でした。

ただし、Prolog では、論理変数のおかげで、実際の値を知る前にコンスを作成できます。LISP では末尾再帰ではなかった非常に多くのプログラムが、Prolog では末尾再帰プログラムに変換されました。

この影響は、今でも多くの Prolog 教科書に見られます。

于 2012-12-31T10:33:15.123 に答える
7

addOneプロシージャは、すでに末尾再帰です。

is / 2は決定論的であるため、先頭と最後の再帰呼び出しの間に選択ポイントはありません。

アキュムレータは、末尾再帰を可能にするために追加されることがあります。私が考えることができるより単純な例は、reverse/2です。これはナイーブリバース（nreverse / 2）、非末尾再帰です

nreverse([], []).
nreverse([X|Xs], R) :- nreverse(Xs, Rs), append(Rs, [X], R).

アキュムレータを追加すると

reverse(L, R) :- reverse(L, [], R).
reverse([], R, R).
reverse([X|Xs], A, R) :- reverse(Xs, [X|A], R).

これで、reverse / 3は末尾再帰になります。再帰呼び出しは最後の呼び出しであり、選択ポイントは残りません。

于 2012-12-31T07:12:51.200 に答える
4

OP は次のように述べています。

しかし、パフォーマンス上の理由から [tail] 再帰を避ける方がよいと読みました。これは本当ですか？常に末尾再帰を使用することは「良い習慣」と見なされますか? 良い習慣を身につけるためにアキュムレータを使用する価値はありますか?

末尾再帰構造を反復 (ループ) に変換するのは、かなり単純な最適化です。テール (再帰) 呼び出しは最後に行われるため、述語/関数/メソッドの先頭にジャンプするだけで、スタック フレームを再帰呼び出しで再利用し、すべての意図と目的のために再帰をループにすることができます。 /サブルーチン。したがって、末尾再帰述語はスタックをオーバーフローしません。最適化が適用された末尾再帰構造には、次の利点があります。

  • 新しいスタック フレームを割り当てたり解放したりする必要がないため、実行がわずかに高速になります。さらに、参照の局所性が向上するため、おそらくページングが少なくなります。
  • 再帰の深さに上限はありません。
  • スタック オーバーフローはありません。

考えられる欠点は？

  • 有用なスタック トレースの損失。TRO がリリース/最適化ビルドでのみ適用され、デバッグ ビルドでは適用されない場合は問題ありませんが...
  • 開発者は TRO に依存するコードを作成します。つまり、コードは TRO を適用して問題なく動作し、TRO を適用しないと失敗します。つまり、上記のケース (リリース/最適化ビルドのみの TRO) では、リリース ビルドとデバッグ ビルドの間に機能的な変更が存在し、基本的に、コンパイラ オプションの選択によって、同一のソース コードから 2 つの異なるプログラムが生成されることを意味します。

もちろん、言語標準が末尾再帰の最適化を要求する場合、これは問題ではありません。

ウィキペディアを引用するには：

テール コールは、コール スタックに新しいスタック フレームを追加せずに実装できるため、重要です。現在のプロシージャのフレームの大部分は不要になり、必要に応じて変更されたテール コールのフレームに置き換えることができます (プロセスのオーバーレイに似ていますが、関数呼び出しの場合)。その後、プログラムは呼び出されたサブルーチンにジャンプできます。標準の呼び出しシーケンスの代わりにこのようなコードを生成することを、末尾呼び出しの削除または末尾呼び出しの最適化と呼びます。

以下も参照してください。

なぜ多くの言語が末尾再帰の最適化を実装しないのか理解できませんでした

于 2012-12-31T18:20:05.203 に答える
2

addoneの最初のバージョンが効率の悪いコードにつながるとは思いません。また、はるかに読みやすいので、回避することをお勧めする理由はありません。

より複雑な例では、コンパイラがコードを末尾再帰に自動的に転送できない場合があります。その場合、最適化として書き直すのが合理的かもしれませんが、それが本当に必要な場合に限られます。

では、動作する末尾再帰バージョンをどのように実装できますaddoneか? reverse不正行為である可能性がありますが、末尾再帰で実装されていると仮定すると (たとえば、こちらを参照)、問題を解決するために使用できます。

accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],Acc,Result) :- reverse(Acc, Result).
addone(List,Result) :- accAddOne(List,[],Result).

しかし、それは非常に不器用です。:-)

ところで、私はより簡単な解決策を見つけることができません。foldrHaskell では通常、末尾再帰が定義されていないのと同じ理由である可能性があります。

于 2012-12-31T02:36:28.193 に答える