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 ;-)

So ancestor basically works, but is calculated in an inefficient manner,
whereas human-parent (or factorial, or append) never works with PR.  I
think that means the first kind of ruleset should be allowed in
PR-friendly dialects and the second kind should be disallowed.  But I
don't know how to define the difference....

      -- Sandro


> 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 Tuesday, 19 December 2006 00:06:15 UTC