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

habilitar la anulación de configuración en esta etiqueta

Question

He escrito un pequeño intérprete de Scheme en una combinación impía de C / C ++, pero todavía tengo que implementar llamadas de cola adecuadas .

Soy consciente del clásico Cheney en el algoritmo MTA , pero ¿hay otras formas agradables de implementar esto? Sé que podría poner la pila de Esquemas en el montón, pero aún así no sería una eliminación adecuada, ya que el estándar dice que uno debería admitir un número ilimitado de llamadas de cola activas.

También he jugado con longjmps, pero hasta ahora creo que solo funcionará bien para llamadas de cola no recursivas no mutuas.

¿Cómo implementan los principales esquemas basados ​​en C la recursión de cola adecuada?

Answer 1

Más simple que escribir un compilador y una máquina virtual es registrar y revisar su intérprete. Como usted tiene un intérprete y no un compilador (supongo), solo necesita un par de transformaciones sencillas para obtener el soporte adecuado para las llamadas de cola.

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

Al final, básicamente implementará una máquina virtual simple en la que, en lugar de usar las llamadas de función regulares para hacer eval, applyProc, etc., pasa los argumentos al establecer variables globales y luego pasa al siguiente argumento (o usa un top). bucle de nivel y contador de programas) ...

return applyProc(rator, rand)

se convierte en

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

Es decir, todas las funciones que normalmente se llaman recursivamente 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;
    ...
  }
}

Edición: Pasé por el mismo proceso para mi hobby intérprete de esquema, escrito en JavaScript. Aproveché muchos procedimientos anónimos, pero podría servir de referencia concreta. Mire el historial de compromiso de FoxScheme desde el 2011-03-13 ( 30707a0432563ce1632a ) hasta el 2011-03-15 ( 5dd3b521dac582507086 ).

Edición ^ 2: la recursión sin cola aún consumirá memoria, incluso si no está en la pila.

Answer 2

Si está interesado en las técnicas de implementación de intérpretes, no hay forma de evitar el libro "LiSP - Lisp in Small Pieces" de Christian Queinnec. Explica todos los aspectos de la implementación de un sistema Scheme 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 olvide revisar los documentos en ReadScheme.org.

La sección

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

Tiene bastantes trabajos sobre optimización de llamadas de cola.

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

Answer 3

Sin saber lo que tiene, diría que la forma más fácil (y más ilustrativa) de hacerlo es implementar el compilador de esquemas y la máquina virtual de los "Tres modelos de implementación para esquemas" de Dybvig.
Lo he hecho aquí en Javascript (también hay una copia del PDF de Dybvig): https://github.com/z5h/zb-lisp

verifique src / compiler.js: compileCons, y la implementación de los "códigos op" en src / vm.js