Sequential algorithm

Tuples

A tuple is a list of objects that complies with a particular structure. A tuple structure is simply a sequence of class descriptors. Each location in a tuple structure is called a slot. The same class descriptor can appear more than once at different slots.

Take a tuple structure:

(Customer,Product)

Here is a tuple that complies with this structure:

(new Customer("Henry"),new DVD("Mickey"))

Note that the subclassing is taken into account, since a DVD is a Product. However, there will be some tuples that do not comply with the structure. :

For example, the following tuple is too large:

(new Customer("Henry"),new CD("Madona"),new DVD("Mickey"))

This tuple is not correctly ordered:

(new DVD("Lord of the rings"),new Customer("Henry"))

And this tuple is too small:

(new Customer("Henry"))

In Java, a tuple is easily implemented as an array of objects:

Java Tuple = Object[]

The Java code to create a tuple and its objects is:

new Object[] {new Customer("Henry"),new DVD("Mickey")}

At run time, the tuples are built either by hand or automatically from the content of the working memory and then passed to the rule engine. Regardless of how they are built, the tuples are passed one after the other to the tuple-matching method through an instance of the generated tuple matcher class. The tuples are passed to the method in an order that is determined either by the engine or specified by a hand-written iterator class.

A tuple does not necessarily have to be complete. A partial tuple is a tuple with unused slots. Unused slots are simply set to null. For instance, the tuple(new Customer("Henry")) that was too small could be coded as (new Customer("Henry"),null) in order to fulfill the tuple structure.

Rule selection in sequential mode

The rules of a rule task that are set with the property algorithm equal to sequential are dynamically translated to Java bytecode. The bytecode is capable of performing sequential processing when the task is executed.

The body property of a rule task is mandatory. It selects the rules of the ruleset that will be taken into account by the rule task.

See also Runtime rule selection.

Control properties in sequential mode

This section contains details of how control properties affect sequential mode execution and tuple structure. See Control properties for rule tasks in execution modes for more general information.

The number of rules to be executed per tuple and the order in which they execute can be specified with control properties: ordering, matchedclasses, firing, firinglimit, and iterator; or small pieces of code.

The ordering property

The ordering property is mandatory for sequential processing. It describes the order by which the rules of the rule task will be executed.

There are two values available:

• literal: The rules are kept in the order in which they are set into the task body (using up/down arrows).

• sorted: The rules are sorted according to their static priorities.

Note that another value, dynamic, is available only for rule tasks using the RetePlus execution mode.

The matchedclasses property

The matchedclasses property is used to specify the tuple structure of the tuples passed to the engine at run time. This property is optional.

ruletask T {
   matchedclasses = { Man, Car }
}

When the matchedclasses property is not provided, the engine computes the tuple structure automatically from the selected rules. Only the simple conditions with no navigation clause, for example in or from, are relevant during the automatic computation of the value of matchedclasses.

Here is the way the engine computes the matchedclasses for an example ruleset:

rule RAB { when {A();B();} then {…} }
rule RA { when {A();} then {…} }
rule RB { when {B();} then {…} }
rule RCB { when {C();B();} then {…} }
rule RABA { when {A();B();A();} then {…} }

matchedclasses computation:

The firing property

The firing property specifies whether, for each tuple, all the rules or only the first rule that applies should be executed. This property is optional.

It has two possible values:

• allrules

  This value means that all the rules that applies should be executed before skipping to the next tuple. This is the default value.

• rule

  This value means that only the first rule that applies should be executed before skipping to the next tuple.

The firinglimit property

The firinglimit property gives another level of control when the firing property is set to allrules. It is used to specify a number that represents the maximum number of rules to be executed before skipping to the next tuple. This number should be greater than zero.

The iterator property

The iterator property is used to specify an expression that evaluates to an instance of the IlrTupleIterator interface that builds the tuples one after the other; see The IlrTupleIterator interface for more details. This property is optional.

The iterator is responsible for building all the possible full tuples that comply with the tuple structure from the data sources to which it is connected.

When the iterator property is not provided, a default working memory iterator is available. This default iterator works on the objects that are currently inserted in the working memory and builds all the possible tuples that correspond to the full tuple structure. The working memory iterator like any other iterator, will not build the partial tuples.

Here is an example that shows the sequence of tuples the working memory iterator builds according to a tuple structure:

Tuple structure:

(Customer,Product)

Working memory:

