如何在Clojure中使用尾递归来运行AST

Question

我有一个ANTLR3 AST,我需要遍历一个后序,深度优先遍历,我已经实现了大致如下的Clojure:

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

我想使用循环... recur将其转换为尾递归,但我无法弄清楚如何有效地使用显式堆栈来执行此操作,因为我需要进行后序遍历.

Answer 1

不是生成遍历树并访问每个节点的尾递归解决方案,您可以使用该函数生成深度优先遍历的延迟序列,tree-seq然后从遍历中的每个对象中获取文本.延迟序列永远不会打击堆栈,因为它们存储了生成堆中序列中下一项所需的所有状态.它们经常被用来代替像这样的递归解决方案,loop而且recur更难以实现.

虽然典型的答案看起来像这样,但我不知道你的树是什么样的.你需要玩"有孩子"的"儿童名单"功能

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

如果tree-seq不适合您的需求,还有其他方法可以从树中生成延迟序列.接下来看看拉链库.

Answer 2

正如您所提到的，使用尾递归实现这一点的唯一方法是切换到使用显式堆栈。一种可能的方法是将树结构转换为堆栈结构，该结构本质上是树的逆波兰符号表示（使用循环和中间堆栈来完成此操作）。然后您将使用另一个循环来遍历堆栈并建立您的结果。

这是我编写的一个示例程序来实现这一点，使用尾递归作为灵感后序的 Java 代码。

(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 结构；)