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

Actually in Jess its driven by both the naming convention of prepending 
"need-" to the name of the fact to generate the name of the subgoal 
fact, and by the "backchain-reactive" declaration that can be attached 
to an ordered or a slotted fact.  In Haley's Eclipse language, one 
indicates backward chaining by enclosing the pattern in a goal form, e.g..
(goal (factorial ?x ?y)) and must be careful to choose between not and 
unknown patterns for negation.

All the approaches I've seen (including your brain dump, if I read it 
correctly) require some kind of syntax or annotation in the rule to 
guide the use of forward vs. backward chaining.

Maybe this is an indication that RIF Core should have some kind of 
facility to annotate rules and patterns with a chaining "pragma" to 
guide the translation?

Mark Proctor wrote:

>It is fully possible to have a pattern in rete that is goal seeking.
>Jess already does this, but it's driven by naming conventions (ordered
>facts) instead of arity. I'm looking to apply predicate style patterns
>in our rule language. See the wiki for a rough brain dump:
>http://wiki.jboss.org/wiki/Wiki.jsp?page=BackwardChaining
>
>Mark
>
>-----Original Message-----
>From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]
>On Behalf Of Boley, Harold
>Sent: 12 December 2006 20:59
>To: Gary Hallmark; W3C RIF WG
>Subject: RE: [TED] Action-188, ISSUE: production rule systems have
>"difficulty" with recursive rules in RIF Core
>
>
>  
>
>>AFAIK, a complete solution is at least a research problem.
>>    
>>
>
>Related issues have been studied using "magic set" transformations:
>http://www.informatik.uni-trier.de/~ley/db/conf/pods/MumickFPR90.html
>http://www.sigmod.org/sigmod/pods/proc03/online/105-behrend.pdf
>http://www.cs.bris.ac.uk/~john/transformation.html
>http://indalog.ual.es/Xindalog/documentacion/transf_xindalog.html
>. . .
>
>-- Harold
>
>
>-----Original Message-----
>From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]
>On Behalf Of Gary Hallmark
>Sent: Tuesday, December 12, 2006 4:17 PM
>To: W3C RIF WG
>Subject: [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 23:14:51 UTC