C# の yield ステートメントを実装するためのアルゴリズム

Question

自分で調べたいのですが、迷っていました おおよそ、yield ステートメントを含む関数を列挙子のステート マシンに変換するアルゴリズムは何ですか? たとえば、C# では次のようになります。

IEnumerator<string> strings(IEnumerable<string> args)
 { IEnumerator<string> enumerator2 = getAnotherEnumerator();     
   foreach(var arg in arg) 
    { enumerator2.MoveNext();
      yield return arg+enumerator.Current;
    } 
 }

これに：

bool MoveNext()
 { switch (this.state)
    {
        case 0:
            this.state = -1;
            this.enumerator2 = getAnotherEnumerator();
            this.argsEnumerator = this.args.GetEnumerator();
            this.state = 1;
            while (this.argsEnumerator.MoveNext())
            {
                this.arg = this.argsEnumerator.Current;
                this.enumerator2.MoveNext();
                this.current = this.arg + this.enumerator2.Current;
                this.state = 2;
                return true;

              state1:
                this.state = 1;
            }
            this.state = -1;
            if (this.argsEnumerator != null) this.argsEnumerator.Dispose();
            break;

        case 2:
            goto state1;
    }
    return false;
}

もちろん、元のコードによっては結果がまったく異なる場合があります。

Answer 1

あなたが見ている特定のコード サンプルには、一連の変換が含まれています。これはアルゴリズムの大まかな説明であることに注意してください。コンパイラーによって使用される実際の名前と、コンパイラーが生成する正確なコードは異なる場合があります。ただし、考え方は同じです。

最初の変換は「foreach」変換で、次のコードを変換します。

foreach (var x in y)
{
   //body
}

このコードに:

var enumerator = y.GetEnumerator();
while (enumerator.MoveNext())
{
    var x = enumerator.Current;
    //body
}

if (y != null)
{
    enumerator.Dispose();
}

2 番目の変換では、関数本体内のすべての yield return ステートメントを検索し、それぞれに番号 (状態値) を割り当て、yield の直後に「goto ラベル」を作成します。

3 番目の変換では、メソッド本体内のすべてのローカル変数と関数の引数をクロージャと呼ばれるオブジェクトに持ち上げます。

例のコードを考えると、次のようになります。

 class ClosureEnumerable : IEnumerable<string>
 {
    private IEnumerable<string> args;
    private ClassType originalThis;
    public ClosureEnumerator(ClassType origThis, IEnumerable<string> args)
    {
        this.args = args;
        this.origianlThis = origThis;
    }
    public IEnumerator<string> GetEnumerator()
    {
        return new Closure(origThis, args);
    }
 }

class Closure : IEnumerator<string>
{
    public Closure(ClassType originalThis, IEnumerable<string> args)
    {
        state = 0;
        this.args = args;
        this.originalThis = originalThis;
    }

    private IEnumerable<string> args;
    private IEnumerator<string> enumerator2;
    private IEnumerator<string> argEnumerator;

    //- Here ClassType is the type of the object that contained the method
    //  This may be optimized away if the method does not access any 
    //  class members
    private ClassType originalThis;

    //This holds the state value.
    private int state;
    //The current value to return
    private string currentValue;

    public string Current
    {
        get 
        {
            return currentValue;
        }
    }
}

次に、メソッド本体が元のメソッドから MoveNext と呼ばれる「Closure」内のメソッドに移動されます。このメソッドはブール値を返し、IEnumerable.MoveNext を実装します。ローカルへのアクセスはすべて「this」を介してルーティングされ、クラス メンバーへのアクセスはすべて this.originalThis を介してルーティングされます。

「yield return expr」は次のように変換されます。

currentValue = expr;
state = //the state number of the yield statement;
return true;

すべての yield Break ステートメントは次のように変換されます。

state = -1;
return false;

関数の最後には「暗黙の」yield Break ステートメントがあります。次に、プロシージャの先頭に switch ステートメントが導入され、状態番号を調べて関連するラベルにジャンプします。

元のメソッドは次のように変換されます。

IEnumerator<string> strings(IEnumerable<string> args)
{
   return new ClosureEnumerable(this,args);
}

メソッドの状態がすべてオブジェクトにプッシュされ、MoveNext メソッドが switch ステートメント / 状態変数を使用するという事実により、反復子はあたかも制御が最後の "yield return" の直後のポイントに戻されているかのように動作できます。次回「MoveNext」が呼び出されるときの「ステートメント」。

ただし、C# コンパイラで使用される変換は、これを行うための最良の方法ではないことを指摘することが重要です。再帰アルゴリズムで「yield」を使用しようとすると、パフォーマンスが低下します。これを行うためのより良い方法を概説した優れた論文がここにあります。

http://research.microsoft.com/en-us/projects/specsharp/iterators.pdf

まだ読んでいない方は読む価値があります。

Answer 2

この質問を見つけました - 私 記事を書きました 最近それについて。ただし、ここで言及されている他のリンクを記事に追加する必要があります...

Answer 3

レイモンド・チェンはこれに答えます。 http://blogs.msdn.com/b/oldnewthing/archive/2008/08/12/8849519.aspx

(シリーズのパート 4 ではなくパート 1 を指すように編集されました)