W3C home > Mailing lists > Public > public-rif-wg@w3.org > October 2008

RE: [PRD] PICK specification

From: Changhai Ke <cke@ilog.fr>
Date: Wed, 22 Oct 2008 12:58:14 +0200
Message-ID: <3E5E1A634BBD5C4A94C4D4A6DE0852E701B1E98B@parmbx02.ilog.biz>
To: "Gary Hallmark" <gary.hallmark@oracle.com>, "RIF WG" <public-rif-wg@w3.org>

Gary and all,

It's not easy to write the comments in an email, let me try. I need to
place your email in the general context of PRD working draft 2 (dated
Sept 22).

Production systems (or inference systems) have this cycle:
- Match: evaluate the rules to determine which are fireable,
constitution of rule instances
- Select: selection of a rule instance to fire, the famous PICK function
below. (the famous PICK function is here).
- Act: execution of the selected rule's actions.

As a first amendment, I think PRD WD should explain this cycle. This is
currently missing and is to be added.

>From there, we can determine a "cycle number". Initially, the cycle
number is 0, then it increases by 1 at each rule execution cycle. As a
matter of fact, the initial facts (if any) will be the facts present at
cycle 0.

Per my comment above, I prefer that the term "age" be mapped into "cycle
number". In fact, in your proposal (correct me if I misunderstand), you
are placed at the cycle N, and age represents the number of cycles prior
to the cycle N. It's hard to figure out how age evolves, and in which
direction. So can we use "cycle number" instead, and talk about
"cycle(n)", "cycle(n+1)" (the next cycle)?

The other comment is about "PICK" itself. In all the explanations, it
seems that we materialize a list of rule instances, that can be ordered,
and then you choose the first one. This is already a biased
understanding.

Some PR systems use a "lazy matching" algorithm. At each cycle, the
engine computes the right instance to fire. Behind, there is not
necessarily a list of rule instances that you can order. Of course, the
result is the same, you only need to pick (or compute) one instance to
fire. We can continue to use "PICK", but maybe a comment can be added in
this direction, and at least we should acknowledge the existence of
"lazy matching".

I also included other comments below, in the text.

Regards,

Changhai

-----Original Message-----
From: public-rif-wg-request@w3.org [mailto:public-rif-wg-request@w3.org]
On Behalf Of Gary Hallmark
Sent: jeudi 16 octobre 2008 08:16
To: RIF WG
Subject: [PRD] PICK specification


The current specification of PICK in the PRD draft has fallen into 
disrepair.  Here's how I would specify it for OBR/Jess.

Function PICK(order, c) returns a rule instance (ri) or nil.  Order is 
either "FIFO" or "LIFO" to indicate a breadth first or depth first 
search strategy, and c is a Configuration.  If nil is returned, then c 
is a terminal configuration.


[CK]
As discussed and agreed (as far as I understand) during the F2F meeting
in NY, rules are serialized in XML and the "rule execution strategy" (or
execution mode) is to be specified in a separate tag. Terms like LIFO,
FIFO or breadth, depth, could be a specific strategy. We can predefine
some strategies (at least the one on the inference systems that we are
defining), and leave the possibility for further definitions, or for
user's extensions.
[/CK]

We need some helpers:

picked(c) returns the rule instance that was picked when in
configuration c.

prior(c, 0) returns c.
prior(c', 1) returns c, where c' is the next configuration after c, as 
given by the overall PRD transition system.
prior(c, age) = prior(prior(c, age - 1), 1)

[CK]
Per my comment above, I prefer to translate these statements by the use
of "cycle" and "cycle number". It's an absolute axis.
[/CK]

priority(r) returns a number, where r is a rule. Higher numbers mean 
higher priority.
repeatable(r) returns true or false, where r is a rule.  If false, then 
no instance of r can directly cause another instance of r to fire.

[CK]
repetable is not the same thing as refraction. Your sentence raises
several remarks.
First, in PRD, we should use the term "refraction", it's used in most of
the papers. It means that a rule instance fired won't fire again, unless
its condition elements change again.
Repeatable is yet another concept. It's a per-rule or per modification
concept. I don't think it's part of the PICK function.
[/CK]

PICK(order, c) is defined as follows. 
First, we construct the agenda relation A(priority, age, ri) where ri is

a rule instance and the other 2 arguments are numbers.  The tuple 
(priority, age, ri) is in A iff both the following are true:
1. one of the following is true:
    a. repeatable(rule(ri)) is true and age is the greatest i such that 
ri is in prior(c, i) and ri is in prior(c, i-1) and ... and ri is in 
prior(c, 0) and ri != picked(prior(c, i)) and ri != picked(prior(c, 
i-1)) and ... and ri != picked(prior(c, 1)), or
    b. repeatable(rule(ri)) is false and age is the greatest i such that

ri is in prior(c, i) and ri is in prior(c, i-1) and ... and ri is in 
prior(c, 0) and rule(ri) != rule(picked(prior(c, i))) and rule(ri) != 
rule(picked(prior(c, i-1))) and ... and rule(ri) != rule(picked(prior(c,

1))), and
2. priority = priority(rule(ri)).


[CK]
It's a bit heavy to repeat the same thing for each cycle.
At each cycle, all the rules that are satisfied are instantiated and
become fireable. After this phase, you eliminate the instances using the
repeatable or non-repeatable setting, then we obtain the real list of
candidates.
[/CK]

Second, we order A by (priority, age).  We order by decreasing priority,

then by increasing or decreasing age, depending on whether PICK's order 
argument is LIFO or FIFO, respectively.  Ties are broken arbitrarily.
Finally, we return the ri from the first tuple in A according to the 
ordering.
Received on Wednesday, 22 October 2008 10:59:46 GMT

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