Cómo implementar las continuaciones?
https://stackoverflow.com/questions/6512
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy trabajando en un intérprete de Scheme escrito en C.En la actualidad se utiliza el tiempo de ejecución de C de la pila como su propia pila, que es la presentación de un problema menor con la implementación de las continuaciones.Mi solución actual es la copia manual de la C de la pila al montón, a continuación, copiar de nuevo cuando sea necesario.Aparte de no ser el estándar de C, esta solución es casi ideal.
¿Cuál es la forma más sencilla de implementar las continuaciones para el Esquema en C?
Solución
Recuerdo haber leído un artículo que puede ser de ayuda para usted: Cheney en el M. T. A. :-)
Algunas implementaciones de Esquema de conocimiento, tales como SISC, asignar su llamado marcos en el montón.
@ollie:Usted no necesita hacer el izamiento si todos tus llamar a los marcos están en el montón.Hay un equilibrio en el rendimiento, por supuesto:el tiempo para levantar, frente a la sobrecarga necesaria para asignar todos los fotogramas en el montón.Tal vez debería ser un ajustables en tiempo de ejecución parámetro en el intérprete.:-P
Otros consejos
Un buen resumen está disponible en Estrategias de implementación para la Primera Clase Continuaciones, un artículo de Clinger, Hartheimer, y Ost.Yo recomiendo mirar en Chez Esquema de la aplicación en particular.
La pila de la copia no es muy compleja y hay un número de bien entendido de las técnicas disponibles para mejorar el rendimiento.Utilizando asigna el montón de marcos también es bastante sencillo, pero hacer un compromiso de creación de sobrecarga para los "normales" de la situación en la que no se utiliza explícita continuaciones.
Si se puede convertir el código de entrada a continuación el estilo de pases (CPS), a continuación, usted puede conseguir lejos con la eliminación de la pila por completo.Sin embargo, mientras que el CPS es elegante añade otro paso de procesamiento en la parte delantera y requiere de una optimización adicional para superar ciertas consecuencias en el rendimiento.
Si usted está comenzando desde cero, usted realmente debe mirar en a Continuación el Estilo de pases (CPS) de la transformación.
Buenas fuentes incluyen "LISP en trozos pequeños" y Marc Feeley del Esquema en los 90 minutos de la presentación.
Parece Dybvig es la tesis de no mencionado hasta ahora.Es una delicia leer.El montón modelo basado en es el más fácil de implementar, pero la pila basada en es más eficiente.Ignorar la cadena basado en el modelo.
R.Kent Dybvig."Tres Modelos de Aplicación para el Régimen".http://www.cs.indiana.edu/~dyb/papers/3imp.pdf
También echa un vistazo a la aplicación papeles en ReadScheme.org.http://library.readscheme.org/page8.html
El resumen es el siguiente:
Esta tesis doctoral presenta tres modelos de implementación para el Plan Lenguaje de programación.La primera es un montón basado en el modelo utilizado en algunos la forma en la mayoría de los Esquema de implementaciones a la fecha;el segundo es un nuevo basado en pila de modelo que es mucho más eciente que el montón modelo basado en la ejecución de la mayoría de los programas;y la tercera es una nueva cadena-basada en el modelo previsto para el uso en un procesador múltiple la implementación del Esquema.
El montón basada en el modelo asigna varios importantes estructuras de datos en un del montón, que incluye listas de parámetros, la unión de los entornos y de la llamada marcos.
La pila basada en el modelo asigna a estas mismas estructuras en una pila siempre que sea posible.Esto se traduce en menos de la asignación del montón, menos memoria referencias, más cortas secuencias de instrucciones, menos de recolección de basura, y un uso más eciente de la memoria.
La cadena-basada en el modelo asigna versiones de estas estructuras a la derecha en el texto del programa, que se representa como una cadena de símbolos.En el cadena-basada en el modelo, el Esquema de los programas se traducen en una FFP lenguaje diseñado especícamente para sistema de apoyo.Los programas en este idioma son ejecutados directamente por la FFP de la máquina, un varios procesadores cadena de reducción de la computadora.
La pila basada en el modelo es de práctica e inmediata de benecio;es el modelo utilizado por el autor del Chez Esquema de sistema, un alto rendimiento de la implementación del Esquema.La cadena-basada en el modelo será útil para proporcionar Esquema de un alto nivel alternativa a la FFP en la FFP de la máquina una vez que la máquina se realiza.
Además de la agradable respuestas que he conseguido hasta ahora, recomiendo Andrew Appel Compilar con las Continuaciones.Está muy bien escrito y aunque no trata directamente con C, es una fuente de muy buenas ideas para el compilador de escritores.
El Pollo a la Wiki también tiene páginas que usted encontrará muy interesantes, tales como estructura interna y proceso de compilación (donde CPS se explica con un ejemplo real de compilación).
Los ejemplos que usted puede mirar son: Pollo (un Esquema de implementación, escrito en C que el apoyo continuaciones);Paul Graham En Lisp - donde se crea un CPS transformador para implementar un subconjunto de las continuaciones en Common Lisp;y Weblocks - una continuación de web basado en marco, que también implementa una forma limitada de las continuaciones en Common Lisp.
Las continuaciones no son el problema:usted puede poner en práctica esas regular con funciones de orden superior mediante CPS.El problema con los ingenuos asignación de pila es que la cola de las llamadas no son optimizados, lo que significa que usted no puede ser el esquema.
El mejor enfoque actual esquema de asignación de los espaguetis a la pila en la pila es el uso de trampolines:esencialmente extra de infraestructura para manejar la no-C-como las llamadas y salidas de los procedimientos.Ver Trampolined Estilo (ps).
Hay código ilustra estas dos ideas.
La manera tradicional es el uso de setjmp y longjmp, aunque hay que tener en cuenta.
He aquí una razonablemente buena explicación
Continuaciones, básicamente, consisten en el estado de guardado de la pila y los registros de la CPU en el momento de los cambios de contexto.A menos que usted no tenga que copiar toda la pila de la pila cuando se cambia, sólo se puede redirigir el puntero de la pila.
Las continuaciones son trivialmente implementado el uso de las fibras. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 .Las únicas cosas que necesitan cuidado de encapsulación son de paso de parámetros y valores de retorno.
En Windows fibras se realiza mediante la CreateFiber/SwitchToFiber de la familia de las llamadas.en Posix sistemas se puede hacer con makecontext/swapcontext.
boost::corutina tiene un trabajo de implementación de corrutinas para C++ que puede servir como un punto de referencia para la aplicación.
El uso explícito de la pila en su lugar.
Patrick es correcta, la única manera de que realmente se puede hacer esto es el uso explícito de la pila en su intérprete, y de elevación de la correspondiente segmento de pila en el montón cuando usted necesita para convertir a continuación.
Este es básicamente el mismo que lo que se necesita para apoyar el cierre de idiomas de apoyo (cierres y las continuaciones de ser algo relacionado).
Como soegaard ha señalado, la principal referencia sigue siendo este
La idea es, una continuación es un cierre que mantiene su evaluación de la pila de control.La pila de control es necesaria para continuar la evalution desde el momento en que la continuación fue creado mediante call/cc.
Oftenly invocando la continuación hace mucho tiempo de ejecución, y se llena la memoria con los duplicados de las pilas.Escribí este estúpido código para demostrar que, en el mit-esquema hace que el plan de choque,
El código de las sumas de 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 usted cambia de 1000 a 100 000 el código se pasan 2 segundos, y si usted crece el número de entrada que se estrelle.