Customer = {c1,c2}
Product  = {p1,p2}

Tuple sequence:

1. (c1,p1)

2. (c1,p2)

3. (c2,p1)

4. (c2,p2)

Sequential execution mode operation

The sequential execution mode generates a tuple matcher class. A tuple matcher class is a list of tuples assembled from the objects in the working memory. The purpose of the tuple matcher class is to match the class used in the condition part of the rules. The tuples are then evaluated one by one, and if the conditions are satisfied, the rule is executed.

For details see:

• Tuple matcher class generation

• The tuple matching loop

• The IlrTupleIterator interface

• Refraction using the RetePlus execution mode

• Refraction using the sequential execution mode

• The static rule application strategy

Tuple matcher class generation

The tuple matching method is a method with a single tuple as its argument. Its body is specified by a sequence of rules. At run time, for each rule in the sequence of rules, the action part of the rule is executed as soon as the effective tuple that was passed to the tuple matching method satisfies the conditions of the rule.

The rule engine translates the body property of a sequential rule task to the body of the tuple matching method according to the values of the other properties of the rule task. The engine creates an instance of the generated matcher class to be able to match the runtime tuples.

When the body of the rule task is static, the translation only occurs the first time the rule task is activated.

Here is the pseudocode that corresponds to the translation:

1. rules = sort( body , ordering );

2. matcherClass = generate(rules, matchedclasses );

3. matcher = instantiate(matcherClass);

where:

• sort is the operation that sorts a set of rules according to an order specified by the ordering property

• generate is the operation that generates the tuple matcher class from a set of rules and a tuple structure specification

• instantiate is the operation that creates an instance of a tuple matcher class so that run-time tuples can be matched

When the body of the rule task is a dynamicselect without a domain, the translation occurs each time the rule task is activated.

Here is the pseudocode that corresponds to the translation:

1. bodyRules = evaluate( body );

2. sortedRules = sort(bodyRules, ordering );

3. matcherClass = generate(sortedRules, matchedclasses );

4. matcher = instantiate(matcherClass);

where: evaluate is the operation that evaluates an expression to get its run-time value.

When the body of the rule task is a dynamicselect with a domain, the translation only occurs the first time the rule task is activated. The generated matcher class is special in that it has the capability to activate the rules individually. Here is the pseudocode that corresponds to the translation:

The first time the rule task is activated:

1. domainRules = evaluate( body .in);

2. matcherClass = generate(domainRules, matchedclasses );

3. matcher = instantiate(matcherClass);

And, at each rule task activation, including the first one:

1. bodyRules = evaluate( body .dynamicselect,domainRules);

2. sortedRules = sort(bodyRules, ordering );

3. matcher.activateRules(sortedRules);

where: activateRules is the operation of the special tuple matcher that activates only a particular set of rules.

An example of the tuple matcher generation

The sequential execution mode generates a tuple matching method that takes a tuple as a single argument, however, at this moment nothing is known about the body of this method. This example describes the way the body is generated.

First of all, each rule of the sequence of rules that has to be translated is itself translated to a well-typed method of the same generated tuple matcher class.

For example, consider rule R:

rule R {
   when {
      c:Customer(category == GOLD);
      p:Product(price < 1000);
   }
   then {
      out.println("R(" + c.name + ',' + p.name + ')');
   }
}

The translated rule is as follows:

void rule_R(Customer c,Product p) {
   if ((c != null) && (p != null)) {
      if (c.category == GOLD) {
         if (p.price < 1000) {
            this.context.out.println( "R(" + c.name + ',' + p.name + ')');
         }
      }
   }
}

The tuple matching loop

The tuple matching loop is embedded in the sequential execution mode. This loop is executed by the engine each time a sequential rule task with a user iterator is executed. A special loop that builds both the tuples and calls the tuple matcher method for each tuple is separately embedded to iterate on the working memory.

Here is the pseudocode that corresponds to the execution of the body of a sequential rule task:

1. i = evaluate(iterator);

2. tuple = new Object[matchedclasses.length];

3. while (i.hasNext()) {

   i.next(tuple);

   matcher.matchObjects(tuple);

   }

where matchObjects is the tuple matching method of the generated tuple matcher class, the matcher object is an instance of this class.

The IlrTupleIterator interface

Handwritten iterators should implement the IlrTupleIterator interface.

The IlrTupleIterator interface provides two methods:

