clojure - 在 Clojure 中评估 AST(抽象语法树)

Question

如何评价AST性能更好？目前，我们将 AST 创建为一棵树，其中叶节点(终结点)是一个参数的函数 - 关键字及其值的映射。终端用关键字表示，函数(非终端)可以是用户(或 clojure)定义的函数。完全生长方法从非终端和终端创建树:

(defn full-growth
  "Creates individual by full growth method: root and intermediate nodes are
   randomly selected from non-terminals Ns,
   leaves at depth depth are randomly selected from terminals Ts"
  [Ns Ts arity-fn depth]
  (if (<= depth 0)
    (rand-nth Ts)
    (let [n (rand-nth Ns)]
      (cons n (repeatedly (arity-fn n) #(full-growth Ns Ts arity-fn(dec depth)))))))

生成的 AST 示例:

=> (def ast (full-growth [+ *] [:x] {+ 2, * 2} 3))
#'gpr.symb-reg/ast
=> ast
(#object[clojure.core$_STAR_ 0x6fc90beb "clojure.core$_STAR_@6fc90beb"]
 (#object[clojure.core$_STAR_ 0x6fc90beb "clojure.core$_STAR_@6fc90beb"]
  (#object[clojure.core$_STAR_ 0x6fc90beb "clojure.core$_STAR_@6fc90beb"]
   :x
   :x)
  (#object[clojure.core$_PLUS_ 0x1b00ba1a "clojure.core$_PLUS_@1b00ba1a"]
   :x
   :x))
 (#object[clojure.core$_PLUS_ 0x1b00ba1a "clojure.core$_PLUS_@1b00ba1a"]
  (#object[clojure.core$_PLUS_ 0x1b00ba1a "clojure.core$_PLUS_@1b00ba1a"]
   :x
   :x)
  (#object[clojure.core$_PLUS_ 0x1b00ba1a "clojure.core$_PLUS_@1b00ba1a"]
   :x
   :x)))

，相当于

`(~* (~* (~* ~:x ~:x) (~+ ~:x ~:x)) (~+ (~+ ~:x ~:x) (~+ ~:x ~:x)))

(def ast `(~* (~* (~* ~:x ~:x) (~+ ~:x ~:x)) (~+ (~+ ~:x ~:x) (~+ ~:x ~:x))))

我们可以编写 fn 来直接评估这个 AST:

(defn ast-fn
  [{x :x}]
  (* (* (* x x) (+ x x)) (+ (+ x x) (+ x x))))

=> (ast-fn {:x 3})
648

我们有两种基于 AST 创建函数的方法，一种是借助 apply 和 map，另一种是借助 comp 和 juxt:

(defn tree-apply
  "((+ :x :x) in) => (apply + [(:x in) (:x in))]"
  ([tree] (fn [in] (tree-apply tree in)))
  ([tree in]
    (if (sequential? tree)
    (apply (first tree) (map #(tree-apply % in) (rest tree)))
    (tree in))))
#'gpr.symb-reg/tree-apply

=> (defn tree-comp
     "(+ :x :x) => (comp (partial apply +) (juxt :x :x))"
     [tree]
     (if (sequential? tree)
       (comp (partial apply (first tree)) (apply juxt (map tree-comp (rest tree))))
       tree))
#'gpr.symb-reg/tree-comp


=> ((tree-apply ast) {:x 3})
648

=> ((tree-comp ast) {:x 3})
648

通过计时 fn，我们测量测试用例上执行函数的时间:

=> (defn timing
     [f interval]
     (let [values (into [] (map (fn[x] {:x x})) interval)]
       (time (into [] (map f) values)))
       true)

=> (timing ast-fn (range -10 10 0.0001))
"Elapsed time: 37.184583 msecs"
true

=> (timing (tree-comp ast) (range -10 10 0.0001))
"Elapsed time: 328.961435 msecs"
true

=> (timing (tree-apply ast) (range -10 10 0.0001))
"Elapsed time: 829.483138 msecs"
true

正如您所看到的，直接函数(ast-fn)、tree-comp 生成函数和 tree-apply 生成函数之间的性能存在巨大差异。

还有更好的办法吗？

编辑: madstap 的答案看起来很有希望。我对他的解决方案做了一些修改(终端也可以是其他一些函数，而不仅仅是关键字，例如无论输入如何都会不断返回值的常量函数):

(defn c [v] (fn [_] v))
(def c1 (c 1))

(defmacro full-growth-macro
     "Creates individual by full growth method: root and intermediate nodes are
      randomly selected from non-terminals Ns,
      leaves at depth depth are randomly selected from terminals Ts"
     [Ns Ts arity-fn depth]
     (let [tree (full-growth Ns Ts arity-fn depth)
           val-map (gensym)
           ast2f (fn ast2f [ast] (if (sequential? ast)
                   (list* (first ast) (map #(ast2f %1) (rest ast)))
                   (list ast val-map)))
           new-tree (ast2f tree)]
       `{:ast '~tree
         :fn (fn [~val-map] ~new-tree)}))

现在，创建 ast-m (使用常量 c1 作为终端)和关联的 ast-m-fn:

=> (def ast-m (full-growth-macro [+ *] [:x c1] {+ 2 * 2} 3))
#'gpr.symb-reg/ast-m
=> ast-m
{:fn
 #object[gpr.symb_reg$fn__20851 0x31802c12 "gpr.symb_reg$fn__20851@31802c12"],
 :ast
 (+
  (* (+ :x :x) (+ :x c1))
  (* (* c1 c1) (* :x c1)))}
=> (defn ast-m-fn
     [{x :x}]
     (+
     (* (+ x x) (+ x 1))
     (* (* 1 1) (* x 1))))
#'gpr.symb-reg/ast-m-fn

时间看起来非常相似:

=> (timing (:fn ast-m) (range -10 10 0.0001))
"Elapsed time: 58.478611 msecs"
true
=> (timing (:fn ast-m) (range -10 10 0.0001))
"Elapsed time: 53.495922 msecs"
true
=> (timing ast-m-fn (range -10 10 0.0001))
"Elapsed time: 74.412357 msecs"
true
=> (timing ast-m-fn (range -10 10 0.0001))
"Elapsed time: 59.556227 msecs"
true

Answer 1

使用宏编写 ast-fn 的等效项。

(ns foo.core
  (:require
   [clojure.walk :as walk]))

(defmacro ast-macro [tree]
  (let [val-map (gensym)
        new-tree (walk/postwalk (fn [x]
                                  (if (keyword? x)
                                    (list val-map x)
                                    x))
                                (eval tree))]
    `(fn [~val-map] ~new-tree)))

在我的机器上，这接近 ast-fn 的性能。 45 毫秒至 50 毫秒。它执行更多查找，但这可以通过一些额外的修补来修复。

编辑:我对此又想了一些。在宏扩展时eval参数将限制您如何使用它(参数不能是本地参数)。让完全增长成为一个宏可以更好地工作。就像 amalloy 所说，这完全取决于您想要在运行时与宏扩展时间做什么。

(defmacro full-growth-macro
  "Creates individual by full growth method: root and intermediate nodes are
   randomly selected from non-terminals Ns,
   leaves at depth depth are randomly selected from terminals Ts"
  [Ns Ts arity-fn depth]
  (let [tree (full-growth Ns Ts arity-fn depth)
        val-map (gensym)
        new-tree (walk/postwalk (fn [x]
                                  (if (keyword? x)
                                    (list val-map x)
                                    x))
                                tree)]
    `{:ast '~tree
      :fn (fn [~val-map] ~new-tree)}))