Re: [PRD] PICK specification (round 2)

I was almost ready to give a +1 with a few minor issues until I thought 
more about your Q3.  First, the minor issues:

We can simplify things slightly if we "hardwire" order=LIFO.  Then, 
picked(c) = PICK(c) -- i.e. PICK is recursive.

Let's swap the first 2 args to lastPicked  so that it is consistent with 
the args to age.  I.e. age(c, ri, test) and lastPicked(c, ri, test)

Changhai and I agreed that we should have a major and minor priority, 
and we order the agenda by major, then age, then minor.
Translators are responsible for assigning the minor.  E.g. number of 
tests, order of rule in the ruleset, etc.

Now, here's the (possible) major issue.  It has to do with an 
interaction of frames, actions, and variables.
Consider the following rule

If c is a Car then modify c.speed = c.speed + 5

Assume repeatable=true.  According to refraction, will the car's speed 
increase by 5 just once, or keep going faster and faster?
To answer, we must first translate to PRD:

Do(Retract(?c[speed->?oldSpeed]) ?c[speed->func:add(?oldSpeed 5)]) :- 
And(?c#Car ?c[speed->?oldSpeed])

Clearly, in each configuration, the binding for ?oldSpeed is distinct 
from that in other configurations.  So in fact the car goes faster and 
faster.  This is not what a user who wrote the original rule expects, 
because ?oldSpeed is an artifact of translation.

Interestingly, this is the default Jess behavior but most users prefer 
the non-default, so-called "slot specific" behavior (wherein the car's 
speed increases only once).  Slot-specific means, consider only the 
variables mentioned in the premise.  And in Jess and OBR, the only 
variable in the premise is ?c, because the modify action doesn't require 
binding ?oldSpeed in the premise.

So, we may have a new use for the bind action.  We need to be able to 
bind a local variable to a frame slot value in the action rather than in 
the condition, so that the rule instances don't have these slot variable 
bindings.  E.g.

Do ?oldSpeed (?c[speed->?oldSpeed] Retract(?c[speed->?oldSpeed]) 
?c[speed->func:add(?oldSpeed 5)]) :- ?c#Car

The above, by simple refraction, will fire just once, because ?c is the 
same in all configurations.

Christian de Sainte Marie wrote:
>
> 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 Wednesday, 29 October 2008 02:31:30 UTC