我正在开发一个流规则引擎，我的一些客户有几百条规则，他们希望对到达系统的每个事件进行评估。这些规则是纯的(即无副作用的)布尔表达式，它们可以任意深度嵌套。
客户在运行时创建、更新和删除规则，我需要动态地检测和适应规则的填充。目前，表达式评估在内部AST上使用解释器，我还没有开始考虑codegen。
和往常一样，树中的一些谓词的评估成本比其他谓词低得多，我一直在寻找一种算法或数据结构，它可以更容易地找到便宜的谓词，并且可以有效地解释为控制整个表达式。我对这种模式的心理标题是"；AND一直到根"；，即所有祖先都是AND的任何谓词都可以被解释为控制。
尽管我花了几天时间搜索文献，阅读了关于ROBDD、CNF、DNF等的内容，但我还没能完成从行业中常见的做法到我的特定用例的循环。我发现一件似乎相关的事情是布尔表达式索引的分析和优化但我不清楚如何在不自己实现BE树数据结构的情况下应用它，因为似乎没有开源实现。
我一直半开玩笑地向我的团队提到，总有一天我们需要一个SAT求解器。我想写一个遍历树并跟踪每个祖先是and还是or的递归算法可能就足够了，但我一直得到"与"；这肯定是一个已解决的问题"；感觉。：)
编辑：在和几个朋友交谈后，我想我可能有一个解决方案的草图
- 将表达式转换为连接范式，其中，根据定义，每个节点都处于有效的短路位置
- 使用Tseitin算法来尝试避免由于CNF变换而导致的表达式大小的指数膨胀
- 对于树中的每个AND，按成本升序对其进行排序(即最便宜的左边)
- 利润^Weval照常：)
您应该认真考虑编译规则(和谓词)。对于同样的事情，解释器比机器代码慢10-50倍。如果规则集不经常更改，这是个好主意。如果规则可以动态更改，这甚至是一个好主意，因为在实践中，它们仍然不会很快更改，尽管现在您的规则编译器已经联机。呃，只是为了制作一个更大的应用程序，内存不再是什么问题了。
使用单个机器指令的布尔表达式评估甚至更好。任何复杂的布尔方程都可以在叶值上以单个机器指令的无分支序列进行编译。没有分支，没有缓存未命中；东西跑得非常快。现在，如果您有昂贵的谓词，您可能希望编译带有分支的代码，以跳过不影响表达式结果的子树，如果它们包含昂贵的谓词的话。
在合理的范围内，你可以生成任何等效的表单(我会因为使用CNF的想法而尖叫到深夜，因为它总是会在你身上爆炸)。你真正想要的是最短的布尔方程(最深的表达式树)，相当于客户端提供的，因为这需要最少的机器指令来执行。这听起来可能很疯狂，但您可能会考虑生成详尽的搜索代码，例如，尝试每一个有机会工作的组合，尤其是在等式中运算符数量相对较少的情况下。超大规模集成电路界一直在努力进行各种优化，将布尔方程合成门。您应该研究Espresso风格的布尔逻辑优化器(https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer)
可能会驱动表达式求值的一件事是谓词的成本。如果我有公式A和B，并且我知道A评估很昂贵，并且通常返回true，那么很明显，我想评估B和A。
您应该考虑通用子表达式求值，这样任何通用子语句都只计算一次。当有昂贵的谓词时，这一点尤为重要；您永远不想对同一个昂贵的谓词求值两次。
大约20年前，我在一个PLC模拟器中实现了这些技巧(这些机器基本上是评估一桶桶(比如数十万)布尔方程的机器，告诉工厂执行器何时移动)，为Rockwell Automation使用了用于AND/OR/NOT的x86机器指令。它超越了罗克韦尔的"；总理；PLC具有自定义硬件，但本质上是一个解释器。
您也可以考虑对方程进行增量求值。基本思想不是一遍又一遍地重新评估所有方程，而是只重新评估那些输入发生变化的方程。细节太长了，无法在这里包括，但我当时做的一项专利解释了如何做到这一点https://patents.google.com/patent/US5623401A/en?inventor=Ira+D+Baxter&oq=Ira+D+Baxter