3 ms·

There's a lot of interesting things you can build on top of these sorts of rules engines, like optimizations. I had to deal with a system that allowed users to

There's a lot of interesting things you can build on top of these sorts of rules engines, like optimizations. I had to deal with a system that allowed users to enter arbitrary boolean expressions and we had to use them to filter out records from a very large stream of data, and optimizing for speed was very important. Thee's the obvious changes, like flattening out deeply-nested expressions as much as possible. You can sort sub-clauses in an AndSpecification so that the ones most likely to be false are first, so that you are more likely to short-circuit and cut down on evaluation time (and you sort in the reverse order for the OrSpecification). But you can actually do some more advanced optimizations. In my case, we knew that for a given expression provided by users the overwhelming majority of records would not match. So for a given expression A we would derive a simpler formula B such that A => B (and thus not B => not A) where B was cheaper to evaluate, then we would evaluate the expression as B and A. If B was false it means A would be false anyway, so we could short-circuit and skip the more expensive test.

PaulHoule 7y ago
If you look close at that article, what they describe is not a real "rules engine" but just a set of boolean valued functions. Real business rules engines use something like https://en.wikipedia.org/wiki/Rete_algorithm https://en.wikipedia.org/wiki/Rete_algorithm Production rules systems in the 1970s (when they were in vogue for "expert systems") did not use indexes and generally had poor execution performance compared to modern "business rules" engine. Production rules are related to other logic-based methods of programming such as "logic programming" (which tends to progress backwards from a desired consequence to prove it is satisfied) or "theorem provers" that could demonstrate that a section of code satisfies certain invariants.
shoo 7y ago
Tangent re: similar idea applicable to speedup old school minimax game search > You can sort sub-clauses in an AndSpecification so that the ones most likely to be false are first, so that you are more likely to short-circuit and cut down on evaluation time (and you sort in the reverse order for the OrSpecification). Similar trick also works in context of Alpha beta pruning when minimax searching through a game tree: at each node various moves are available, getting tighter Alpha beta bounds for pruning earlier in the search gives a massive speedup, getting tighter bounds corresponds to selecting a relatively strong move to investigate first. So if you have some heuristic to guess what a good move is for the current player and use that heuristic to define the order that moves are attempted, that can give a large speedup. Unlike some other situations with heuristics (e.g. a*, where heuristic estimating distance to goal must always be a lower bound to true difference to goal in order to guarantee that the solution obtained by the search is optimal) , there's no requirement that the heuristic used to order moves during search have any guaranteed relationship to the true order -- so that frees you to use wacky empirical heuristics -- e.g. fitting a statistical machine learning model to suggest the search order based on features that can be defined and quickly evaluated at each search node. When I played around with this idea to accelerate minimax search it generated a fun little project to instrument the search with metrics to collect training data, fit a simple model to predict a strong move (i used random forest) and then make the model evaluation run really fast at predict time: the model was fitted offline before search so I could encode the fitted model -- a bunch of decision trees -- into C code (lots of gotos!) that was then included into the game search code

PaulHoule 7y ago

If you look close at that article, what they describe is not a real "rules engine" but just a set of boolean valued functions. Real business rules engines use something like https://en.wikipedia.org/wiki/Rete_algorithm https://en.wikipedia.org/wiki/Rete_algorithm Production rules systems in the 1970s (when they were in vogue for "expert systems") did not use indexes and generally had poor execution performance compared to modern "business rules" engine. Production rules are related to other logic-based methods of programming such as "logic programming" (which tends to progress backwards from a desired consequence to prove it is satisfied) or "theorem provers" that could demonstrate that a section of code satisfies certain invariants.

shoo 7y ago

Tangent re: similar idea applicable to speedup old school minimax game search > You can sort sub-clauses in an AndSpecification so that the ones most likely to be false are first, so that you are more likely to short-circuit and cut down on evaluation time (and you sort in the reverse order for the OrSpecification). Similar trick also works in context of Alpha beta pruning when minimax searching through a game tree: at each node various moves are available, getting tighter Alpha beta bounds for pruning earlier in the search gives a massive speedup, getting tighter bounds corresponds to selecting a relatively strong move to investigate first. So if you have some heuristic to guess what a good move is for the current player and use that heuristic to define the order that moves are attempted, that can give a large speedup. Unlike some other situations with heuristics (e.g. a*, where heuristic estimating distance to goal must always be a lower bound to true difference to goal in order to guarantee that the solution obtained by the search is optimal) , there's no requirement that the heuristic used to order moves during search have any guaranteed relationship to the true order -- so that frees you to use wacky empirical heuristics -- e.g. fitting a statistical machine learning model to suggest the search order based on features that can be defined and quickly evaluated at each search node. When I played around with this idea to accelerate minimax search it generated a fun little project to instrument the search with metrics to collect training data, fit a simple model to predict a strong move (i used random forest) and then make the model evaluation run really fast at predict time: the model was fitted offline before search so I could encode the fitted model -- a bunch of decision trees -- into C code (lots of gotos!) that was then included into the game search code