[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.

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)

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.

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)).
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, 16 October 2008 06:17:13 UTC