RE: [PRD] PICK specification

Christian: can you register an action for me to explain "refraction" vs.
"repeatability"?

Gary: Your terms "LIFO" and "FIFO" are not clear to me. If we leave a
hook to let users to define new strategies (as we all agree to propose
to do), you will be able to define them as extensions. Is that fine?

Changhai

-----Original Message-----
From: Gary Hallmark [mailto:gary.hallmark@oracle.com] 
Sent: mercredi 22 octobre 2008 22:49
To: Changhai Ke
Cc: RIF WG
Subject: Re: [PRD] PICK specification



Changhai Ke wrote:
> 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).
>   
I think you should really be looking at the latest at 
http://www.w3.org/2005/rules/wiki/PRD
> 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.
>   
This is the meat of the spec and is described formally as a labeled 
terminal transition system. 
> 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)?
>   
clearly there is an isomorphism here.  I think of prior cycles as the 
history, and so "age" seems like a reasonable term.
> 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".
>   
No.  This is a formal spec, not an implementation guide.
> 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]
>   
Agreed.  We need some syntax at the ruleset level to designate the 
(conflict resolution) strategy as either FIFO or LIFO, and an accessor 
strategy(rs) that returns either FIFO or LIFO if rs is a ruleset.
> 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.
>   
You'll have to do a better job with the definition of "refraction".  My 
notion of "repeatable" is precisely defined in my specification of PICK,

below.  You should propose an alternative definition of PICK that 
captures what you mean by
"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]
>   
Well, it certainly *is* part of my proposed PICK function.  So you'll 
have to propose another.
> 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]
>   
you do know the difference between a formal specification and an 
implementation, right?
> 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 Thursday, 23 October 2008 13:26:53 UTC