La mayoría de las arquitecturas que he visto dependen de una pila de llamadas para guardar / restaurar el contexto antes de las llamadas a funciones. Es un paradigma tan común que las operaciones push y pop están integradas en la mayoría de los procesadores. ¿Hay sistemas que funcionan sin una pila? Si es así, ¿cómo funcionan y para qué se usan?
Una alternativa popular (algo) a una pila de llamadas son continuations .
La máquina virtual Parrot está basada en la continuación, por ejemplo. Es completamente sin pila: los datos se mantienen en registros (como Dalvik o LuaVM, Parrot se basa en registros), y el flujo de control se representa con continuaciones (a diferencia de Dalvik o LuaVM, que tienen una pila de llamadas).
Otra estructura de datos popular, utilizada normalmente por las máquinas virtuales Smalltalk y Lisp es la pila de espaguetis, que es casi como una red de pilas.
Como @rwong señaló , el estilo de paso continuo es una alternativa a una pila de llamadas. Los programas escritos en (o transformados a) el estilo de paso de continuación nunca regresan, por lo que no hay necesidad de una pila.
Respondiendo a su pregunta desde una perspectiva diferente: es posible tener una pila de llamadas sin tener una pila separada, asignando los marcos de pila en el montón. Algunas implementaciones de Lisp y Scheme hacen esto.
En los días anteriores, los procesadores no tenían instrucciones de pila y los lenguajes de programación no admitían la recursión. Con el tiempo, cada vez más idiomas eligen admitir la recursión y el conjunto de hardware seguido de las capacidades de asignación de marcos de pila. Este soporte ha variado mucho a lo largo de los años con diferentes procesadores. Algunos procesadores adoptaron cuadros de pila y / o registros de puntero de pila; algunas instrucciones adoptadas que lograrían la asignación de marcos de pila en una sola instrucción.
A medida que los procesadores avanzan con un solo nivel, luego con cachés multinivel, una ventaja crítica de la pila es la de la ubicación del caché. La parte superior de la pila está casi siempre en el caché. Siempre que pueda hacer algo que tenga una gran tasa de aciertos de caché, estará en el camino correcto con los procesadores modernos. La memoria caché aplicada a la pila significa que las variables locales, los parámetros, etc. están casi siempre en la memoria caché y disfrutan del nivel más alto de rendimiento.
En resumen, el uso de la pila evolucionó tanto en hardware como en software. Hay otros modelos (por ejemplo, el cálculo de flujo de datos se intentó durante un período prolongado), sin embargo, la ubicación de la pila hace que funcione realmente bien. Además, el código de procedimiento es justo lo que quieren los procesadores para el rendimiento: una instrucción que le dice qué hacer después de otra. Cuando las instrucciones están fuera de orden lineal, el procesador se ralentiza enormemente, al menos todavía, ya que no hemos descubierto cómo hacer el acceso aleatorio tan rápido como el acceso secuencial. (Por cierto, hay problemas similares en cada nivel de memoria, desde el caché a la memoria principal, al disco ...)
Entre el rendimiento demostrado de las instrucciones de acceso secuencial y el comportamiento de almacenamiento en caché beneficioso de la pila de llamadas, tenemos, al menos en la actualidad, un modelo de rendimiento ganador.
(También podríamos lanzar la mutabilidad de las estructuras de datos en las obras ...)
Esto no significa que otros modelos de programación no puedan funcionar, especialmente cuando pueden traducirse a las instrucciones secuenciales y al modelo de pila de llamadas del hardware actual. Pero hay una clara ventaja para los modelos que admiten dónde está el hardware. Sin embargo, las cosas no siempre son iguales, por lo que podríamos ver cambios en el futuro a medida que las diferentes tecnologías de memoria y transistores permiten más paralelismo. Siempre es una broma entre los lenguajes de programación y las capacidades de hardware, así que ya veremos.
TL;DR
El resto de esta respuesta es una colección aleatoria de pensamientos y anécdotas, y por lo tanto algo desorganizados.
La pila que ha descrito (como un mecanismo de llamada de función) es específica de la programación imperativa.
Debajo de la programación imperativa, encontrará el código de la máquina. El código de máquina puede emular la pila de llamadas ejecutando una pequeña secuencia de instrucciones.
Debajo del código de máquina, encontrará el hardware responsable de ejecutar el software. Si bien el microprocesador moderno es demasiado complejo para describirlo aquí, uno puede imaginar que existe un diseño muy simple que es lento pero que aún es capaz de ejecutar el mismo código de máquina. Un diseño tan simple hará uso de los elementos básicos de la lógica digital:
Las siguientes discusiones contenían muchos ejemplos de formas alternativas de estructurar programas imperativos.
La estructura de tal programa se verá así:
void main(void)
{
do
{
// validate inputs for task 1
// execute task 1, inlined,
// must complete in a deterministically short amount of time
// and limited to a statically allocated amount of memory
// ...
// validate inputs for task 2
// execute task 2, inlined
// ...
// validate inputs for task N
// execute task N, inlined
}
while (true);
// if this line is reached, tell the programmers to prepare
// themselves to appear before an accident investigation board.
return 0;
}
Este estilo sería apropiado para los microcontroladores, es decir, para aquellos que ven el software como un complemento de las funciones del hardware.
No, no necesariamente.
Lea el documento anterior de Appel La recolección de basura puede ser más rápida que la Asignación de pila . Utiliza estilo de paso de continuación y muestra una implementación sin apilamiento.
Observe también que las arquitecturas de computadoras antiguas (por ejemplo, IBM / 360 ) no tenían ningún registro de pila de hardware. Pero el sistema operativo y el compilador reservaron un registro para el puntero de pila por convención (relacionado con convenciones de llamada ) para que puedan tener un software pila de llamadas .
En principio, un compilador y optimizador del programa C completo podría detectar el caso (algo común para los sistemas integrados) en el que el gráfico de llamadas se conoce estáticamente y sin ninguna recursión (o punteros de función). En tal sistema, cada función podría mantener su dirección de retorno en una ubicación estática fija (y así fue como funcionó Fortran77 en las computadoras de la era de 1970).
En estos días, los procesadores también tienen pilas de llamadas (e instrucciones de llamada y devolución de la máquina) conscientes de cachés de CPU .
Hasta ahora tienes algunas buenas respuestas; Permítame darle un ejemplo poco práctico pero altamente educativo de cómo puede diseñar un lenguaje sin la noción de pilas o "flujo de control" en absoluto. Aquí hay un programa que determina factoriales:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)
Colocamos este programa en una cadena y evaluamos el programa mediante una sustitución textual. Entonces, cuando estamos evaluando f(3) , hacemos una búsqueda y reemplazamos con 3 para i, como esto:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)
Genial. Ahora realizamos otra sustitución textual: vemos que la condición del "si" es falsa y hacemos otra cadena de reemplazo, produciendo el programa:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)
Ahora hacemos otra cadena de reemplazo en todas las sub-expresiones que involucran constantes:
function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)
Y ves cómo va esto; No voy a trabajar más el punto. Podríamos seguir haciendo una serie de sustituciones de cadenas hasta que bajemos a let x = 6 y lo hagamos.
Usamos la pila tradicionalmente para variables locales e información de continuación; recuerda, una pila no te dice de dónde vienes, te dice a dónde vas a ir con ese valor de retorno en la mano.
En el modelo de programación de sustitución de cadenas, no hay "variables locales" en la pila; los parámetros formales se sustituyen por sus valores cuando la función se aplica a su argumento, en lugar de colocarse en una tabla de búsqueda en la pila. Y no hay "ir a algún lado" porque la evaluación del programa es simplemente aplicar reglas simples para la sustitución de cadenas para producir un programa diferente pero equivalente.
Ahora, por supuesto, hacer sustituciones de cadenas probablemente no sea el camino a seguir. Pero los lenguajes de programación que admiten el "razonamiento ecuacional" (como Haskell) utilizan lógicamente utilizando esta técnica.
Desde la publicación por Parnas en 1972 de Sobre los criterios que se utilizarán en los sistemas de descomposición En los módulos se ha aceptado razonablemente que la información que se oculta en el software es algo bueno. Esto sigue a un largo debate a lo largo de los años 60 sobre descomposición estructural y programación modular.
Un resultado necesario de las relaciones de caja negra entre los módulos implementados por diferentes grupos en cualquier sistema de subprocesos múltiples requiere un mecanismo para permitir la reentrada y un medio para rastrear el gráfico de llamadas dinámico del sistema. El flujo controlado de ejecución tiene que pasar tanto dentro como fuera de múltiples módulos.
Tan pronto como el alcance léxico sea insuficiente para rastrear el comportamiento dinámico, se requiere cierta contabilidad en tiempo de ejecución para rastrear la diferencia.
Dado que cualquier subproceso (por definición) tiene solo un único puntero de instrucción actual, una pila LIFO es apropiada para rastrear cada invocación.
Entonces, mientras el modelo de continuación no mantiene una estructura de datos explícitamente para la pila, ¡todavía hay una llamada anidada de módulos que debe mantenerse en algún lugar!
Incluso los idiomas declarativos mantienen el historial de evaluación o, a la inversa, aplanan el plan de ejecución por razones de rendimiento y mantienen el progreso de alguna otra manera.
La estructura de bucle sin fin identificada por rwong es común en aplicaciones de alta confiabilidad con una programación estática que no permite muchos la programación estructura, pero exige que toda la aplicación se considere una caja blanca sin ocultación de información significativa.
Varios bucles sin fin concurrentes no requieren ninguna estructura para retener las direcciones de retorno ya que no llaman a las funciones, lo que hace que la pregunta sea discutible. Si se comunican utilizando variables compartidas, estas pueden degenerar fácilmente en análogos de dirección de retorno heredados al estilo Fortran.
Todos los mainframes antiguos (IBM System / 360) no tenían ninguna noción de pila. En el 260, por ejemplo, los parámetros se construyeron en una ubicación fija en la memoria y cuando se llamó a una subrutina, se llamó con R1 que apunta al bloque de parámetros y R14 que contiene la dirección de retorno. La rutina llamada, si quisiera llamar a otra subrutina, tendría que almacenar R14 en una ubicación conocida antes de hacer esa llamada.
Esto es mucho más confiable que una pila porque todo se puede almacenar en ubicaciones de memoria fijas establecidas en el momento de la compilación y se puede garantizar al 100% que los procesos nunca se quedarán sin pila. No hay ninguno de los "Asignar 1 MB y cruzar los dedos" que tenemos que hacer hoy en día.
Se permitieron llamadas de subrutina recursivas en PL / I especificando la palabra clave RECURSIVE . Significaron que la memoria utilizada por la subrutina se asignó dinámicamente en lugar de estáticamente. Pero las llamadas recursivas eran tan raras como lo son ahora.
El funcionamiento sin apilamiento también hace que los subprocesos múltiples masivos sean mucho más fáciles, por lo que a menudo se hacen intentos para hacer que los lenguajes modernos no sean acosados. No hay ninguna razón en absoluto, por ejemplo, la razón por la cual un compilador de C ++ no podría modificarse el back-end para usar memoria asignada dinámicamente en lugar de pilas.
Lea otras preguntas en las etiquetas computer-architecture