Saturday, July 31, 2010

Slot Specific and Refraction

Slot Specific and Refraction are two techniques to help with recursive loop problems when writting rules. Drools currently implements neither.

Refraction
Refraction has been around a long time and was part of the original LEX and MEA conflict resolution strategies. When a rule + fact[] fires the set of facts that make up the rule continue to be true. When the fields for an existing set of facts are changed any rules that fact[] have previously fired against are not re-added to the agenda for firing. Simply put a rule cannot refire for any give set of data regardless of whether the set of data is modified by the current rule or other rules. However if a modification to the fact[] stops it being true for a given rule and then later the fact[] becomes true again for that rule it can now be refired.
The OPS5 manual on refraction:

http://www.math-cs.gordon.edu/courses/cs323/OPS5/ops5.html
    REFRACTION

This term comes from the neurobiological observation of a refractory
period
for a neuron, which means that the neuron is not able to fire
immediately without first going through a relaxation process. In a
similar way, OPS5 will not allow the same instantiation in the conflict
set from firing twice in a row. This prevents the inference engine from
entering into an infinite loop.
Refraction is supported in OPSJ and JRules, however it is not supported in Drools, Clips or Jess (please correct me if i'm wrong).

Slot Specific
Jess also recently introduced "slot-specific" as an alternative way of dealing with recursive looping. You can read a thread here on "slot-specific" and refraction in Jess, http://www.mail-archive.com/jess-users@sandia.gov/msg05488.html. Slot specific means a pattern will only propagated facts for fields that are changed which it constrains on. This means you can modify a value in the consequence and if the rule does not constrain on that field it will not refire. Clips COOL (Clips Object Oriented Language) has this feature (but not deftemplates) as default for all fields of an Object. However "slot-specific" is not implemented in Drools, JRules or OPSJ (please correct me if i'm wrong).

Refraction + Slot-Specific + onChange
I think there are advantages and disadvantages to each idea and I've been trying to think of better ways to deal with recursion in Drools and realised the two can be used together.

In Drools 6.0 I propose refraction to be the default behaviour for the engine, so no rules that have fired and still true can be reactived from a modify without first being made false. However "slot-specific" can override this allowing a pattern to react to changes on specific fields. With "Differential Diff", previous called "True modify" refraction is trivial to support. A performant slot specific implementation will not be trivial, especially with our support for nested accessors.
http://blog.athico.com/2010/03/drools-halves-memory-use-with-new-true.html
http://blog.athico.com/2010/01/rete-and-true-modify.html

I propose "onChange" property listeners as a mechanism to specify which slots can receive modification updates. "onChange" would be a magical field supported in patterns that specifies whether a pattern listens to and propagates changes, "onChange" would give us "slot-specific" type semantics but with more user control and flexability. It takes an array of field names, here are example semantics:

Person( onChange == [name]) // listen to any "name" property changes, if "name" is changed then propagate, other property changes will not be propagated.
// Notice we don't need quotes as property names never have spaces

Person( onChange == [name, age, location]) // listens and propagates "name", "age" and "location" changes.

Person( onChange == [*] ) // listen to all properties and propagates, this is the behaviour of current Drools.

Person( onChange == [!name, *]) // listen to all properties except "name".

Person( onChange == [name, *]) // is allowed but obviously redundant

Person( onChange == [name, !name, *]) // is not allowed

By default Drools will not listen to any field changes:
Person() // will match just once and never refire again for any given Person instance

All in all onChange allows the user to take advantage of slot-specific and refraction qualities, while not locking the user into either. I've also previously discussed constraining on previous values of a field, which would give even more fine grained control.

Field Versioning
There are times when you need to compare between current and previous values of a field, users can do this now by intermediary facts; i.e. inserting an Event to represent the before and after value for a field change, but it's a little clunky. Intead we can provide built in support for this into the language, using an @ver(int) attribute. The idea is that Drools would store previous values, only on demand, so you only pay the cost if you use this feature. The value for @ver is an effective "diff" value counting backwards starting from 0, which is now. So @ver(0) is the current field value, @ver(-1) is the previous field value @ver(-2) is the value 2 versions ago.

SomeFact( fieldName != fieldName @ver( -1 ) )

So any field with no @ver is effectively, and you could write it as such, @ver(0)
SomeFact( @ver(0) fieldName != fieldName @ver( -1 ) )

We can allow bindings to previous versions:
SomeFact( $var : @ver(-2) fieldName )
OtherFact( field == $var )

We should also support the ability to add a range of values to a list, for processing with accumulate:
SomeFact $list : @var(0....-5) fieldName )

