¿Por qué los programas usan pilas de llamadas, si las llamadas a funciones anidadas se pueden incorporar?

¿Por qué no hacer que el compilador tome un programa como este?

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

y convertirlo en un programa como este:

function c(b) { return b^2 + 5 };

eliminando así la necesidad de la computadora de recordar la dirección de retorno de c (b)?

Supongo que el aumento del espacio en el disco duro y la RAM necesarios para almacenar el programa y admitir su compilación (respectivamente) es la razón por la que utilizamos pilas de llamadas. ¿Es eso correcto?

Esto se llama "en línea" y muchos compiladores lo hacen como una estrategia de optimización en los casos en que tiene sentido.

En su ejemplo particular, esta optimización ahorraría espacio y tiempo de ejecución. Pero si se llamó a la función en varios lugares del programa (¡no es raro!), Aumentaría el tamaño del código, por lo que la estrategia se vuelve más dudosa. (Y, por supuesto, si una función se llamara a sí misma directa o indirectamente, sería imposible alinearla, ya que el código tendría un tamaño infinito).

Y, obviamente, solo es posible para funciones "privadas". Las funciones que están expuestas para los llamantes externos no se pueden optimizar, al menos no en idiomas con enlaces dinámicos.

Hay dos partes en su pregunta: ¿Por qué tener múltiples funciones (en lugar de reemplazar las llamadas de función con su definición) y por qué implementar esas funciones con pilas de llamadas en lugar de asignar estáticamente sus datos en otro lugar?

La primera razón es la recursividad. No solo el tipo "oh, hagamos una nueva llamada de función para cada elemento de esta lista", también el tipo modesto donde tiene quizás dos llamadas de una función activa al mismo tiempo, con muchas otras funciones entre ellas. Necesita poner variables locales en una pila para soportar esto, y no puede en línea funciones recursivas en general.

Entonces hay un problema para las bibliotecas: no sabes qué funciones se llamarán desde dónde y con qué frecuencia, por lo que una "biblioteca" nunca podría realmente compilarse, solo enviarse a todos los clientes en algún formato conveniente de alto nivel que luego se pueda en línea en la aplicación. Además de otros problemas con esto, pierde completamente el enlace dinámico con todas sus ventajas.

Además, hay muchas razones para no funciones en línea, incluso cuando podría:

1. No es necesariamente más rápido. Configurar el marco de la pila y derribarlo son tal vez una docena de instrucciones de un solo ciclo, para muchas funciones grandes o en bucle que ni siquiera son el 0.1% de su tiempo de ejecución.
2. Puede ser más lento La duplicación de código tiene costos, por ejemplo, ejercerá más presión en el caché de instrucciones.
3. Algunas funciones son muy grandes y se llaman desde muchos lugares, al incluirlas en todas partes aumenta el binario mucho más allá de lo razonable.
4. Los compiladores a menudo tienen dificultades con funciones muy grandes. Si todo lo demás es igual, una función de tamaño 2 * N toma más de 2 * T tiempo, mientras que una función de tamaño N toma tiempo T.

Las pilas nos permiten omitir con elegancia los límites impuestos por el número finito de registros.

Imagine tener exactamente 26 "registros az" globales (o incluso tener solo los registros de 7 bytes del chip 8080) Y cada función que escriba en esta aplicación comparte esta lista plana.

Un comienzo ingenuo sería asignar los primeros registros a la primera función, y sabiendo que solo tomó 3, comience con "d" para la segunda función ... Se acaba rápidamente.

En cambio, si tiene una cinta metafórica, como la máquina de Turing, puede hacer que cada función inicie una "llamada a otra función" guardando todas las variables que está usando y reenvíe () la cinta, y luego la función de llamada puede confundirse con tantas se registra como quiere. Cuando finaliza la llamada, devuelve el control a la función principal, que sabe dónde enganchar la salida de la persona que llama, según sea necesario, y luego reproduce la cinta hacia atrás para restaurar su estado.

Su marco de llamada básico es solo eso, y se crean y descartan mediante secuencias de código de máquina estandarizadas que el compilador realiza alrededor de las transiciones de una función a otra. (Ha pasado mucho tiempo desde que tuve que recordar mis marcos de pila C, pero puedes leer sobre las diversas formas en que las tareas de quién deja qué en X86_calling_conventions ).

(la recursividad es increíble, pero si alguna vez hubiera tenido que hacer malabarismos con los registros sin una pila, realmente apreciaría las pilas).

Supongo que el aumento del espacio en el disco duro y la RAM necesarios para almacenar el programa y admitir su compilación (respectivamente) es la razón por la que utilizamos pilas de llamadas. ¿Es eso correcto?

Si bien podemos incorporar más en estos días, ("más velocidad" siempre es buena; "menos kb de ensamblaje" significa muy poco en un mundo de transmisiones de video) La principal limitación está en la capacidad del compilador de aplanar ciertos tipos de patrones de código.

Por ejemplo, objetos polimórficos: si no conoce el único tipo de objeto que recibirá, no puede aplanarlo; debe mirar la tabla de características del objeto y llamar a través de ese puntero ... trivial para hacer en tiempo de ejecución, imposible de alinear en tiempo de compilación.

Una cadena de herramientas moderna puede alinear felizmente una función definida polimórficamente cuando ha aplanado lo suficiente a la persona que llama para saber exactamente qué sabor de obj es:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

en lo anterior, el compilador puede optar por mantenerse en línea estática, desde InlineMe a través de cualquier acción interna (), ni la necesidad de tocar ninguna vtables en tiempo de ejecución.

Sin embargo, cualquier incertidumbre en lo que el sabor del objeto se deja como una llamada a una función discreta, aunque algunas otras invocaciones de la misma función están entre líneas.

