RE: ISSUE-28: Recursion in the RIF Core

First, my apologies for a late posting of the recursion issue to the
Issues board.  Sponsor work has increased, and I haven't kept up to
date properly.  That said, however, I still want to record the issue
officially and clarify some aspects before stating the resolution.

Axel's generalization of the issue makes an important point IMO.  If
the RIF Core allows "degrees of freedom" that not all rule languages
can express or implement, then should those features be restricted (by
putting them out of the Core) or restrictable (e.g., by profiles)?

(Profiles is the next issue to be - finally - posted.)

If we say that the Core should not be limited by what PR language can
handle (vs. what PR implementations can handle) - Paul's point - and we
leave recursion in, then will a difficulty arise when compliance is
defined?

If we can come to a resolution by email, it isn't necessary to spend
meeting time on discussion.

Regards,
Deborah

-----Original Message-----
From: public-rif-wg-request@w3.org
[mailto:public-rif-wg-request@w3.org] On Behalf Of Paul Vincent
Sent: Tuesday, February 20, 2007 6:39 AM
To: Rule Interchange Format (RIF) Working Group WG
Subject: RE: ISSUE-28: Recursion in the RIF Core 
Importance: Low


>	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.

Gary suggested a scheme whereby it would be possible to map a recursive
PROLOG-type rule into a PR language (by effectively simulating bwd
chaining). And of course procedural extensions to PR languages can
certainly handle recursion (albeit not as "PR rules" per se). 

But saying 
"PR language implementations can handle recursion" 
...does not equal 
"PR can handle recursion" 
(for me anyway). So this makes RIF Core "PR possible" rather than "PR
friendly". Hence, I assume, the "outstanding issue" for RIF. 

But is it worth debating further? That would be my question.

[Conjecture:]
Of course, the counterargument is that without recursion, RIF Core is
"meaningless" (as a rule language or maybe as a rule representation). 

And of course, a countercounterargument is that RIF Core probably
*cannot* be a core subset covering all rule language semantics and
still
be a useful language in its own right (eg RIF Horn profile), and indeed
this should not be its goal: at best it should represent some common
expression representation scheme and/or a generalized rule metamodel
and/or rule classification scheme. 

Just my 2 eurocents...

Paul Vincent
TIBCO - ETG/Business Rules 
 
 
 -----Original Message-----
From: public-rif-wg-request@w3.org
[mailto:public-rif-wg-request@w3.org]
On Behalf Of Michael Kifer
Sent: 20 February 2007 09:51
To: axel@polleres.net
Cc: Rule Interchange Format (RIF) Working Group WG
Subject: 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 14:23:40 UTC