thumb|342px|Estructura de la pila de llamadas. En la figura se ve una pila, creciendo de abajo hacia arriba.La subrutina DrawSquare (DibujaCuadrado) es llamada y se crea un stack frame para ella (en azul). Luego, DrawSquare llama a la subrutina DrawLine (DibujaLinea), la cual tiene su propio stack frame (en verde). El stack frame de cada subrutina tiene, en este caso, tres partes: una dirección de retorno que indica la siguiente dirección a ejecutar después de que termine la subrutina, los parámetros con que fue llamada la subrutina (que se cargan antes de llamarla), y un espacio reservado para las variables y las constantes locales de la subrutina.

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.

Descripción 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.

Funciones de la pila de llamadas Según lo observado arriba, el propósito primario de una pila de llamadas es:

Almacenamiento de la dirección de retorno - Cuando se llama una subrutina, la localización de la instrucción para retornar necesita guardarse en alguna parte. Usando una pila para guardar la dirección de retorno tiene importantes ventajas sobre las otras alternativas. Una de ellas es que cada tarea tiene su propia pila, y así, la subrutina puede ser reentrante, es decir, puede estar activa simultáneamente para distintas tareas que hacen cosas diferentes. Otro beneficio es que la recursividad se soporta automáticamente. Cuando una función se llama a sí misma (recursivamente), una dirección de retorno necesita almacenarse para cada activación de tal función, de tal manera de poder usarla luego para retornar desde la activación de la función. Esta capacidad es automática con una pila.

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:

Almacenamiento local de datos - Una subrutina frecuentemente necesita memoria para almacenar los valores de las variables locales, las variables que son conocidas solamente dentro de la subrutina activa y no conservan sus valores después de que la subrutina retorna. A menudo es conveniente asignar el espacio para las variables locales simplemente moviendo el tope de la pila lo suficiente para proporcionar el espacio necesario. Esto es muy rápido de hacer comparado con, por ejemplo, una asignación de memoria en el heap. Observe que cada activación separada de una subrutina toma su propio espacio separado en la pila para sus variables locales.

Paso de parámetros - A menudo las subrutinas requieren que los valores para sus parámetros les sean suministrados por el código que las llama, y no es infrecuente que el espacio para estos parámetros descanse en la pila de llamadas. Por lo general, si solamente hay algunos pequeños parámetros, los registros del procesador se usarán para pasar los valores, pero si hay más parámetros de los que se pueda manejar de esta manera, será necesario espacio en memoria. La pila de llamadas trabaja bien como un lugar para estos parámetros, especialmente ya que a cada llamada a una subrutina, la cual tendrá diferentes valores para los parámetros, le será dado un espacio aparte en la pila de llamadas para esos valores.

Pila de evaluación - Los operandos para las operaciones aritméticas o lógicas muy frecuentemente son puestos en un registro y operados allí. Sin embargo, en algunas situaciones los operandos pueden ser apilados hasta una profundidad arbitraria, lo que significa que se debe usar algo más que los registros. La pila de tales operandos, similar al de una calculadora RPN, se llama pila de evaluación, y puede ocupar espacio en la pila de llamadas.

Puntero a la instancia actual - Algunos lenguajes orientados objeto (ej., C++), almacenan el puntero this junto con los argumentos de la función en la pila de llamadas cuando se están invocando los métodos. El puntero this señala la instancia del objeto asociado al método que se invocará. El puntero this es una parte esencial del contexto de ejecución en lenguajes orientadas objetos, puesto que proporciona el acceso a los datos del miembro y la V-Table del objeto actual. El puntero this enlaza las capas (layers) usadas en el diseño orientado a objetos con las capas (tipos de stack frames) de la pila de llamadas del tiempo de ejecución.

Envolviendo el contexto de la subrutina - En algunos lenguajes de programación (ej. Pascal y Ada) soportan subrutinas anidadas, permitiendo a una rutina interna acceder al contexto de su rutina externa que la contiene, es decir, los parámetros y las variables locales dentro del alcance de la rutina externa. Tal anidamiento estático se puede repetir - una función, declarada dentro de una función, declarada dentro de una función,... La implementación debe proporcionar un medio por el cual una función llamada en cualquier nivel de anidado estático dado pueda referenciar al marco que envuelve a cada nivel de anidado envolvente. Comúnmente, esta referencia es implementada por un puntero al marco que lo envuelve (o abarca), llamado un "downstack link" o "static link", para distinguirlo del "dynamic link" que hace referencia al procedimiento llamador inmediato (que no necesita ser la función padre estática). Por ejemplo, los lenguajes a menudo permiten a las rutinas internas llamarse a sí mismas recursivamente, resultando en múltiples marcos de llamada para las invocaciones de la rutina interna, todos estos enlaces estáticos apuntan al mismo contexto externo de rutina. En vez de un enlace estático, las referencias a los marcos estáticos envolventes pueden ser recolectados en un arreglo de punteros conocido como display el cual es indexado para localizar un marco deseado. La Burroughs B6500 tenía dicho display en el hardware que soportaba hasta 32 niveles de anidado estático.

Otro estado de retorno - Además de la dirección de retorno, en algunos ambientes puede haber otra máquina o estados de software que necesitan ser restaurados cuando una subrutina retorna. Esto pudo incluir cosas como el nivel de privilegio, información de manejo de excepciones, modos aritméticos, y así sucesivamente. Si fuera necesario, esto puede ser almacenado en la pila de llamadas justo como lo es la dirección de retorno.

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.

Estructura 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):

center

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:

el espacio para las variables locales de la rutina, la dirección de retorno del que llama a la rutina (p.e. en el marco de pila DrawLine, una dirección dentro del código de DrawSquare), y los valores de los parámetros pasados a la rutina (si los hay).

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.