¿Son las pilas la única forma razonable de estructurar programas?

74

La mayoría de las arquitecturas que he visto se basan en 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 utilizan?

CondiciónRacer
fuente
55
Dado que se espera que las funciones se comporten en lenguajes tipo C (es decir, puede anidar llamadas tan profundas como desee y puede volver a salir en orden inverso), no tengo claro cómo podría implementarse llamadas a funciones sin que sea increíblemente ineficiente. Podría, por ejemplo, obligar al programador a usar un estilo de paso continuo o alguna otra forma extraña de programación, pero nadie parece trabajar realmente con CPS en el nivel bajo por alguna razón.
Kevin
55
GLSL funciona sin una pila (al igual que otros idiomas en ese soporte específico). Simplemente no permite llamadas recursivas.
Leushenko
3
También es posible que desee buscar en las ventanas de registro , que utilizan algunas arquitecturas RISC.
Mark Booth
2
@Kevin: "Los primeros compiladores de FORTRAN no admitían la recurrencia en las subrutinas. Las arquitecturas informáticas tempranas no admitían el concepto de una pila, y cuando admitían directamente las llamadas de subrutina, la ubicación de retorno a menudo se almacenaba en una ubicación fija adyacente al código de subrutina, que sí no permitir que se vuelva a llamar a una subrutina antes de que vuelva una llamada anterior de la subrutina. Aunque no se especifica en Fortran 77, muchos compiladores F77 admitieron la recursión como una opción, mientras que se convirtió en un estándar en Fortran 90 ". en.wikipedia.org/wiki/Fortran#FORTRAN_II
Mooing Duck
3
El microcontrolador P8X32A ("Propeller") no tiene el concepto de una pila en su lenguaje de ensamblaje estándar (PASM). Las instrucciones responsables del salto también modifican automáticamente la instrucción de retorno en la RAM para determinar a dónde regresar, que se puede elegir arbitrariamente. Curiosamente, el lenguaje "Spin" (un lenguaje de alto nivel interpretado que se ejecuta en el mismo chip) tiene una semántica de pila tradicional.
Wossname

Respuestas:

50

Una alternativa (algo) popular a una pila de llamadas son las continuaciones .

El Parrot VM está basado en la continuación, por ejemplo. Es completamente sin pila: los datos se mantienen en registros (como Dalvik o LuaVM, Parrot está basado 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 típicamente por las máquinas virtuales Smalltalk y Lisp es la pila de espaguetis, que es algo así como una red de pilas.

Como señaló @rwong , el estilo de paso de continuación es una alternativa a una pila de llamadas. Los programas escritos en (o transformados en) estilo de paso de continuación nunca regresan, por lo que no hay necesidad de una pila.

Responde tu pregunta desde una perspectiva diferente: es posible tener una pila de llamadas sin tener una pila separada, asignando los marcos de la pila en el montón. Algunas implementaciones de Lisp y Scheme hacen esto.

Jörg W Mittag
fuente
44
Depende de su definición de una pila. No estoy seguro de que tener una lista vinculada (o una matriz de punteros ao ...) de marcos de pila sea tanto "no una pila" como "una representación diferente de una pila"; y los programas en lenguajes CPS (en la práctica) tienden a construir lo que efectivamente son listas vinculadas de continuaciones que son muy similares a las pilas (si no lo ha hecho, puede consultar GHC, que empuja lo que llama "continuaciones" en una pila lineal) por eficiencia).
Jonathan Cast
66
"Los programas escritos en (o transformados a) estilo de paso de continuación nunca regresan " ... suena ominoso.
Rob Penridge
55
@RobPenridge: es un poco críptico, estoy de acuerdo. CPS significa que, en lugar de regresar, las funciones toman como argumento adicional otra función a la que llamar cuando se realiza su trabajo. Entonces, cuando llamas a una función y tienes otro trabajo que debes hacer después de haber llamado a la función, en lugar de esperar a que la función regrese y luego continuar con tu trabajo, envuelves el trabajo restante ("la continuación" ) en una función y pasa esa función como argumento adicional. La función que llamó luego llama a esa función en lugar de regresar, y así sucesivamente. Ninguna función regresa, solo
Jörg W Mittag
3
... llama a la siguiente función. Por lo tanto, no necesita una pila de llamadas, porque nunca necesita regresar y restaurar el estado de enlace de una función llamada anteriormente. En lugar de cargar con el estado pasado para que pueda volver a él, cargue con el estado futuro , si lo desea.
Jörg W Mittag
1
@jcast: la característica definitoria de una pila es IMO que solo puede acceder al elemento superior. Una lista de continuaciones, OTOH, le daría acceso a todas las continuaciones y no solo al mejor stackframe. Si tiene excepciones reanudables de estilo Smalltalk, por ejemplo, debe poder atravesar la pila sin reventarla. Y tener continuaciones en el lenguaje mientras todavía se quiere mantener la idea familiar de una pila de llamadas conduce a pilas de espagueti, que es básicamente un árbol de pilas donde las continuaciones "bifurcan" la pila.
Jörg W Mittag
36

