¿Cuáles son las alternativas al uso de una pila para representar la semántica de llamadas de función?

19

Todos sabemos y amamos que las llamadas a funciones generalmente se implementan usando la pila; hay marcos, direcciones de retorno, parámetros, todo el lote.

Sin embargo, la pila es un detalle de implementación: las convenciones de llamada pueden hacer cosas diferentes (es decir, x86 fastcall usa (algunos) registros, MIPS y seguidores usan ventanas de registro, etc.) y las optimizaciones pueden hacer incluso otras cosas (alineación, omisión de puntero de marco, optimización de llamadas de cola ..).

Claro, la presencia de instrucciones de pila convenientes en muchas máquinas (máquinas virtuales como JVM y CLR, pero también máquinas reales como x86 con su PUSH / POP, etc.) hace que sea conveniente usarlo para llamadas a funciones, pero en algunos casos es posible para programar de una manera en la que no se necesita una pila de llamadas (estoy pensando en el estilo de paso de continuación aquí, o en los actores en un sistema de paso de mensajes)

Entonces, comencé a preguntarme: ¿es posible implementar una semántica de llamadas de función sin una pila, o mejor, usando una estructura de datos diferente (una cola, tal vez, o un mapa asociativo?)
Por supuesto, entiendo que una pila es muy conveniente (hay una razón por la cual es omnipresente) pero recientemente me topé con una implementación que me hizo preguntarme ...

¿Alguno de ustedes sabe si alguna vez se ha hecho en algún idioma / máquina / máquina virtual y, de ser así, cuáles son las notables diferencias y deficiencias?

EDITAR: Mi intuición es que los diferentes enfoques de subcálculo pueden usar diferentes estructuras de datos. Por ejemplo, el cálculo lambda no se basa en la pila (la idea de la aplicación de funciones se captura mediante reducciones) pero estaba buscando un lenguaje / máquina / ejemplo real. Por eso estoy preguntando ...

Lorenzo Dematté
fuente
Clean utiliza un gráfico y una máquina de reescritura de gráficos, que a su vez se implementa utilizando una máquina de tres pilas, pero con un contenido diferente al habitual.
Para máquinas virtuales, se puede usar una lista vinculada. Cada nodo de la lista es un marco. Dado que la máquina virtual utiliza la pila de hardware, esto permite que existan tramas en el montón sin la sobrecarga de realloc().
shawnhcorey

Respuestas:

19

Dependiendo del idioma, puede no ser necesario usar una pila de llamadas. Las pilas de llamadas solo son necesarias en idiomas que permiten la recursividad o recursividad mutua. Si el lenguaje no permite la recursividad, solo una invocación de cualquier procedimiento puede estar activa en cualquier momento, y las variables locales para ese procedimiento pueden asignarse estáticamente. Dichos lenguajes deben prever cambios de contexto, para el manejo de interrupciones, pero esto aún no requiere una pila.

Consulte FORTRAN IV (y versiones anteriores) y versiones anteriores de COBOL para ver ejemplos de idiomas que no requieren pilas de llamadas.

Consulte Control Data 6600 (y máquinas de Control Data anteriores) para ver un ejemplo de una supercomputadora temprana altamente exitosa que no proporcionó soporte directo de hardware para las pilas de llamadas. Consulte el PDP-8 para ver un ejemplo de una minicomputadora temprana muy exitosa que no admitía pilas de llamadas.

Hasta donde yo sé, las máquinas de pila Burroughs B5000 fueron las primeras máquinas con pilas de llamadas de hardware. Las máquinas B5000 fueron diseñadas desde cero para ejecutar ALGOL, lo que requería recursividad. También tenían una de las primeras arquitecturas basadas en descriptores, que sentaron las bases para las arquitecturas de capacidad.

Hasta donde yo sé, fue el PDP-6 (que se convirtió en el DEC-10) el que popularizó el hardware de la pila de llamadas, cuando la comunidad de hackers del MIT recibió uno y descubrió que la operación PUSHJ (Push Return Address and Jump) permitió que la rutina de impresión decimal se redujera de 50 instrucciones a 10.

La semántica de llamada de función más básica en un lenguaje que permite la recursividad requiere capacidades que coincidan muy bien con una pila. Si eso es todo lo que necesita, una pila básica es una buena combinación simple. Si necesita más que eso, entonces su estructura de datos tiene que hacer más.

