¿Hay alguna razón técnica por la que C#no emita la "cola"? ¿Instrucción CIL?

.net mono

Question

Posible duplicado:
¿Por qué .net / C # no elimina la recursión de la cola?

Tome el siguiente código C #:

using System;
namespace TailTest
{
class MainClass
{
public static void Main (string[] args)
{
Counter(0);
}
static void Counter(int i)
{
Console.WriteLine(i);
if (i < int.MaxValue) Counter(++i);
}
}
}

El compilador de C # (el mío de todos modos) compilará el método de contador en el siguiente CIL:

.method private static hidebysig default void Counter (int32 i) cil managed
{
.maxstack 8
IL_0000: ldarg.0
IL_0001: call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006: ldarg.0
IL_0007: ldc.i4 2147483647
IL_000c: bge IL_0019
IL_0011: ldarg.0
IL_0012: ldc.i4.1
IL_0013: add
IL_0014: call void class TailTest.MainClass::Counter(int32)
IL_0019: ret
}

El problema con el código anterior es que causará un desbordamiento de pila (en aproximadamente i = 262000 en mi hardware). Para solucionar este problema, algunos idiomas hacen lo que se denomina eliminación de llamadas de cola o optimización de llamadas de cola (TCO). Esencialmente, convierten la llamada recursiva en un bucle.

Mi entendimiento es que la implementación de 64 bits del .NET 4 JIT ahora realiza TCO y evita el desbordamiento en el código como el CIL anterior. Sin embargo, el JIT de 32 bits no lo hace. Mono tampoco parece. Es interesante que el JIT (que está bajo presión de tiempo y recursos) haga TCO mientras que el compilador de C # no lo haga. Mi pregunta es ¿por qué el compilador de C # en sí no es más consciente del TCO?

Hay una instrucción CIL que le indica al JIT que realice el TCO. Por ejemplo, el compilador de C # podría generar el siguiente CIL:

.method private static hidebysig default void Counter (int32 i) cil managed
{
.maxstack 8
IL_0000: ldarg.0
IL_0001: call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006: ldarg.0
IL_0007: ldc.i4 2147483647
IL_000c: bge IL_001c
IL_0011: ldarg.0
IL_0012: ldc.i4.1
IL_0013: add
IL_0014: tail.
IL_0017: call void class TailTest.MainClass::Counter(int32)
IL_001c: ret
}

A diferencia del original, este código no se desbordará y se ejecutará hasta su finalización incluso en el JIT de 32 bits (tanto .NET como Mono). La magia está en la tail. Instrucción CIL. Los compiladores como F # generarán CIL que incluye esta instrucción automáticamente.

Entonces, mi pregunta es, ¿hay alguna razón técnica por la que el compilador de C # no haga esto?

Entiendo que históricamente tal vez no haya valido la pena. El código como Counter() no ha sido común en C # idiomático y / o el marco .NET. Puede ver fácilmente el TCO para C # como una optimización innecesaria o prematura.

Con la introducción de LINQ y otras cosas, parece que los desarrolladores de C # y C # se están moviendo en direcciones más funcionales. Por lo tanto, sería bueno si el uso de la recursión no fuera algo tan inseguro. Pero mi pregunta es realmente más técnica.

Me estoy perdiendo algo que hace que el TCO sea una mala idea (o arriesgada) para C #. ¿O hay algo que hace que sea particularmente difícil hacerlo bien? Eso es realmente lo que espero entender. ¿Alguna idea?

EDIT: Gracias por la gran información. Solo quería dejar en claro que no estoy criticando la falta o la exigencia de esta función. No estoy muy interesado en lo racional en torno a la priorización. Mi curiosidad es qué obstáculos podría no percibir o comprender que hacen que esto sea algo difícil, peligroso o indeseable.

Quizás un contexto diferente ayude a enfocar la conversación ...

Digamos que iba a implementar mi propio lenguaje similar a C # en el CLR. ¿Por qué no incluiría (además del costo de oportunidad) la emisión automática y transparente de la "cola"? instrucción donde sea apropiado? ¿Qué desafíos encontraría o qué restricciones introduciría al admitir esta característica en un lenguaje muy parecido a C #?

Gracias de nuevo (y de antemano) por las respuestas.

Answer 1

Buena pregunta. No tengo una respuesta concreta, pero tengo algunos pensamientos que pueden resultarte interesantes. (Me han dicho antes que no debería publicar cosas como respuestas, pero hey ...) La respuesta de Yahia parece ser la más definitiva que probablemente obtendrás, aunque también haré un ping a Eric Lippert para ver si él quiere chime adentro

