Come camminare un AST con la coda ricorsione in Clojure

Question

ho un AST ANTLR3 che ho bisogno di attraversare con un post-ordine, attraversamento in profondità prima che ho implementato come grosso modo la seguente Clojure:

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

Mi piacerebbe convertirlo in ricorsione in coda usando loop ... ricorrere, ma non sono stato in grado di capire come utilizzare efficacemente uno stack esplicito per fare ciò poiché ho bisogno di un traversal post-order.

Answer 1

Invece di produrre un Soluzione ricorsiva di coda che attraversa l'albero e visita ciascun nodo, è possibile produrre una sequenza lenta di lenta prima attraversamento utilizzando la funzione tree-seq e quindi ottenere il testo da ciascun oggetto nella traversal. Le sequenze pigro non fanno mai esplodere lo stack perché memorizzano tutto lo stato richiesto per produrre l'elemento successivo nella sequenza nell'heap. Sono molto spesso utilizzati invece di soluzioni ricorsive come questa dove loop e recur sono più difficili.

Non so come sia il tuo albero, anche se una risposta tipica sarebbe simile a questa. Si avrebbe bisogno di giocare con il "Con figli" "lista dei figli" funzioni

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

Se albero-ss non soddisfa le tue necessità, ci sono altri modi per produrre una sequenza pigro da un albero. Guarda la libreria zipper successiva.

Answer 2

Come accennato, l'unico modo per implementare questo utilizzando la ricorsione in coda è passare all'utilizzo di uno stack esplicito. Un possibile approccio consiste nel convertire la struttura ad albero in una struttura di stack che è essenzialmente una rappresentazione di notazione polacca inversa dell'albero (utilizzando un ciclo e una pila intermedia per ottenere ciò). Dovresti quindi usare un altro ciclo per attraversare lo stack e creare il tuo risultato.

Ecco un programma di esempio che ho scritto per realizzare questo, utilizzando il codice Java a postorder using tail recursion come ispirazione.

(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)) 

Si può chiamare come tale:

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

lascio come esercizio al lettore per convertire questo lavoro con una struttura Antlr AST;)

Answer 3

Non sono esperto del clojure, ma penso di capire quello che stai cercando.

Ecco alcuni pseudocodici. Lo stack qui nel mio pseudocodice ha l'aspetto di un oggetto stateful, ma è piuttosto possibile utilizzarne uno immutabile. Usa qualcosa come l'heap di O (profondità dell'albero * max di bambini per nodo).

walk_tree(TreeNode node) { 
    stack = new Stack<Pair<TreeNode, Boolean>>(); 
    push(Pair(node, True), stack) 
    walk_tree_aux(stack); 
} 
walk_tree_aux(Stack<Pair<TreeNode, Boolean>> stack) { -- this should be tail-recursive 
    if stack is empty, return; 
    let (topnode, topflag) = pop(stack); 
    if (topflag is true) { 
     push Pair(topnode, False) onto stack); 
     for each child of topnode, in reverse order: 
      push(Pair(child, True)) onto stack 
     walk_tree_aux(stack); 
    } else { -- topflag is false 
     process(topnode) 
     walk_tree_aux(stack); 
    } 
}