Fibonacci Example

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:

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

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

Figure 8.6. Fibonacci Example: "Recurse" Audit View 1

Fibonacci Example: "Recurse" Audit View 1

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.

Figure 8.7. Fibonacci Example: "Recurse" Agenda View 1

Fibonacci Example: "Recurse" 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. 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.

Figure 8.8. Fibonacci Example: "Recurse" Agenda View 2

Fibonacci Example: "Recurse" Agenda View 2

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.

Figure 8.9. Fibonacci Example: "Bootstrap" Audit View

Fibonacci Example: "Bootstrap" Audit View