Summary

In the design of applications, rules are everywhere: business rules, game rules, routing rules, "expert systems", code and query optimizers, and rule-based "agents" and triggers. But to implement rules, they have to be converted into code -- usually in the form of decision trees that become increasingly difficult to maintain as the number of rules grows. Recent developments in computer science, however, make it possible to automatically convert rules into decision trees that are guaranteed to be correct and efficient, even for large numbers of rules, without using a specialized logic or rule language like Prolog or Lisp. This presentation will give an overview of how to implement rule-driven systems directly in Python, using Python itself as the language for specifying rules, with faster development and execution times than would be obtained by hand-coding if-then trees. Examples will be based on the predicate dispatch implementation included in the latest version of the PyProtocols package.

Part 1: The Rules We Live By

• Rules Are Everywhere
  • Regulations: No one under 17 admitted without parent or guardian
  • Business Rules: All fish meals are 20% off on Tuesdays for senior citizens, except on holidays
  • Game Rules: A chess move is illegal if the moving player's king is in check afterwards
  • Optimization Rules: A basic block with no entries to it is dead code, and can be eliminated
  • Formatting Rules: A <p> contained in a <div class="foo"> should use italic lettering
  • Real apps may have dozens or even hundreds of rules, all interacting!
• Correctness and Efficiency
  • Correctness
    • Most-specific rules normally take precedence, BUT
    • Sometimes, multiple rules contribute to the answer
      • e.g. pricing rules like "add $20 if custom size, $5 if custom color"
    • Dependent tests must occur in correct order
      • (E.g. "x<>0 and y/x>23" must be in that order)
  • Efficiency
    • Each test performed at most once (no retesting)
    • Highest-fanout tests performed first
    • Overlap tests where possible (e.g. w/lookup tables, binary search, etc.)
• Approaches for Translating Rules to Code
  • Write out all the rules, most-specific first
    • Good chance of correctness, near-zero chance of efficiency
    • Rules are centralized, readable
    • Not a bad choice, but not often used in practice
  • Merge rules into a decision tree
    • Avoids retesting partial conditions
    • Rules are centralized, but extremely hard to read
    • Modification becomes more difficult as rules are added
    • Most common approach
  • "Expert system" or "Backward-chaining Rule Engine"
    • Correct, and reasonably efficient, BUT...
    • Rarely integrated well with host language (unless host language is Prolog or Lisp!)
    • Usually requires learning additional language, and data conversion in/out of rule system
• Predicate Dispatch - A better way
  • Builds a decision tree automatically
  • Rules and actions are expressed in target language (e.g. Python)
  • Rules can be added dynamically at runtime, updating the decision tree
  • Guaranteed correct, and very efficient
    • Rule semantics do not depend on definition order
    • Intelligent use of hash tables, binary search, etc.
    • Fanout optimization and dependency detection
  • Allows decentralization of rules!
• Seminal Papers on Predicate Dispatch
  • Predicate Dispatching: A Unified Theory of Dispatch
    • http://citeseer.ist.psu.edu/ernst98predicate.html
  • Efficient Multiple and Predicate Dispatching
    • http://citeseer.ist.psu.edu/chambers99efficient.html
• PyProtocols dispatch package builds on the Chambers&Chen algorithm:
  • Adapted for Python method resolution order
  • Added support for range/equality comparisons w/combo hash+binary searches
  • Lazy build-out of decision tree (doesn't generate branches that haven't been used yet)
  • Support for arbitrary method combination, not just "most specific method"
  • Allows adding custom selection and indexing techniques

Part 2: Implementing Rules with PyProtocols' dispatch package

• aPredicate + aBody = aRule
  • [Example rule here]
  • Predicate = when does this rule apply?
    • PyProtocols uses "when()" decorators
  • Body = what to do about it
    • PyProtocols uses normal functions
• Collection of Rules = Generic Function
  • Declared with @dispatch.generic()
    • [example gf here]
  • Selects applicable rules
    • i.e., those whose predicate is true
  • Determines which rule bodies to execute
    • Usually, the one whose predicate is most specific
• Most Specific == Logical Implication
  • isinstance(x,int) implies isinstance(x,object)
    • isinstance(x,int) is more specific
  • (A and B) implies A
    • (A and B) is more specific than A
  • A>10 implies A>1
    • A>10 is more specific
  • A<1 implies A<10
    • A<1 is more specific
  • etc.
• Refuse the Temptation to Guess
  • If no rules apply, raise NoApplicableMethods
  • If two rules with identical or overlapping predicates apply, raise AmbiguousMethodError
  • Not a common issue in practice, unless accidental code duplication
  • Might be a false positive, because..
• Implication Detection isn't Perfect
  • e.g. doesn't know that 'x is None' implies 'not x'
    • (So, if one rule uses 'x is None' and one uses 'not x', they will conflict when both apply)
  • Currently knows about:
    • Class relationships
    • Comparison operators (<,>, ==, !=, etc.)
    • Logical operators (and, or, not)
• Method Combination
  • Usually, you just want most-specific rule
  • Lots of not-so-usual cases:
    • More-specific rule needs to modify return value of a less-specific rule
    • Result Combination
      • sum/min/max of rules' return values
      • first false result, first true result
    • Custom Precedence
      • Sometimes, precedence is unimportant
      • Sometimes, a special sequence is needed
      • Maybe you even want to allow ambiguity!
• The Default Method Combination
  • [source of default method combiner here]
• Custom Method Combination
  • [source code for simple "sum of results" combiner]
• Specifying Method Combination
  • [example using "sum" combiner]
• Generic Functions = Decentralized Rules = Modular Extensibility
  • Add new operations for existing types
  • Add new types to existing operations
  • Change system behaviors by importing modules with additional rules
    • Allows base system to remain the same, but still have custom behaviors for different users
• Predicate Dispatch without Generic Functions
  • dispatch.functions.Dispatcher class
  • Uses __setitem__/__getitem__
  • [examples]

Part 3: Past, Present, and Future

(Bonus material, for use if above runs short and there are no questions)

• Great Moments in Forgetfulness
• When is it safe to forget about things?
• The Evolution of Dispatch
• Other Implementations