- From: Changhai Ke <cke@ilog.fr>
- Date: Wed, 22 Oct 2008 12:58:14 +0200
- 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 UTC