12 comments:

  1. cool.. sounds really interesting..
    Some question about the onChange approach.
    When you include onChange inside a pattern, the listeners will be associated with that rule right? it will not be a global listener for that property right?
    Sounds like you are trying to stop the recursion adding some listeners inside the pattern. That causes that the LHS of the rules looks really complex. What about something like:

    define ListenersforPerson
    Person.name
    Person.age
    end

    Rule One
    listeners ListenerforPerson, ...
    when
    Person()
    then
    doSomething();
    end

    So you can apply the same logic for braking loops in different rules without adding too much complexity into the LHS.

    Just my two cents..

    ReplyDelete
  2. Tibco BusinessEvents is supposed to have slot specific, but in my experience it's hit or miss on whether it works or not.

    ReplyDelete
  3. By default implicit onChange listeners will be added for any constrained field, which will not complicate the rule language. So a rule will look like below:
    Person( name == "mark", age == 34)

    But will have the execution semantics of Clips COOL, or Jess "slot-specific" if you where to specify it for eachof those slots on a deftemplate".

    It should be possible to add something additional at the type declaration level that says all patterns that use this Type listen to a given field or all fields, as some will want it to globally behave as Drools does now.

    ReplyDelete
  4. great.. did you see another implementation that covers the field versioning stuff?
    It would be nice to see how they keep the old versions of a fact fields in memory, or in a persistent storage. Sounds like a huge amount of data being kept in memory.
    At the same time sounds like you can generate events to represent the fact changes and using that you can leverage the events life cycle to know when you can discard from memory old versions that will not be evaluated anymore.

    ReplyDelete
  5. Great article. One small point of information re. Jess. It has had the ‘slot-specific' feature for some time. It now also supports 'no-loop'. I believe no-loop provides OPS5-style refraction. From the manual..."If a rule includes the declaration (declare (no-loop TRUE)), then nothing that a rule does while firing can cause the immediate reactivation of the same rule". This is compared with the slot-specific' mechanism in Jess and described as 'stronger'.

    You define the two different approaches of 'slot-specific' and 'refraction'. I'll call this 'full' refraction, because it seems to me that 'slot-specific' is really best understood as a refraction mechanism in its own right. There is a third refraction strategy I have seen. This is where refraction is enforced regardless of any changes to any slot values (rather like full-refraction), but only where the LHS only matches the fact and does not contain any additional slot-specific constraints. It fits well with higher-level rule languages that hide such matches on the LHS - i.e., the non-slot specific match on a fact is produced implicitly by some action in the consequence that acts on that fact where the fact is not otherwise explicitly represented in the LHS of the rule. This is the approach taken in Microsoft's engine which uses a higher-level abstract rule modelling language (with something of a common heritage with RuleML) extended with bindings to underlying data. I'll invent a name for this - how about 'fact-match'.

    So, I think we have a taxonomy of three basic refraction approaches:

    slot-specific: Consequence changes values of slots explicitly constrained on LHS
    fact-match: Consequence changes values of any slots, but no slots are explicitly constrained on LHS
    full: Consequence changes values of any slots, regardless of which slots, if any, are constrained on the LHS

    Apart from obvious performance concerns, I love the idea of fine-grained control over slot-specific refraction proposed here. Explicit control is a good thing. Modern engines are performant enough for most scenarios, so a bit of additional overhead is not necessarily a problem, as long as developers are aware of the possible consequences of their decisions. They are often used to making lots of such trade-offs each time they write code.

    The use of built-in versioning sounds intriguing. Looking forward to seeing the results.

    ReplyDelete
  6. "I believe no-loop provides OPS5-style refraction."
    No-loop is different to refraction. No loop says "I'm current executing, can I add myself to the agenda". Where as refraction means a rule+data can never be added to the agenda, by any rule, unless its "relaxed" first, i.e. made false.

    ReplyDelete
  7. Oh, OK. I think I've got it now. So where the firing of a rule would *immediately* (i.e., in a match-resolve-act cycle caused directly by the firing rule) cause the same rule to reactivate, Jess' no-loop prevents that. However, some later modification or re-assertion of a fact matched by the firing rule may cause the rule to be reactivated for the same match. Moreover, I've been experimenting with no-loop and realised that once all matching activations of a no-loop rule have been retracted during the modification of a fact, no further activations of the rule for that modified fact will reappear during the match-resolve-act cycle, even for different combinations of the modified fact and other facts. In other words, no activations will reappear in the next cycle for (rule+fact[])* where fact[] contains the modified fact.

    What I think you are saying is that the OPS5 approach is different in two respects. First, it extends indefinitely, potentially across many subsequent cycles. Secondly, it is limited to the specific rule+fact[] represented by the fired activation. Also, the rule will never reactivate the given rule+fact[] until that match first becomes false, and then later becomes true. This is certainly different behaviour to Jess' no-loop.

    Googling, I see an interesting discussion on this subject from last year between Wolfgang and Chris Welty on the RIF-PRD. Chris wrote:

    "Although [no-loop] appears in several rule engines, [the W3C RIF Working Group] could not find a clear common semantic description (in terms of our model). Some systems interpret no-loop to mean that a rule may only fire once, others that at most 1 instance of a rule may be active at a time, others that a rule instance's actions may not directly re-instantiate the same rule, etc."

    My little taxonomy starts to look way too simplistic. There are clearly other dimensions to consider with regard to different refraction approaches, including lifetime across multiple match-resolve-act cycles, restriction to specific rule+fact[] activations, etc.

    ReplyDelete
  8. Issues I see are with identity, specifically hash id.

    If the slot is part of the hashing then it's a different object by hash id.

    Using VM 'pointer' value is problematic as it's not semantic, and should be lifted and can be referenced if used in the LHS.

    ReplyDelete
  9. Some further thoughts on this at http://geekswithblogs.net/cyoung/archive/2010/09/09/the-dimensions-of-refraction.aspx

    ReplyDelete
    Replies
    1. I believe we can inject in Refraction capabilities into Drools Rule Engine using a simple Agenda Filter. I have tested this with test cases against JRules and Drools and get similar results. Without the Refraction Agenda Filter it loops infinitely as expected. Here is what the code looks like

      ---------Agenda Filter---------------------------


      package test;

      import java.util.ArrayList;
      import java.util.List;

      import org.drools.runtime.rule.Activation;
      import org.drools.runtime.rule.AgendaFilter;

      /**
      * This custom agenda filter injects refraction behavior into the rule engine
      * @author Mukundan Agaram
      *
      */
      public class RefractionAgendaFilter implements AgendaFilter {
      private List encounteredActivations = new ArrayList();

      @Override
      public boolean accept(Activation act)
      {
      //Check for a Refraction
      if (encounteredActivations.contains(act))
      {
      //Remove from encountered activations for future firing
      encounteredActivations.remove(act);
      //return false so the rule is not selected as part of the refraction
      return false;
      }
      //Otherwise add the rule to check for potential refractions in the future
      encounteredActivations.add(act);
      //select the rule to be part of the agenda
      return true;
      }

      }

      -----------------DRL------------------------
      //created on: Jan 15, 2013
      package test
      dialect "mvel"

      rule testFooBar1
      salience 100
      when
      $foo : Foo()
      $bar : Bar(y > 0)
      then
      $foo.setX(($foo.getX() + $bar.getY()));
      System.out.println("Fired "+drools.getRule().getName())
      update($foo);
      end

      rule testFooBar2
      salience 150
      when
      $foo : Foo(x >= 6)
      then
      System.out.println("Fired "+drools.getRule().getName())
      end

      rule testFooBar3
      salience 50
      when
      $foo : Foo(x >= 7)
      then
      System.out.println("Fired "+drools.getRule().getName())
      end

      ----------------Runtime execution code--------------------------

      package test;

      import org.drools.KnowledgeBase;
      import org.drools.KnowledgeBaseFactory;
      import org.drools.builder.KnowledgeBuilder;
      import org.drools.builder.KnowledgeBuilderFactory;
      import org.drools.builder.ResourceType;
      import org.drools.io.ResourceFactory;
      import org.drools.runtime.StatefulKnowledgeSession;

      public class TestFooBarMain {

      private static void test()
      {
      KnowledgeBuilder kbuilder = KnowledgeBuilderFactory.newKnowledgeBuilder();

      kbuilder.add( ResourceFactory.newClassPathResource( "TestFooBar.drl", TestFooBarMain.class ),

      ResourceType.DRL );

      if ( kbuilder.hasErrors() ) {

      System.out.println( kbuilder.getErrors().toString() );

      }
      else
      {
      System.out.println("DRL parsing - success!");
      }


      KnowledgeBase kbase = KnowledgeBaseFactory.newKnowledgeBase();
      kbase.addKnowledgePackages( kbuilder.getKnowledgePackages() );

      StatefulKnowledgeSession ksession = kbase.newStatefulKnowledgeSession();

      Foo foo1 = new Foo();
      foo1.setX(6);

      Bar bar1 = new Bar();
      bar1.setY(3);

      ksession.insert(foo1);
      ksession.insert(bar1);

      ksession.fireAllRules(new RefractionAgendaFilter());
      }



      /**
      * @param args
      */
      public static void main(String[] args) {
      test();

      }

      }

      ----------------Facts-------------------------
      package test;

      public class Foo {

      private int x;
      private int y;

      public int getX() {
      return x;
      }
      public void setX(int x) {
      this.x = x;
      }
      public int getY() {
      return y;
      }
      public void setY(int y) {
      this.y = y;
      }
      }

      package test;

      public class Bar {

      public int getX() {
      return x;
      }
      public void setX(int x) {
      this.x = x;
      }
      public int getY() {
      return y;
      }
      public void setY(int y) {
      this.y = y;
      }

      private int x;
      private int y;
      }


      Please try it out and tell me what you think. I believe is a much needed feature of a forward chaining rule engine for commercial purposes. Any feedback is deeply appreciated.

      Thanks,
      Muk A


      Delete
  10. Muk A,

    Probably best to discuss this in the dev mailing list:
    http://www.jboss.org/drools/lists

    Mark

    ReplyDelete
  11. Thanks Mark. I did already post it to the forum and I have seen and interesting article from Esteban covering the options available.

    ReplyDelete