Fibonacci Example

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:

  1. Open the class org.drools.examples.FibonacciExample in your Eclipse IDE

  2. 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.

Figure 8.6. Fibonacci Example "Recurse" Audit View 1

Fibonacci Example "Recurse" Audit View 1

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.

Figure 8.7. Fibonacci Example "Recurse" Agenda View 1

Fibonacci Example "Recurse" Agenda View 1

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.

Figure 8.8. Fibonacci Example "Recurse" Agenda View 2

Fibonacci Example "Recurse" Agenda View 2

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.

Figure 8.9. Fibonacci Example "Bootstrap" Audit View 1

Fibonacci Example "Bootstrap" Audit View 1