¿Cómo funciona un lenguaje sin pila?

Question

He oído hablar de lenguajes sin pila. Sin embargo, no tengo idea de cómo se implementaría dicho lenguaje. ¿Alguien puede explicar?

Answer 1

Los sistemas operativos modernos que tenemos (Windows, Linux) funcionan con lo que yo llamo el "modelo de pila grande". Y ese modelo es incorrecto, a veces, y motiva la necesidad de "sin pila". idiomas.

El " modelo de pila grande " asume que un programa compilado asignará " marcos de pila " para llamadas a funciones en una región contigua de memoria, utilizando instrucciones de la máquina para ajustar registros que contienen el puntero de pila (y el puntero de marco de pila opcional) muy rápidamente. Esto conduce a una función rápida llamada / devolución, al precio de tener una región grande y contigua para la pila. Debido a que el 99,99% de todos los programas que se ejecutan en estos sistemas operativos modernos funcionan bien con el modelo de pila grande, los compiladores, los cargadores e incluso el sistema operativo "conocen". sobre esta área de pila.

Un problema común que tienen todas estas aplicaciones es, " ¿qué tamaño debería tener mi pila? " . Debido a que la memoria es muy barata, lo que sucede en su mayoría es que se reserva una gran parte para la pila (el valor predeterminado de MS es 1Mb), y la estructura típica de llamadas a aplicaciones nunca se acerca a su uso. Pero si una aplicación lo usa todo, muere con una referencia de memoria ilegal ("Lo siento Dave, no puedo hacer eso"), en virtud de alcanzar el final de su pila.

La mayoría de los llamados '' sin pila '' los idiomas no son realmente apilados. Simplemente no usan la pila contigua proporcionada por estos sistemas. Lo que hacen en su lugar es asignar un marco de pila del montón en cada llamada de función. El costo por llamada de función aumenta un poco; Si las funciones son típicamente complejas, o el lenguaje es interpretativo, este costo adicional es insignificante. (También se pueden determinar los DAG de llamadas en el gráfico de llamadas del programa y asignar un segmento de almacenamiento dinámico para cubrir todo el DAG; de esta manera se obtiene tanto la asignación de almacenamiento dinámico como la velocidad de las llamadas a la función de pila grande clásica para todas las llamadas dentro del DAG de llamadas).

Hay varias razones para usar la asignación de montón para los marcos de pila:

1) Si el programa hace una recursión profunda dependiendo del problema específico que está resolviendo, es muy difícil preasignar una "pila grande" área de antemano porque no se conoce el tamaño necesario. Uno puede organizar torpemente las llamadas de función para verificar si queda suficiente pila, y si no, reasignar una porción más grande, copiar la pila anterior y reajustar todos los punteros en la pila; eso es tan incómodo que no conozco ninguna implementación. La asignación de marcos de pila significa que la aplicación nunca tiene que pedir perdón hasta que haya literalmente no queda memoria asignable.

2) El programa bifurca subtareas. Cada subtarea requiere su propia pila y, por lo tanto, no puede usar la "pila grande". previsto. Entonces, uno necesita asignar pilas para cada subtarea. Si tiene miles de subtareas posibles, es posible que ahora necesite miles de "pilas grandes", y la demanda de memoria de repente se vuelve ridícula. La asignación de marcos de pila resuelve este problema. A menudo, la subtarea "pilas" consulte las tareas principales para implementar el alcance léxico; como subtareas fork, un árbol de '' subestacas '' se crea llamado " pila de cactus " ;.

3) Su idioma tiene continuaciones. Esto requiere que los datos en el ámbito léxico visibles para la función actual se conserven de alguna manera para su posterior reutilización. Esto se puede implementar copiando los marcos de la pila principal, subiendo la pila de cactus y procediendo.

El lenguaje de programación PARLANSE que implementé hace 1) y 2). Estoy trabajando en 3).

Answer 2

Stackless Python todavía tiene una pila de Python (aunque puede tener optimización de llamadas de cola y otros trucos para combinar marcos de llamadas ), pero está completamente divorciada de la pila C del intérprete.

