在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)、树-comp生成函数和树应用生成函数在性能上存在巨大差异。

有什么更好的办法吗？

编辑：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：

=> (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操作将限制您如何使用这个参数(参数不能是本地的)。使full-growth成为一个宏可以更好地工作。就像阿姆合金说的，这都是你想在运行时和宏扩展时间做什么的问题。

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

Answer 2

您正在以一种效率低得多的方式重新实现编译器所做的大量工作，在运行时使用哈希映射按名称进行变量查找。通常，编译器可以将局部变量预解析到堆栈中的一个已知位置，并使用单个字节码指令查找它们，但您可以强制它调用许多函数，以找出用于x的变量。同样，您需要经过几个级别的动态调度，以了解您想要调用*，而编译器通常可以在源代码中看到一个文字*并发出对clojure.lang.Numbers/multiply的简单调用。

通过将所有这些内容推迟到运行时，您会对自己施加不可避免的惩罚。我认为你已经尽了最大的努力来加快速度。