recursion - ¿Cómo se implementa un lenguaje interpretado "sin pila"?

lisp stack

Question

Estoy creando mi propio lenguaje interpretado de tipo Lisp, y quiero hacer la optimización de llamadas de cola. Quiero liberar a mi intérprete de la pila de C para poder administrar mis propios saltos de función a función y mi propia magia de pila para lograr el TCO. (Realmente no quiero decir sin apilar, solo el hecho de que las llamadas no agregan marcos a la pila de C. Me gustaría usar una pila propia que no crezca con las llamadas de cola). Como Stackless Python, y a diferencia de Ruby o ... Python estándar, supongo.

Pero, como mi lenguaje es un derivado de Lisp, toda la evaluación de las expresiones-s actualmente se realiza recursivamente (porque es la forma más obvia en la que pensé para hacer este proceso no lineal y altamente jerárquico). Tengo una función eval, que llama a una función de Lambda :: apply cada vez que encuentra una llamada de función. La función Apply luego llama a eval para ejecutar el cuerpo de la función, y así sucesivamente. Recurrencia mutua sin cola de pila C. La única parte iterativa que uso actualmente es evaluar un cuerpo de s-expresiones secuenciales.

(defun f (x y)
    (a x y)) ; tail call! goto instead of call. 
             ; (do not grow the stack, keep return addr)

(defun a (x y)
    (+ x y))

; ...

(print (f 1 2)) ; how does the return work here? how does it know it''s supposed to
                ; return the value here to be used by print, and how does it know
                ; how to continue execution here??

Entonces, ¿cómo evito usar la recursión de C? ¿O puedo usar algún tipo de goto que salte a través de las funciones c? longjmp, tal vez? Realmente no lo sé. Por favor ten paciencia conmigo, en su mayoría soy auto- (Internet-) enseñado en programación.

Answer 1

La recursión de cola se puede considerar como una reutilización para el destinatario del mismo marco de pila que está utilizando actualmente para la persona que llama. Por lo tanto, solo puede restablecer los argumentos y pasar al principio de la función.

Answer 2

Lo que estás buscando se llama estilo de paso continuo . Este estilo agrega un elemento adicional a cada llamada de función (si lo desea, podría pensar en él como un parámetro), que designa el siguiente bit de código a ejecutar (la continuación k puede considerarse como una función que toma un solo parámetro ). Por ejemplo, puede volver a escribir su ejemplo en CPS de esta manera:

(defun f (x y k)
    (a x y k))

(defun a (x y k)
    (+ x y k))

(f 1 2 print)

La implementación de + calculará la suma de x y y , luego, pasará el resultado a k forma similar (k sum) .

Su bucle principal de intérprete entonces no necesita ser recursivo en absoluto. En un bucle, aplicará cada aplicación de función una tras otra, pasando la continuación.

Se necesita un poco de trabajo para envolver su cabeza alrededor de esto. Recomiendo algunos materiales de lectura como el excelente SICP .

Answer 3

Una solución es lo que a veces se llama "estilo trampolín". El trampolín es un bucle de nivel superior que se desplaza a pequeñas funciones que realizan un pequeño paso de cálculo antes de regresar.

Me he sentado aquí durante casi media hora tratando de crear un buen ejemplo. Desafortunadamente, tengo que hacer algo inútil y enviarte a un enlace:

http://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Section_5

El documento se llama "Esquema: un intérprete para el cálculo de Lambda extendido", y la sección 5 implementa un intérprete de esquema de trabajo en un dialecto obsoleto de Lisp. El secreto está en cómo usan el ** CLINK ** en lugar de una pila. Los otros globales se utilizan para pasar datos entre las funciones de implementación, como los registros de una CPU. Ignoraría ** QUEUE **, ** TICK **, y ** PROCESS **, ya que se ocupan de subprocesos e interrupciones falsas. ** EVLIS ** y ** UNEVLIS ** se utilizan, específicamente, para evaluar argumentos de funciones. Los argumentos sin evaluar se almacenan en ** UNEVLIS **, hasta que se evalúan y salen en ** EVLIS **.

Funciones a las que prestar atención, con algunas pequeñas notas:

MLOOP: MLOOP es el bucle principal del intérprete, o "trampolín". Ignorar ** TICK **, su único trabajo es llamar a cualquier función que esté en ** PC **. Una y otra vez.

GUARDAR: GUARDAR conserva todos los registros en el ** CLINK **, que es básicamente el mismo que cuando C guarda los registros en la pila antes de una llamada de función. El ** CLINK ** es en realidad una "continuación" para el intérprete. (Una continuación es solo el estado de un cálculo. Un marco de pila guardado también es técnicamente una continuación. Por lo tanto, algunos Lisps guardan la pila en el montón para implementar call / cc).

RESTAURAR: RESTAURAR restaura los "registros" como se guardaron en el ** CLINK **. Es similar a restaurar un marco de pila en un lenguaje basado en pila. Entonces, básicamente es "retorno", excepto que alguna función ha pegado explícitamente el valor de retorno en ** VALUE **. (** VALOR ** obviamente no está bloqueado por RESTORE). También tenga en cuenta que RESTORE no siempre tiene que regresar a una función de llamada. Algunas funciones realmente GUARDARÁN un cálculo completamente nuevo, que RESTORE alegremente "restaurará".

AEVAL: AEVAL es la función EVAL.

EVLIS: EVLIS existe para evaluar los argumentos de una función y aplicar una función a esos argumentos. Para evitar la recursión, SALVA EVLIS-1. EVLIS-1 solo sería un código antiguo regular después de la aplicación de la función si el código se escribiera de forma recursiva. Sin embargo, para evitar la recursión, y la pila, es una "continuación" separada.

Espero haber sido de alguna ayuda. Solo desearía que mi respuesta (y enlace) fuera más corta.