Estoy buscando técnicas de implementación para lenguajes de programación, y recientemente encontré pilas de espagueti, que supuestamente son una buena opción para un modelo de estilo de paso de continuación (dado su uso, por ejemplo, en Scheme y SML / NJ ). En aras de la simplicidad, consideremos solo un proceso de subproceso único para esta pregunta.

Sin embargo, estoy un poco confundido por el diagrama en Wikipedia (también encontrado en otros lugares ). En particular, no entiendo cómo puede surgir tal situación. Solo puedo imaginar que las ramas en gris son inalcanzables y deberían ser recolectadas de basura. Por otro lado, con mi vago entendimiento de cómo implementar CPS usando pilas de espagueti, no puedo imaginar cómo podrías obtener un bucle en esa estructura. Tengo que concluir que, en lugar de un "árbol de puntero padre", en realidad es un gráfico acíclico dirigido, con tantas fuentes que no son basura como hilos, y tantos sumideros como "puntos de salida" (potenciales).

Pero mi comprensión de esta implementación es bastante vaga, así que creo que probablemente me estoy perdiendo algo. Espero que alguien pueda aclararme aquí sobre "pilas de llamadas de espagueti", con lo que me refiero a la estructura de datos utilizada en Scheme y / o SML / NJ para implementar procesos basados ​​en CPS.

1. Dada la siguiente pila de llamadas de espagueti:

   [exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                   ^
                                    `---- [frame C]
   

   Según tengo entendido, cualquier control de flujo de B desenrolla la pila saltando a un padre (A se vuelve activo, B inalcanzable ahora es basura), o reemplazando el marco activo por un subgráfico, conectado solo usando referencias mantenidas por B o referencias a los nuevos marcos. La ejecución no puede fluir al marco C, lo que debe significar que el marco C es basura.

2. En lugar de la situación anterior, creo que puede surgir la siguiente situación libre de basura:

   [exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   Por ejemplo, puedo imaginar que el cuadro Z pertenece a alguna función de decisión, que continúa con el cuadro X o el cuadro Y (cualquiera de los cuales volvería a W). Esto significa que las pilas de llamadas de espagueti no son " árboles punteros principales ".

3. Sin embargo, no puedo imaginar ninguna situación en la que se pueda construir un bucle. Tome la siguiente situación, por ejemplo:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   Sé que los enlaces recursivos son una cosa, pero dudo mucho que esto sea sensato. Si Q regresara a R, el cuadro Q se "gasta". Si R volviera a P, y P no puede simplemente volver a Q, ya que primero tendría que reinicializarse. Como tal, los bucles causarían estados inconsistentes. (A menos que, por supuesto, no comprenda mal el propósito de esta estructura de datos, y solo use los nodos como plantilla para su marco actual).

A partir de estas observaciones, tengo que concluir que una pila de llamadas de espagueti (sin basura) es en realidad un DAG. ¿Es esto correcto? ¿O estoy malinterpretando el propósito de esta estructura de datos?

Actualizaciones:

• He hojeado una copia del siguiente documento:

  EA Hauck y BA Dent. 1968. Mecanismo de apilamiento B6500 / B7500 de Burroughs. En Actas de la conferencia conjunta de computación de primavera del 30 de abril al 2 de mayo de 1968 (AFIPS '68 (Primavera)). ACM, Nueva York, NY, EE. UU., 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Este artículo parece definir el sistema de pila Suguaro. Como resultado, este sistema de pila Suguaro es una pila de llamadas tradicional que permite que varios "trabajos" recorran los marcos de una pila parcialmente compartida; no está absolutamente relacionado con las continuaciones

• El siguiente documento (y su documento complementario de 1996) aparentemente explica lo que está sucediendo en el compilador SML / NJ:

  Zhong Shao y Andrew W. Appel. 2000. Conversión de cierre eficiente y segura para el espacio. ACM Trans. Programa. Lang. Syst. 22, 1 (enero de 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Creo que debería leer este documento ( copia en el sitio web del autor ) antes de hacer cualquier otra cosa con esta pregunta. El concepto de "cierres vinculados de forma segura" es muy similar al sistema de pila Suguaro, ya que siempre es muy superficial y solo tiene la intención de compartir variables libres:

  Nuestro nuevo algoritmo de conversión de cierre utiliza cierres vinculados de forma segura (la tercera columna en la Figura 1) que contiene solo las variables realmente necesarias en la función, pero evita la copia del cierre al agrupar las variables con la misma vida útil en un registro compartible. [...] A diferencia de los cierres vinculados, el nivel de anidamiento de los cierres vinculados de forma segura nunca excede más de dos (una capa para el cierre en sí; otra para registros de diferentes tiempos de vida), por lo que aún disfrutan de un tiempo de acceso variable muy rápido.

  El documento también menciona explícitamente que no usa "ninguna pila de tiempo de ejecución":

  En cambio, tratamos todos los registros de activación como cierres para funciones de continuación y los asignamos en registros en el montón.

  Creo que entendí mal o leí mal el artículo de Wikipedia, ya que las pilas de espagueti no se usan para controlar el flujo. Sin embargo, después de una lectura cuidadosa de los documentos por parte de Appel y Shao, tal vez podría repetir la pregunta en referencia al gráfico de dependencia de los cierres en lugar de la "pila de llamadas de espagueti" (que aparentemente no es una cosa).

¿Son los Spaghetti Stacks los árboles de punteros y padres?

Sí, las pilas de espaguetis son árboles de padres e indicadores. Puede pensar que una pila de espagueti tiene la misma estructura que una colección de listas enlazadas que comparten estructura. Cuando se ve como un todo, la colección de listas forma un árbol. Pero cuando se ve individualmente, cada lista forma una pila.

Cada proceso en el sistema tendrá una de estas listas, que representa su pila de control. El encabezado de la lista es la parte superior de la pila (es decir, el marco activo). Su nextpuntero hace referencia al marco principal.

Lo que ves en el diagrama es la estructura para múltiples procesos. Se resalta la pila para el proceso "activo". Las partes del árbol que no forman parte de la pila activa están atenuadas. Estos representan pilas para otros procesos.

¿Las pilas de espagueti forman un DAG?

Dado que las pilas de Spaghetti son árboles de puntero padre, de hecho son DAG. Pero solo los DAG que también son árboles pueden ser pilas de Spaghetti. Entonces no, las pilas de espagueti no forman DAG que no sean árboles.

Su ejemplo de una función de decisión combina la estructura de una pila de control con los datos almacenados en la pila. Ciertamente, cualquier estructura podría formarse si comenzamos a considerar los datos. Pero como estructura de datos, cada nodo en una pila de espagueti tendrá exactamente un padre.