Saturday, May 26, 2007

Dynamic Salience Expressions

The other week in the mailing list someone was asking about whether it's possible to have the salience's value derived from the matched facts. Which got me thinking as I haven't seen that in any other rule engines - I only know a few engines, so someone with more experience care to verify that?

Anyway a few weeks later and a bored friday night dynamic salience expressions are born :) The salience value can now be derived from an expression that has full access to the variables bindings, ofcourse integer values can still be specified. Before, during conflict resolution, the salience value was read directly from the rule on each comparison, now when the Activation is created the salience value is determined once and stored in the Activation for comparison during conflict resolution. So now you can write things like have rules with the highest priced items combined with the shoppers bonus rating fire first:
rule "high value fires first"
salience (person.bonus * item.price)
when
person : Person()
item : Item()
then
...
end


MVEL is used for the salience expressions, as part of the pluggeable dialect system we have just built - I'll blog on pluggeable dialects and parsers next week.

Update -- Thanks to Johan Lindberg, who has pointed out that Clips and Jess allow the salience to be set via function calls in Jess/Clips.

11 comments:

  1. ...as I haven't seen that in any other rule engines...

    Clips has dynamic salience as well.

    Since you can fetch salience from a function, I'm guessing that you could send the matched facts in as arguments and have the function calculate a salience for you based on them, but I've never tried that.

    The salience behaviour is set using the set-salience-evaluation command which accepts when-defined, when-activated, and every-cycle as values. The last two will give you dynamic salience.

    See the Clips docs for more.

    ReplyDelete
  2. wow, I love this feature.

    Am on vacation, hope it is already available on version 4MR2, will check it out.

    Awsome job! -- Arjun Dhar

    ReplyDelete
  3. Johan, Thanks for that. I'm just reading the docs now and trying to understand the value of the "set-salience-bevaiour". If it's a function call is it correct to say that when setting it to "when-defined" would error if you use bound variables? what is the exact value of those three commands?

    ReplyDelete
  4. Well, it depends on what you mean by would error. You can do the following:

    |CLIPS> (defglobal ?*s* = 10)
    |CLIPS> (defrule foo
    | (declare (salience ?*s*))
    | (bla)
    | =>)
    |CLIPS> (assert (bla))
    |==> f-0 (bla)
    |==> Activation 10 foo: f-0
    |[Fact-0]

    without an error. But if you update ?*s*, it won't change the salience of the activation or any other activation of that rule for that matter.

    |CLIPS> (bind ?*s* 20)
    |:== ?*s* ==> 20 <== 10
    |20
    |CLIPS> (agenda)
    |10 foo: f-0
    |For a total of 1 activation.

    However,

    |CLIPS> (set-salience-evaluation when-activated)
    |when-activated
    |CLIPS> (retract 0)
    |<== f-0 (bla)
    |<== Activation 10 foo: f-0
    |CLIPS> (assert (bla))
    |==> f-1 (bla)
    |==> Activation 20 foo: f-1
    |[Fact-1]

    If you use every-cycle, salience is (re-)calculated at the time of rule definition, activation and after rules firing.

    ReplyDelete
  5. It turned out to be a little more difficult than I thought to implement your, rather simple, example of dynamic salience in Clips.

    At first I couldn't think of a way to actually pull out and use the matched values to modify salience.

    I've managed to get a working version using the test-CE but it only works if you set set-salience-evaluation to every-cycle. Apparently there's a difference in when the salience value is calculated between the two. If you use every-cycle it appears to evaluate the whole LHS before applying salience whereas if you use when-activated that appears to be done earlier.

    Here's the Clips DialogWindow:
    | CLIPS (V6.24 06/15/06)
    |CLIPS> (set-salience-evaluation every-cycle)
    |when-defined
    |CLIPS> (defglobal ?*salience* = 100)
    |CLIPS> (deftemplate person
    | (slot rating))
    |CLIPS> (deftemplate item
    | (slot price))
    |CLIPS> (defrule high-value-fires-first
    | (declare (salience ?*salience*))
    |
    | ?person <- (person (rating ?rating))
    | ?item <- (item (price ?price))
    |
    | (test (bind ?*salience* (* ?rating ?price)))
    | =>)
    |CLIPS>
    |(assert (person (rating 10)))
    |==> f-0 (person (rating 10))
    |[Fact-0]
    |CLIPS> (assert (item (price 5)))
    |==> f-1 (item (price 5))
    |==> Activation 50 high-value-fires-first: f-0,f-1
    |[Fact-1]
    |CLIPS> (assert (item (price 2)))
    |==> f-2 (item (price 2))
    |==> Activation 20 high-value-fires-first: f-0,f-2
    |[Fact-2]
    |CLIPS> (set-salience-evaluation when-defined)
    |every-cycle
    |CLIPS> (reset)
    |<== f-0 (person (rating 10))
    |<== Activation 20 high-value-fires-first: f-0,f-2
    |<== Activation 50 high-value-fires-first: f-0,f-1
    |<== f-1 (item (price 5))
    |<== f-2 (item (price 2))
    |==> f-0 (initial-fact)
    |CLIPS> (assert (person (rating 10)))
    |==> f-1 (person (rating 10))
    |[Fact-1]
    |CLIPS> (assert (item (price 5)))
    |==> f-2 (item (price 5))
    |==> Activation 20 high-value-fires-first: f-1,f-2
    |[Fact-2]
    |CLIPS> ?*salience*
    |50
    |CLIPS> (assert (item (price 2)))
    |==> f-3 (item (price 2))
    |==> Activation 20 high-value-fires-first: f-1,f-3
    |[Fact-3]
    |CLIPS> ?*salience*
    |20

    These last few lines didn't behave at all like I expected. I would have imagined that the second activation (f-1,f-3) would get a salience value of 50 but I'm sure there's a good reason for it not to.

    ReplyDelete
  6. Clips salience expressions only work with bound globals?

    I've stuck with the salience value being determined on activation, it seems the simplest way and what people expect. I don't like promoting the use of mutable globals used in rule decision making. Because the activation has access to the tuple it of course has full access to any locally bound variables and globals.

    I've just almost finished the pluggeable dialect system, which I'll blog soon. So now predicates, return values, evals, salience expressions and consequences can be written in any language you want. The pluggeable parser should be coming soon, along with a clips implementation. You can see my salience implementation, for MVEL, here:
    http://anonsvn.labs.jboss.com/labs/jbossrules/trunk/drools-compiler/src/main/java/org/drools/rule/builder/dialect/mvel/MVELSalienceBuilder.java
    http://anonsvn.labs.jboss.com/labs/jbossrules/trunk/drools-core/src/main/java/org/drools/base/mvel/MVELSalienceExpression.java
    http://anonsvn.labs.jboss.com/labs/jbossrules/trunk/drools-core/src/main/java/org/drools/reteoo/RuleTerminalNode.java

    In the later class the salience is set on the Activation creation:
    final AgendaItem item = new AgendaItem( context.getPropagationNumber(), cloned, rule.getSalience().getValue( tuple, workingMemory ), context, this.rule, this.subrule );

    ReplyDelete
  7. Clips salience expressions only work with bound globals?

    No, it's not the only way. You can change the references to the global variable into function calls if you want. I only used globals because it was less to type and easier to inspect from the shell.

    ReplyDelete
  8. You can change the references to the global variable into function calls if you want.

    Let me be a bit more specific because any old function wont work. The first thing I tried (and had hoped would work) was:

    |(deffunction calc-salience (?rating ?price)
    | (* ?rating ?price))

    and

    |(defrule high-value-fires-first
    | (declare (salience (calc-salience ?rating ?price)))
    | ...
    | =>)

    unfortunately you get a Variable rating is unbound if you try the above. But then again, it makes sense, ?rating hasn't been bound. Yet. But you can't move the salience declaration either because then you get a Syntax Error.

    So, more specifically, the function calls that actually work are those that can access a state variable somewhere.

    I agree that your design is nicer because you don't have to make the round trip via a state variable. I wonder how Jess works in this situation?

    ReplyDelete
  9. The intent behind the implementation of dynamic salience in CLIPS is that global variables referenced by the salience declaration are set by the RHS of other "meta" rules which reason about the salience values which should be assigned. There's no directly supported mechanism for using LHS variable values as part of the salience evaluation, although if you're using when-activated salience, you can use the trick shown in this post of binding a global variable to LHS variables. I originally added the feature because it seemed like it might be useful, but personally in the last 15 or so years have never come across a situation where I was tempted to use it.

    ReplyDelete
  10. Hey Gary, good to here from you - your book has been a bible for me, so thank you.

    We have a jess/clips like parser coming soon, can we tempted over to work with us ;) Either way please do email me, so we can exchange IM details, would love to chat to you about rule engines in general.

    ReplyDelete
  11. general thought on dynamic salience. although it's useful, I think users should be aware that it may have a slight performance cost :)

    calculating the salience once when the activation is a good compromise. Another and more expensive form would be to recalculate the salience of all activations. I don't know of any cases that would need that kind of functionality. The only time re-calculating all activations would be needed is if the rule involves a global. Since globals can change value w/o triggering a modify, the existing activations in the agenda wouldn't know the salience should be updated.

    normal facts changes would result in modify, so using calculate once on creation of activation is more than sufficient.

    ReplyDelete