¿Cuál es una buena manera de reescribir esta función no recursiva?

Question

Por alguna razón, estoy teniendo problemas para pensar en una buena forma de reescribir esta función, así que usa un espacio de pila constante. La mayoría de las discusiones en línea sobre la recurrencia de árboles hacen trampa al usar la función de Fibonacci y explotar las propiedades de ese problema en particular. ¿Alguien tiene alguna idea para este uso del "mundo real" (bueno, más del mundo real que la serie de Fibonacci) de la recursión?

Clojure es un caso interesante ya que no tiene la optimización de la cola de llamadas, sino que solo se repite la cola a través del formulario especial "recurrir". También desaconseja fuertemente el uso del estado mutable. Tiene muchas construcciones perezosas que incluyen tree-seq, pero no puedo ver cómo pueden ayudarme en este caso. ¿Alguien puede compartir algunas técnicas que han recogido de C, Scheme, Haskell u otros lenguajes de programación?

(defn flatten [x] 
    (let [type (:type x)] 
    (cond (or (= type :NIL) (= type :TEXT)) 
      x 
      (= type :CONCAT) 
      (doc-concat (flatten (:doc1 x)) 
         (flatten (:doc2 x))) 
      (= type :NEST) 
      (doc-nest (:level x) 
        (flatten (:doc x))) 
      (= type :LINE) 
      (doc-text " ") 
      (= type :UNION) 
      (recur (:doc1 x))))) 

edición: Por petición en los comentarios ...

reformulado en términos generales y usando Esquema - ¿cómo puedo volver a escribir el siguiente patrón de recurrencia por lo que no consume espacio de pila ni requiere cola- ¿Optimización de llamada de llamadas no auto?

(define (frob x) 
    (cond ((foo? x) 
     x) 
     ((bar? x) 
     (macerate (f x) (frob (g x)))) 
     ((thud? x) 
     (frobnicate (frob (g x)) 
        (frob (h x)))))) 

me eligieron nombres molestos para llevar a casa el punto de que estoy en busca de respuestas que no se basan en las propiedades algebraicas de x, maceran, zorglub, f, g, h o. Solo quiero reescribir la recursión.

ACTUALIZACIÓN:

Rich Hickey ha añadido amablemente una explícita trampoline function a Clojure.

Answer 1

Por favor, no downvote esto porque es feo. Sé que es feo. Pero es una forma de hacerlo en estilo trampolín (sin desbordamiento de pila del sistema), y sin utilizar gotos.

push x,1 on homemade stack 
while stack length > 1 
    n = pop 
    if (n==1) 
    x = pop 
    if (type(x)==NIL || type(x)==TEXT) 
     push x // this is the "return value" 
    else if (type(x)==CONCAT) 
     push 2 // say call doc-concat 
     push doc2(x), 1 // 2nd recursion 
     push doc1(x), 1 // 1st recursion 
    else if (type(x)==NEST) 
     push 3 // say call doc-nest 
     push level(x) // push level argument to doc-nest 
     push doc(x), 1 // schedule recursion 
    else if (type(x)==LINE) 
     push " " // return a blank 
    else if (type(x)==UNION) 
     push doc1(x), 1 // just recur 
    else if (n==2) 
    push doc-concat(pop, pop) // finish the CONCAT case 
    else if (n==3) 
    push doc-nest(pop, pop) // finish the NEST case 
    endif 
endwhile 
// final value is the only value on the stack 

Answer 2

El principal obstáculo para transformar fácilmente su algoritmo es que no da como resultado una secuencia de llamadas a la misma función; pero alterna entre unos pocos, cada uno operando sobre el resultado del otro.

diría que tiene tres alternativas:

1. reformular completamente el algoritmo (que es lo que los ejemplos de Fibonacci hacen).
   • combinan todas las funciones en una sola con muchos cond (feo, y tal vez no dé como resultado una recursión de cola real, incluso con una sola función).
   • gira el flujo de adentro hacia afuera: escribe una única función recursiva de cola que transforma los datos de entrada en la secuencia de operaciones que se deben realizar y luego evalúa.

Answer 3

Si aplanar hace llamar dos veces (en el: caso CONCAT) ¿Cómo puede ser convertida en un bucle? Tal vez me estoy perdiendo algo. Parece que es intrínsecamente una caminata en el árbol.

Es decir, hay maneras de hacer un árbol-paseo sin pila, pero algo tiene que ser sin límites, como si lo hace con un FIFO, o como se sugirió, con continuaciones.

Answer 4

Se puede usar la continuación de pases:

(define (frob0 x k) 
    (cond ((foo? x) 
     (k x)) 
     ((bar? x) 
     (frob0 (g x) 
      (lambda (y) 
      (k (macerate (f x) y)))) 
     ((thud? x) 
     (frob0 (g x) 
      (lambda (y) 
      (frob0 (h x) 
       (lambda (z) 
       (k (frobnicate y z)))))))) 

(define (frob x) 
    (frob0 x (lambda (y) y)) 

Esto no hará las cosas más fáciles de entender :-(

Answer 5

lo mejor que puedo llegar a es algo como esto:

(define (doaction vars action) 
    (cond ((symbol=? action 'frob) 
     (cond ((foo? (first vars)) 
       (first vars)) 
       ((bar? (first vars)) 
       (doaction (list (f (first vars)) (doaction (g x) 'frob)) 'macerate) 
etc... 

no es recursivo totalmente cola, pero probablemente lo mejor que se puede conseguir. TCO es realmente el camino a seguir. (entiendo que Clojure no puede tenerlo debido a la JVM).

Answer 6

La técnica general estándar es la conversión a trampolined style. Para su problema particular (implementando los combinadores de impresión bonita), puede encontrar útil el artículo de 1980 "Prettyprinting" de Derek Oppen (no en la web AFAIK). Presenta un algoritmo imperativo basado en la pila similar al posterior funcional de Wadler.

Answer 7

La siguiente no es una respuesta concreta a su pregunta, pero espero que sea un ejemplo útil. Reemplaza múltiples recursiones (que de otra manera requerirían una pila de llamadas ilimitada) con una pila de tareas.

(en código Haskellish):

 
data Tree = Null | Node Tree Val Tree
 

-- original, non-tail-recursive function: flatten :: Tree -> Result flatten Null = nullval flatten (Node a v b) = nodefunc (flatten a) v (flatten b)
 

-- modified, tail-recursive code: data Task = A Val Tree | B Result Val
 

eval :: Tree -> [Task] -> Result use :: Result -> [Task] -> Result
 

eval Null tasks = use nullval tasks eval (Node a v b) tasks = eval a ((A v b):tasks)
 

use aval ((A v b):tasks) = eval b ((B aval v):tasks) use bval ((B aval v):tasks) = use (nodefunc aval v bval) tasks use val [] = val
 

-- actual substitute function flatten2 :: Tree -> Result flatten2 tree = eval tree []