Implementación eficiente de la recursividad final en lenguajes imperativos basada en nuevas técnicas de compilación

Resumen

El trabajo propone una implementacion eficiente de los programas recursivos finales en lenguajes imperativos, mas en concreto en pascal, la eficiencia radica en que un proceso recursivo final (ya sea expresado sintacticamente mediante procedimientos o funciones, ya sea mediante llamadas recursivas directas o indirectas) se ejecuta en espacio constante, sin crecimiento de la pila de control. La obtencion de este comportamiento se debe a tecnicas alternativas de compilacion, en que se modifica el tratamiento de cualquier llamada final a un subprograma, este o no involucrado en un proceso recursivo. Como consecuencia, no solo el espacio consumido no crece sino que esta clase de llamadas puede ejecutarse mas rapidamente que en la implementacion habitual, con una ratio de mejora muy alta en ciertos casos particulares. Concretamente, los procesos expresados mediante recursividad final directa resultan en un comportamiento (tanto espacial como temporalmente) que es en todo asimilable al de los programas iterativos equivalente, y ciertas formas de recursividad mutua pueden llegar a tener esta misma caracteristica. La tecnica propuesta es mas simple que otras estrategias conocidas para lenguajes como scheme (de caracteristicas diferentes de pascal). Sin embargo, se han encontrado varias restricciones que han de cumplir las llamadas finales para que resulten optimadas. Algunas de ellas se han identificado como universales, o inherentes al lenguaje pascal, y surgirian de igual modo al considerar cualquier tecnica alternativa. Otra es producto directo de la estrategia utilizada y en principio, no se da en scheme. No obstante, la estrategia propuesta puede ser integrada con facilidad en cualquier compilador existente de pascal, cosa dudosa con las tecnicas conocidas para scheme. Por otro lado, se argumenta que esta restriccion tiene escaso impacto en la programacion habitual en el lenguaje. Finalmente, la presencia de la optimacion de l