RE: [PRD] PICK specification

Let me first write what I mean by "refraction" and "repeatability". I
expect to do this on next Monday.

Changhai

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

actually, as far as I can tell, my PICK proposal (when all rules are 
"repeatable") has the same behavior as "refraction".
PICK assumes that one can compare 2 rule instances for equality, and 
this should be better defined.  The natural definition is that ri1 = ri2

iff rule(ri1) = rule(ri2) and substitution(ri1)=substitution(ri2).  The 
substitutions are equal iff corresponding Consts are equal.  Therefore, 
objects can be equal even if their frames are not.  I claim this 
accounts for refraction.  Do you have a counter-example?  I.e. a ruleset

that when evaluated with my proposed PICK, does not "refract" properly?

Gary Hallmark wrote:
>
> 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 Friday, 24 October 2008 14:49:22 UTC