W3C home > Mailing lists > Public > public-rif-wg@w3.org > May 2006

[RIF] Evaluation of RIRAF for IRL and LIFE

From: Hassan At-Kaci <hak@ilog.com>
Date: Mon, 15 May 2006 19:06:10 -0700
Message-ID: <44693392.8040808@ilog.com>
To: public-rif-wg@w3.org

http:/www.w3.org/2005/rules/wg/track/actions/16
http:/www.w3.org/2006/05/09-rif-minutes.html

This is done in fulfillment by Hassan Ait-Kaci of an evaluation of the
current rule system classification framefork proposed by HarodBoley -
see RuleSystem_Arrangement_Framework (a.k.a., RIFRAF) - taken informally
during the 2006-02-21 weekly RIF conf-call meeting, and renewed as a
formal action during the meeting of May 9, 2006.

A good way to assess whether a proposed classification ontology is
adequate (i.e., whether it provides a well-defined an complete set of
identifying discriminators) is to attempt classifying some concrete
candidate language. Thus, my evaluation of the proposed classification
scheme was to take the standpoint of a rule language designer and/or
implementor that would like to classify their own rule language using a
W3C RIF to make the language implementations RIF-compliant.

So I tried to classify two candidate rule systems into this proposed
classification framework; namely:

    (1) IRL (ILOG Rule Language), ILOG's Business Rule Language, an
        industrial production rule system in the OPS5-family of
        languages;

    (2) LIFE (Logic, Inheritance, Function, Equations), an academic
        Constraint Logic Programming language that enhances Prolog with
        so-called "frames" (i.e., attributed objects), inheritance,
        and interpreted functions.

I chose these two languages as candidates because:

    * they are representatives of two very different rule-based languages
      lying at opposite positions on the rule language spectrum;

    * they are actual systems (IRL underlies all the JRules releases, and
      LIFE is implemented as the WildLife 1.02 system);

    * one is an academic research system and the other is a commercial
      product;

    * each offers a rich set of particular extensions from the bare
      canonical representative of their class of languages;

and...

    * I know them rather well.

The protocol I have followed is to copy Harold's original rule system
classification ontology for each system being classified (i.e., LIFE and
IRL). Then, the classification procedure consists in commenting how each
specific discriminator is, or not, appropriate to identify relevant
features of the system being classified. This is done as far as the
RIFRAF entries make sense to me. When they don't, I show that with
"???".

In the sequel, by LIFE, I will mean either the language implemented by
the WildLife 1.02 interpreter, or possible variations and extensions
thereof supporting variations and extensions of the basic OSF constraint
formalism on which it is based. In examples, I will use the concrete
syntax of the WildLife system - which is mostly compatible with
Edinburgh Prolog syntax.

In what follows, what's in all caps is the original RIFRAF descriptions.
The rest are my entries.

In my opinion, although it offers a workable potential, the proposed
RIFRAF ontology, as stands now, is far from being either accurate or
complete. It suffers from using preconceived notions that do not
necessarily fit all rule-based languages (e.g., it assumes that rules
use functional Herbrand terms to represents objects - for a language
like IRL, this make no sense -, there is no mention of such things as
negation, nor of collections or aggregates, etc., ...).

Be that as it may, I think that with some work, it could be refined,
amended, and completed.

-hak

------------------------------------------------------------------------------

CLASSIFYING LIFE AND IRL AS RULE SYSTEMS

===== SYN: SYNTACTIC DISCRIMINATORS =====

