離開 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

 

參考資料

• ScottGu’s Blog - ASP.NET MVC 2: Strongly Typed Html Helpers
  
• Wikipedia – Expert System
  
• Open source projects
  • RuleEngine
    
  • NRuler
    
  • NxBRE
    
  • Drools.NET
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

NOTE:  NxBRE、Drools.NET 是從 Java port 的 .NET 版本。