Re: [PRD] PICK specification

Changhai Ke wrote:
> Christian: can you register an action for me to explain "refraction" vs.
> "repeatability"?
>   
I would like the "explanation" to be a refinement of my proposed PICK 
function, if possible.
I haven't been able to fully grasp the various informal explanations.
> 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?
>   
LIFO means pick the newest rule instance.  FIFO means pick the oldest.  
This comes from Jess/CLIPS. 
If Ilog doesn't support FIFO, I'm happy to "hard wire" the spec to 
LIFO.  I've never seen anybody use FIFO.

I would like to amend my PICK proposal to add a third component to the 
Agenda ordering key.  Recall that I propose ordering by priority, then 
by age.  The amendment is to have 2 priority components: major and 
minor.  Both are attributes of a Rule.
The agenda is ordered by (major (descending), age (ascending), minor 
(descending)).  E.g. I think in Ilog the minor priority is determined by 
the order of the rule in the ruleset.
> 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 18:12:25 UTC