c# - que - patron de diseño iterator c++

¿Una función de iterador perezoso recursivo correctamente implementada nunca apilará el desbordamiento?

Question

tl; dr;

En C #, ¿tiene garantías de que una función de iterador perezoso que no llame a nada más que a sí misma y tenga una condición de salida de recursión válida no provocará un desbordamiento de pila?

Pregunta detallada:

Sé que, como regla general, no obtiene garantías de que la instrucción Tail Call Optimization (TCO) sea generada por el compilador de C # (o el JIT), por lo que si bien puede obtener el TCO, no hay garantías.

Dado este reconocimiento de TCO, me pregunto si el iterador perezoso funciona (usando yield return etc.) debido a su naturaleza como coroutine. ¿Cada llamada de cola en un espacio de pila es suficiente? Mi intuición de coroutines debido a su re-ingreso es que cada llamada de cola está optimizada por defecto, ya que la capacidad de saltar de la función y pasar a la siguiente desde el marco del padre en lugar de crear un nuevo marco parece natural.

¿Es este comportamiento en C #, o las llamadas recursivas de las funciones del iterador de C # crean un nuevo marco desde el actual en lugar de saltar al marco principal y volver a ingresar con los nuevos parámetros?

Ejemplo:

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

Mi intuición se basa en las subPermutations ejemplo subPermutations es simplemente una computación subPermutations , parece ser una llamada para iterarla, puede saber que es una computación apilada (es una parte de las funciones sig que es una función de iterador), y por lo tanto inmediatamente salte de su marco actual y expanda la computación apilada a un nuevo marco, lo que no cuesta espacio de pila adicional sobre lo que estaba allí antes de que se intentara la llamada recursiva ...

Esta intuición puede ser totalmente infundada ...

Answer 1

Entonces, comencemos con un método de ejemplo, para que tengamos algo de referencia:

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

Aquí está nuestro bloque de iteradores recursivos. Solo quiero tomarme un momento para mencionar algunas propiedades de este método que pueden (o no) terminar siendo relevantes.

• Hay una llamada recursiva, pero la llamada recursiva es después de un yield .

• Cuando alcanzamos nuestra llamada recursiva, lo único que hacemos después de ese punto es producir todos sus resultados. No hay proyección en cada elemento, no hay bloque final, nada después de esos rendimientos, etc.

Entonces, ¿qué sucede cuando un código va y escribe lo siguiente?

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

Bueno, lo primero que sucede cuando alcanzamos esta afirmación es evaluar Foo() a un valor. En este caso, esto crea la máquina de estado que representa el generador de la secuencia. Sin embargo, no hemos ejecutado ninguno de los códigos en el cuerpo del método.

A continuación, llamamos MoveNext . Llegamos a nuestro primer bloque de yield , obtenemos un valor e imprimimos.

Después de eso, el nivel más externo llama MoveNext nuevamente. Aquí el método MoveNext nuestra máquina de estado alcanza su propio bloque foreach . Al igual que el método Main , evaluará Foo() a un valor, creando una segunda máquina de estados. Inmediatamente llamará a MoveNext en esa máquina de estados. Esa segunda máquina de estado alcanzará su primer yield , le dará el valor al primer iterador, que lo devolverá al método principal, que lo imprimirá.

Entonces el método principal llama a MoveNext nuevamente. El primer iterador solicita al segundo iterador su segundo elemento, el segundo iterador alcanza su método foreach , crea un tercer iterador y obtiene un valor de este. El valor se pasa todo el camino hacia arriba.

Como podemos ver aquí cada vez que nosotros, como nuestro iterador de nivel superior para otro elemento, la pila es siempre un nivel más profundo que antes. A pesar de que estamos usando máquinas de estado, y que crear los iteradores no consume mucho espacio de pila, obtener el siguiente elemento de la secuencia consumirá más y más espacio de pila, hasta que se agote.

Al ejecutar el código, podemos ver que las cosas funcionan exactamente como se describe aquí, y la pila se desbordará.

Entonces, ¿cómo podría optimizarse esto?

Bueno, lo que esperamos hacer aquí es que el iterador de nivel superior se dé cuenta de que cuando llegue a la foreach que "a partir de ahora, el resto de los elementos de mi secuencia son idénticos a todos los elementos de la llamada recursiva. ". Esto se parece mucho a una situación típica de TCO.

Así que en este punto tenemos dos problemas por resolver. Primero, si reconocemos que estamos en esta situación, ¿podemos realmente evitar la creación de máquinas de estado adicionales y, por lo tanto, el espacio de pila en continuo aumento? No sería tan fácil, probablemente no tan fácil como el TCO tradicional de bloques sin iteradores. Necesitaría establecer todos los campos de instancia de la máquina de estado en cualquiera de los campos de instancia que serían de la máquina de estado que se crearía si hubiera llamado a Foo . Solo voy a agitar mis manos en este punto y decir que esto suena posible , pero no exactamente súper.

Entonces tenemos el otro problema. ¿Cómo podemos reconocer que estamos realmente en esta posición donde el TCO es válido? Necesitamos que nos llamemos a nosotros mismos recursivamente, no debemos hacer nada con ese método, aparte de iterar todo y generar cada elemento exactamente como está, no debemos estar en un try o using bloque (de lo contrario, el bloque sería perderse), y no puede haber ningún método después de esa iteración.

Ahora, si hubiera un yield foreach operador, entonces esto no sería tan malo. Acabas de establecer la regla de que si la última declaración en el bloque del iterador es un yield foreach operador con una llamada recursiva al método al final, aplica el TCO. Lamentablemente, en C # (a diferencia de otros lenguajes .NET) no tenemos yield foreach operador. Tenemos que escribir todo el operador foreach , mientras que no hacemos nada más que entregar el artículo exactamente como está. Eso parece ... un poco incómodo.

Recordar:

• ¿Es posible que el compilador use Tail Call Optimization para bloques de iteradores recursivos?
  • Más probable.
• ¿Lo hace el compilador alguna vez?
  • No parece ser así.
• ¿Sería particularmente factible agregar este soporte al compilador?
  • Probablemente no.