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

I disagree with this. It is easier for a Prolog programmer than a PRR  
programmer. It does not involve computing the transitive closure.
It requires the use of cut, which, although I abhor, I find  
preferable to the tedium of trying ensure than only one rule fires.  
In Go! you can do this quite elegantly:

myAncestor:[symbol,symbol]{}.
myAncestor(X,Y)::nonvar(Y) :-- parent(X,Y).
myAncestor(X,Y)::nonvar(Y) :-- parent(Z,Y), myAncestor(X,Z).

The issue with running out of memory speaks to a couple of core  
differences between PRR-based systems and LP-based systems. The most  
obvious is, of course, the forward-chaining vs backward chaining. A  
more subtle, but perhaps more significant difference is in the way  
disjunction is handled.

Prolog handles disjunction via backtracking.
PRR cannot directly handle disjunction.
CL handles disjunction via model checking (a gross simplification but  
hey, that is what I am into at times)

These differences in the procedural interpretation are quite  
important. In both of PRR and Prolog the procedural interpretation is  
an integral part of the language. Any rule interchange is going to  
have to respect that.

Frank




On Dec 18, 2006, at 12:43 PM, Gary Hallmark wrote:

>
> Sorry, I should have said "the answer is *yes*" (the PR system will  
> run out of memory before the factorial and append rules stop firing)
>
> Also, it isn't very hard (for an experience PR programmer) to make  
> the PR system generate only relevant answers for "who are *my*  
> ancestors".  It's probably harder to make a prolog system answer  
> this query without doing a full search of the transitive closure.
>
> Gary Hallmark wrote:
>
>>
>> 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 Tuesday, 19 December 2006 04:44:37 UTC