在 Clojure 中评估 AST（抽象语法树）
Evaluating AST (abstract syntax tree) in Clojure
如何评估性能更好的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))))
我们可以将直接计算这个 AST 的 fn 写成：
(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 的回答看起来很有希望。我对他的解决方案做了一些修改（终端也可以是其他一些函数，而不仅仅是关键字，比如常量函数，它不断 returns 值，无论输入如何）：
(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
您正在以一种效率低得多的方式重新实现编译器所做的相当大一部分工作，即在运行时使用哈希映射按名称查找变量。通常，编译器可以将局部变量预先解析到堆栈上的已知位置，并使用单个字节码指令查找它们，但是您强制它调用许多函数以找出要用于 x 的变量。同样，您会经历多个级别的动态分派，以便发现您想要调用 *，而编译器通常可以在源代码中看到文字 * 并发出对 clojure.lang.Numbers/multiply.
通过将所有这些东西推迟到运行时，您对自己施加了不可避免的惩罚。我认为您已经尽了最大的努力来加快速度。
使用宏写出等价于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 一个宏可以更好地工作。就像 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)}))
如何评估性能更好的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))))
我们可以将直接计算这个 AST 的 fn 写成：
(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 的回答看起来很有希望。我对他的解决方案做了一些修改（终端也可以是其他一些函数，而不仅仅是关键字，比如常量函数，它不断 returns 值，无论输入如何）：
(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
您正在以一种效率低得多的方式重新实现编译器所做的相当大一部分工作，即在运行时使用哈希映射按名称查找变量。通常，编译器可以将局部变量预先解析到堆栈上的已知位置，并使用单个字节码指令查找它们，但是您强制它调用许多函数以找出要用于 x 的变量。同样，您会经历多个级别的动态分派，以便发现您想要调用 *，而编译器通常可以在源代码中看到文字 * 并发出对 clojure.lang.Numbers/multiply.
通过将所有这些东西推迟到运行时，您对自己施加了不可避免的惩罚。我认为您已经尽了最大的努力来加快速度。
使用宏写出等价于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 一个宏可以更好地工作。就像 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)}))