c++ - ¿Puede Tail Call Optimization y RAII Co-Exist?

recursion compiler-construction

Question

No puedo pensar en un verdadero lenguaje RAII que también tenga una optimización de la cola de llamadas en las especificaciones, pero sé que muchas implementaciones de C ++ pueden hacerlo como una optimización específica de la implementación.

Esto plantea una pregunta para aquellas implementaciones que lo hacen: dado que los destructores son invocados al final del alcance de una variable automática y no por una rutina de recolección de basura separada, ¿no viola la restricción de TCO que una llamada recursiva debe ser la última instrucción en el fin de una función?

Por ejemplo:-

#include <iostream>

class test_object {
public:
    test_object() { std::cout << "Constructing.../n"; }
    ~test_object() { std::cout << "Destructing.../n"; }
};

void test_function(int count);

int main()
{
    test_function(999);
}

void test_function(int count)
{
    if (!count) return;
    test_object obj;
    test_function(count - 1);
}

"Construir ..." sería escrito 999 veces y luego "Destruyendo ..." otras 999 veces. En última instancia, 999 instancias test_object se asignarán automáticamente antes del desenrollado. Pero suponiendo que una implementación tuviera un TCO, ¿habría 1000 marcos de pila o solo 1?

¿El destructor después de la llamada recursiva colisiona con los requisitos de implementación de TCO de facto?

Answer 1

Si el compilador realiza el TCO, el orden en que se invocan los destructores cambia con respecto a cuándo no realiza el TCO.

Si el compilador puede demostrar que este reordenamiento no tiene importancia (por ejemplo, si el destructor es trivial), entonces, según la regla de si-si , puede realizar un TCO. Sin embargo, en su ejemplo, el compilador no puede probar eso y no hará TCO.

Answer 2

Tomado al valor nominal, ciertamente parecería que RAII funciona contra TCO. Sin embargo, recuerde que hay una serie de formas en que el compilador puede "salirse con la suya", por así decirlo.

El primer y más obvio caso es si el destructor es trivial, lo que significa que es el destructor predeterminado (generado por el compilador) y todos los sub-objetos también tienen destructores triviales, entonces el destructor es efectivamente inexistente (siempre optimizado). En ese caso, TCO se puede realizar como de costumbre.

Entonces, el destructor podría estar en línea (su código se toma y se coloca directamente en la función en lugar de llamarse como una función). En ese caso, se reduce a tener un código de "limpieza" después de la declaración de devolución. El compilador puede reordenar operaciones si puede determinar que el resultado final es el mismo (la regla "como si"), y lo hará (en general) si el reordenamiento conduce a un mejor código, y yo asumiría que TCO es una de las consideraciones que aplica la mayoría de los compiladores (es decir, si puede reordenar cosas tales que el código se convierta en adecuado para TCO, entonces lo hará).

Y para el resto de los casos, donde el compilador no puede ser "lo suficientemente listo" para hacerlo por sí mismo, entonces se vuelve responsabilidad del programador. La presencia de esta llamada automática de destrucción hace que sea un poco más difícil para el programador ver el código de limpieza inhibidor de TCO después de la llamada final, pero no hace ninguna diferencia en términos de la capacidad del programador para hacer el función un candidato para TCO. Por ejemplo:

void nonRAII_recursion(int a) {
  int* arr = new int[a];
  // do some stuff with array "arr"
  delete[] arr;
  nonRAII_recursion(--a);  // tail-call
};

Ahora, una implementación RAII_recursion ingenua podría ser:

void RAII_recursion(int a) {
  std::vector<int> arr(a);
  // do some stuff with vector "arr"
  RAII_recursion(--a);  // tail-call
};  // arr gets destroyed here, not good for TCO.

Pero un programador inteligente todavía puede ver que esto no funcionará (a menos que el vector destructor esté en línea, lo que es probable en este caso), y puede rectificar la situación fácilmente:

void RAII_recursion(int a) {
  {
    std::vector<int> arr(a);
    // do some stuff with vector "arr"
  }; // arr gets destroyed here
  RAII_recursion(--a);  // tail-call
};

Y estoy bastante seguro de que podrías demostrar que no hay casos en los que este tipo de truco no se pueda utilizar para garantizar que se pueda aplicar el TCO. Entonces, RAII meramente hace un poco más difícil ver si se puede aplicar TCO. Pero creo que los programadores que son lo suficientemente inteligentes como para diseñar llamadas recursivas con capacidad TCO también son lo suficientemente sabios como para ver esas llamadas al destructor "ocultas" que tendrían que forzarse antes de la llamada final.

NOTA AGREGADA: Mírelo de esta manera, el destructor esconde algún código de limpieza automática. Si necesita el código de limpieza (es decir, un destructor no trivial), lo necesitará ya sea que use RAII o no (por ejemplo, matriz tipo C o lo que sea). Y luego, si desea que el TCO sea posible, debe ser posible realizar la limpieza antes de realizar la llamada final (con o sin RAII), y es posible, entonces es posible forzar la destrucción de los objetos RAII. antes de la llamada final (por ejemplo, poniéndolos dentro de un alcance extra).