Name: Fibonacci Main class: org.drools.examples.FibonacciExample Type: java application Rules file: Fibonacci.drl Objective: Demonsrates Recursion, 'not' CEs and Cross Product Matching
The Fibonacci Numbers, http://en.wikipedia.org/wiki/Fibonacci_number, invented by Leonardo of Pisa, http://en.wikipedia.org/wiki/Fibonacci, are obtained by starting with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. The first Fibonacci numbers for n = 0, 1,... are: * 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946... The Fibonacci Example demonstrates recursion and conflict resolution with Salience values.
A single fact Class is used in this example, Fibonacci. It has two fields, sequence and value. The sequence field is used to indicate the position of the object in the Fibonacci number sequence and the value field shows the value of that Fibonacci object for that sequence position.
Example 8.22. Fibonacci Class
public static class Fibonacci { private int sequence; private long value; ... setters and getters go here... }
Execute the example:
Open the class org.drools.examples.FibonacciExample
in your Eclipse IDE
Right-click the class an select "Run as..." -> "Java application"
And Eclipse shows the following output in its console, "...snip..." shows repeated bits removed to save space:
Example 8.23. Fibonacci Example Console Output
recurse for 50 recurse for 49 recurse for 48 recurse for 47 ...snip... recurse for 5 recurse for 4 recurse for 3 recurse for 2 1 == 1 2 == 1 3 == 2 4 == 3 5 == 5 6 == 8 ...snip... 47 == 2971215073 48 == 4807526976 49 == 7778742049 50 == 12586269025
To kick this off from java we only insert a single Fibonacci object, with a sequence of 50, a recurse rule is then used to insert the other 49 Fibonacci objects. This example doesn't use PropertyChangeSupport and uses the MVEL dialect, this means we can use the modify keyword, which allows a block setter action which also notifies the engine of changes.
Example 8.24. Fibonacci Example Execution
ksession.insert( new Fibonacci( 50 ) ); ksession.fireAllRules();
The recurse rule is very simple, it matches each asserted Fibonacci object with a value of -1, it then creates and asserts a new Fibonacci object with a sequence of one less than the currently matched object. Each time a Fibonacci object is added, as long as one with a "sequence == 1" does not exist, the rule re-matches again and fires; causing the recursion. The 'not' conditional element is used to stop the rule matching once we have all 50 Fibonacci objects in memory. The rule also has a salience value, this is because we need to have all 50 Fibonacci objects asserted before we execute the Bootstrap rule.
Example 8.25. Fibonacci Example : 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
The audit view shows the original assertion of the Fibonacci object with a sequence of 50, this was done from Java land. From there the audit view shows the continual recursion of the rule, each asserted Fibonacci causes the "Recurse" rule to become activate again, which then fires.
When a Fibonacci with a sequence of 2 is asserted the "Bootstrap" rule is matched and activated along with the "Recurse" rule.
Example 8.26. Fibonacci Example : Rule "Bootstrap"
rule Bootstrap when f : Fibonacci( sequence == 1 || == 2, value == -1 ) // this is a multi-restriction || on a single field then modify ( f ){ value = 1 }; System.out.println( f.sequence + " == " + f.value ); end
At this point the Agenda looks like the figure shown below. However the "Bootstrap" rule does not fire as the "Recurse" rule has a higher salience.
When a Fibonacci with a sequence of 1 is asserted the "Bootstrap" rule is matched again, causing two activations for this rule; note that the "Recurse" rule does not match and activate because the 'not conditional element stops the rule matching when a Fibonacci with a sequence of 1 exists.
Once we have two Fibonacci objects both with values not equal to -1 the "calculate" rule is able to match; remember it was the "Bootstrap" rule that set the Fibonacci's with sequences 1 and 2 to values of 1. At this point we have 50 Fibonacci objects in the Working Memory and we some how need to select the correct ones to calculate each of their values in turn. With three Fibonacci patterns in a rule with no field constriants to correctly constrain the available cross products we have 50x50x50 possible permutations, thats 125K possible rule firings. The "Calculate" rule uses the field constraints to correctly constraint the thee Fibonacci patterns and in the correct order; this technique is called "cross product matching". The first pattern finds any Fibonacci with a value != -1 and binds both the pattern and the field. The second Fibonacci does too but it adds an additional field constraint to make sure that its sequence is one greater than the Fibonacci bound to f1. When this rule first fires we know that only sequences 1 and 2 have values of 1 and the two constraints ensure that f1 references sequence 1 and f2 references sequence2. The final pattern finds the Fibonacci of a value == -1 with a sequence one greater than f2. At this point we have three Fibonacci objects correctly selected from the available cross products and we can do the maths calculating the value for Fibonacci sequence = 3.
Example 8.27. Fibonacci Example : Rule "Calculate"
rule Calculate when f1 : Fibonacci( s1 : sequence, value != -1 ) // here we bind sequence f2 : Fibonacci( sequence == (s1 + 1 ), value != -1 ) // here we don't, just to demonstrate the different way bindings can be used f3 : Fibonacci( s3 : sequence == (f2.sequence + 1 ), value == -1 ) then modify ( f3 ) { value = f1.value + f2.value }; System.out.println( s3 + " == " + f3.value ); // see how you can access pattern and field bindings end
The MVEL modify keyword updated the value of the Fibonacci object bound to f3, this means we have a new Fibonacci object with a value != -1, this allows the "Calculate" rule to rematch and calculate the next Fibonacci number. The Audit view below shows the how the firing of the last "Bootstrap" modifies the Fibonacci object enabling the "Calculate" rule to match, which then modifies another Fibonacci object allowing the "Calculate" rule to rematch. This continues till the value is set for all Fibonacci objects.