En los viejos tiempos, los procesadores no tenían instrucciones de pila, y los lenguajes de programación no admitían la recursividad. Con el tiempo, cada vez más idiomas optan por admitir la recursividad, y el hardware siguió a la suite con 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 marcos de pila y / o registros de puntero de pila; algunas adoptaron instrucciones 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 y luego con cachés de varios niveles, una ventaja crítica de la pila es la de la localidad de caché. La parte superior de la pila casi siempre está en el caché. Siempre que pueda hacer algo que tenga una gran tasa de aciertos de caché, está en el camino correcto con los procesadores modernos. La memoria caché aplicada a la pila significa que las variables locales, parámetros, etc. casi siempre están en la memoria caché y disfrutan del más alto nivel de rendimiento.

En resumen, el uso de la pila evolucionó tanto en hardware como en software. Existen otros modelos (por ejemplo, la informática de flujo de datos se intentó durante un período prolongado), sin embargo, la localidad de la pila hace que funcione realmente bien. Además, el código de procedimiento es justo lo que los procesadores quieren 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 por el momento, ya que no hemos descubierto cómo hacer que el acceso aleatorio sea tan rápido como el acceso secuencial. (Por cierto, hay problemas similares en cada nivel de memoria, desde caché, memoria principal, 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.

(Podríamos incluir mutabilidad de las estructuras de datos en las obras también ...)

Esto no significa que otros modelos de programación no puedan funcionar, especialmente cuando se pueden traducir a las instrucciones secuenciales y al modelo de pila de llamadas del hardware actual. Pero existe una clara ventaja para los modelos que admiten dónde está el hardware. Sin embargo, las cosas no siempre permanecen igual, por lo que podríamos ver cambios en el futuro a medida que diferentes tecnologías de memoria y transistores permitan un mayor paralelismo. Siempre es una broma entre lenguajes de programación y capacidades de hardware, ¡así que ya veremos!

Erik Eidt
fuente
9
De hecho, las GPU todavía no tienen pilas. Se le prohíbe recurrir en GLSL / SPIR-V / OpenCL (no estoy seguro acerca de HLSL, pero probablemente, no veo ninguna razón por la cual sería diferente). La forma en que manejan realmente las llamadas "pilas" de funciones es mediante el uso de una cantidad absurdamente grande de registros.
LinearZoetrope
@Jsor: Eso es en gran medida un detalle de implementación, como se puede ver en la arquitectura SPARC. Al igual que su GPU, SPARC tiene un gran conjunto de registros, pero es único en el sentido de que tiene una ventana deslizante que en forma envolvente derrama los registros muy antiguos en una pila en la RAM. Entonces es realmente un híbrido entre los dos modelos. Y SPARC no especificó exactamente cuántos registros físicos había, ni qué tan grande era la ventana de registro, por lo que diferentes implementaciones podrían ubicarse en cualquier lugar en esa escala de "gran cantidad de registros" a "lo suficiente para una ventana, en cada llamada de función derrame directamente a la pila "
MSalters
Una desventaja del modelo de pila de llamadas es que la matriz y / o el desbordamiento de la dirección deben observarse con mucho cuidado, ya que los programas auto modificables como un exploit son posibles si los bits arbitrarios del montón son ejecutables.
BenPen
14

TL; DR

  • Pila de llamadas como un mecanismo de llamada de función:
    1. Normalmente se simula por hardware, pero no es fundamental para la construcción de hardware
    2. Es fundamental para la programación imperativa.
    3. No es fundamental para la programación funcional.
  • La pila como abstracción de "último en entrar, primero en salir" (LIFO) es fundamental para la informática, los algoritmos e incluso algunos dominios no técnicos.
  • Algunos ejemplos de organización de programas que no usan pilas de llamadas:
    • Estilo de paso continuo (CPS)
    • Máquina de estado: un bucle gigante, con todo en línea. (Supuestamente inspirada en la arquitectura de firmware de Saab Gripen, y atribuida a una comunicación de Henry Spencer y reproducida por John Carmack.) (Nota # 1)
    • Arquitectura de flujo de datos: una red de actores conectados por colas (FIFO). Las colas a veces se llaman canales.

El resto de esta respuesta es una colección aleatoria de pensamientos y anécdotas, y por lo tanto, algo desorganizada.


La pila que ha descrito (como 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 ser descrito 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:

  1. Lógica combinacional, es decir, una conexión de compuertas lógicas (y, o, no, ...) Tenga en cuenta que la "lógica combinacional" excluye las retroalimentaciones.
  2. Memoria, es decir, chanclas, pestillos, registros, SRAM, DRAM, etc.
  3. Una máquina de estado que consiste en cierta lógica combinatoria y algo de memoria, lo suficiente como para que pueda implementar un "controlador" que gestione el resto del hardware.

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 microcontroladores, es decir, para aquellos que ven el software como un complemento de las funciones del hardware.


rwong
fuente
@Peteris: las pilas son estructuras de datos LIFO.
Christopher Creutzig
1
Interesante. Lo hubiera pensado al revés. Por ejemplo, FORTRAN es un lenguaje de programación imperativo, y las primeras versiones no usaban una pila de llamadas. Sin embargo, la recursividad es fundamental para la programación funcional, y no creo que sea posible implementarla en el caso general sin usar una pila.
TED
@TED: en una implementación de lenguaje funcional, hay una estructura de datos de pila (o típicamente un árbol) que representa los cálculos pendientes, pero no necesariamente lo ejecuta con instrucciones utilizando los modos de direccionamiento orientado a la pila de la máquina o incluso las instrucciones de llamada / devolución (de forma anidada / recursiva, tal vez solo como parte de un bucle de máquina de estado).
davidbak
@davidbak - IIRC, un algoritmo recursivo tiene que ser recursivo en la cola para poder deshacerse de la pila. Probablemente hay algunos otros casos en los que podría optimizarlo, pero en el caso general , debe tener una pila . De hecho, me dijeron que había una prueba matemática de esto flotando en alguna parte. Esta respuesta afirma que es el teorema de Church-Turing (creo que basado en el hecho de que las máquinas de Turing usan una pila?)
TED
1
@TED ​​- Estoy de acuerdo contigo. Creo que la falta de comunicación aquí es que leí la publicación del OP para hablar sobre la arquitectura del sistema, lo que significaba para mí la arquitectura de la máquina . Creo que otros que han respondido aquí tienen la misma comprensión. Entonces, aquellos de nosotros que entendimos que ese es el contexto, hemos respondido respondiendo que no necesita una pila en el nivel del modo de instrucción / direccionamiento de la máquina. Pero puedo ver que la pregunta también puede interpretarse en el sentido de que, simplemente, un sistema de lenguaje en general necesita una pila de llamadas. Esa respuesta también es no, pero por diferentes razones.
davidbak
11

No, no necesariamente

Lea la recolección de basura en papel viejo de Appel puede ser más rápido que la asignación de pila . Utiliza el estilo de paso continuo y muestra una implementación sin pila.

Observe también que las arquitecturas informáticas 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 la pila por convención (relacionado con las convenciones de llamada ) para que pudieran tener una pila de llamadas de software .

En principio, todo un compilador y optimizador de programa C podría detectar el caso (algo común para los sistemas integrados) en el que el gráfico de llamadas es estáticamente conocido y sin recurrencia (o punteros de función). En dicho sistema, cada función podría mantener su dirección de retorno en una ubicación estática fija (y así fue como Fortran77 funcionaba en las computadoras de la era de 1970).

En estos días, los procesadores también tienen pilas de llamadas (e instrucciones de máquina de llamada y devolución) conscientes de los cachés de la CPU .

Basile Starynkevitch
fuente
1
Estoy bastante seguro de que FORTRAN dejó de usar ubicaciones de retorno estáticas cuando salió FORTRAN-66 y requirió soporte para SUBROUTINEy FUNCTION. Sin embargo, tiene razón para versiones anteriores (FORTRAN-IV y posiblemente WATFIV).
TMN
Y COBOL, por supuesto. Y un excelente punto sobre IBM / 360: tuvo bastante uso a pesar de que faltaban modos de direccionamiento de pila de hardware. (R14, creo que era?) Y tenía compiladores para lenguajes basados ​​en pila, por ejemplo, PL / I, Ada, Algol, C.
davidbak
De hecho, estudié el 360 en la universidad y al principio me pareció desconcertante.
JDługosz
1
@ JDługosz La mejor manera para que los estudiantes modernos de arquitectura de computadoras consideren el 360 es como una máquina RISC muy simple ... aunque con más de un formato de instrucción ... y algunas anomalías como TRy TRT.
davidbak
¿Qué tal "cero y agregar empaquetado" para mover un registro? Pero "ramificar y vincular" en lugar de apilar para la dirección de retorno ha regresado.
JDługosz
10

Tienes algunas buenas respuestas hasta ahora; déjame darte un ejemplo poco práctico pero altamente educativo de cómo puedes diseñar un lenguaje sin la noción de pilas o "flujo de control". Aquí hay un programa que determina los factoriales:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Ponemos este programa en una cadena y evaluamos el programa mediante sustitución textual. Entonces, cuando estamos evaluando f(3), hacemos una búsqueda y reemplazamos con 3 para i, así:

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)

Excelente. Ahora realizamos otra sustitución textual: vemos que la condición del "si" es falsa y reemplazamos otra cadena, 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 subexpresiones que involucran constantes:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

Y ya ves cómo va esto; No voy a trabajar más el punto. Podríamos seguir haciendo una serie de sustituciones de cuerdas hasta que nos pongamos manos a la obra let x = 6y hayamos terminado.

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 después 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 otro 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 cuerdas probablemente no sea el camino a seguir. Pero los lenguajes de programación que admiten el "razonamiento equitativo" (como Haskell) utilizan lógicamente esta técnica.

Eric Lippert
fuente
3
Retina es un ejemplo de un lenguaje de programación basado en Regex que utiliza operaciones de cadena para el cálculo.
Andrew Piliser
2
@AndrewPiliser Diseñado e implementado por este tipo genial .
gato
3

Desde la publicación de Parnas en 1972 de Sobre los criterios que se utilizarán para descomponer los sistemas en módulos, se ha aceptado razonablemente que la información oculta en el software es algo bueno. Esto sigue a un largo debate a lo largo de los años 60 sobre la descomposición estructural y la programación modular.

Modularidad

Un resultado necesario de las relaciones de caja negra entre módulos implementados por diferentes grupos en cualquier sistema de subprocesos múltiples requiere un mecanismo que permita la reentrada y un medio para rastrear el gráfico dinámico de llamadas del sistema. El flujo controlado de ejecución tiene que pasar dentro y fuera de múltiples módulos.

Alcance dinámico

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 puntero de instrucción actual, una pila LIFO es apropiada para rastrear cada invocación.

Excepciones

Por lo tanto, si bien 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 alguna parte!

Incluso los lenguajes declarativos mantienen el historial de evaluación o, por el contrario, 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 programación estática que no permite muchas estructuras de programación comunes pero exige que toda la aplicación se considere una caja blanca sin ocultar información significativa.

Múltiples bucles sin fin concurrentes no requieren ninguna estructura para contener direcciones de retorno ya que no llaman a funciones, lo que hace que la pregunta sea discutible. Si se comunican usando variables compartidas, estas pueden degenerar fácilmente en análogos de direcciones de retorno de estilo Fortran heredados.

Pekka
fuente
1
Te pintas en un rincón asumiendo " cualquier sistema multihilo". Las máquinas de estado finito acopladas pueden tener múltiples subprocesos en su implementación, pero no requieren una pila LIFO. No hay limitación en los FSM de que regrese a cualquier estado anterior, y mucho menos en orden LIFO. Entonces, ese es un sistema real de múltiples subprocesos para el que no es válido. Y si se limita a una definición de subprocesos múltiples como "pilas de llamadas de función independientes paralelas", termina con una definición circular.
MSalters
No leo la pregunta de esa manera. OP está familiarizado con las llamadas a funciones, pero pregunta sobre otros sistemas.
MSalters
@MSalters Actualizado para incorporar bucles sin fin concurrentes. El modelo es válido, pero limita la escalabilidad. Sugeriría que incluso las máquinas de estado moderadas incorporen llamadas de función para permitir la reutilización del código.
Pekka
2

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ó R1apuntando al bloque de parámetros y R14conteniendo la dirección de retorno. La rutina llamada, si quería llamar a otra subrutina, tendría que almacenarse R14en 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 fija 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 1MB 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 era asignada dinámicamente en lugar de estáticamente. Pero las llamadas recursivas eran tan raras como lo son ahora.

La operación sin apilamiento también facilita mucho el subprocesamiento múltiple masivo, por lo que a menudo se hacen intentos para que los lenguajes modernos no tengan acecho. No hay ninguna razón en absoluto, por ejemplo, por qué un compilador de C ++ no puede modificarse en el back-end para usar memoria asignada dinámicamente en lugar de pilas.

Martin Kochanski
fuente