[TED] Action-188, ISSUE: production rule systems have "difficulty" with recursive rules in RIF Core

Production rule systems based on the rete algorithm 
(http://en.wikipedia.org/wiki/Rete_algorithm) have a procedural 
semantics characterized by forward chaining 
(http://en.wikipedia.org/wiki/Forward_chaining).  The inference engine 
fires rules whose conditions match data ("facts") in working memory.  
The rules may add facts or otherwise modify working memory, which may 
cause additional rules to fire, etc.

The current proposal for a RIF Core is positive Horn clauses.  Such 
clauses may be recursive, meaning that the relation name in the head of 
a rule also occurs (directly or indirectly) in the body of that rule.  
Because the semantics of a set of positive Horn clauses can be defined 
without reference to an evaluation strategy, an implementation is free 
to use something other than forward chaining.  In fact, most prolog 
implementations use backward chaining.

The issue here is:  is there a general strategy to evaluate recursive 
positive Horn rules using forward chaining, so that every ruleset in RIF 
Core can be translated to production rules?  I don't really know for 
sure, but I suspect the answer is "no".  Here is a simple example to 
illustrate the problem:

Consider the 2 RIF Core rules below that define factorial (on 
non-negative integers).  We assume a built in successor function "succ" 
and multiply function "mult".

factorial(0 1)
factorial(?in ?out) :- factorial(?x ?y) & And(?in = succ(?x)  ?out = 
mult(?in ?y))

A naive translation from RIF Core to a "generic" production rule 
language might produce the following:

assert(factorial(0, 1))
IF factorial(?x, ?y)
THEN assert(factorial(?x + 1, (?x + 1) * ?y))

The problem with the naive translation is it will generate *all* 
factorial facts:
factorial(1 1)
factorial(2 2)
factorial(3 6)
factorial(4 24)
factorial(5 120)
...etc....
until memory is exhausted.  In other words, the naive translation using 
forward chaining is not "goal directed".  In contrast, a backward 
chaining implementation would start with a query such as:

:- factorial(4 ?out)

and may terminate after generating subgoals factorial(3 ?), factorial(2 
?), and factorial(1 ?).

One technique to make production rule systems more goal-directed is to 
explicitly represent subgoals as facts.  Jess and Haley (and probably 
others) PR systems even have some special syntax to make this a bit 
easier, but it is by no means hidden from the rule author. 

To illustrate the technique, we could translate the factorial rules (and 
the query) from RIF Core to our "generic" PR language as follows:

// translation of rules
assert(factorial(0, 1))
IF need_factorial(?x) and not(factorial(?x, ?)) and not(factorial(?x - 
1, ?))
THEN assert(need_factorial(?x -1))
IF need_factorial(?x) and factorial(?x - 1, ?y)
THEN assert(factorial(?x, ?x * ?y))

// translation of query
assert(need_factorial(4))
IF factorial(4, ?out) THEN print("factorial of 4 is " ?out)

The above translation has some deficiencies, however. 
- The translation doesn't work for queries like :- factorial(?in, 24)
- The need_factorial subgoals are never removed from working memory. 
- More complex rules involving mutual recursion, double recursion, etc. 
are, well, more complex...

AFAIK, a complete solution is at least a research problem.

Received on Tuesday, 12 December 2006 20:16:19 UTC