El mejor ejemplo de que necesito más de lo que he encontrado es la "continuación", la capacidad de suspender un cálculo en el medio, guardarlo como una burbuja de estado congelada y volver a dispararlo más tarde, posiblemente muchas veces. Las continuaciones se hicieron populares en el dialecto Scheme de LISP, como una forma de implementar, entre otras cosas, salidas de error. Las continuaciones requieren la capacidad de capturar el entorno de ejecución actual y reproducirlo más tarde, y una pila es algo inconveniente para eso.

La "Estructura e interpretación de los programas de computadora" de Abelson & Sussman entra en algunos detalles sobre las continuaciones.

John R. Strohm
fuente
2
Esa fue una gran visión histórica, ¡gracias! Cuando hice mi pregunta, tenía en mente las continuaciones, especialmente el estilo de paso de continuación (CPS). En ese caso, una pila no solo es inconveniente, sino que probablemente no sea necesaria: no necesita recordar dónde regresar, proporciona un punto donde continuar su ejecución. Me preguntaba si otros enfoques sin pila eran comunes, y me diste algunos muy buenos que no conocía.
Lorenzo Dematté
Ligeramente relacionado: usted señaló correctamente "si el idioma no permite la recursividad". ¿Qué pasa con el lenguaje con recursividad, en particular funciones que no son recursivas? ¿Necesitan una pila "por diseño"?
Lorenzo Dematté
"Las pilas de llamadas solo son necesarias en idiomas que permiten la recursión o recursividad mutua" - no. Si una función puede ser llamada desde más de un lugar (por ejemplo, ambos fooy barpuede llamar baz), entonces las necesidades de función para saber lo que para volver a. Si anidas esta información de "a quién regresar", entonces terminas con una pila. No importa cómo lo llame o si es compatible con el hardware de la CPU o algo que emule en el software (o incluso si es una lista vinculada de entradas asignadas estáticamente), sigue siendo una pila.
Brendan
@Brendan no necesariamente (al menos, ese es el propósito de mi pregunta). "¿A dónde regresar?" O mejor "a dónde ir después" ¿necesita ser una pila, es decir, una estructura LIFO? ¿Podría ser un árbol, un mapa, una cola o algo más?
Lorenzo Dematté
Por ejemplo, mi intuición es que CPS solo necesita un árbol, pero no estoy seguro ni sé dónde mirar. Es por eso que pregunto ...
Lorenzo Dematté
6

No es posible implementar semántica de llamadas de función sin usar algún tipo de pila. Solo es posible jugar juegos de palabras (p. Ej., Use un nombre diferente para ello, como "FILO return buffer").

Es posible usar algo que no implemente la semántica de llamadas de función (por ejemplo, estilo de paso de continuación, actores), y luego construir una semántica de llamadas de función encima; pero esto significa agregar algún tipo de estructura de datos para rastrear dónde se pasa el control cuando la función regresa, y esa estructura de datos sería un tipo de pila (o una pila con un nombre / descripción diferente).

Imagine que tiene muchas funciones que pueden llamarse entre sí. En tiempo de ejecución, cada función debe saber a dónde regresar cuando sale de la función. Si firstllama secondentonces tiene:

second returns to somewhere in first

Luego, si tiene secondllamadas third:

third returns to somewhere in second
second returns to somewhere in first

Luego, si tiene thirdllamadas fourth:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

A medida que se llama a cada función, se debe almacenar más información sobre "dónde regresar" en alguna parte.

Si una función regresa, entonces su información de "dónde regresar" se usa y ya no es necesaria. Por ejemplo, si fourthregresa a algún lugar third, la cantidad de información sobre "dónde regresar" se convertiría en:

third returns to somewhere in second
second returns to somewhere in first

Básicamente; "semántica de llamada de función" implica que:

  • debe tener información sobre "dónde regresar"
  • la cantidad de información crece a medida que se llaman funciones y se reduce cuando las funciones regresan
  • la primera parte de la información almacenada de "dónde devolver" será la última parte de la información "dónde devolver" descartada

Esto describe un búfer FILO / LIFO o una pila.

