19

tl;dr;

C# では、それ自体しか呼び出さず、有効な再帰終了条件を持つ遅延反復子関数がスタック オーバーフローを引き起こさないという保証はありますか?

詳細な質問:

原則として、TCO (Tail Call Optimization) 命令が C# コンパイラ (または JIT) によって生成されるという保証は得られないことを私は知っています。

この TCO の認識を考えると、コルーチンとしての性質のために遅延イテレータ関数 ( yield returnetc を使用) があるのではないかと考えています。再入可能性があるため、コルーチンの私の直感は、新しいフレームを作成する代わりに、関数から飛び出して親のフレームから次の関数にジャンプする機能が自然に見えるため、各末尾呼び出しがデフォルトで最適化されるということです。

これは C# での動作ですか、それとも C# イテレータ関数の再帰呼び出しは、親フレームに飛び出して新しいパラメータで再入力するのではなく、現在のフレームから新しいフレームを作成しますか?

例：

public static IEnumerable<IEnumerable<T>> GeneratePermutations<T>(this IEnumerable<T> choices, int numberToChoose)
{
    if (numberToChoose == 1)
    {
        foreach (var choice in choices)
            yield return new T[] { choice };
        yield break;
    }

    var subPermutations = choices.SelectMany(choice =>
        choices.Where(elem => !EqualityComparer<T>.Default.Equals(elem, choice))
            .GeneratePermutations(numberToChoose - 1)
            .Select(permutation => (new T[] { choice }).Concat(permutation)));
    foreach (var perm in subPermutations)
        yield return perm;
}

私の直感は、上記の例に基づいていますsubPermutations。それは単に山積みの計算であり、それを反復するように呼び出されたように見えます。現在のフレームから、ヒープされた計算を新しいフレームに拡張します-再帰呼び出しが試行される前にそこにあったものに余分なスタックスペースはかかりません...

この直感はまったく根拠のないものかもしれません...

4

1 に答える 1

10

それでは、参照するものがあるように、メソッドの例で始めましょう。

public static IEnumerable<int> Foo()
{
    yield return 1;
    foreach (var n in Foo())
        yield return n;
}

これが再帰反復子ブロックです。少し時間を取って、関連する可能性がある (または関連しない可能性がある) このメソッドのいくつかのプロパティを呼び出したいと思います。

  • 再帰呼び出しがありますが、再帰呼び出しはyield.

  • 再帰呼び出しに到達すると、その時点以降に行うことは、すべての結果を生成することだけです。各アイテムの投影、finallyブロック、利回りの後には何もありません。

では、コードが次のように記述された場合はどうなるでしょうか。

foreach(var n in Foo())
    Console.WriteLine(n);

さて、このステートメントに到達したときに最初に起こることはFoo()、値を評価することです。この場合、シーケンスのジェネレータを表すステート マシンが作成されます。ただし、メソッド本体のコードは実際には実行していません。

次に、 を呼び出しますMoveNext。最初のブロックにヒットしyield、値を生成して出力します。

その後、最も外側のレベルがMoveNext再び呼び出します。ここで、ステート マシンのMoveNextメソッドが独自のforeachブロックに到達します。Mainメソッドと同様Foo()に、値を評価して、2 番目のステート マシンを作成します。MoveNextその後、すぐにそのステート マシンを呼び出します。その 2 番目のステート マシンは最初の に到達yieldし、最初のイテレータに値を渡します。最初のイテレータは、その値をメイン メソッドに戻して出力します。

次に、メイン メソッドがMoveNext再度呼び出されます。最初のイテレータは 2 番目のイテレータに 2 番目のアイテムを要求し、2 番目のイテレータはそのforeachメソッドに到達し、3 番目のイテレータを作成し、そこから値を取得します。値はずっと上に渡されます。

ここでわかるように、別のアイテムのトップ レベル イテレータを使用するたびに、スタックは常に以前よりも 1 レベル深くなります。ステート マシンを使用していて、反復子を作成しても多くのスタック スペースが消費されないという事実にもかかわらず、シーケンス内の次の項目を取得すると、スタック スペースがなくなるまで、ますます多くのスタック スペースが消費されます。

コードを実行すると、ここで説明したとおりに動作し、スタックがオーバーフローすることがわかります。

では、これを最適化するにはどうすればよいでしょうか。

ここでやりたいことは、最上位イテレータがforeach、「これからは、シーケンス内の残りのアイテムが再帰呼び出し内のすべてのアイテムと同一である」ということを認識できるようにすることです。 . これは、典型的な TCO の状況によく似ています。

したがって、この時点で解決すべき問題が 2 つあります。まず、この状況にあることを認識した場合、実際に追加のステート マシンの作成を回避できるので、スタック スペースが増え続けることはありません。それほど簡単ではなく、従来の非反復子ブロックの TCO ほど簡単ではない可能性があります。ステート マシンのすべてのインスタンス フィールドを、 を呼び出した場合に作成されるステート マシンのインスタンス フィールドに設定する必要がありますFoo。この時点で手を振って、これは可能に聞こえますが、それぞれが完璧であるとは言えません。

次に、別の問題があります。TCO が有効なこの位置に実際にいることをどのように認識できますか? 再帰的に自分自身を呼び出す必要があります。そのメソッド呼び出しでは、全体を反復して各アイテムをそのままの状態で生成する以外に何もする必要はありません。tryorusingブロックにいる必要はありません (そうしないと、finallyブロックが失われます)であり、その繰り返しの後にメソッドが存在することはできません。

さて、yield foreachオペレーターがいれば、これはそれほど悪くないでしょう。反復子ブロックの最後のステートメントがyield foreach、メソッドへの再帰呼び出しを最後に持つ演算子である場合は、TCO を適用するというルールを設定するだけです。残念ながら、C# には (他の .NET 言語とは異なり)yield foreach演算子がありません。演算子全体を入力する必要がありforeachますが、アイテムをそのままの状態で生成する以外には何もしません。それは…ちょっとむずかしそうですね。

要点をまとめると：

  • コンパイラが再帰反復子ブロックに末尾呼び出しの最適化を使用することは可能ですか?
    • 最も可能性が高い。
  • コンパイラによってこれまでに行われましたか？
    • そうは見えません。
  • このサポートをコンパイラに追加することは特に実現可能でしょうか?
    • おそらくそうではありません。
于 2014-08-14T19:42:05.950 に答える