Dynamic Languages and Java/Rule-based Systems
From JVMLanguages
| Table of contents |
Introduction
In this chapter I will introduce rule-based languages and talk about the kinds of problems that they can solve.
Terminology
Fact: A fact is a single piece of data, usually represented as a tuple or structured object, that sits within the knowledge-base. Facts are asserted, or added to the knowledge-base, during initialization of the engine, in response to changing external conditions, or during the course of rule evaluation. Facts can be retracted when they no longer apply. Some rule engines allow facts to be modified, while others require the facts remain immutible.
Rule: A rule is composed of two parts: a stimulus, or query, which is executed against the knowledge-base at each stop, and a response, or piece of code which is executed when the rule fires. Often this response will assert new facts, and possibly retract the facts which it matched. Some rule engines will allow this response to have side-effects outside of the rule engine (e.g., sending data or prompting the user), while others force all interaction to be done asynchronously via the knowledge base.
Agenda: The agenda is a list of rules that can fire in response to the currently asserted facts. It is sometimes important that rules fire in order, and generating of the agenda is generally the most computationally-intensive bit of the rule engine.
Rete Algorithm
At the core of any efficient rule engine is something known as the "Rete Algorithm." Rete, which is latin for 'rule', was the name choosen by Charles L. Forgy when he published his seminal paper "Rete: A Fast Algorithm for the Many Pattern/ Many Object Pattern Match Problem" (Artificial Intelligence 19 (1982)). This algorithm allows a dynamic set of data to be compared against a static set of rules, in a very efficient manner.
Building a Rete network
Optimization
Forward vs. Backward Chaining
There are two main types of rule evaluation. Forward chaining involves taking a fact-base and applying rules against this entire fact-base until a stable point is reached. Backwards chaining involves a specific query against a fact-base and rule set, where the relevant rules are fired iteratively to reach answer the specified query.
Example
Rule Engines
Jess
One of the original implementations of the Rete algorithm was a LISP-based system called CLIPS.
A port of CLIPS to Java was done by Sandia Laboratories called Jess. Although the definition language for Jess is still LISP-based and is fully compatible with CLIPS, it supports many features that make integration between Jess code and Java very simple.
Calling Java Methods
Shadow Facts
Extension Support
Forward vs. Backward Chaining
Jess (and its predecessor, CLIPS) are primarily designed for forward chaining. However, they do have some support for backward chaining.
Drools
Drools also uses the Rete algorithm, but relies on Java code rather than a LISP derivitive to implement its rule matching logic and its actions.
Drools also allows for the creation of domain-specific extensions.
XSLT
XSLT is not a general-purpose rule engine like Jess and Drools. Instead, it is a language designed specifically for transforming XML documents. However, at the core of XSLT is a rule-engine, where templates are matched against XML trees.
Are there any streaming XSLT implementations that use Rete? (Why not?)
TermWare
TermWare is a term rewriting framework, which can be embedded in Java application. Strategy of transformation is choosed from set of predefined strategies or can be build as Java class, implementing RewritingStrategy interface.
javax.rules API (JSR-94)
A Java Community Request, JSR-94, was created to provide a consistent API across all Java-based rule engines. Both Jess and Drools support the javax.rules API.
