Re: ISSUE-28: Recursion in the RIF Core

I thought that we did sort out this issue. Namely, that recursive clauses
can be expressed by PR. I am also confused why did this issue came back.


	--michael  

> Now I am a bit confused about that, to be honest, if I think it a bit 
> further:
> 
> if we assume that RIF core should be common to ALL rules languages 
> around, would we also need to cut down other degrees of freedom which 
> Core allows: e.g. that we do not differentiate between the symbols 
> allowed for constants and function symbols, which some systems/languages 
> do, that we allow the same symbol to be used with different arities,
> which some systems don't allow.
>   Next, there are languages which e.g. restrict the allowed arity of 
> predicates and thus would neither cover all of RIF Core, e.g. SWRL
> only allows unary and binary preds in Horn rules.
> 
> Would these then also be issues?
> 
> I don't think we need to go that far. If we define the core really only 
> as "what is expressible by any implemented rules system" then we'd 
> probably end up with propositional nonrecursive horn-rules with one 
> proposition in the antecedent?
> 
> Probably I got this wrong, but it would be good if we define where to 
> draw the line, right?
> 
> just my 2 cents,
> Axel
> 
> Rule Interchange Format (RIF) Working Group Issue Tracker wrote:
> > ISSUE-28: Recursion in the RIF Core
> > 
> > http://www.w3.org/2005/rules/wg/track/issues/28
> > 
> > Raised by: Deborah Nichols
> > On product: Technical Design
> > 
> > Issue:  Recursion in the RIF Core
> > Opened by Deborah Nichols [on behalf of RIF Chairs]
> > 
> > This issue concerns whether or not to include recursion in the specification 
> > of the RIF Core.
> > 
> > Summary of an argument for exclusion:  
> > Assuming 
> > (1) that the RIF Core consists of positive Horn clauses and 
> > (2) that the RIF Core should be “common to” (i.e., translatable into) all RIF 
> > dialects, and 
> > (3) since positive Horn includes recursive formulas, 
> > then (4) if Production Rules cannot support recursion, 
> > the conclusion is (5) that would be no “compliant” PR dialect of the RIF 
> > Core.  
> > But it isn’t acceptable not to have a PR dialect of RIF; 
> > therefore, (6) recursion should be “removed” from the Core.
> > (One method of “removal” would be to use profiles; see related Issue.)
> > 
> > Background and discussion:
> > 
> > At F2F4, Gary Hallmark took an action [#188] to address the question whether 
> > recursive rules should be included in the RIF Core.  Of particular concern was 
> > the handling of recursion for Production Rule (PR) systems.  Gary presented 
> > the issue in email on 12 Dec 2006 (http://lists.w3.org/Archives/Public/public-
> > rif-wg/2006Dec/0035.html), questioning whether production-rule (PR) systems 
> > can support recursion and could implement a Core that included it.  
> > 
> > "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 ….[factorial example follows]"
> > 
> > The implication for the RIF Core, as Gary stated later in the thread, is that:
> > 
> >  "As I understand it, RIF Core should be common to *all* RIF dialects, 
> >  including a production rule dialect.  Now, it's clear that there are 
> >  aspects of production rules that probably won't translate to Core (e.g. 
> >  priority, retract).  That may be ok if we can add them to the dialect 
> >  without breaking the Core semantics.  On the other hand, it is critical 
> >  that *everything* in Core can be translated to PR, otherwise we have 
> >  dialects of Core itself, which means it really isn't a Core.  Therefore, 
> >  if Core supports recursive rules, then so should PR.   If we don't think 
> >  it’s practical to support recursive rules in PR, then we should remove 
> >  this feature from Core."
> > 
> > This issue is related to the “profiles” issue:  If RIF supports profiles, then 
> > recursion may be the most obvious feature to make “optional”.  
> > 
> > The recursion issue also has implications for defining conformance to the RIF 
> > Core.  See Dave Reynolds’ explanation 
> > (http://lists.w3.org/Archives/Public/public-rif-wg/2007Jan/0079.html):
> > 
> > "The specific issue that triggered a lot of this is the extent to which 
> > existing production rule engines can implement recursive Horn rules and 
> > so whether RIF Core should be RIF-Horn-without-recursion. Given a target 
> > query pattern (or some other context of use information) then a PR RIF 
> > translator can implement recursive horn rules but may be non-terminating 
> > for unrestricted queries. So either RIF has to convey that context of 
> > use, or the issue of ruleset termination is outside of RIF conformance, 
> > or we need some other notion of RIF Core."
> > 
> > Chris Welty summarized the discussion of the nature of the Core, from the 16 
> > Dec telcon (http://lists.w3.org/Archives/Public/public-rif-wg/2007Jan/0093): 
> > 
> > "We then went on discussing the nature of the CORE. The discussion centered
> > on whether or not all languages were required to be able to translate 
> > FROM "all" of the CORE to be conformant.  Some continue to feel this is 
> > unrealistic, however we lack examples that demonstrate it.  Several expressed 
> > support for a very limited notion of profiles for the CORE.  Profiles would 
> > specify features that we may consider "optional" or that may determine the 
> > degree of conformance of a translation.  Examples of features in a possible 
> > CORE profile were: recursion, decidability, complexity bounds, functions.
> > 
> > "There seemed to be consensus that there is one core dialect with the 
> > expressivity of about Horn and that we should move forward with the 
> > specification of that dialect, independently of other considerations.  If 
> > there is a notion of profiles it should be extremely restricted so that 
> > the "CORE is still a core".  At the moment, we do not have any 
> > specific "features" of the CORE that anyone has objected to, except possibly 
> > recursive rules, so it is still not clear that we need profiles for the CORE.
> >  
> > "We discussed whether RIF dialects must include and extend the CORE.  The 
> > possibility of profiles opens the door for some dialects to eliminate certain 
> > features (again, from a very restricted set).  In other words, profiles may 
> > allow some dialects to extend a subset of the CORE."
> > 
> > Links to related email threads concerning PR and recursion:
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0035 
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0127 contains 
> > discussion following on Gary’s factorial example.
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0202
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0047.html questions 
> > whether recursion should be included in a PR system.
> > 
> > Related threads on “recursive rules” vs. “recursive terms”:
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0114 
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Dec/0103 
> > 
> > An earlier (March 2006) discussion of recursion: 
> > http://lists.w3.org/Archives/Public/public-rif-wg/2006Mar/0106.html
> > 
> > 
> > 
> > 
> > 
> > 
> 
> 
> -- 
> Dr. Axel Polleres
> email: axel@polleres.net  url: http://www.polleres.net/
> 
> 
> 
> 
> 
>

Received on Tuesday, 20 February 2007 09:51:24 UTC