Declarative programming for Python

Declarative programming for Python - draft

by thinker

關鍵字:

在很多系統內，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 &#8743; A2 &#8743; A3 → B1 &#8744; B2
&#8660; &#172;(A1 &#8743; A2 &#8743; A3) &#8744; B1 &#8744; 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
&#172;(A1 &#8743; A2 &#8743; A3) &#8744; B1 &#8744; B2
&#8660; &#172;(A1 &#8743; A2) &#8744; B1 &#8744; 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: