robot
最新文章(10)
Mqskit 和其它相關工具
CPython 的 GC 二、三事
寫 Mecurial Extension 是件快樂的事!
Mozilla 台灣辨公室徵人啟事
關於 Apple 的兩項專利
core dump 之前的 frame
怎麼發出 beep 聲?
先承認你要找的是奴才吧!
程式碼要清的多乾淨?
FreeBSD 的 Thread-Local Storage 實作
首頁
新編
最新留言
Entries RSS
重要關鍵字(10)
coding (122)
Python (93)
FreeBSD (71)
WEB (61)
URL (48)
hardware (46)
javascript (36)
Linux (34)
blog (30)
C++ (16)
所有關鍵字
新增 URL
Declarative programming for Python - draft
by thinker
2 Columns
關鍵字:
Python
coding
在很多系統內,declarative programming 可以提供直覺的方法,定義 rule (規則)。透過 reasoning (推論) 這些 rule,可以得到一些結果。系統再依據推論結果,決定之後的流程。 Business rules engine 就是提供這樣的功能,讓使用者透過直覺易學的 declarative programming language,一些商業上的規則,以提供系統彈性、降低系統複雜度、加快開發流程。 linkname:Drools http://drools.org/ 就是這樣的 engine,提供多種環境: 如 Java、$Python$。 本文在 $Python$ 環境下,討論 rules engine 的使用。 == 為何用 $Python$? == 一切都是為了開發方便,drools 這類的 rules engine,需另外用其它(如 xml)語法定義 rule,將使的開發過程更加複雜。常常,business rules 並不是由 user 自行定義,而是由 programmer 經過訪查 user 的意見後,由 programmer 定義。如果不能整合成程式語言的一部分,將造成 programmer 在 $coding$ 和 maintain 時的困擾。 == 解決的問題 == * linkname:[dicision problem] http://en.wikipedia.org/wiki/Decision_problem * linkname:[function problem] http://en.wikipedia.org/wiki/Function_problem == First-order logic == 我們採用 language of linkname:[First-order logic] http://en.wikipedia.org/wiki/First_order_logic 描述 rule,AI 領域常使用 FOL 描述各種的推論規則。透過 FOL,我們可以將決策問題,簡化成 search 的問題,使用電腦 search 可能或正確的解答。一個 FOL 語言包括 # formation rules (i.e. recursive definitions for forming well-formed formulas). # transformation rules (i.e. inference rules for deriving theorems). # a (possibly countably infinite) set of axioms or axiom schemata. 我們使用 $Python$ 所定義的語法和物件模型,定義一套 FOL 語言,以擴充 $Python$ 的功能。以此方式,FOL 將和 $Python$ 風格相容,而非使用字串描述另一套風格完全不相容的語言。 == 推論的困境 == Rule engine 的運作過程,是透過邏輯推論,在問題空間裡,搜索命題的結論。然而,並不是所有命題都有解答,這就是 linkname:[decidable/semideciable] http://en.wikipedia.org/wiki/Decision_problem 的問題。不確定有解答的命題,可能因為一直找不到答案,而使的系統無止盡的搜索問題空間。當問題空間是無現大時,我們永遠不知道,沒找到解答,是否是因為推論的不夠深遠,或推論的方向錯誤。因此,rule engine 只能推論在限定之步驟內能推論出來的命題。 相關連結: * linkname:[Decision problem] http://en.wikipedia.org/wiki/Decision_problem * linkname:[Function problem] http://en.wikipedia.org/wiki/Function_problem == Normal form == 所有的邏輯語句都可以 normal form (NF) 表示,將 bussiness rules 以 NF 表示,可以降低 rule engine 的複雜度。 {{{ A1 ∧ A2 ∧ A3 → B1 ∨ B2 ⇔ ¬(A1 ∧ A2 ∧ A3) ∨ B1 ∨ B2 }}} 將所有的 sentance 轉成 normal form,除了理論上的做法,還有一些細節的困難得解決。理論上的做法是將 sentance 轉成 conjunction of disjunction 或 disjunction of conjunction。一般情況,你的 sentance 會是多層而複雜的 compound expression (如下以類 lisp 語法表示): {{{ (or (or A B) (and $C$ D E) F (and (or G H) I J)) }}} 轉成 conjunction of disjunction 的演算法可簡單描素如下: {{{ def conjunction_of(sentance): if sentance is an atom: return sentance if sentance is a not_sentance: if sub_sentance_of(sentance) is atom: return sentance elif sub_sentance_of(sentance) is or_sentance or and_sentance: return conjunction_of(de_morgan(sentance)) elif sub_sentance_of(sentance) is not_sentance: return conjunction_of(sub_sentance_of(sub_sentance_of(sentance))) sub_sentances = [conjunction_of(sub) \ for sub in sentance.sub_sentances] if sentance is an or_sentance: new_sentance = distributivity(new_or_sentance_from(sub_sentances)) elif sentance is an and_sentance: new_sentance = new_and_sentance_from(sub_sentances) return new_sentance }}} 這個 algorithm 可以得到正確的結果,但是會產生多餘的 expression。例如: {{{ A & A & B }}} 一部分的 expression 是可以合併的,卻是沒有。 == 推論 == linkname:Resolution http://en.wikipedia.org/wiki/Resolution_%28logic%29 是,是Rule engine 的推論基礎。透過不斷的使用 resolution,最後得到結論。 {{{ A3 AND ¬(A1 ∧ A2 ∧ A3) ∨ B1 ∨ B2 ⇔ ¬(A1 ∧ A2) ∨ B1 ∨ B2 }}} == 結合 $Python$ == == Examples == 下面是個初步的構想,有些 operator 的優先順序的問題並沒有考慮進去。 {{{ from rule_engine import * class rules(rule_DB): is_lawyer = REL() is_big = REL() is_busy = REL() is_a_lot_of_work = REL() is_house_of = REL() some_one = VAR() a_house = VAR() props = (prop(is_lawyer(some_one) & is_house_of(a_house, some_one) >> \ is_big(a_house)), \ prop(is_big(a_house) >> is_a_lot_of_work(a_house)), \ prop(is_house_of(a_house, some_one) & \ is_a_lot_of_work(a_house) >> \ is_busy(some_one)) \ ) John = CONST() house = CONST() facts = (prop(rules.is_lawyer(John)), \ prop(rules.is_busy(John)), \ prop(rules.is_house_of(house, John)) \ ) if rules().is_true(facts): print 'yes, John is busy!' else: print 'No, John may not be busy!' }}} ....... TO BE CONTINUE
最後更新時間: 2006-07-16 15:42:38 CST |
引用
查詢:
COMMENTS: