Re: W3C RIF: "recursive rules" vs "recursive terms"

The naive translation of recursive rules into PR usually attempts to 
produce all possible answers (all possible facts), until it runs out of 
working memory.  In PR,  each answer is a fact is an "object" (i.e. 
takes up some memory).  So the issue is, will the PR system run out of 
memory before rules stop firing?  For the factorial and append examples, 
there are an infinite number of answers and so the answer is no.  For 
the ancestor example, it depends on the size of transitive closure vs. 
memory size.   Note that without some kind of goal seeking "tricks" 
added to the naive translation, you can't generate only relevant facts 
for queries like "who are *my* ancestors" .

Fortunately, business users seem less concerned about their ancestry 
than are academics ;-)

Sandro Hawke wrote:

>>Sandro - PR rules are not explicitly referenced at runtime (ie they may
>>be named for rule management, but not for execution). So they cannot
>>"recurse" and I cannot build logical recursive definitions using PR.
>>    
>>
>
>Can you define "ancestor" in PR?   Something like:
>
>   if parent(x,y) then ancestor(x,y).
>   if parent(x,y) and ancestor(y,z) then ancestor(x,z).
>
>That's a recursive ruleset, but it's not going to produce any infinite
>loop, right?
>
>On the other hand, saying "everyone has a parent":
>
>  if human(x) then there exists y such that parent(x,y) and human(y)
>
>will cause an infinite loop (when turning to a Production Rule creation a
>new object y for each firing).
>
>The danger, I *think* is not in creating new facts but in creating new
>"objects" (which is essentially equivalent to having function terms in
>logic), AND having recursion.  Maybe in some definable combination.  I'm
>sure there's a formal result here that I don't know or can't quite
>remember.
>
>  
>
>>My question (rhetorical at this stage is): why would I want to do =
>>recursion?
>>    
>>
>
>The ancestor example above is probably compelling, right?   You see the
>value of that kind of rule?
>
>The first program I got paid to write ($3/hr) figured out the cost of a
>product based on the costs of all its components, and the costs of those
>components based on their components, etc, recursively.  How's that for
>a use case?  :-)  
>
>  
>
>>Some problems are best defined in terms of "rules" that =
>>reference themselves (c.f "clever programming techniques" as implied in =
>>http://blogs.msdn.com/ericlippert/archive/2004/07/21/189974.aspx ). =
>>Recursion may be common in logic systems, but in PR systems (mostly =
>>implementing business rules), it is so rare I am not aware of any =
>>commercially successful PR system that provides it.
>>    
>>
>
>When you say that, you're talking about some different kind of recursion
>than I am in this message, right?   
>
>  
>
>>Note also our previous discussions on recursion -  =
>>http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0106.html=20
>>    
>>
>
>Thanks for finding that.
>
>     - Sandro
>
>  
>

Received on Monday, 18 December 2006 20:24:59 UTC