Estoy trabajando en un intérprete de Scheme escrito en C. Actualmente usa la pila C runtime como su propia pila, que presenta un problema menor con la implementación de continuaciones. Mi solución actual es la copia manual de la pila C al montón y luego copiarla cuando sea necesario. Además de no ser estándar C, esta solución no es ideal.¿Cómo implementar las continuaciones?
¿Cuál es la forma más sencilla de implementar las continuaciones para Scheme en C?
Recuerdo haber leído un artículo que pueda ser de ayuda para usted: Cheney on the M.T.A. :-)
Algunas implementaciones del Esquema yo sepa, como SISC, asignar sus marcos de llamadas en el montón.
@ollie: No necesita realizar el levantamiento si todos sus marcos de llamada están en el montón. Por supuesto, hay una compensación en el rendimiento: el momento de izar, frente a la sobrecarga requerida para asignar todos los cuadros en el montón. Tal vez debería ser un parámetro de tiempo de ejecución sintonizable en el intérprete. :-P
Use una pila explícita en su lugar.
Patrick está en lo cierto, la única forma en que realmente puede hacer esto es usar una pila explícita en su intérprete, y alzar el segmento apropiado de la pila en el montón cuando necesite convertir a una continuación.
Esto es básicamente lo mismo que lo que se necesita para admitir cierres en idiomas que los soportan (cierres y continuaciones que están algo relacionados).
Pero, para apoyar los cierres, ¿no podrías simplemente hacer un levantamiento lambda? – apg
La forma tradicional es usar setjmp y longjmp, aunque hay advertencias.
Aquí hay una reasonably good explanation
Un buen resumen está disponible en Implementation Strategies for First-Class Continuations, un artículo de Clinger, Hartheimer y Ost. Recomiendo mirar la implementación de Chez Scheme en particular.
El copiado en pila no es tan complejo y hay una serie de técnicas bien conocidas disponibles para mejorar el rendimiento. El uso de marcos asignados en el montón también es bastante simple, pero se compensa la creación de sobrecarga para la situación "normal" en la que no se usan las continuaciones explícitas.
Si convierte el código de entrada al estilo de paso de continuación (CPS), puede salirse con la suya eliminando la pila por completo. Sin embargo, aunque CPS es elegante, agrega otro paso de procesamiento en el front end y requiere una optimización adicional para superar ciertas implicaciones de rendimiento.
Los ejemplos que puede ver son: Chicken (una implementación del Esquema, escrita en C que admite continuaciones); El On Lisp de Paul Graham, donde crea un transformador CPS para implementar un subconjunto de continuaciones en Common Lisp; y Weblocks - un marco web basado en continuación, que también implementa una forma limitada de continuación en Common Lisp.
Si está empezando desde cero, realmente debería mirar a la transformación de estilo de paso de continuación (CPS).
Buenas fuentes incluyen "LISP en piezas pequeñas" y Marc Feeley's Scheme in 90 minutes presentation.
El libro de Queinnec Lisp In Small Pieces * está * disponible (al menos en su edición francesa de Paracampus) –
Las continuas no son el problema: puede implementar aquellas con funciones regulares de orden superior utilizando CPS.El problema con la asignación de pila ingenua es que las llamadas de cola nunca se optimizan, lo que significa que no se puede planificar.
El mejor enfoque actual para la pila de spaghetti del esquema de mapeo en la pila es el uso de camas elásticas: infraestructura esencialmente extra para manejar llamadas no similares a C y salidas de procedimientos. Ver Trampolined Style (ps).
Hay some code que ilustran estas dos ideas.
Las mejoras consisten básicamente en el estado guardado de la pila y los registros de la CPU en el punto de los conmutadores de contexto. Por lo menos, no es necesario copiar toda la pila al montón cuando se cambia, solo se puede redirigir el puntero de la pila.
Las mejoras se implementan trivialmente utilizando fibras. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 . Las únicas cosas que necesitan una encapsulación cuidadosa son el paso de parámetros y los valores de retorno.
En Windows, las fibras se realizan mediante la familia de llamadas CreateFiber/SwitchToFiber. en sistemas que cumplen con Posix se puede hacer con makecontext/swapcontext.
boost :: coroutine tiene una implementación funcional de corutinas para C++ que puede servir como un punto de referencia para la implementación.
* implementado de forma trivial ... necesita una encapsulación cuidadosa * - hay una cierta cantidad de tensión en este párrafo. Esta respuesta se mejoraría con un enlace a algún código. –
Además de las buenas respuestas que tiene hasta ahora, le recomiendo el Compiling with Continuations de Andrew Appel. Está muy bien escrito y, aunque no trata directamente con C, es una fuente de ideas realmente buenas para los escritores de compiladores.
El Chicken Wiki también tiene páginas que encontrará muy interesantes, como internal structure y compilation process (donde se explica CPS con un ejemplo real de compilación).
Me gusta mucho el libro de Appel. Una ventaja es que puede consultar el código fuente del compilador SML/NJ, que es un buen ejemplo vivo del proceso que Appel describe en el libro. –
Parece que la tesis de Dybvig no se menciona hasta ahora. Es una delicia para leer. El modelo basado en el montón es el más fácil de implementar, pero el stack basado en es más eficiente. Ignora el modelo basado en cuerdas.
R. Kent Dybvig. "Tres modelos de implementación para el esquema". http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
Consulte también los documentos de implementación en ReadScheme.org. http://library.readscheme.org/page8.html
El resumen es el siguiente:
Esta tesis presenta tres modelos de implementación para el Esquema programa- ción de idioma. El primero es un modelo basado en el montón utilizado en algún formulario en la mayoría de las implementaciones de Scheme hasta la fecha; el segundo es un nuevo modelo basado en la pila que es considerablemente más eficiente que el modelo basado en el montón al ejecutar la mayoría de los programas; y el tercero es un nuevo modelo basado en cadenas destinado a ser utilizado en una implementación de múltiples procesadores de Scheme.
El modelo basado en el montón asigna varias estructuras de datos importantes en un montón de , incluidas listas de parámetros reales, entornos de enlace y marcos de llamada .
El modelo basado en la pila asigna estas mismas estructuras en una pila siempre que sea posible.Esto da como resultado una menor asignación de almacenamiento dinámico, menos referencias de memoria , secuencias de instrucciones más cortas, menos recolección de basura, y un uso más eficiente de la memoria.
El modelo basado en cadenas asigna versiones de estas estructuras directamente en el texto del programa, que se representa como una cadena de símbolos. En el modelo basado en cadenas, los programas Scheme se traducen a un lenguaje FFP diseñado específicamente para admitir Scheme. Los programas en este lenguaje son ejecutados directamente por la máquina FFP, una computadora de reducción de secuencia de múltiples procesadores .
El modelo basado en pila es de benet práctico inmediato; es el modelo utilizado por el sistema Chez Scheme del autor, una implementación de alto rendimiento del Esquema. El modelo basado en cadenas será útil para proporcionando Scheme como una alternativa de alto nivel a FFP en la máquina de FFP una vez que la máquina se haya realizado.
Como soegaard señaló, la referencia principal sigue siendo this one
La idea es, una continuación es un cierre que mantiene su pila de control de evaluación. La pila de control es necesaria para continuar la evaluación desde el momento en que se creó la continuación usando call/cc.
A menudo invocar la continuación hace que el tiempo de ejecución sea largo y rellena la memoria con pilas duplicadas. Escribí este código estúpido para demostrar que, en mit-scheme, hace que el esquema falle,
El código suma los primeros 1000 números 1+2+3+...+1000.
(call-with-current-continuation
(lambda (break)
((lambda (s) (s s 1000 break))
(lambda (s n cc)
(if (= 0 n)
(cc 0)
(+ n
;; non-tail-recursive,
;; the stack grows at each recursive call
(call-with-current-continuation
(lambda (__)
(s s (- n 1) __)))))))))
Si cambia de 1000 hasta los 100 000 del código gastará 2 segundos, y si crece el número de entrada que se colgará.
-1: ¿Una pila explícita es qué? ¿Una estructura de datos asignada en el montón que modela una pila? ¿Una estructura de datos asignada en el montón que modela el historial de usos de la pila? Relevancia para la pregunta? –