• boolean hasNext()

  This method is used to test whether there are still tuples to build.

• void next(Object[] tuple)

  This method is used to build the next tuple. The array is created by the engine and reused for each tuple. The engine is aware of the size of the array since it corresponds exactly to the size of the tuple structure.

Here is an example Java class that implements a tuple iterator that builds tuples of the (Object) tuple structure from a list of objects:

import java.util.* ;
public class ListIterator implements IlrTupleIterator {
   private List list;
   private int index;
   public ListIterator(List list) {
      this.list = list;
      this.index = 0;
   }

   public boolean hasNext() {
      return (this.index >= this.list.size());
   }

   public void next(Object[] tuple) {
      tuple[0] = this.list.get((this.index)++);
   }

   public void reset() {
      this.index = 0;
   }
}

Here is an example of code that uses such a tuple iterator through a ruleset parameter:

ruleset RS {
in ListIterator iter;
}

rule R1 { when { Customer(…); } then {…} }
rule R2 { when { Customer(…); } then {…} }
…

ruletask T {
   algorithm = sequential;
   ordering = literal;
   matchedclasses = { Customer }
   iterator = iter;
   initialaction = {
   iter.reset();
}
}

Refraction using the RetePlus execution mode

The refraction principle enforces that only one rule instance is created for a given tuple. Since the data unit for an engine cycle is the working memory, the engine can easily record all the possible tuples and check that there is only one rule instance for each tuple.

For example consider the following ruleset:

rule Person {
   when {
      Person();
   } 
   then {
   …
   }
}

rule PersonProduct {
   when {
      Person();
      Product();
   } 
   then {
   …
   }
}

ruletask main {
   algorithm = default;  // RetePlus algorithm
   ordering = literal;
   body = {Person,PersonProduct}
}

If the main code inserts the following objects into the working memory, the actions below can be traced:

1. context.insert(new Person("Henry"));

2. context.insert(new CD("Madona"));

3. context.insert(new DVD("Mickey"));

4. context.execute();

The execution trace will be:

1. Person(Henry)

2. PersonProduct(Henry,Madona)

3. PersonProduct(Henry,Mickey)

Refraction using the sequential execution mode

The data unit for an engine cycle is the tuple. The engine does not record the tuples as they are matched, it rather forgets them between cycles. Therefore, there is no built-in support for refraction.

Using the sequential execution mode, the above rule task becomes:

ruletask main {
   algorithm = sequential;
   ordering = literal;
   body = {Person,PersonProduct}
}

The computed tuple structure will be:

(Person,Product)

The generated tuple matching code will be:

void matchObjects(Object[] tuple) {
   rule_Person((Person)tuple[0]);
   rule_PersonProduct((Person)tuple[0],(Product)tuple[1]);
}

The main code remains the same:

1. context.insert(new Person("Henry"));

2. context.insert(new CD("Madona"));

3. context.insert(new DVD("Mickey"));

4. context.execute();

The working memory iterator loop will be:

1. matcher.matchObjects((Person("Henry"),CD("Madona")));

2. matcher.matchObjects((Person("Henry"),DVD("Mickey")));

The execution trace will be:

1. // matcher.matchObjects((Person("Henry"),CD("Madona")));

2. Person(Henry)

3. PersonProduct(Henry,Madona)

4. // matcher.matchObjects((Person("Henry"),DVD("Mickey")));

5. Person(Henry)

6. PersonProduct(Henry,Mickey)

The execution trace shows that, using the sequential execution mode, the same rule will be executed twice for the same parts of two different tuples.

Although there is no built-in support for refraction, the sequential execution mode uses a particular rule application strategy when it generates the body of the tuple matching method. The strategy, however, will try to limit the use of refraction.

The static rule application strategy

The static rule application strategy is the process by which a single rule application is selected among many potential rule applications. The sequential execution mode uses this strategy to determine which rule the engine can apply to a tuple that comprehends the tuple structure.

The rule engine requires a strategy when it generates the body of the tuple matching method to apply the rules to the single tuple argument. This strategy tries to avoid refraction issues when only a single tuple is considered. Such issues can occur with subclassing, because an object can be an instance of several classes simultaneously and can be a member of different slots of a tuple.

This strategy is used for each of the selected rules and it is implemented in two passes:

1. All rule applications are identified.

2. Only the most relevant rule applications are added to the body of the generated matching method.

