Как пройти AST с хвостовой рекурсией в Clojure

Вместо создания хвостового рекурсивного решения, которое обходит дерево и посещает каждый узел, вы можете создать ленивую последовательность обхода в глубину с помощью функции tree-seq, а затем получить текст из каждого объекта в обходе. . Ленивые последовательности никогда не уничтожают стек, поскольку они сохраняют все состояние, необходимое для создания следующего элемента последовательности в куче. Они очень часто используются вместо рекурсивных решений, подобных этому, где loop и recur более сложны.

Я не знаю, как выглядит ваше дерево, хотя типичный ответ будет выглядеть примерно так. Вам нужно будет поиграть с функциями «Список детей» «Имеет детей».

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

Если tree-seq не соответствует вашим потребностям, существуют другие способы создания ленивой последовательности из дерева. Посмотрите на библиотеку молнии дальше.

Как вы упомянули, единственный способ реализовать это с помощью хвостовой рекурсии — переключиться на использование явного стека. Один из возможных подходов состоит в том, чтобы преобразовать древовидную структуру в структуру стека, которая по существу является представлением дерева в обратной польской нотации (используя для этого цикл и промежуточный стек). Затем вы должны использовать другой цикл для обхода стека и создания результата.

Вот пример программы, которую я написал для этого, используя код Java по адресу postorder с использованием хвостовой рекурсии. как вдохновение.

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

Вы можете назвать это так:

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

Я оставляю читателю в качестве упражнения преобразовать это для работы со структурой Antlr AST;)

Я не разбираюсь в clojure, но думаю, что понимаю, что вы ищете.

Вот какой-то псевдокод. Стек здесь, в моем псевдокоде, выглядит как объект с состоянием, но вместо него вполне возможно использовать неизменяемый. Он использует что-то вроде кучи O (глубина дерева * максимальное количество детей на узел).

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);
    }
}