¿Es esta una forma genérica de convertir cualquier procedimiento recursivo en recursión de cola?

13

Parece que he encontrado una forma genérica de convertir cualquier procedimiento recursivo a recursión de cola:

  1. Defina un subprocedimiento auxiliar con un parámetro adicional "resultado".
  2. Aplique lo que se aplicaría al valor de retorno del procedimiento a ese parámetro.
  3. Llame a este procedimiento auxiliar para comenzar. El valor inicial para el parámetro "resultado" es el valor para el punto de salida del proceso recursivo, de modo que el proceso iterativo resultante comienza desde donde el proceso recursivo comienza a reducirse.

Por ejemplo, aquí está el procedimiento recursivo original para convertir ( ejercicio SICP 1.17 ):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Aquí está el procedimiento convertido, recursivo de cola ( ejercicio SICP 1.18 ):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

¿Alguien puede probar o refutar esto?

nalzok
fuente
1
Primer pensamiento: esto podría funcionar para todas las funciones recursivas individuales , pero me sorprendería si funcionara para funciones que realizan múltiples llamadas recursivas, ya que eso implicaría, por ejemplo, que podría implementar quicksort sin necesidad de apilar espacio. (Existente implementaciones eficientes de quicksort generalmente hacer 1 llamada recursiva en la pila, y poner la otra llamada recursiva en una cola de llamada que puede ser (manualmente o automáticamente) convertido en un bucle.)O(Iniciar sesiónnorte)
j_random_hacker
Segundo pensamiento: elegir bser una potencia de 2 muestra que inicialmente establecer product0 no es del todo correcto; pero cambiarlo a 1 no funciona cuando bes extraño. ¿Quizás necesita 2 parámetros de acumulador diferentes?
j_random_hacker
3
Realmente no ha definido una transformación de una definición recursiva que no sea de cola, agregar un parámetro de resultado y usarlo para la acumulación es bastante vago, y apenas se generaliza a casos más complejos, por ejemplo, recorridos de árbol, donde tiene dos llamadas recursivas. Sin embargo, existe una idea más precisa de "continuación", en la que realiza parte del trabajo y luego permite que asuma una función de "continuación", recibiendo como parámetro el trabajo que ha realizado hasta ahora. Se llama estilo de paso de continuación (cps), consulte en.wikipedia.org/wiki/Continuation-passing_style .
Ariel el
44
Estas diapositivas fsl.cs.illinois.edu/images/d/d5/CS422-Fall-2006-13.pdf contienen una descripción de la transformación cps, en la que toma alguna expresión arbitraria (posiblemente con definiciones de funciones con llamadas sin cola) y transformarlo en una expresión equivalente con solo llamadas de cola.
Ariel
@j_random_hacker Sí, puedo ver que mi procedimiento "convertido" de hecho es incorrecto ...
nalzok

Respuestas:

12

Su descripción de su algoritmo es realmente demasiado vaga para evaluarla en este momento. Pero, aquí hay algunas cosas a considerar.

CPS

De hecho, hay una manera de transformar cualquier código en un formulario que use solo llamadas de cola. Esta es la transformación CPS. CPS ( estilo de paso de continuación ) es una forma de expresar código pasando cada función a una continuación. Una continuación es una noción abstracta que representa "el resto de un cálculo". En el código expresado en forma CPS, la forma natural de reificar una continuación es como una función que acepta un valor. En CPS, en lugar de que una función devuelva un valor, aplica la función que representa la continuación actual al ser "devuelto" por la función.

Por ejemplo, considere la siguiente función:

(lambda (a b c d)
  (+ (- a b) (* c d)))

Esto podría expresarse en CPS de la siguiente manera:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

Es feo, y a menudo lento, pero tiene ciertas ventajas:

  • La transformación puede ser completamente automatizada. Por lo tanto, no es necesario escribir (o ver) el código en forma de CPS.
  • Combinado con thunking y trampolining , se puede usar para proporcionar optimización de cola en idiomas que no ofrecen optimización de cola. (La optimización de la llamada de cola de las funciones recursivas de cola directamente se puede lograr a través de otros medios, como convertir la llamada recursiva en un bucle. Pero la recursión indirecta no es tan trivial para convertir de esta manera).
  • Con CPS, las continuaciones se convierten en objetos de primera clase. Dado que las continuaciones son la esencia del control, esto permite que prácticamente cualquier operador de control se implemente como una biblioteca sin requerir ningún soporte especial del lenguaje. Por ejemplo, goto, excepciones y subprocesos cooperativos se pueden modelar utilizando continuaciones.

TCO

Me parece que la única razón para preocuparse por la recursividad de cola (o las llamadas de cola en general) es para fines de optimización de llamadas de cola (TCO). Por lo tanto, creo que una mejor pregunta es "¿mi código de rendimiento de transformación es optimizable por cola?".

Si consideramos una vez más CPS, una de sus características es que el código expresado en CPS consiste únicamente en llamadas de cola. Como todo es una llamada de cola, no necesitamos guardar un punto de retorno en la pila. Entonces, todo el código en forma de CPS debe ser optimizado, ¿verdad?

Bueno, no del todo. Verá, si bien puede parecer que hemos eliminado la pila, todo lo que hemos hecho es simplemente cambiar la forma en que la representamos. La pila ahora es parte del cierre que representa una continuación. Entonces, CPS no hace que todo nuestro código sea optimizado mágicamente.

Entonces, si CPS no puede hacer que todo sea TCO, ¿hay una transformación específica para la recursión directa que pueda? No, no en general. Algunas recursiones son lineales, pero otras no. Las recursiones no lineales (p. Ej., Árbol) simplemente deben mantener una cantidad variable de estado en alguna parte.

Nathan Davis
fuente
es un poco confuso cuando está en la subsección " TCO ", cuando dice "cola optimizada" en realidad quiere decir "con uso constante de memoria". Que el uso dinámico de la memoria no sea constante todavía no niega el hecho de que las llamadas son realmente de cola y no hay un crecimiento ilimitado en el uso de la pila . SICP llama a estos cálculos "iterativos", por lo que decir "aunque es TCO, todavía no lo hace iterativo" podría haber sido una mejor redacción (para mí).
Will Ness
@ WillNess Todavía tenemos una pila de llamadas, solo se representa de manera diferente. La estructura no cambia solo porque estamos usando el montón, en lugar de la pila de hardware . Después de todo, hay muchas estructuras de datos basadas en memoria dinámica de montón que tienen "pila" en su nombre.
Nathan Davis
El único punto aquí es que algunos idiomas tienen límites fijos para usar la pila de llamadas.
Will Ness