A rule application is an application of the rule to the tuple, according to the tuple structure and modulo combination and subclassing. Modulo combination means that the classes of the rule conditions do not have to be in the same order as the tuple structure and that the rule may have fewer conditions than the length of the tuple structure. Modulo subclassing means that the classes of the tuple structure can be subclasses of the rule condition classes. Note that the reverse is not true.

A rule application is more relevant than another rule application if the following conditions are met:

• It is equivalent to the other one and:

  • It reuses fewer times the same slots than the other one.

  • Or it reuses the same number of times the same slots than the other one, but it also uses the slots in an order that is closer to the declaration order of the tuple structure than the other one.

• Or it is less general but it uses fewer times the same slots than the other one.

• Or it is more general and it uses fewer times the same slots than the other one.

Examples of the rule application strategy

Here is an example of how the strategy selects a single rule application from a set of equivalent rule applications:

XOM:

Product is an Object

Tuple structure:

(Product,Product)

Ruleset:

rule RuleProduct{ 
   when {
      Product();
   } 
   then {
      …
   }
 }

rule RuleProductProduct{
   when {
      Product();
      Product();
   } 
   then {
      …
   } 
}

Equivalent applications of RuleProduct:

1. RuleProduct((Product)tuple[0])

2. RuleProduct((Product)tuple[1])

The first application RuleProduct((Product)tuple[0]), is favored because the order by which it uses the slots of the tuple is closer to the initial declaration order than the second application:

Equivalent applications of RuleProductProduct:

1. RuleProductProduct((Product)tuple[0],(Product)tuple[0])

2. RuleProductProduct((Product)tuple[0],(Product)tuple[1])

3. RuleProductProduct((Product)tuple[1],(Product)tuple[0])

4. RuleProductProduct((Product)tuple[1],(Product)tuple[1])

The first and last applications are quickly eliminated since they are reusing twice the same slot which is not the case the second and third applications. The second and third applications cover far more potential tuples than the first and last. Finally, the second application RuleProductProduct((Product)tuple[0],(Product)tuple[1]), is favored because the order by which it uses the slots of the tuple is closer to the initial declaration order than the third application:

Here is an example of how the strategy selects a single rule application from a set of nonequivalent rule applications:

XOM:

Product is an Object

CD is a Product

DVD is a Product

Tuple structure:

(Product,CD,DVD)

Ruleset:

rule RuleProduct{
   when {
      Product();
   } 
   then {
      …
   }
}

rule RuleProductCD{
   when {
      Product();
      CD();
   } 
   then {
      …
   } 
}

rule RuleCDCD{ 
   when {
      CD();
      CD();
   }
  then {
      …
   } 
}

rule RuleProductProduct{
   when {
      Product();
      Product();
   } 
   then {
      …
   } 
}

ruletask T {
   algorithm = sequential;
   ordering = literal;
   body = { RuleProduct, RuleProductCD, RuleCDCD, RuleProductProduct }
   matchedclasses = {Product,CD,DVD}
}

Applications of RuleProduct:

1. RuleProduct((Product)tuple[0])

2. RuleProduct((CD)tuple[1])

3. RuleProduct((DVD)tuple[2])

The first application RuleProduct((Product)tuple[0]), is favored because it is more general than the second and third applications since a CD and a DVD are both a Product:

Applications of Rule RPC:

1. RuleProductCD((Product)tuple[0],(CD)tuple[1])

2. RuleProductCD((CD)tuple[1],(CD)tuple[1])

3. RuleProductCD((DVD)tuple[2],(CD)tuple[1])

The second and third applications are eliminated since they are both less general than the first application RuleProductCD((Product)tuple[0],(CD)tuple[1]).

Applications of Rule RCC:

• RuleCDCD((CD)tuple[1],(CD)tuple[1])

Applications of RuleProductProduct:

1. RuleProductProduct((Product)tuple[0],(Product)tuple[0])

2. RuleProductProduct((Product)tuple[0],(CD)tuple[1])

3. RuleProductProduct((Product)tuple[0],(DVD)tuple[2])

4. RuleProductProduct((CD)tuple[1],(Product)tuple[0])

5. RuleProductProduct((CD)tuple[1],(CD)tuple[1])

6. RuleProductProduct((CD)tuple[1],(DVD)tuple[2])

7. RuleProductProduct((DVD)tuple[2],(Product)tuple[0])