SYN.1. RESTRICTED VS. UNRESTRICTED USE OF LOGIC VARIABLES

   SYN.1.1. SINGLE OCCURRENCE VS. MULTIPLE OCCURRENCE (IMPLICIT VARIABLE
      EQUALITY)

      [IRL]

      IRL uses three sorts of variables: (1) object handles; (2) local
      names; and, (3) global names - (1) and (2) have scope limited to a
      rule; (3) are visible by the whole ruleset.  Only object handles
      are bound by pattern matching and may not occur multiply in a
      rule's pattern, but can occur multiply in a rule's condition and
      body. All three kinds of variables can be destructively assigned to
      in a rule's body.

      For example, the IRL rule "raise-rate" below states that if an
      account has an interest rate greater than 1% but less than 2%, then
      that account's interest rate is raised to 2%.

      rule raise_rate {
        when {
	 ?a: Account(?r: rate; ?r > 1; ?r < 2);
        } then {
	 modify (?a) { ?r = 2; }
        }
      }

      In this rule the pattern to match is "?a: Account(?r: rate)". The
      variables ?a and ?r are object handles that get bound by pattern
      matching. The rule's condition (a Boolean expression evaluated
      after matching has bound its handles) is "?r > 1; ?r < 2", and the
      rule's body is "modify (?a) { ?r = 2; }". In both the condition and
      body Java-like global variables and local variables may also be
      used as they are in Java.

      Object handles may be viewed as logical variables, but only insofar
      as they are used as such for object pattern matching, the operation
      that binds them to their values. In conditions and actions, these
      handles behave like ordinary programming language variables (i.e.,
      for JRules, like Java variables).

      [LIFE]

      LIFE uses logical variables (LVs) as in Prolog, but are typed (or
      more exactly have sorts - types or values). An unsorted occurrence
      is implicitly sorted with the most general sort \top (written "@")
      - this generalized the notion of "unbound" in Prolog.  LIFE LV's
      are used a object tags. They may appear multiply (even with
      different sorts - the final sort being the intersection). The scope
      of a variable is that of the clause it appears in.

      "Binding" a variable in LIFE amounts to unifying or matching the
      object it tags with another one (namely, a function or predicate
      formal argument).

      LIFE also supports global variables (GVs). GVs have the scope of a
      module.

      LIFE supports non-monotonic variable assignment for both LVs and
      GVs in the form of a backtrackable destructive assigment.

      Finally, LIFE has a notion of global persistent variables that may
      be modified by non-backtrackable assigment. These have the scope of
      a module.

   SYN.1.2. RANGE-RESTRICTED RULES (NO HEAD-ONLY VARIABLES)
      VS. NON-RANGE-RESTRICTED RULES

      [IRL]

      In IRL, the range of variables are specified as types. Types of IRL
      are the same as in Java.

      [LIFE]

      In LIFE the range of variables are specified as sorts (types or
      values). For example, to express that "john likes all humans",
      in Prolog, one may write:

      likes(john,X) :- human(X).

      This would also work in LIFE; however, a more natural way is to
      write:

      likes(john,human).

      where "human" is a type in a taxonomy of classes including all
      human objects. Note that no variable is needed (single occurrences
      variables are redundant and can be erased).

   SYN.1.3. (FURTHER RESTRICTIONS FROM STATIC ANALYSIS RESEARCH)

      [Not sure I understand this criterion -hak]

