7.4. Fibonacci example decisions (recursion and conflict resolution)
The Fibonacci example decision set demonstrates how the decision engine uses recursion to resolve execution conflicts for rules in a sequence. The example focuses on resolving conflicts through salience values that you can define in rules.
The following is an overview of the Fibonacci example:
-
Name:
fibonacci
-
Main class:
org.drools.examples.fibonacci.FibonacciExample
(insrc/main/java
) -
Module:
drools-examples
- Type: Java application
-
Rule file:
org.drools.examples.fibonacci.Fibonacci.drl
(insrc/main/resources
) - Objective: Demonstrates recursion and conflict resolution through rule salience
The Fibonacci Numbers form a sequence starting with 0 and 1. The next Fibonacci number is obtained by adding the two preceding Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, and so on.
The Fibonacci example uses the single fact class Fibonacci
with the following two fields:
-
sequence
-
value
The sequence
field indicates the position of the object in the Fibonacci number sequence. The value
field shows the value of that Fibonacci object for that sequence position, where -1
indicates a value that still needs to be computed.
Fibonacci class
public static class Fibonacci { private int sequence; private long value; public Fibonacci( final int sequence ) { this.sequence = sequence; this.value = -1; } ... setters and getters go here... }
To execute the example, run the org.drools.examples.fibonacci.FibonacciExample
class as a Java application in your IDE.
After the execution, the following output appears in the IDE console window:
Fibonacci example output in the IDE console
recurse for 50 recurse for 49 recurse for 48 recurse for 47 ... recurse for 5 recurse for 4 recurse for 3 recurse for 2 1 == 1 2 == 1 3 == 2 4 == 3 5 == 5 6 == 8 ... 47 == 2971215073 48 == 4807526976 49 == 7778742049 50 == 12586269025
To achieve this behavior in Java, the example inserts a single Fibonacci
object with a sequence field of 50
. The example then uses a recursive rule to insert the other 49 Fibonacci
objects.
Instead of implementing the PropertyChangeSupport
interface to use dynamic facts, this example uses the MVEL dialect modify
keyword to enable a block setter action and notify the decision engine of changes.
Fibonacci example execution
ksession.insert( new Fibonacci( 50 ) ); ksession.fireAllRules();
This example uses the following three rules:
-
"Recurse"
-
"Bootstrap"
-
"Calculate"
The rule "Recurse"
matches each asserted Fibonacci
object with a value of -1
, creating and asserting a new Fibonacci
object with a sequence of one less than the currently matched object. Each time a Fibonacci object is added while the one with a sequence field equal to 1
does not exist, the rule re-matches and fires again. The not
conditional element is used to stop the rule matching once you have all 50 Fibonacci objects in memory. The rule also has a salience
value because you need to have all 50 Fibonacci
objects asserted before you execute the "Bootstrap"
rule.
Rule "Recurse"
rule "Recurse" salience 10 when f : Fibonacci ( value == -1 ) not ( Fibonacci ( sequence == 1 ) ) then insert( new Fibonacci( f.sequence - 1 ) ); System.out.println( "recurse for " + f.sequence ); end
To better understand the execution flow of this example, you can load the audit log file from target/fibonacci.log
into your IDE debug view or Audit View, if available (for example, in Window
In this example, the Audit View shows the original assertion of the Fibonacci
object with a sequence
field of 50
, done from Java code. From there on, the Audit View shows the continual recursion of the rule, where each asserted Fibonacci
object causes the "Recurse"
rule to become activated and to fire again.
図7.7 Rule "Recurse" in Audit View
When a Fibonacci
object with a sequence
field of 2
is asserted, the "Bootstrap"
rule is matched and activated along with the "Recurse"
rule. Notice the multiple restrictions on field sequence
that test for equality with 1
or 2
:
Rule "Bootstrap"
rule "Bootstrap" when f : Fibonacci( sequence == 1 || == 2, value == -1 ) // multi-restriction then modify ( f ){ value = 1 }; System.out.println( f.sequence + " == " + f.value ); end
You can also use the Agenda View in your IDE to investigate the state of the decision engine agenda. The "Bootstrap"
rule does not fire yet because the "Recurse"
rule has a higher salience value.
図7.8 Rules "Recurse" and "Bootstrap" in Agenda View 1
When a Fibonacci
object with a sequence
of 1
is asserted, the "Bootstrap"
rule is matched again, causing two activations for this rule. The "Recurse"
rule does not match and activate because the not
conditional element stops the rule matching as soon as a Fibonacci
object with a sequence
of 1
exists.
図7.9 Rules "Recurse" and "Bootstrap" in Agenda View 2
The "Bootstrap"
rule sets the objects with a sequence
of 1
and 2
to a value of 1
. Now that you have two Fibonacci
objects with values not equal to -1
, the "Calculate"
rule is able to match.
At this point in the example, nearly 50 Fibonacci
objects exist in the working memory. You need to select a suitable triple to calculate each of their values in turn. If you use three Fibonacci patterns in a rule without field constraints to confine the possible cross products, the result would be 50x49x48 possible combinations, leading to about 125,000 possible rule firings, most of them incorrect.
The "Calculate"
rule uses field constraints to evaluate the three Fibonacci patterns in the correct order. This technique is called cross-product matching.
The first pattern finds any Fibonacci
object with a value != -1
and binds both the pattern and the field. The second Fibonacci
object does the same thing, but adds an additional field constraint to ensure that its sequence is greater by one than the Fibonacci
object bound to f1
. When this rule fires for the first time, you know that only sequences 1
and 2
have values of 1
, and the two constraints ensure that f1
references sequence 1
and that f2
references sequence 2
.
The final pattern finds the Fibonacci
object with a value equal to -1
and with a sequence one greater than f2
.
At this point in the example, three Fibonacci
objects are correctly selected from the available cross products, and you can calculate the value for the third Fibonacci
object that is bound to f3
.
Rule "Calculate"
rule "Calculate" when // Bind f1 and s1. f1 : Fibonacci( s1 : sequence, value != -1 ) // Bind f2 and v2, refer to bound variable s1. f2 : Fibonacci( sequence == (s1 + 1), v2 : value != -1 ) // Bind f3 and s3, alternative reference of f2.sequence. f3 : Fibonacci( s3 : sequence == (f2.sequence + 1 ), value == -1 ) then // Note the various referencing techniques. modify ( f3 ) { value = f1.value + v2 }; System.out.println( s3 + " == " + f3.value ); end
The modify
statement updates the value of the Fibonacci
object bound to f3
. This means that you now have another new Fibonacci
object with a value not equal to -1
, which allows the "Calculate"
rule to re-match and calculate the next Fibonacci number.
The debug view or Audit View of your IDE shows how the firing of the last "Bootstrap"
rule modifies the Fibonacci
object, enabling the "Calculate"
rule to match, which then modifies another Fibonacci
object that enables the "Calculate"
rule to match again. This process continues until the value is set for all Fibonacci
objects.
図7.10 Rules in Audit View