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

From: Gary Hallmark <gary.hallmark@oracle.com>
Date: Tue, 12 Dec 2006 12:17:14 -0800
Message-ID: <457F0E4A.6010108@oracle.com>
To: W3C RIF WG <public-rif-wg@w3.org>
```
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

:- 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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:34 GMT