SYN.2. PREDICATE VARIABLES PERMITTED VS. NOT PERMITTED

     * SECOND-ORDER SYNTACTIC SUGAR ALLOWING VARIABLES IN PREDICATE
       POSITIONS OF QUERIES OR RULE BODIES AND POSSIBLY RULE HEADS
       (FURTHER GENERALIZED TO FUNCTION AND EVEN ATOM POSITIONS IN
       [HTTP://WWW.W3.ORG/SUBMISSION/SWSF-SWSL/#SWSL-RULES-HILOG])

       [IRL]

       In IRL, rules do not denote predicates nor functions. They have
       names but these names are for documentation purposes and not used
       to "call" rules. Rules are activated ("fire") by data-driven
       pattern matching. Hence, rules are not bindable to variables.
       Java-style reflection is used whenever rules are used as objects.

       [LIFE]

       LIFE has both relational rules (Horn clauses over objects) and
       functional rules (rewrite rules on objects).

       Functions are fully higher-order (not only 2nd, but any order).

       Predicates are first-order. However, everything in LIFE is an
       object, including logical atoms and clauses. As a result, a variable
       may appear where a predicate is expected. In fact, predicates may
       also be "computed" as the result of functional expressions.

       For example, if the function 'foo' is defined thus:

       foo(bar,X) -> do_this(X).
       foo(buz,X) -> do_that(X).

       then one can write the Horn-clause:

       bah(X,Y) :- foo(X,Y).

       such that the query bah(bar,boo) gives the same as do_this(boo).

       A form of "higher-orderness" may also be achieved with LIFE's
       cyclic terms which allows anything to self-refer - including clauses
       and predicates. For example, the following rule prints itself out:

       C:(self(X) :- write(C)).

       To wit, in WildLife:

       > self(1)?
       _A: (self(1) :- write(_A))

       *** Yes

       Finally, LIFE supports all traditional Prolog-style meta-programming
       ('listing', 'clause', 'assert', 'retract', etc...) and replaces
       the so-called "univ" term destructor '=..' with other operators
       (the function 'root_sort' returns the constructor of a term,
       and the function 'features' returns its list of attributes).


SYN.3. MONOTONIC LLOYD-TOPOR EXTENSIONS ALLOWED VS. NOT ALLOWED

     * SYNTACTIC SUGAR FOR EXTENDING HORN LOGIC WITH DISJUNCTION IN RULE
       BODIES AS WELL AS CONJUNCTION AND CLASSICAL IMPLICATION IN RULE
       HEADS [HTTP://WWW.W3.ORG/SUBMISSION/SWSF-SWSL/#SWSL-RULES-MON-LT]

     [IRL]

     IRL's rules are production rules, not inference rules. Such
     issues are irrelevant for it.

     [LIFE]

     All these extensions being purely syntactic transformations, with
     LIFE's term-expansion facility (which generalizes Prolog's Definite
     Clause Grammars and Functional Monads), it is a simple matter of
     implementing these transformations as syntactic monads. (This is
     what LIFE's "accumulators" were designed to do.)

SYN.4. EXPLICIT VS. IMPLICIT RULE SCOPE

     * ALLOWING FORMULAS AND/OR NAMES DENOTING WHAT HAS BEEN CALLED
       MODULES, CONTEXTS, RULESETS, OR MODELS
       [HTTP://WWW.ISI.EDU/~ARGOS/MATTHEW/TRIPLE_BY_EXAMPLE.HTML]

     [IRL]

     No. (IRL uses Java-like packages.)

     [LIFE]

     No. (LIFE uses Modula-like modules.)

     SYN.4.1. SLOTTED (KEYED, ROLE-NAMED) VS. POSITIONAL ARGUMENTS

         * ALLOWING N-ARY ATOMS WITH A SET OF N 'ATTRIBUTE=VALUE' PAIRS
           AS IN RDF/OWL PROPERTIES, F-LOGIC METHODS, AND OBJECT-ORIENTED
           SYSTEMS [HTTP://WWW.RULEML.ORG/INDOO]

         [IRL]

         IRL uses Java-like values and objects. Pattern-matching works on
         object structures.

         [LIFE]

         LIFE supports Order-Sorted Feature (OSF) terms - also known as
         psi-terms - which generalize algebraic terms (i.e., Prolog
         terms) with keyword-labelled as well as positional subterms.
	A psi-term is a rooted labelled graph. I may contain cycles.

SYN.5. WEBIZED VS. NON-WEBIZED NAMES

     * ALLOWING URIS AS OIDS FOR CONSTANTS, FUNCTIONS, SLOTS, PREDICATES,
       CLASSES, AND/OR LABELS [HTTP://WWW.W3.ORG/2000/10/SWAP/PRIMER.HTML]

     [IRL]

     There is no support for URIs or web-aware naming.

     [LIFE]

     There is no support for URIs or web-aware naming.

===== SES: SYNTACTIC-ENTAILING-SEMANTIC DISCRIMINATORS =====

SES.1. HOMOGENEOUS (BODY HAS SINGLE EXPRESSIVENESS CLASS) VS. HYBRID (BODY
     HAS TWO EXPRESSIVENESS CLASSES) RULES

     ???

SES.2. FACT-ONLY (DATABASE TABLES) VS. RULE-ONLY VS. FACT-AND-RULE BASES

     [IRL]

     IRL supports production rules. Facts are objects in the working
     memory.

     IRL also supports Decision Tables.

     [LIFE]

     LIFE supports both facts and rules as in Prolog, as well as
     persistent objects.

   SES.2.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS (ALSO
      UNDER "VARIABLE-FUL VS. ... CLAUSES")

      [IRL]

      IRL facts are ground only.

      [LIFE]

      LIFE facts may be ground or non-ground. The notion of "ground" in
      LIFE is somewhat irrelevant since values are sorts are minimal
      types (i.e., they have no subsorts). The notion of "extensional"
      sort is what corresponds to the conventional notion of "value".  An
      extensional sort is one that denotes a singleton set. For examples,
      numbers, strings, lists, etc., are extensional. (NB: WildLife 1.02
      does not enforce sort extensionality - i.e, X = 1 and Y = 1, does
      not imply that X = Y.)

SES.3. FUNCTION-FUL (FO HORN LOGIC) VS. FUNCTION-FREE (FO DATALOG)

   [IRL]

   IRL's objects are attributed graphs as in Java, not Herbrand terms.
   What corresponds to a Prolog "functor" is a Java-style constructor.
   IRL uses Java-like interpreted functions in rule conditions and
   bodies.

   [LIFE]

   LIFE terms are psi-terms.  What corresponds to a Prolog "functor" is
   the root sort. Prolog terms are special cases of psi-terms, so
   "uninterpreted functions" are simply sorts.

   SES.3.1. FUNCTION ARITY/ARITIES

   [IRL]

   Object constructors may be used with less attributes than their class
   definition prescribes. Missing attributes are implicitly there and may
   be referred to by using "dotted" projection on a constructed object's
   handle.

   [LIFE]

   WildLife 1.02 implements features as total functions (meaning that one
   can attach any feature to any object).  Hence, Prolog-like terms in
   LIFE using a functor symbol as root sort doe not have fixed arities.
   In theory, however, partial features can also be accommodated so as to
   enforced fixed arity if needed.

   SES.3.2. FIXED VS. UNFIXED FUNCTION NESTING DEPTH

   [IRL]

   There is no limit to either object or function nesting depth.

   [LIFE]

   There is no limit to either object or function nesting depth.

   SES.3.3. UNINTERPRETED VS. INTERPRETED FUNCTIONS

   [IRL]

   Functions are interpreted. Object contructors are not.

   [LIFE]

   LIFE supports interpreted functions (i.e., those symbols that have a
   functional definition). All other constructions are non-interpreted as
   functions - they are objects or predicates.

   Example of a LIFE function definition:

   fact(0) -> 1.
   fact(N:int) -> N*fact(N-1).

SES.4. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) CLAUSES

   SES.4.1. VARIABLE-FUL (NON-GROUND) VS. VARIABLE-FREE (GROUND) FACTS (ALSO
      UNDER "FACT-ONLY ... BASES")

   (see SES.2.1)

SES.5. PREDICATE ARITY/ARITIES

   [IRL]

   ILR does not have relational predicates. Boolean expressions using
   built-in, user-defined, or library-defined, functions and methods are
   evaluated as done in Java. All these functions have fixed arities.


   [LIFE]

   Nothing has fixed arity in LIFE. However, interpreted functions may be
   "curryed" (i.e., called with less arguments than specified by their
   definitions - such calls yield functional abstractions as in lambda
   calculus).

SES.6. NUMBER OF PREMISES IN RULES

   [IRL]

   The premise of a rule consists is possibly many object patterns and
   conditions (Boolean expressions) on their parts.

   [LIFE]

   A relational rule is Horn-like (i.e, of the form: A0 :- A1, ..., An,
   with n >= 0, where the Ai's are literals; i.e., psi-terms denoting
   relations).

   A function rule is a rewrite rule of the form A -> B, where A is a
   psi-term and B is of the form  "B0 | B1, ..., Bn", with n>=0, where
   B1, ..., Bn are literals. (This is read, "B0 such that B1 and ... Bn").

SES.7. LABELED (ANCHORED, OIDED) VS. UNLABELED CLAUSES

   ???

   SES.7.1. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF USER PREDICATES

   ???

   SES.7.2. LABELS ALLOWED VS. NOT ALLOWED AS ARGUMENTS OF PRIORITY-GIVING
      SYSTEM PREDICATE 'OVERRIDES' (CF. SCLP)

   ???

  SES.8. CERTAIN VS. UNCERTAIN CLAUSES AND ATOMS

  [IRL]

  IRL does not support uncertainty (neither fuzzy nor stochastic).

  [LIFE]

  LIFE does not support uncertainty (neither fuzzy nor stochastic).

===== SEM: SEMANTIC DISCRIMINATORS =====

  SEM.1. TERMINATING (ALL QUERIES TERMINATE) VS. NON-TERMINATING (AT LEAST ONE
     QUERY DOES NOT TERMINATE) RULEBASES

  [IRL]

  It is very easy to write a non-terminating IRL program.

  [LIFE]

  It is very easy to write a non-terminating LIFE program.

  SEM.2. FINITE-MODEL VS. INFINITE-MODEL RULEBASES (CF. DECIDABILITY)

  [IRL]

  IRL is Turing-complete (one can emulate a TM quite easily) and
  therefore is undecidable.

  [LIFE]

  LIFE is Turing-complete (one can emulate a TM quite easily) and
  therefore is undecidable.

  SEM.3. MODALITY/INTENTIONALITY (BEYOND FOL)

  [IRL]

  IRL supports event-driven and time-dependent rules (using so-called
  "chronicles").

  [LIFE]

  There are no modalities in LIFE.

===== PRAG: PRAGMATIC DISCRIMINATORS =====

PRAG.1. INFERENCE CONTROL

   PRAG.1.1. FORWARD CHAINING VS. BACKWARD CHAINING VS. BIDIRECTIONAL CHAINING

   [IRL]

   IRL uses forward-chaining and supports at least two evaluation modes:

   (1) "normal" RETE-style mode (rules are fired according to specified
       priorities, refraction, and recency),

   (2) "sequential" mode (rules are applied in the order specified).

   [LIFE]

   LIFE uses backward-chaining for relations and forward-chaining for
   functions. Rules are tried in the order they are specified.

   PRAG.1.2. INCREMENTAL VS. EXHAUSTIVE

   ???

PRAG.2. COMPLEXITY

   ???

PRAG.3. INTEROPERABILITY

   [IRL]

   IRL does not interoperate with other rule systems.

   [LIFE]

   Most Edinburgh-style Prolog programs will run under LIFE as expected
   (up to defining in LIFE a few additional predicates for Prolog
   built-ins that may not exist in LIFE). The contrary is generally not
   true.

   PRAG.3.1. ANNOTATIONS (INCLUDING CONTROLLED ENGLISH)

   [IRL]

   Annotations are limited to comments.

   [LIFE]

   Annotations are limited to comments.

   PRAG.3.2. TEST CASES

   ???

   PRAG.3.3. MAPPINGS

   ???

     PRAG.3.3.1. WITHIN EXPRESSIVE EQUIVALENCE CLASSES ("CLUSTERS")

     PRAG.3.3.2. BETWEEN EXPRESSIVE EQUIVALENCE CLASSES (IMPERFECT OR "LOSSY")

   PRAG.3.4. (FURTHER INTEROPERABILITY DISCRIMINATORS SHOULD GO HERE)

-------------------------------------------------------------------------------------

-- 
Hassan At-Kaci
ILOG, Inc. - Product Division R&D
tel/fax: +1 (604) 930-5603 - email: hak @ ilog . com
Received on Tuesday, 16 May 2006 02:06:19 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:29 GMT