Casos que ese enfoque no puede manejar:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

No son lenguajes y plataformas con pilas limitadas o ninguna llamada. Los microprocesadores PIC tienen una pila de hardware limitada a entre 2 y 32 entradas . Esto crea restricciones de diseño.

COBOL prohíbe la recursión: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-to-recursively-call-a-paragraph

Imponer una prohibición de recursión significa que puede representar el callgraph completo del programa estáticamente como un DAG. Su compilador podría emitir una copia de una función para cada lugar desde el que se llama con un salto fijo en lugar de un retorno. No se requiere pila, solo más espacio de programa, potencialmente bastante para sistemas complejos. Pero para sistemas integrados pequeños, esto significa que puede garantizar que no se produzca un desbordamiento de pila en el tiempo de ejecución, lo que sería una mala noticia para su control de reactores nucleares / turbinas a reacción / acelerador de automóviles, etc.

¿Quieres función de procesos en línea , y la mayoría ( optimización ) compiladores está haciendo eso.

Tenga en cuenta que la alineación requiere que se conozca la función llamada (y es efectiva solo si esa función llamada no es demasiado grande), ya que conceptualmente está sustituyendo la llamada por la reescritura de la función llamada. Por lo tanto, generalmente no puede alinear una función desconocida (por ejemplo, un puntero de función, que incluye funciones de bibliotecas compartidas vinculadas dinámicamente ), que tal vez sea visible como un método virtual en alguna vtable ; pero algunos compiladores a veces pueden optimizar a través de técnicas de desvirtualización ). Por supuesto, no siempre es posible alinear funciones recursivas (algunos compiladores inteligentes pueden usar una evaluación parcial y, en algunos casos, pueden alinear funciones recursivas).

Observe también que la alineación, incluso cuando es fácilmente posible, no siempre es efectiva: usted (en realidad su compilador) podría aumentar tanto el tamaño del código que las memorias caché de la CPU (o el predictor de rama ) funcionarían de manera menos eficiente, y eso haría que su programa se ejecute más lento.

^{Me estoy centrando un poco en el estilo de programación funcional , ya que etiquetó su pregunta como tal.}

Tenga en cuenta que no necesita tener ninguna pila de llamadas (al menos en el sentido de la máquina de la expresión "pila de llamadas"). Podrías usar solo el montón.

Por lo tanto, eche un vistazo a las continuaciones y lea más sobre el estilo de paso de continuación (CPS) y la transformación de CPS (intuitivamente, podría usar los cierres de continuación como "marcos de llamada" reified asignados en el montón, y son una especie de imitación de una pila de llamadas; entonces necesitas un recolector de basura eficiente ).

Andrew Appel escribió un libro Compilando con Continuaciones y una vieja recolección de basura de papel puede ser más rápida que la asignación de la pila . Ver también el artículo de A. Kennedy (ICFP2007) Compilación con Continuaciones, Continuación

También recomiendo leer el libro Lisp In Small Pieces de Queinnec , que tiene varios capítulos relacionados con la continuación y la compilación.

Tenga en cuenta también que algunos idiomas (por ejemplo, Brainfuck ) o máquinas abstractas (por ejemplo , OISC , RAM ) no tienen ninguna función de llamada, pero todavía están completos en Turing , por lo que ni siquiera (en teoría) necesita ningún mecanismo de llamada de función, incluso si Es extremadamente conveniente. Por cierto, algunas arquitecturas de conjuntos de instrucciones antiguas (por ejemplo, IBM / 370 ) ni siquiera tienen una pila de llamadas de hardware, o una instrucción de máquina de llamadas de inserción (el IBM / 370 solo tenía una instrucción de máquina Branch and Link )

Por último, si su programa completo (incluidas todas las bibliotecas necesarias) no tiene ninguna recursividad, puede almacenar la dirección de retorno (y las variables "locales", que en realidad se están volviendo estáticas) de cada función en ubicaciones estáticas. Los compiladores antiguos de Fortran77 hicieron eso a principios de la década de 1980 (por lo que los programas compilados no usaban ninguna pila de llamadas en ese momento).

La alineación (reemplazo de llamadas de función con funcionalidad equivalente) funciona bien como estrategia de optimización para pequeñas funciones simples. La sobrecarga de una llamada de función puede intercambiarse efectivamente por una pequeña penalización en el tamaño del programa adicional (o en algunos casos, sin penalización alguna).

Sin embargo, las funciones grandes que a su vez llaman a otras funciones podrían conducir a una enorme explosión en el tamaño del programa si todo estuviera en línea.

El objetivo de las funciones invocables es facilitar la reutilización eficiente, no solo por parte del programador, sino también por la máquina misma, y ​​eso incluye propiedades como memoria razonable o huella en el disco.

Para lo que vale: puede tener funciones invocables sin una pila de llamadas. Por ejemplo: IBM System / 360. Al programar en lenguajes como FORTRAN en ese hardware, el contador del programa (dirección de retorno) se guardaría en una pequeña sección de memoria reservada justo antes del punto de entrada de la función. Permite funciones reutilizables, pero no permite la recursividad o el código de subprocesos múltiples (un intento de una llamada recursiva o reentrante daría como resultado que se sobrescribiera una dirección de retorno previamente guardada).

Como se explica en otras respuestas, las pilas son cosas buenas. Facilitan la recursividad y las llamadas multiproceso. Si bien cualquier algoritmo codificado para usar la recursión podría codificarse sin depender de la recursividad, el resultado puede ser más complejo, más difícil de mantener y puede ser menos eficiente. No estoy seguro de que una arquitectura sin pila pueda soportar múltiples subprocesos.