Parte de la blogs.msdn.com/b/ericlippert/archive/2009/06/22/… del blogs.msdn.com/b/ericlippert/archive/2009/06/22/… Hans ha vinculado en los comentarios probablemente cubrirá algunos de sus pensamientos, pero estoy seguro de que hay más:

Me preguntan "¿por qué C # no implementa la característica X?" todo el tiempo. La respuesta es siempre la misma: porque nunca nadie diseñó, especificó, implementó, probó, documentó y envió esa característica. Las seis cosas son necesarias para hacer que una característica suceda. Todos ellos cuestan enormes cantidades de tiempo, esfuerzo y dinero. Las características no son baratas, y nos esforzamos mucho para asegurarnos de que solo estemos enviando las características que brindan los mejores beneficios posibles a nuestros usuarios, dado nuestro limitado presupuesto de tiempo, esfuerzo y presupuesto.

Ahora volviendo a mis propios pensamientos:

Sospecho que nunca ha sido una prioridad, pero hay una buena razón para no ser demasiado entusiasta al respecto: si los desarrolladores confían en ello, es necesario garantizarlo . Tu escribiste:

Por lo tanto, sería bueno si el uso de la recursión no fuera algo tan inseguro. Pero mi pregunta es realmente más técnica.

Ahora, mire la blogs.msdn.com/b/davbr/archive/2007/06/20/… del blogs.msdn.com/b/davbr/archive/2007/06/20/… . Eso fue en 2007, y declara explícitamente :

Tenga en cuenta que estas declaraciones se aplican a los JIT tal como eran cuando Grant y Fei revisaron el código base y son propensos a cambiar a su antojo. No debes tener dependencias en este comportamiento. Utilice esta información solo para su entretenimiento personal.

Luego hay una larga lista de condiciones que se requieren antes de que se apliquen las llamadas de cola. Muchos de ellos no son triviales para adivinar desde el punto de vista de un codificador.

Tiene toda la razón de que sería bueno si el uso de la recursión fuera seguro en ciertas circunstancias, pero creo que ese es el caso si se puede garantizar que sea seguro. Si fuera seguro en el 95% de los casos, pero el 5% era difícil de predecir, tendríamos toda una serie de errores "funciona en mi máquina".

Lo que me gustaría es que el lenguaje C # me permita establecer un requisito de optimización de llamadas de cola. El compilador podría verificar que es correcto e idealmente proporcionar más que solo una sugerencia al JIT de que este comportamiento es necesario. Básicamente, si voy a repetir de manera un tanto incontrolada, es mejor que sepa que va a funcionar. ¿Te imaginas si la recolección de basura solo estuviera habilitada en algunas configuraciones? ¡Eek!

Por lo tanto, hacer +1 a la idea de que la recursión de la cola es un concepto útil, pero creo que necesitamos más apoyo del lenguaje, el JIT y el compilador antes de que realmente pueda considerarse "seguro".

Answer 2

revisa los siguientes enlaces

¿Por qué .NET / C # no optimiza la recursión de la llamada de cola? / 491463 # 491463
http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=166013&wa=wsignin1.0

La siguiente declaración es oficial de MS (Luke Hoban Visual C # Compiler Program Manager) y se copia desde el último enlace

Gracias por la sugerencia. Hemos considerado emitir instrucciones de llamada de cola en varios puntos en el desarrollo del compilador de C #. Sin embargo, hay algunos problemas sutiles que nos han empujado a evitar esto hasta ahora: 1) En realidad, el uso de la instrucción .tail en el CLR implica un costo general no trivial (no es solo una instrucción de salto, ya que las llamadas de cola finalmente se convierten en en muchos entornos menos estrictos, como los entornos de tiempo de ejecución de lenguaje funcional donde las llamadas de cola están muy optimizadas). 2) Existen pocos métodos reales de C # en los que sería legal emitir llamadas de cola (otros lenguajes fomentan patrones de codificación que tienen más recurrencia de cola, y muchos de los que dependen en gran medida de la optimización de la llamada de cola realmente hacen reescritura global (como las transformaciones de paso de continuación ) para aumentar la cantidad de recursión de la cola). 3) En parte debido a 2), los casos en los que los métodos de C # apilan desbordamiento debido a una recursión profunda que debería haber tenido éxito son bastante raros.

Dicho todo esto, continuamos observando esto, y es posible que en una futura versión del compilador encontremos algunos patrones en los que tiene sentido emitir instrucciones .tail.