Haskell (como se implementa comúnmente) no tiene una pila de llamadas; la evaluación se basa en reducción de gráficos .

Answer 3

Hay un buen artículo sobre el marco de lenguaje Parrot en http: // www .linux-mag.com / cache / 7373 / 1.html . Parrot no usa la pila para llamar y este artículo explica un poco la técnica.

Answer 4

En los entornos sin pila con los que estoy más o menos familiarizado (máquina de Turing, ensamblaje y Brainfuck), es común implementar su propia pila. No hay nada fundamental sobre tener una pila integrada en el lenguaje.

En el más práctico de estos, el ensamblaje, simplemente elige una región de memoria disponible, configura el registro de la pila para que apunte hacia la parte inferior, luego incrementa o disminuye para implementar tus empujes y estallidos.

EDITAR: Sé que algunas arquitecturas tienen pilas dedicadas, pero no son necesarias.

Answer 5

Hay una descripción fácil de entender de las continuaciones en este artículo: http: // www. defmacro.org/ramblings/fp.html

Las continuaciones son algo que puede pasar a una función en un lenguaje basado en pila, pero que también puede ser utilizado por la semántica propia de un lenguaje para hacerlo "sin pila". Por supuesto, la pila todavía está allí, pero como describió Ira Baxter, no es un gran segmento contiguo.

Answer 6

Digamos que desea implementar el stackless C. Lo primero que debe darse cuenta es que esto no necesita un stack:

a == b

Pero, ¿esto?

isequal(a, b) { return a == b; }

No. Debido a que un compilador inteligente alineará las llamadas a isequal , convirtiéndolas en a == b . Entonces, ¿por qué no simplemente en línea todo? Claro, generará más código, pero si vale la pena deshacerse de la pila, entonces esto es fácil con una pequeña compensación.

¿Qué pasa con la recursividad? No hay problema. Una función recursiva de cola como:

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

Todavía puede estar en línea, porque realmente es solo un bucle for disfrazado:

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

En teoría, un compilador realmente inteligente podría resolverlo por usted. Pero uno menos inteligente aún podría aplanarlo como un goto:

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

Hay un caso en el que tienes que hacer un pequeño intercambio. Esto no puede estar en línea:

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless C simplemente no puede hacer esto. ¿Estás renunciando mucho? Realmente no. Esto es algo normal que C tampoco puede hacer bien. Si no me cree, simplemente llame a fib (1000) y vea qué sucede con su preciosa computadora.

Answer 7

Llámame antiguo, pero puedo recordar cuando los estándares FORTRAN y COBOL no admitían llamadas recursivas y, por lo tanto, no requerían una pila. De hecho, recuerdo las implementaciones para máquinas de la serie CDC 6000 donde no había una pila, y FORTRAN haría cosas extrañas si intentaras llamar a una subrutina de forma recursiva.

Para el registro, en lugar de una pila de llamadas, el conjunto de instrucciones de la serie CDC 6000 utilizó la instrucción RJ para llamar a una subrutina. Esto guardó el valor actual de la PC en la ubicación de destino de la llamada y luego se bifurca a la ubicación siguiente. Al final, una subrutina realizaría un salto indirecto a la ubicación del objetivo de la llamada. Eso volvió a cargar la PC guardada, volviendo efectivamente a la persona que llama.

Obviamente, eso no funciona con llamadas recursivas. (Y recuerdo que el compilador CDC FORTRAN IV generaría código roto si intentara la recursividad ...)

Answer 8

Por favor, siéntase libre de corregirme si me equivoco, pero creo que asignar memoria en el montón para cada marco de llamada de función provocaría una pérdida de memoria extrema. Después de todo, el sistema operativo tiene que administrar esta memoria. Creo que la forma de evitar esta pérdida de memoria sería un caché para marcos de llamadas. Entonces, si necesita un caché de todos modos, también podríamos ponerlo en la memoria y llamarlo una pila.