[PRD] PICK specification (round 2)

All (but PRD people in particular :-),

My current understanding of what the specification of a PICK under a refraction+priority+recency CR could be as follows (reflecting what I understand is the agreement between Changhai and Gary, at least):

The essential idea, as Gary puts it, is that an instance of a rule does not fire more than once in its lifetime, where the lifetime of an instance is the longest span of contiguous states where it is an instance.

Trying to capture that more precisely, now...

Lots of helper functions, first:

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

prior: C_RS x |N -> C_RS, where C_RS is the set of configurations and |N is the set of integers, is a helper function that, given a configuration, c, and a number of cycles, i, returns the i-th configuration prior to c in the systems history:
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, or c' if c' is the initial configuration;
prior(c, age) = prior(prior(c, age - 1), 1).

Notice that, if i is greater than the number of cycle since the initial configuration, prior(c, i) always returns the initial configuration.
So, let cycle: C_RS -> |N, be a helper function that return the numer of cycles between the input configuration and the initial configuration, that is:
cycle(c) = min(i | forall j >= i, prior(c, j) = prior(c, i))

Let us now define an integer function age(c, ri, test), where c is a configuration, ri is a rule instance in instance(c), and test is a boolean function that takes two rule instances as input:
age(c, ri, test) = min(cycle(c), max(i | forall j, 0 =< j =< i, exists ri' in instance(prior(c, j)), such that test(ri, ri') is true)).

age(c, ri, test) tells us "how old" is a rule instance ri in a configuration c, according to some "test" to check whether ri was already present in c's predecessors.

lastPicked(ri, c) is an integer that returns the number of cycle between c and the last configuration when ri was last picked, where the test to checked if ri was picked is a booleean function "test" that compares two rule instances:
lastPicked(ri, c, test) = min(i | forall configurations c'=prior(c, i) such that test(picked(c'), ri) is true), if there is a configuration c'=prior(c,i), 0<=i<=cycle(c) that satisfies the condition;
lastPicked(ri, c, test) = cycle(c)+1 is there is none.

finally, let us define two "tests":
- sameInstance(ri, ri') is true iff rule(ri) = rule(ri') and, forall variables ?x_i in Var(rule(ri)), subst_ri(?x_i) = subst_ri'(?x_i), where subst_ri, resp. subst_ri' is the substitution associated with ri, resp. ri'.
- sameRule(ri, ri') is true iff rule(ri) = rule(ri').

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.

Given all that help, 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(c, ri, sameInstance) < lastPicked(ri, c, sameInstance)
   b. repeatable(rule(ri)) is false and age(c, ri, sameInstance) < lastPicked(ri, c, sameInstance) and age(c, ri, sameRule) >= lastPicked(ri, c, sameRule)
2. priority = priority(rule(ri)).
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.

Condition 1.a says exactly that an instance cannot be fired twice in its life time, that is, that there has to be at least one configuration where it is not an instance, according to the sameInstance test, after it is fired, before it is fireable again: that corresponds to refraction.

Condition 1.b says that, in addtion to not being fireable twice in its lifetime, an instance cannot be fired if it was not already there when another instance of the same rule was last fired. In other words, when an instance of a non-repeatable rule is picked, it kind of freezes the set of fireable instances of that rule to the ones that were instances in that configuration, until there is at least one configuration where there is no instances of that rule at all (and, of course, a specific instance can still not be fired more than once in its life time). That corresponds to Jess's no-loop as Gary describes it (well, as I understand Gary describes it :-)

Example:
R1: if P(?x) then print ?x

and there are two facts: P(A) and P(B). The result will be
A B or B A, whether R1 is repeatable or not: both instances (R1 ((?x = A))) and (R1 ((?x=B))) are instances in all the configurations, so that they both fire once and only once if R1 is repeatable, and they are the same age, so that whichever is fired first, the other one was already present when it fired (so it can still fire later).

Now, consider
R2: if P(?x) then P(?x+1) and print ?x

and there is one single fact: P(1).

If R2 is repeatable, the result is:
1 2 3 4 5 ..., because R2 adds a new fact each time it is fired, that the each new fact matches in all the subsequent configurations but the corresponding instance is fired only once (and it is, by construction, when the new fact is first available, because there is no other fireable instance), and that each instance is fired only once during its lifetime.

But if R2 is non-repeatable, the result is:
1
because all the instance (R2 ((?x=2))) that is in the second configuration did not pre-exist the firing of the first instance of R2, and is thus barred by the no-repeat condition.

Question 1: is the strategy with simple refraction+priority+recency prevalent enough that we include it in PRD (simple refraction=refraction with rule-level repeatability=1.a)?

Question 2: what about the strategy with non-repeatable refraction-with-rule-level-non-repeatability(1.b)+priority+recency? Is it implemented/implementable by everybody?

Question 3: this does not account for refraction with object- or property-level repeatability, that would be like 1.a with the test being sameInstanceButForSomePropertyValues instead of sameInstance; that is, the instance sameness test is only on some of the binding values, excluding the subsitution for variables that bind to the values of some "repeatable properties" (property-level repeatability) or excluding the variables that bind to the values of any property of a "repeatable object" (object-level repeatability). This is what I understand Changhai calls repeatability. Is that implemented/implementable by anybody but ILOG?

Cheers,

Christian

Received on Tuesday, 28 October 2008 22:22:08 UTC