在Clojure中評估AST（抽象語法樹）

Question

如何評估AST具有更好的性能？ 目前我們創建AST作爲樹，其中葉節點（終端）是一個參數的函數 - 關鍵字及其值的映射。終端用關鍵字表示，功能（非終端）可以是用戶（或clojure）定義的功能。生成AST的

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

實施例：：完全生長方法從非端子和端子創建樹

=> (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，一個與應用和地圖的幫助下，和其他與幫助補償和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）之間的性能差異巨大，樹木補償產生的功能和樹申請生成的函數。

有一些更好的辦法？

編輯： 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：

時機看起來非常相似：

=> (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在macroexpansion時間的參數將限制你如何使用它（參數不能是本地的）。製作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)})) 

Answer 2

你重新實現的編譯器做相當大的一部分es以一種效率低得多的方式，在運行時使用hashmaps進行名稱變量查找。通常情況下，編譯器可以預先將當地人解析到堆棧中的已知位置，然後用單個字節碼指令查找它們，但是您可以強制它調用很多函數，以便找出用於x的變量。同樣的，你去通過動態調度的幾個層次，以找出你要調用*，而通常的編譯器可以看到在源代碼中的字面*併發出一個簡單的調用clojure.lang.Numbers/multiply。

通過推遲所有這些東西到運行時，你對自己施加一個不可避免的懲罰。我認爲你已經儘可能地加快了速度。