Re: ISSUE-28: Recursion in the RIF Core

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:40:40 UTC