ISSUE-28: Recursion in the RIF Core

Recursion in the RIF Core

State:

CLOSED

Product:

Technical Design (multiple dialects/documents)

Raised by:

Deborah Nichols

Opened on:

2007-02-19

Description:

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

Related Actions Items:

No related actions

Related emails:

1. irc log from F2F8 (from sandro@w3.org on 2007-11-08)

Related notes:

Display change log