2010年10月1日 星期五

離開 LINQ 的 Expression Tree (一)

話說 .NET Framework 在 3.5 發布以後出現的 LINQ,真令人驚豔!這傢伙威力的強大相信大家早有體會了,而 expression tree (運算式樹) 是在 LINQ 中是非常重要的元素,其重要性看 namespace 就能知道 (System.Linq.Expressions)。

Expression tree 自此之後開始快速欺凌擴展 .NET 程式設計師的視野,應用之廣泛像是 ASP.NET MVC 2 中開始提供在強型別 View 中應用 lambda 運算式 (lambda 也是一種 expression tree) 來作為舊語法無法支援 IntelliSense、編譯時期檢查和 refactoring support 的取代品(強烈建議使用),可參考 ScottGu’s Blog - ASP.NET MVC 2: Strongly Typed Html Helpers 這篇文章,相信有經驗的你很快的可以分辨出孰優孰劣。

我自己則是應用 expression tree 在推論引擎的實作上,先提一下推論引擎。前一段時間為了實作規則庫推論引擎(專家系統的一種分支),花了一段時間研究,這種系統的特性是:一個規則庫(Rule Base 或 Knowledge Base)、工作記憶體(Working Memory)與推論引擎(Inference Engine),架構大致如下:


你可以開始試想,在規則庫中有一條規則如下,你如何實作 (必須考慮它具有異動性,例如體重大於300kg的豬滿街跑時,>=300kg 的豬就不能叫做肥豬了吧.... 沒養過豬300是隨便舉例的 XD) ? 當規則庫內含有上千條類似這樣的規則時,執行效能又會怎樣?

條件:Sex="M" And Type=”Pig” And Weight>=300
推論:是一頭公肥豬!

【註】其實 Outlook 中的管理規則及通知,也很像是一的小型的專家系統,雖然他可能不需要千上百條規則,你有試想過把這樣的特性導入到你的應用程式中嗎? ^^

為了這個推論引擎,我搜尋了許多參考而歸納了幾個不同的做法,小小作個整理。包含試作和過去做過的案子(使用不同的語言),以下方法大概都算得上有實務經驗:

  1. 解譯型 (interpretation)
    每執行一次就解譯一條規則,解譯的過程可能會出現大量的 if、switch...,沒有特殊技術,就是完全邊讀邊跑,像是直譯語言一樣,所以速度上較慢 (自己寫的話搞不好還會比常見的直譯語言更慢)。 相關可參考的開源碼實作有 RuleEngine
  2. 編譯型 (compilation)
    • 程式碼編譯 (code compilation)
      運用動態組成程式碼,如 C# code,利用 System.Runtime.CompilerServices 命名空間中的類別支援,動態編譯出類別。相關可參考的開源碼實作有 NRuler
    • 運算式樹 (expression tree)
      我們可以單獨的把 expression tree 拿出來用,它不一定得跟 LINQ 扯在一起!老實說,我注意到運算式樹的時候,大概就決定了這種作法,它在速度(編譯!)與可用性上兼而有之,真的是很難得,雖然過程中有卡關,那都是自己的不夠理解,我之後會陸續分享卡關經驗。相關開源碼實作我沒找到 (其實是因為自己太想寫了,沒認真找 XD),所以我打算陸續這些實作經驗。















下一次,我想就以上的例子提供簡單的實作,希望下一篇文很快就能跟大家見面 XD

 

參考資料

NOTE:  NxBREDrools.NET 是從 Java port 的 .NET 版本。

1 則留言:

匿名 提到...

加油,很期待你的研究成果。