Name: Fibonacci Main class: org.drools.examples.FibonacciExample Type: Java application Rules file: Fibonacci.drl Objective: Demonstrates Recursion, the CE <kw>not</kw> and cross product matching
The Fibonacci Numbers (see http://en.wikipedia.org/wiki/Fibonacci_number) discovered by Leonardo of Pisa (see http://en.wikipedia.org/wiki/Fibonacci) is a sequence that starts with 0 and 1. The next Fibonacci number is obtained by adding the two preceding Fibonacci numbers. The Fibonacci sequence begins with 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.
The single fact class Fibonacci
is used in this
example. It has two fields, sequence and value. The sequence field
is used to indicate the position of the object in the Fibonacci
number sequence. The value field shows the value of that
Fibonacci object for that sequence position, using -1 to indicate
a value that still needs to be computed.
Example 8.22. 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... }
Execute the example:
Open the class org.drools.examples.FibonacciExample
in your Eclipse IDE.
Right-click the class and select "Run as..." and then "Java application"
Eclipse shows the following output in its console window (with "...snip..." indicating lines that were 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 field of 50. A recursive rule is then used
to insert the other 49 Fibonacci
objects. This example
doesn't use
PropertyChangeSupport
. It uses the MVEL dialect, which
means we can use the <kw>modify</kw> 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 rule Recurse is very simple. It 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
<kw>not</kw> conditional element is used to stop the rule's matching
once we have all 50 Fibonacci objects in memory. The rule also has a
salience value, 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 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.
When a Fibonacci
object with a sequence field of 2 is
asserted the "Bootstrap" rule is matched and activated along with the
"Recurse" rule. Note the multi-restriction on field
sequence
, testing for equality with 1 or 2.
Example 8.26. Fibonacci Example: 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
At this point the Agenda looks as shown below. However, the "Bootstrap" rule does not fire because the "Recurse" rule has a higher salience.
When a Fibonacci
object 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 <kw>not</kw> conditional element stops the rule's matching
as soon as a Fibonacci
object with a sequence of 1
exists.
Once we have two Fibonacci
objects with values
not equal to -1 the "Calculate" rule is able to match. It was
the "Bootstrap" rule that set the objects with sequence 1 and 2 to
values of 1. At this point we have 50 Fibonacci objects in the Working
Memory. Now we need to select a suitable triple to calculate each
of their values in turn. Using three Fibonacci patterns in a rule without
field constraints to confine the possible cross products would result
in 50x49x48 possible combinations, leading to about 125,000 possible rule
firings, most of them incorrect. The "Calculate" rule uses field
constraints to correctly constraint the thee Fibonacci patterns 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 this, too, but
it adds an additional field constraint to ensure that its sequence is
greater by one than the Fibonacci bound to f1
. When this
rule fires for the first time, 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 sequence 2. The
final pattern finds the Fibonacci with a value equal to -1 and 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 calculate the value for the
third Fibonacci
object that's bound to f3
.
Example 8.27. Fibonacci Example: 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 rechniques. modify ( f3 ) { value = f1.value + v2 }; System.out.println( s3 + " == " + f3.value ); end
The <kw>modify</kw> statement updated the value of the
Fibonacci
object bound to f3
. This means
we now have another new Fibonacci object with a value not equal to -1,
which allows the "Calculate" rule to rematch and calculate the next
Fibonacci number. The Audit view below shows 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 match again.
This continues till the value is set for all Fibonacci
objects.