Si intenta utilizar un tipo de árbol, cada nodo del árbol nunca tendrá más de un hijo. Nota: un nodo con varios hijos solo puede suceder si una función llama a 2 o más funciones al mismo tiempo , lo que requiere algún tipo de concurrencia (por ejemplo, hilos, fork (), etc.) y no sería "semántica de llamada de función". Si cada nodo en el árbol nunca tendrá más de un hijo; entonces ese "árbol" solo se usaría como un buffer FILO / LIFO o una pila; y debido a que solo se usa como un buffer FILO / LIFO o una pila, es justo afirmar que el "árbol" es una pila (y la única diferencia son los juegos de palabras y / o los detalles de implementación).

Lo mismo se aplica a cualquier otra estructura de datos que podría usarse para implementar la "semántica de llamada de función": se usará como una pila (y la única diferencia son los juegos de palabras y / o los detalles de implementación); a menos que rompa la "semántica de llamada de función". Nota: proporcionaría ejemplos para otras estructuras de datos si pudiera, pero no puedo pensar en ninguna otra estructura que sea un poco plausible.

Por supuesto, cómo se implementa una pila es un detalle de implementación. Podría ser un área de memoria (donde realiza un seguimiento de una "parte superior de la pila actual"), podría ser algún tipo de lista vinculada (donde realiza un seguimiento de la "entrada actual en la lista"), o podría implementarse en algunos Otra manera. Tampoco importa si el hardware tiene soporte incorporado o no.

Nota: Si solo una invocación de cualquier procedimiento puede estar activa en cualquier momento; entonces puede asignar estáticamente espacio para la información de "dónde regresar". Esto sigue siendo una pila (p. Ej., Una lista vinculada de entradas asignadas estáticamente que se utiliza de forma FILO / LIFO).

También tenga en cuenta que hay algunas cosas que no siguen a la "semántica de llamada de función". Estas cosas incluyen "semánticas potencialmente muy diferentes" (por ejemplo, paso de continuación, modelo de actor); y también incluye extensiones comunes a la "semántica de llamadas de función" como concurrencia (hilos, fibras, lo que sea), setjmp/ longjmp, manejo de excepciones, etc.

Brendan
fuente
Por definición, una pila es una colección LIFO: último en entrar, primero en salir. Una cola es una colección FIFO.
John R. Strohm
Entonces, ¿es una pila la única estructura de datos aceptable? Si es así, ¿por qué?
Lorenzo Dematté
@ JohnR.Strohm: Corregido :-)
Brendan
1
Para lenguajes sin recursión (directa o mutal), es posible asignar estáticamente para cada método una variable que identificará el lugar desde el cual se llamó por última vez a ese método. Si el enlazador es consciente de tales cosas, puede asignar tales variables de una manera que no será peor que lo que haría una pila si se tomaran todas las rutas de ejecución estáticamente posibles .
supercat
4

El lenguaje concatenativo de juguete XY utiliza una cola de llamadas y una pila de datos para la ejecución.

Cada paso de cómputo simplemente implica eliminar la siguiente palabra a ejecutar y, en el caso de las funciones integradas, alimentar su función interna con la pila de datos y la cola de llamadas como argumentos, o con las definiciones de usuario, empujando las palabras que la componen al frente de la cola.

Entonces, si tenemos una función para duplicar el elemento superior:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Luego, la composición funciona +y duptiene las siguientes firmas típicas de pila / cola:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

Y paradójicamente, doublese verá así:

double [X Y] -> [X dup^+^Y]

Entonces, en cierto sentido, XY no tiene pila.

Karl Damgaard Asmussen
fuente
¡Wow gracias! Voy a mirar en que ... no estoy seguro que realmente se aplica a las llamadas de función, pero vale la pena verlo de todos modos
Lorenzo Dematte
1
@ Karl Damgaard Asmussen "empujando las palabras que lo componen al frente de la cola" "empujando al frente" ¿No es eso una pila?
@ guesttttttt222222222 no realmente. Una pila de llamadas almacena punteros de retorno, y cuando la función regresa, se abre la pila de llamadas. La cola de ejecución almacena solo punteros a funciones, y cuando ejecuta la siguiente función, se expande a su definición y se empuja al frente de la cola. En XY, la cola de ejecución es en realidad una disminución, ya que hay operaciones que también funcionan en la parte posterior de la cola de ejecución.
Karl Damgaard Asmussen