ISSUE-28: Recursion in the RIF Core

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

Received on Monday, 19 February 2007 22:40:25 UTC