¿Cuáles son algunas buenas maneras de implementar la eliminación de llamadas finales?

He escrito un pequeño intérprete de Scheme en una mezcla impía de C/C++, pero todavía tengo que implementar proper tail calls.¿Cuáles son algunas buenas maneras de implementar la eliminación de llamadas finales?

Conozco el clásico Cheney on the MTA algorithm, pero ¿hay otras buenas formas de implementar esto? Sé que podría poner la pila de Scheme en el montón, pero eso aún no sería una eliminación adecuada, ya que el estándar dice que uno debe admitir un número ilimitado de llamadas de cola activas.

También he jugueteado con longjmps, pero hasta ahora creo que solo funcionará bien para recursivas no recíprocas llamadas de cola.

¿Cómo implementan los Esquemas principales basados en C la ejecución correcta de la cola?

Fuente

2011-05-14 csl

Veo que se ha formulado una pregunta muy similar: http://stackoverflow.com/questions/5986058/how-does-one-implement-a-stackless-interpreted-language – csl

Encontré que el JScheme original de Peter Norvig implementa esto muy bien con un simple trampolín. Desplácese hacia abajo hasta eval() en http://norvig.com/jscheme/Scheme.java – csl

Más simple que escribir un compilador y VM es registrar y trampolínar a su intérprete. Como tiene un intérprete y no un compilador (supongo), solo necesita un par de transformaciones sencillas para obtener el soporte adecuado para las llamadas finales.

Primero tendrá que escribir todo en el estilo de continuación de paso, lo que puede ser extraño pensar y hacer en C/C++. Dan Friedman ParentheC tutorial le guía a través de la transformación de un alto nivel, programa recursivo en una forma que es traducible a C.

Al final, se implementará esencialmente una sencilla máquina virtual, donde en lugar de utilizar la función normal llama a hacer eval, applyProc, etc., se pasa argumentos por los parámetros de variables globales y luego hacer un goto al siguiente argumento (o utilizar un bucle de nivel superior y contador de programa) ...

return applyProc(rator, rand)

convierte

reg_rator = rator 
reg_rand = rand 
reg_pc = applyProc 
return

Es decir, todas sus funciones que normalmente se llaman recíprocamente se reducen a un pseudoensamblaje en el que solo son bloques de código que no se repiten. Un bucle de nivel superior controla el programa:

for(;;) { 
    switch(reg_pc) { 
    case EVAL: 
     eval(); 
     break; 
    case APPLY_PROC: 
     applyProc(); 
     break; 
    ... 
    } 
}

Editar: que pasaron por el mismo proceso para mi hobby Esquema intérprete, escrito en JavaScript. Aproveché muchos procedimientos anónimos, pero podría ser una referencia concreta. Mira FoxScheme's commit history partir de 2011-03-13 (30707a0432563ce1632a) a través 2011-03-15 (5dd3b521dac582507086).

Editar^2: La recursividad sin cola seguirá consumiendo memoria, incluso si no está en la pila.

Fuente

2011-05-15 01:50:36 erjiang

(Editar^2) Corregí la pregunta con respecto a lo que dice el estándar, gracias. – csl

Sin saber lo que tiene, diría que la manera más fácil (y más esclarecedora) de hacerlo es implementar el compilador de esquemas y VM de "Three Implementation Models for Scheme" de Dybvig.
lo he hecho aquí en Javascript (una copia del PDF de Dybvig es allí también): https://github.com/z5h/zb-lisp

cheque src/compiler.js: compileCons, y la aplicación de los códigos "OP" src/vm.js

Fuente

2011-05-14 20:44:40 z5h

No estoy usando una VM subyacente, al menos no todavía. Tengo eprogn, eval y evlis. Pero usa la pila C, por lo que explota en bucles recursivos. Pero gracias por las recomendaciones! – csl

Si está interesado en las técnicas de implementación de intérpretes, no no hay manera de evitar el libro "LiSP - Lisp en pequeñas piezas" por Christian Queinnec. Explica todos los aspectos de la implementación de un sistema Scheme muy a fondo con el código completo . Es un libro maravilloso.

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

Pero no se olvide de revisar los documentos sobre ReadScheme.org.

La sección

Compilador Tecnología/Técnicas de implementación y optimización http://library.readscheme.org/page8.html

tiene un buen número de trabajos sobre la optimización de llamada de cola.

Entre otros, encontrará un enlace a la tesis de Dybvig (un clásico), que está muy bien escrito. Explica y motiva todo en de una manera muy clara.

Fuente

2011-05-15 10:59:43 soegaard

+1 para la recomendación LiSP, pero se dirige a cualquiera que se vaya y descargue el código del sitio de Queinnec: varios capítulos dependen en gran medida de Meroonet, un sistema de objetos similar al CLOS que se describe al final del libro. Luché durante días para que funcionase en un Esquema moderno antes de descubrir que alguien había empaquetado Meroon, un sistema de objetos relacionado para usar con Gambit. Puede adaptar el código muy fácilmente para ejecutar con Meroon en lugar de Meroonet, y funciona sin problemas en Gambit. YMMV, natch. http://www.math.purdue.edu/~lucier/software/Meroon/ – spacemanaki

Gracias por las recomendaciones de lectura. Tengo el libro de Queinnec, y he visto sus primeras soluciones eval y evlis. Supongo que también usa CPS en el capítulo posterior, que parece ser la manera de hecho de hacerlo. – csl

¿Cuáles son algunas buenas maneras de implementar la eliminación de llamadas finales?

Respuesta

Cuestiones relacionadas