Llama la cola en las arquitecturas sin una pila de llamadas

Question

Mi respuesta a una reciente pregunta sobre GOTOs y la recursión de cola se establece en términos de una pila de llamadas. Me preocupa que no era lo bastante general, por lo que pregunto: ¿cómo es la noción de una llamada de cola (o equivalente) útil en arquitecturas sin una pila de llamadas

?

De paso continuación, todas las llamadas funciones reemplazar la función de llamada, y son por lo tanto las llamadas de cola, por lo que "llamada de cola" no parece ser una distinción útil. En la mensajería y arquitecturas basadas en eventos, no parece ser un equivalente, aunque por favor, corríjanme si me equivoco. Las dos últimas arquitecturas son casos interesantes ya que están asociados con la programación orientada a objetos, en lugar de FP. ¿Qué pasa con otras arquitecturas? Fueron las antiguas máquinas Lisp basan en llamadas-pilas?

Edit: Según " qué diablos es: Continuación Pasando Estilo ( CPS) "(y Alex abajo), el equivalente de una llamada de cola bajo paso de continuación no es 'llamados función reemplaza la función que llama' pero 'función de llamada pasa la continuación que se le dio, en lugar de crear una nueva continuación'. Este tipo de llamada cola es útil, a diferencia de lo que he afirmado.

Además, no estoy interesado en los sistemas que utilizan pilas de llamadas en un nivel inferior, para el nivel superior no requiere una pila de llamadas. Esta restricción no se aplica a la respuesta de Alex porque él está escribiendo sobre el hecho de que otras arquitecturas de invocación ( es este el término correcto? ) a menudo tienen una pila de llamadas equivalente, no es que tienen una pila de llamadas en algún lugar bajo el capó. En el caso de paso de continuación, la estructura es como una arborescencia , pero con bordes en la dirección opuesta. equivalentes pila de llamadas son muy importantes para mis intereses.

Answer 1

En la remota posibilidad de que esta intereses pregunta que alguien que no sea yo, tengo una ampliado respuesta para la otra pregunta que también responde a éste. Aquí está el resumen, versión no riguroso.

Cuando un sistema computacional realiza sub-cómputos (es decir, un cálculo se inicia y se debe hacer una pausa mientras que otro cálculo se lleva a cabo debido a que el primero depende del resultado de la segunda), una relación de dependencia entre los puntos de ejecución surge naturalmente. En las arquitecturas basadas en la pila de llamadas, la relación es topológicamente un gráfico de ruta . En CPS, es un árbol, donde cada camino entre la raíz y un nodo es una continuación. En el paso de mensajes y roscado, es una colección de gráficos de trayectoria. manejo de eventos síncrono es básicamente el paso de mensajes. Inicio de una sub-cálculo consiste en extender la relación de dependencia, excepto en una llamada cola que sustituye a una hoja más bien que añadiendo a la misma.

La traducción de la cola de llamadas para la gestión de eventos asíncrono es más complejo, por lo que en lugar de considerar una versión más general. Si A está suscrito a un evento en el canal 1, B está suscrito al mismo evento en el canal 2 y el manipulador de B meramente desencadena el evento en el canal 1 (que traduce el caso en todos los canales), entonces A puede estar suscrito al evento en el canal 2 en lugar de la suscripción B. Esto es más general porque el equivalente de una llamada de cola requiere que

• suscripción de A en el canal 1 se cancelará cuando A está suscrito en el canal 2
• los manipuladores son auto-darse de baja (cuando se invoca, se cancelan la suscripción)

Ahora para dos sistemas que no realizan sub-cálculos: cálculo lambda (o sistemas plazo reescritura en general) y RPN. Para el cálculo lambda, cola llamadas corresponden aproximadamente a una secuencia de reducciones en donde la longitud del término es O (1) (ver procesos iterativos en sección 1.2 SICP ). Tome RPN utilizar una pila de datos y una pila de operaciones (en contraposición a una corriente de operaciones; las operaciones son aquellos aún para ser procesado), y un entorno que mapea símbolos a una secuencia de operaciones. llamadas de la cola podrían corresponder a procesos con O (1) crecimiento de la pila.

Answer 2

"Arquitecturas sin una pila de llamadas" normalmente "simular" una en algún nivel - por ejemplo, de vuelta en el momento de la IBM 360, se utilizó el S-Type Convención varillaje usando Register-ahorran áreas y los argumentos de las listas indicadas, por convención, por ciertos registros de propósito general.

Así "llamada de cola" puede todavía cuestión: ¿la necesidad función de llamada para preservar la información necesaria para reanudar la ejecución después de que el punto de llamada (una vez que la función llamada es terminada), o lo hace saber que no va a haber ninguna ejecución tras el punto de llamada, y así simplemente reutilizar de la persona que llama "información para reanudar la ejecución" en lugar?

Así, por ejemplo, una optimización de llamada de cola podría significar no anexar la continuidad necesaria para reanudar la ejecución en lo vinculado lista está siendo utilizado para el propósito ... lo que me gusta ver como una "simulación de pila de llamadas" (en algún nivel, aunque obviamente una disposición más flexible - no quiere tener continuidad de paso de los aficionados saltando por todo mi respuesta; -).