Algoritmo per l'implementazione della dichiarazione di rendimento C #

Question

Mi piacerebbe scoprirlo da solo, ma mi chiedevo più o meno qual è l'algoritmo per convertire una funzione con dichiarazioni di rendimento in una macchina a stati per un enumeratore? Ad esempio, come fa C # a trasformare questo:

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

in questo:

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;
}

Naturalmente il risultato può essere completamente diverso a seconda del codice originale.

Answer 1

Il particolare esempio di codice che stai guardando comporta una serie di trasformazioni. Questa è una descrizione approssimativa dell'algoritmo. I nomi effettivi utilizzati dal compilatore e il codice esatto che genera possono essere diversi. L'idea è la stessa, tuttavia.

La prima trasformazione è la "quotazione foreach" trasformazione, che trasforma questo codice:

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

in questo codice:

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

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

La seconda trasformazione trova tutte le dichiarazioni di rendimento nel corpo della funzione, assegna un numero a ciascuna (un valore di stato) e crea un'etichetta "goto" subito dopo la resa.

La terza trasformazione solleva tutte le variabili locali e gli argomenti delle funzioni nel corpo del metodo in un oggetto chiamato chiusura.

Dato il codice nel tuo esempio, sarebbe simile a questo:

 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;
        }
    }
}

Il corpo del metodo viene quindi spostato dal metodo originale a un metodo all'interno di " Chiusura " chiamato MoveNext, che restituisce un valore booleano e implementa IEnumerable.MoveNext. Qualsiasi accesso a tutti i locali viene instradato attraverso "questo", e qualsiasi accesso a tutti i membri della classe viene instradato attraverso questo. Originale. Questo.

Qualsiasi "rendimento di rendimento expr" è tradotto in:

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

Qualsiasi dichiarazione di rottura del rendimento è tradotta in:

state = -1;
return false;

Esiste un " implicito " rendita break break alla fine della funzione. Viene quindi introdotta un'istruzione switch all'inizio della procedura che esamina il numero di stato e passa all'etichetta associata.

Il metodo originale viene quindi tradotto in qualcosa del genere:

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

Il fatto che lo stato del metodo sia tutto inserito in un oggetto e che il metodo MoveNext utilizzi un'istruzione switch / variabile di stato è ciò che consente all'iteratore di comportarsi come se il controllo fosse passato al punto immediatamente dopo l'ultimo "rendimento di rendimento" la prossima volta " MoveNext " viene chiamato.

È importante sottolineare, tuttavia, che la trasformazione utilizzata dal compilatore C # non è il modo migliore per farlo. Soffre di scarse prestazioni quando si tenta di utilizzare "rendimento" con algoritmi ricorsivi. C'è un buon documento che delinea un modo migliore per farlo qui:

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

Vale la pena leggerlo se non l'hai ancora letto.

Answer 2

Ho appena scoperto questa domanda: ho recentemente scritto un articolo su di esso. Dovrò aggiungere gli altri collegamenti citati qui nell'articolo però ...

Answer 3

Raymond Chen risponde a questo; http://blogs.msdn.com/b/ oldnewthing / archive / 2008/08/12 / 8849519.aspx

(modificato per indicare la parte 1 della serie, non la parte 4)