Auswertung AST (abstrakter Syntaxbaum) in Clojure

Question

Wie AST mit besserer Leistung zu bewerten? Derzeit erstellen wir AST als Baum, wo Blattknoten (Terminals) Funktionen eines Arguments sind - Karte der Schlüsselwörter und ihrer Werte. Terminals werden mit Schlüsselwörtern dargestellt, und Funktionen (Nicht-Terminals) können Benutzer (oder Clojure) definierte Funktionen sein. Vollwachstumsverfahren erzeugt Baum aus Nicht-Terminals und Terminals:

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

Beispiel erzeugt 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))) 

, die

entspricht

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

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

Wir fn schreiben kann, die direkt auswertet diese AST als:

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

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

Wir haben zwei Methoden für die Funktion der Erstellung auf Basis von AST, ein mit Hilfe der Anwendung und die Karte, und die andere mit Hilfe von comp und 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 

Mit Timing fn wir zum Ausführen von Funktionen über Testfälle messen Zeit:

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

Wie Sie in der Leistung gibt es großen Unterschied zwischen direkter Funktion (ast-fn), Baum-comp erzeugte Funktion und Baum gelten generierte Funktion zu sehen.

Gibt es einen besseren Weg?

Bearbeiten: madstap die Antwort sieht ziemlich vielversprechend aus. Ich habe einige Änderungen an seiner Lösung (Klemmen könnten auch einige andere Funktionen, nicht nur Schlüsselwort, wie konstante Funktion, die ständig Wert zurückgibt, unabhängig vom Eingangssignal):

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

nun die Schaffung ast-m (bei Verwendung von konstante c1 als Terminal) und zugehöriger ast-m-fn:

-Timing sieht sehr ähnlich aus:

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

Verwenden Sie ein Makro, um das Äquivalent von ast-fn zu schreiben.

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

Auf meinem Rechner kommt dieser nahe der perf von ast-fn. 45 msec bis 50 msec. Es tut mehr Nachschläge, aber das kann mit etwas Basteln behoben werden.

Edit: Ich dachte mehr darüber. eval Das Argument bei Makroexpansionszeit begrenzt, wie Sie das verwenden können (das Argument kann kein lokaler sein). Making full-growth ein Makro könnte besser funktionieren. Wie Amalloy sagt, dreht sich alles darum, was Sie zur Laufzeit gegen Makroexpansionszeit machen wollen.

Answer 2

Sie sind zu einem erheblichen Teil Neuimplementierung was der Compiler tun es, in einer sehr viel weniger effizienten Art und Weise, verwendet hashmaps für die variable Suche nach Namen zur Laufzeit. Normalerweise kann der Compiler die lokalen Variablen an einer bekannten Stelle im Stapel vorlistieren und sie mit einer einzigen Bytecode-Anweisung nachschlagen. Sie müssen jedoch viele Funktionen aufrufen, um herauszufinden, welche Variable für x verwendet werden soll. Ebenso durchlaufen Sie verschiedene Ebenen der dynamischen Verteilung, um herauszufinden, ob Sie * aufrufen möchten, während der Compiler normalerweise einen Literal * im Quellcode sehen und einen einfachen Aufruf an clojure.lang.Numbers/multiply ausgeben kann.

Indem Sie all diese Dinge zur Laufzeit verschieben, erlegen Sie sich eine unvermeidliche Strafe auf. Ich denke, du hast so viel wie möglich getan, um die Dinge zu beschleunigen.