เป็นเรื่องบังเอิญ ฉันได้ทำงานกับโค้ดการจัดการ AST ใน ไลบรารี Tupelo Forest< /ก>. คุณสามารถดูโค้ดตัวอย่างที่นี่ และวิดีโอจาก Clojure/Conj ปี 2017 ที่นี่
ข้อมูลต่อไปนี้แสดงให้เห็นว่าฉันจะแก้ไขปัญหานี้อย่างไร ฉันพยายามทำให้ชื่อปรากฏชัดในตัวเองมากที่สุดเท่าที่จะเป็นไปได้ ดังนั้นจึงควรเข้าใจได้ง่ายว่าอัลกอริทึมดำเนินไปอย่างไร
พื้นฐาน:
(def op->arity {:add 2
:sub 2
:mul 2
:div 2
:pow 2})
(def op-set (set (keys op->arity)))
(defn choose-rand-op [] (rand-elem op-set))
(def arg-set #{:x :y})
(defn choose-rand-arg [] (rand-elem arg-set))
(defn num-hids [] (count (all-hids)))
ฟังก์ชั่นตัวช่วย:
(s/defn hid->empty-kids :- s/Int
[hid :- HID]
(let [op (hid->attr hid :op)
arity (grab op op->arity)
kid-slots-used (count (hid->kids hid))
result (- arity kid-slots-used)]
(verify (= 2 arity))
(verify (not (neg? result)))
result))
(s/defn node-has-empty-slot? :- s/Bool
[hid :- HID]
(pos? (hid->empty-kids hid)))
(s/defn total-empty-kids :- s/Int
[]
(reduce +
(mapv hid->empty-kids (all-hids))))
(s/defn add-op-node :- HID
[op :- s/Keyword]
(add-node {:tag :op :op op} )) ; add node w no kids
(s/defn add-leaf-node :- tsk/KeyMap
[parent-hid :- HID
arg :- s/Keyword]
(kids-append parent-hid [(add-leaf {:tag :arg :arg arg})]))
(s/defn need-more-op? :- s/Bool
[tgt-size :- s/Int]
(let [num-op (num-hids)
total-size-so-far (+ num-op (total-empty-kids))
result (< total-size-so-far tgt-size)]
result))
อัลกอริธึมหลัก:
(s/defn build-rand-ast :- tsk/Vec ; bush result
[ast-size]
(verify (<= 3 ast-size)) ; 1 op & 2 args minimum; #todo refine this
(with-debug-hid
(with-forest (new-forest)
(let [root-hid (add-op-node (choose-rand-op))] ; root of AST
; Fill in random op nodes into the tree
(while (need-more-op? ast-size)
(let [node-hid (rand-elem (all-hids))]
(when (node-has-empty-slot? node-hid)
(kids-append node-hid
[(add-op-node (choose-rand-op))]))))
; Fill in random arg nodes in empty leaf slots
(doseq [node-hid (all-hids)]
(while (node-has-empty-slot? node-hid)
(add-leaf-node node-hid (choose-rand-arg))))
(hid->bush root-hid)))))
(defn bush->form [it]
(let [head (xfirst it)
tag (grab :tag head)]
(if (= :op tag)
(list (kw->sym (grab :op head))
(bush->form (xsecond it))
(bush->form (xthird it)))
(kw->sym (grab :arg head)))))
(dotest
(let [tgt-size 13]
(dotimes [i 5]
(let [ast (build-rand-ast tgt-size)
res-str (pretty-str ast)]
(nl)
(println res-str)
(println (pretty-str (bush->form ast))) ))))
โดยจะพิมพ์ผลลัพธ์ในรูปแบบ "บุช" แบบลำดับชั้นและในรูปแบบที่กระเพื่อมเช่นกัน นี่คือผลลัพธ์ทั่วไป 2 รายการ:
[{:tag :op, :op :mul}
[{:tag :op, :op :div}
[{:tag :op, :op :pow}
[{:tag :op, :op :sub}
[{:tag :arg, :arg :y, :value nil}]
[{:tag :arg, :arg :x, :value nil}]]
[{:tag :op, :op :div}
[{:tag :arg, :arg :y, :value nil}]
[{:tag :arg, :arg :y, :value nil}]]]
[{:tag :arg, :arg :y, :value nil}]]
[{:tag :op, :op :pow}
[{:tag :arg, :arg :x, :value nil}]
[{:tag :arg, :arg :y, :value nil}]]]
(mul (div (pow (sub y x) (div y y)) y) (pow x y))
[{:tag :op, :op :div}
[{:tag :op, :op :mul}
[{:tag :op, :op :pow}
[{:tag :arg, :arg :x, :value nil}]
[{:tag :arg, :arg :y, :value nil}]]
[{:tag :op, :op :add}
[{:tag :op, :op :div}
[{:tag :arg, :arg :x, :value nil}]
[{:tag :arg, :arg :y, :value nil}]]
[{:tag :arg, :arg :x, :value nil}]]]
[{:tag :op, :op :mul}
[{:tag :arg, :arg :x, :value nil}]
[{:tag :arg, :arg :y, :value nil}]]]
(div (mul (pow x y) (add (div x y) x)) (mul x y))
ฉันใช้รหัส op ตัวอักษรสามตัวแทนสัญลักษณ์ทางคณิตศาสตร์เพื่อความง่าย แต่สามารถแทนที่ได้อย่างง่ายดายด้วยชื่อสัญลักษณ์ฟังก์ชัน Clojure สำหรับอินพุตเป็น eval
person
Alan Thompson
schedule
01.09.2018