stack language-design stackless

stack - ¿Cómo funciona un lenguaje sin pilas?



language-design stackless (8)

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

Digamos que quería implementar el stackless C. Lo primero es darse cuenta de que esto no necesita una pila:

a == b

Pero, ¿esto?

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

No. Porque un compilador inteligente llamará a isequal , convirtiéndolo en a == b . Entonces, ¿por qué no solo en línea todo? Claro, usted generará más código, pero si deshacerse de la pila vale la pena para usted, entonces esto es fácil con una pequeña compensación.

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

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

Todavía puede estar en línea, porque en realidad es solo un ciclo para disfrazarse:

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

En teoría, un compilador realmente inteligente podría darte cuenta de eso. Pero uno menos inteligente podría aplanarlo como un goto:

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

Hay un caso en el que tiene que hacer una pequeña transacción. Esto no puede ser inline:

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

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

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

En el ensamblaje más práctico, simplemente elija la región de memoria disponible para usted, configure el registro de la pila para que apunte hacia abajo, luego incremente o disminuya para implementar sus impulsos y saltos.

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

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

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

Llámame antiguo, pero recuerdo 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 las máquinas de la serie CDC 6000 donde no había una pila, y FORTRAN haría cosas extrañas si intentara llamar una subrutina recursivamente.

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 de PC actual en la ubicación de destino de la llamada y luego se bifurca a la ubicación que lo sigue. Al final, una subrutina realizaría un salto indirecto a la ubicación del objetivo de la llamada. Esa PC guardada recargó, efectivamente volviendo a la persona que llama.

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

Los sistemas operativos modernos que tenemos (Windows, Linux) operan con lo que yo llamo el "modelo de la gran pila". Y ese modelo está equivocado, a veces, y motiva la necesidad de idiomas "apilados".

El "modelo de gran stack" asume que un programa compilado asignará "frames de pila" para llamadas de función en una región contigua de memoria, usando instrucciones de 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 llamada / devolución de función rápida, al precio de tener una región grande y contigua para la pila. Dado que el 99,99% de todos los programas que se ejecutan bajo estos sistemas operativos modernos funcionan bien con el modelo de gran stack, los compiladores, cargadores e incluso el sistema operativo "saben" sobre esta área de pila.

Un problema común que tienen todas estas aplicaciones es "¿qué tan grande debe ser mi pila?" . Dado que la memoria es muy barata, lo que sucede principalmente es que se reserva un gran trozo para la pila (MS tiene un valor predeterminado de 1Mb), y la estructura típica de las llamadas a la aplicación nunca llega a utilizarlo. 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 llegar al final de su pila.

La mayoría de los llamados lenguajes "apilados" 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 de programa y asignar un segmento de montón para cubrir todo el DAG, de esta manera se obtiene la asignación de montón y la velocidad de las llamadas a la función clásica de Big-stack para todas las llamadas dentro de la llamada DAG).

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

1) Si el programa realiza recursiones profundas dependiendo del problema específico que está resolviendo, es muy difícil preasignar un área de "gran pila" de antemano porque no se conoce el tamaño necesario. Uno puede organizar torpemente llamadas de función para verificar si queda suficiente pila, y si no, reasignar un trozo más grande, copiar la pila anterior y reajustar todos los punteros en la pila; eso es tan incomodo que no conozco ninguna implementación. Asignar marcos de pila significa que la aplicación nunca tiene que decir que lo siente hasta que literalmente no queda memoria asignable.

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

3) Tu idioma tiene continuaciones. Estos requieren que los datos en el alcance léxico visibles para la función actual de alguna manera se conserven para su reutilización posterior. Esto se puede implementar copiando cuadros de pila padre, subiendo por la pila de cactus y procediendo.

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

Por favor, siéntete libre de corregirme si me equivoco, pero creo que asignar memoria en el montón para cada cuadro de llamada de función causaría una gran cantidad de memoria. El sistema operativo, después de todo, tiene que administrar esta memoria. Pensaría que la manera de evitar esta paliza de memoria sería un caché para los marcos de llamadas. Entonces, si necesita un caché de todos modos, también podemos hacerlo contiguo en memoria y llamarlo pila.

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

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