Pila de llamadas

En ciencias de la computación, una pila de llamadas (en inglés call stack) es una estructura dinámica de datos LIFO, (una pila), que almacena la información sobre las subrutinas activas de un programa de computadora. Esta clase de pila también es conocida como una pila de ejecución, pila de programa, pila de control, pila de función, o pila de tiempo de ejecución, y a menudo se describe simplemente como "la pila". Aunque el mantenimiento de la pila de llamadas es importante para el correcto funcionamiento de la mayoría de programas, los detalles por lo general están ocultos y de forma automática en los lenguajes de alto nivel. Muchos conjuntos de instrucciones de computadora proveen instrucciones especiales para manipular pilas.
Una pila de llamadas es de uso frecuente para varios propósitos relacionados, pero la principal razón de su uso, es seguir el curso del punto al cual cada subrutina activa debe retornar el control cuando termine de ejecutar. (Las subrutinas activas son las que se han llamado pero todavía no han completado su ejecución ni retornando al lugar siguiente desde donde han sido llamadas). Si, por ejemplo, una subrutina DibujaCuadrado llama a una subrutina DibujaLinea desde cuatro lugares diferentes, el código de DibujaLinea debe tener una manera de saber a dónde retornar. Esto es típicamente hecho por un código que, para cada llamada dentro de DibujaCuadrado, pone la dirección de la instrucción luego de la sentencia de llamada particular (la "dirección de retorno") en la pila de llamadas.
Puesto que la pila de llamadas se organiza como una pila, el programa que llama (a la subrutina) empuja (push) la dirección de retorno en la pila (la dirección en la que el programa continuará después de volver de la subrutina), y la subrutina llamada, cuando finaliza, retira (pop) la dirección de retorno de la pila de llamadas y transfiere el control a esa dirección. Si una subrutina llamada, llama a otra subrutina, la primera empuja (push) su dirección de retorno en la pila de llamadas, y así sucesivamente, con la información de direcciones de retorno apilándose y desapilándose como el programa dicte. Si el empujar (push) consume todo el espacio asignado para la pila de llamadas, ocurre un error llamado desbordamiento de pila. Agregando una entrada de subrutina a la pila de llamadas es a veces llamado bobinando o enrollando (winding); inversamente, la eliminación de entradas es llamado desenbobinando o desenrollando (unwinding).
Usualmente hay exactamente una pila de llamadas asociada a un programa en ejecución (o más precisamente, con cada tarea o hilo de un proceso), aunque pilas adicionales pueden ser creados para el manejo de señales o la multitarea cooperativa (como con setcontext). Puesto que hay solamente una pila en este importante contexto, puede ser referida como la pila (implícita, "de la tarea").
En lenguajes de programación de alto nivel, las características específicas de la pila de llamadas usualmente son ocultas al programador. Ellos sólo tienen acceso a la lista de funciones, y no a la memoria de la pila en sí misma. La mayoría de los lenguajes ensambladores, por una parte, requieren que los programas sean invocados con manipulación directa de la pila. En un lenguaje de programación, los detalles reales de la pila dependen del compilador, del sistema operativo, y del conjunto de instrucciones disponible.
Según lo observado arriba, el propósito primario de una pila de llamadas es:
Una pila de llamadas puede servir para funciones adicionales, dependiendo del lenguaje, del sistema operativo, y del ambiente de la máquina. Entre ellos puede estar:
La pila de llamadas típica se usa para la dirección de retorno, variables locales, y los parámetros (conocido como el call frame). En algunos ambientes puede haber más o menos funciones asignadas a la pila de llamadas. En el lenguaje de programación Forth, por ejemplo, solamente la dirección de retorno y las variables locales son almacenadas en la pila de llamadas (que en ese ambiente es llamado la pila de retorno); los parámetros son almacenados en una pila de datos separado. La mayoría de los Forth también tiene una tercera pila para los parámetros de punto flotante.
Una pila de llamadas está compuesta de marcos de pila (stack frames - a veces llamados registros de activación). Estas son estructuras de datos dependientes de la máquina que contienen la información de estado de la subrutina. Cada stack frame corresponde a una llamada a una subrutina que activa, es decir, que todavía no ha terminado con un retorno a quien la llamó. Por ejemplo, si una subrutina llamada DrawLine (DibujaLinea) se ejecuta actualmente, acabando de ser llamada por una subrutina DrawSquare (DibujaCuadrado), la parte superior de la pila de llamadas puede presentarse como esto (donde la pila está creciendo de abajo hacia arriba):
El stack frame en el tope de la pila (en verde) es para la rutina actualmente en ejecución (DrawLine). En el más común acercamiento para el stack frame incluye:
La pila se accede a menudo mediante un registro llamado puntero de pila (Stack Pointer) (ver registro de pila), que también sirve para indicar al tope actual de la pila. Alternativamente, la memoria dentro del marco de pila (Stack Frame) se puede acceder mediante un registro separado, a menudo llamado puntero del marco (Frame Pointer); típicamente apunta a un cierto lugar fijo en la estructura del marco, tal como la localización de la dirección de retorno.
No todos los stack frames tienen el mismo tamaño. Diferentes subrutinas tienen diferente número de parámetros, de modo que esa parte del stack frame será diferente para diversas subrutinas, aunque usualmente se fija a través de todas las activaciones de una subrutina en particular. De igual forma, la cantidad de espacio necesaria para las variables locales será diferente para diversas subrutinas. De hecho, algunos lenguajes soportan asignaciones dinámicas de memoria para las variables locales en la pila, en este caso el tamaño del área para las variables locales varía de una a otra activación de una subrutina, y no es conocida cuando es compilada la subrutina. En el último caso, el acceso vía un puntero de frame, en vez de a través del puntero de pila, es usualmente necesario puesto que los desplazamientos relativos (offsets) desde el tope de la pila a valores tales como la dirección de retorno no serían conocidas en tiempo de compilación.
En muchos sistemas un stack frame tiene un campo para contener el valor anterior del registro del puntero del frame, es decir, el valor que tenía con el programa, que llamó a la subrutina, mientras se estaba ejecutando. Por ejemplo, en el diagrama de arriba, el marco de pila de DrawLine (en verde) tendría una posición de memoria manteniendo el valor del puntero del marco que DrawSquare (en azul) está utilizando. El valor es guardado al entrar en la subrutina y es restaurado pare el retorno. Tener tal campo en una localización conocida del stack frame permite que el código tenga acceso a cada frame sucesivamente por debajo el frame de la rutina actualmente en ejecución.
Los lenguajes de programación que soportan subrutinas anidadas tienen un campo en el frame de llamada que apunta al frame de llamada de la rutina externa que invocó la rutina (anidada) interna. Esto a veces llamado un display.​ Este apuntador proporciona a las rutinas internas (así como cualesquiera otras rutinas internas que pueda invocar) el acceso a los parámetros y las variables locales de la rutina externa (la que invoca). Algunos computadores, tales como los grandes sistemas de Burroughs, tienen "registros de display" especiales para soportar tales funciones anidadas.
Para algunos propósitos, el marco de pila de una subrutina y el de la rutina que la llama pueden ser considerados como un solapado (overlap), el solapado consiste en el área donde los parámetros son pasados desde la rutina que llama a la rutina que es llamada. En algunos ambientes, la rutina que llama, empuja (push) cada argumento sobre la pila, extendiendo así su marco de pila; después invoca a la subrutina (la cual usará esos parámetros). En otros ambientes, la rutina que llama tiene un área preasignada en el tope de su marco de pila para mantener los argumentos que suministra a otras subrutinas que llama. Esta área a veces se entiende por el área de argumentos salientes o el callout area. Bajo este punto, el área se calcula mediante el compilador para ser tan grande como sea necesario para cualquier llamado a subrutina.
La manipulación de la pila de llamadas que se necesita en el lugar donde se realiza la llamada a una subrutina es mínima (lo que es bueno puesto que puede haber muchos lugares de donde se llama cada subrutina). Los valores para los argumentos reales son evaluados en el sitio de la llamada, puesto que son específicos para una particular llamada, y pueden ser o empujados (push) sobre la pila o colocados en los registros, según lo determinado por la convención de llamada utilizada. La instrucción de llamada real, tal como "Branch and link" es entonces típicamente ejecutada para transferir el control al código de la subrutina de destino.
En la subrutina que ha sido llamada, al primer código ejecutado se le llama el prólogo de la subrutina, puesto que hace el trabajo necesario antes de que comience el código para las sentencias de la rutina.
El prólogo comúnmente guardará la dirección de retorno, dejado en un registro por la instrucción de llamada, empujando (push) dicho valor sobre la pila de llamadas. Similarmente, los valores actuales del puntero de pila o del puntero del marco pueden empujarse (push) a la pila. Alternativamente, algunas arquitecturas de conjunto de instrucciones, proporcionan automáticamente la funcionalidad comparable, como parte de la acción de la instrucción de llamada en sí misma, y en tal ambiente, el prólogo no necesita hacer esto.
Si están siendo usados los punteros del marco, el prólogo típicamente fijará el nuevo valor del registro del puntero del marco desde el puntero de pila. Entonces, el espacio en la pila para las variables locales puede asignarse incrementalmente cambiando así al puntero de pila.
El lenguaje de programación Forth, permite el bobinado explícito de la pila de llamadas (llamada en Forth la «pila de retorno»). El lenguaje de programación del Scheme, permite el bobinado de marcos especiales en la pila, a través de un «reembobinado».
Cuando una subrutina está lista para retornar, ejecuta un epílogo que deshace los pasos del prólogo. Esto típicamente restaurará los valores de registros previamente guardados (tales como el valor del puntero del marco) tomándolos desde el marco de pila, descargará (pop) todo el marco de la pila cambiando el valor del puntero de pila, y finalmente bifurcará a la instrucción indicada en la dirección de retorno. Bajo muchas convenciones de llamada, entre los elementos eliminados (pop) de la pila por el epílogo, se incluyen los valores originales de los argumentos con que fue llamada la rutina, en este caso, usualmente no hay otras manipulaciones de la pila que necesiten ser hechas por la subrutina que llama. Sin embargo, con algunas convenciones de llamada, es la responsabilidad de la rutina que llama quitar los argumentos de la pila después del retorno.
El Retorno de la función llamada hará una remoción (pop) del marco en el tope de la pila, quizás dejando un valor de retorno.
Algunos lenguajes (como Pascal) permiten una sentencia goto global para transferir el control fuera de una función anidada y llevarlo hacia dentro de función externa previamente invocada. Esta operación requiere que la pila sea desenrolado, quitando tantos marcos de pila como se necesiten para restaurar el contexto apropiado para transferir el control a la declaración de destino dentro de la función externa que la envuelve. Tales transferencias de control se usan generalmente sólo para el tratamiento de errores.
Otras lenguajes (tales como Object Pascal/Delphi) proporcionan el manejo de excepciones, que también requiere desenrollar la pila. El marco de pila de una función contiene una o más entradas que especifican manejadores de excepción. Cuando una excepción es lanzada, se desenrolla la pila hasta que se encuentra un manejador de excepción que esté preparado para atrapar (catch) tal excepción. El Common Lisp permite el control de lo que sucede cuando la pila es desenrollada usando el operador especial unwind-protect.
Cuando se aplica una continuación, la pila se desenrolla y después rebobina con la pila de la continuación. Esta no es la única manera de ejecutar continuaciones; por ejemplo, usando múltiples pilas explícitas, la aplicación de una continuación pueden simplemente activar su pila y enrollar un valor que será pasado.
Una técnica recientemente divulgada​ usa las pilas de llamadas de una manera diferente a otras discutidas en esta página. Se usa las pilas de llamadas para la reducción del juego de pruebas. Brevemente, la reducción del juego de pruebas busca reducir el número de casos de pruebas en un juego de pruebas mientras que retiene un alto porcentaje de la efectividad de la detección de falla del juego original. Dos casos de pruebas son considerados equivalentes si generan el mismo conjunto de pilas de llamadas durante la ejecución. Para más detalles, ver (​).
Tomando muestras en tiempos aleatorios de la pila de llamadas puede ser muy útil para optimizar el desempeño de los programas. La razón es que si una instrucción de llamada a subrutina aparece en la pila de llamadas en una cierta fracción del tiempo de ejecución, su posible remoción pudiera ahorrar esa cantidad de tiempo. Ver análisis de desempeño y muestreo profundo.
La mezcla de los datos del flujo de control que afectan la ejecución del código (direcciones de retorno, punteros de frame guardados) y datos simples del programa (parámetros, valores de retorno) en una pila de llamadas es un riesgo de seguridad, posiblemente explotable por medio del desbordamiento de búfer (en el artículo son explicados el riesgo y el exploit).