8. RuleProductProduct((DVD)tuple[2],(CD)tuple[1])

9. RuleProductProduct((DVD)tuple[2],(DVD)tuple[2])

The fifth and ninth applications are eliminated since they are both less general than the first application. The sixth and eighth applications are also eliminated since they are respectively less general than applications three and two. No other applications can be eliminated because the assumption that a Product is either a CD or a DVD does not hold, a Book for example may also be encountered.

This leaves:

1. RuleProductProduct((Product)tuple[0],(Product)tuple[0])

2. RuleProductProduct((Product)tuple[0],(CD)tuple[1])

3. RuleProductProduct((Product)tuple[0],(DVD)tuple[2])

4. RuleProductProduct((CD)tuple[1],(Product)tuple[0])

5. RuleProductProduct((DVD)tuple[2],(Product)tuple[0])

In this particular case, the strategy is not able to statically cure the single tuple refraction issue. For instance, the tuple (C,C,D) where C is a CD and D is a DVD gives multiple calls to RuleProductProduct with the same object couples.

However, note that the matchedclasses property specified for this ruleset (Product,CD,DVD) is a little peculiar. Different matchedclasses of the form (Product,CD,CD,Product) or (CD,DVD) or (Product,Product,CD,DVD) would solve the single tuple refraction issue. The first form (Product,CD,CD,Product) is the form that the sequential execution mode would automatically compute if the matchedclasses rule task property was removed.

Known limitation of the sequential algorithm

In almost all cases there is no limitation in the number of rules handled by a single task which has an algorithm property equal to sequential. The only exception is with extremely large decision tables with an otherwise. The processing is as follows: All the conditions of all the lines are negated in a single expression. This single expression becomes the body of a single method once translated to bytecode. This is an issue since the Java verifier rejects methods with too big a body. The scalability algorithm used for the rules does not go down to the method body. The user will be notified of this limitation when the class loader rejects the rules. The limit in the number of rules is not clear-cut, but the number is likely to be several thousands. The limitation also affects a ruleset that uses dynamic rule compilation (see Activating dynamic rule compilation).

The following table outlines the limitations of sequential processing, in particular its use combined with certain ILOG® Rule Language (IRL) constructs.

IlrContext mycontext="....";
IlrExceptionHandler myhandler="....";
mycontext.setExceptionHandler(myhandler);

Example 1: IRL limitation causing compilation error

This example results in JIT compilation errors due to missing enumerators.

ruletask T {
  algorithm = sequential;
  body = { R1, R2, R3, R4, R5, R6, R7, R8, R9 }
}

rule R1 {
  when {
    not MyObject();  // No enumerator, an error will occur
  }
  then {
  }
}

rule R2 {
  when {
    exists MyObject();  // No enumerator, an error will occur
  }
  then {
  }
}

rule R3 {
  when {
    collect MyObject() where (size() == 1);  // No enumerator, an error
                                                will occur
  }
  then {
  }
}

function Object getObject() {
  return new MyObject();
}

function Object[] getObjects() {
  Object objs = new Object[1];
  objs[0] = getObject();
  return objs;
}

rule R4 {
  when {
    not MyObject() from getObject();  // An enumerator, no error
  }
  then {
  }
} 

rule R5 {
  when {
    not MyObject() in getObjects();  // An enumerator, no error
  }
  then {
  }
} 

rule R6 {
  when {
    exists MyObject() from getObject();  // An enumerator, no error
  }
  then {
  }
} 

rule R7 {
  when {
    exists MyObject() in getObjects();  // An enumerator, no error
  }
  then {
  }
} 

rule R8 {
  when {
    collect MyObject() from getObject() where (size() == 1); 
    // An enumerator, no error
  }
  then {
  }
} 

rule R9 {
  when {
    collect MyObject() in getObjects() where (size() == 1);  
    // An enumerator, no error
  }
  then {
  }
}

Example 2: IRL showing construct limitations

Here is an example with a collect construct to demonstrate the scope of the bindings. This holds for not and exists too. This example also results in JIT compilation errors due to the use of unsupported constructs.

rule R10 {
  when {
    r:MyRootObject();
    c:collect MyObject(n:name; n.startsWith("ilog")) in r.getObjects(); 
    where (s:size(); s > 1);
  }
  then {
    out.println(r);  // correct
    out.println(c);  // correct
    out.println(s);  // correct
    out.println(n);  // error
  }
}