Cómo caminar un AST con la recursión de cola en Clojure

Question

tengo un AST ANTLR3 la que tengo que atravesar el uso de un post-orden, recorrido en profundidad que he implementado como más o menos lo siguiente Clojure:

(defn walk-tree [^CommonTree node] 
    (if (zero? (.getChildCount node)) 
    (read-string (.getText node)) 
    (execute-node 
     (map-action node) 
     (map walk-tree (.getChildren node))))))) 

Me gustaría convertir esto en recursividad de cola utilizando loop ... recurre, pero no he podido averiguar cómo usar efectivamente una pila explícita para hacer esto, ya que necesito un recorrido posterior a la orden.

Answer 1

En lugar de producir una una solución recursiva de cola que atraviesa el árbol y visita cada nodo, puede generar una secuencia diferida del primer recorrido de profundidad utilizando la función tree-seq y luego obtener el texto de cada objeto en el recorrido. Las secuencias diferidas nunca explotan en la pila porque almacenan todo el estado requerido para producir el siguiente elemento de la secuencia en el montón. Se usan muy a menudo en lugar de soluciones recursivas como esta, donde loop y recur son más difíciles.

No sé cómo es tu árbol, aunque una respuesta típica sería algo como esto. Lo que se necesita para jugar con la "lista "Tiene hijos" de los niños" funciones

(map #(.getText %) ;; Has Children?  List of Children Input Tree 
    (tree-seq #(> (.getChildCount #) 0) #(.getChildren %) my-antlr-ast)) 

Si el árbol-ss no satisface sus necesidades hay otras maneras de producir una secuencia perezosa de un árbol. Mire la biblioteca de cremalleras siguiente.

Answer 2

Como mencionas, la única forma de implementar esto utilizando la recursividad final es cambiar a usar una pila explícita. Un enfoque posible es convertir la estructura de árbol en una estructura de pila que es esencialmente una representación de anotación polaca inversa del árbol (utilizando un bucle y una pila intermedia para lograr esto). Luego usarías otro ciclo para atravesar la pila y construir tu resultado.

Aquí hay un programa de ejemplo que escribí para lograr esto, usando el código de Java en postorder using tail recursion como inspiración.

(def op-map {'+ +, '- -, '* *, '/ /}) 

;; Convert the tree to a linear, postfix notation stack 
(defn build-traversal [tree] 
    (loop [stack [tree] traversal []] 
    (if (empty? stack) 
     traversal 
     (let [e (peek stack) 
      s (pop stack)] 
     (if (seq? e) 
      (recur (into s (rest e)) 
       (conj traversal {:op (first e) :count (count (rest e))})) 
      (recur s (conj traversal {:arg e}))))))) 

;; Pop the last n items off the stack, returning a vector with the remaining 
;; stack and a list of the last n items in the order they were added to 
;; the stack 
(defn pop-n [stack n] 
    (loop [i n s stack t '()] 
    (if (= i 0) 
     [s t] 
     (recur (dec i) (pop s) (conj t (peek s)))))) 

;; Evaluate the operations in a depth-first manner, using a temporary stack 
;; to hold intermediate results. 
(defn eval-traversal [traversal] 
    (loop [op-stack traversal arg-stack []] 
    (if (empty? op-stack) 
     (peek arg-stack) 
     (let [o (peek op-stack) 
      s (pop op-stack)] 
     (if-let [a (:arg o)] 
      (recur s (conj arg-stack a)) 
      (let [[args op-args] (pop-n arg-stack (:count o))] 
      (recur s (conj args (apply (op-map (:op o)) op-args))))))))) 

(defn eval-tree [tree] (-> tree build-traversal eval-traversal)) 

Se le puede llamar como tal:

user> (def t '(* (+ 1 2) (- 4 1 2) (/ 6 3))) 
#'user/t 
user> (eval-tree t) 
6 

lo dejo como ejercicio para el lector para convertir esto funcione con una estructura Antlr AST;)

Answer 3

No soy habilidoso en clojure, pero creo que entiendo lo que estás buscando.

Aquí hay un pseudocódigo. La pila aquí en mi pseudocódigo parece un objeto con estado, pero es bastante factible usar una inmutable en su lugar. Utiliza algo así como O (profundidad de árbol * máximo de hijos por nodo) montón.