Introduction

The Fibonacci Numbers, invented by Leonardo of Pisa 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.

Running the Fibonacci Example

Change into the drools-examples directory and run the Fibonacci example:

D:\java\workspaces\drools-2.0>maven fibonacci-java
 __  __
|  \/  |__ _Apache__ ___
| |\/| / _` \ V / -_) ' \  ~ intelligent projects ~
|_|  |_\__,_|\_/\___|_||_|  v. 1.0

(bunch of output)

fibonacci-java:
    [java] Using drl: fibonacci.java.drl
    [java] recurse for 50
    [java] recurse for 49
    [java] recurse for 48
    [java] recurse for 47
    [java] recurse for 46
    [java] recurse for 45
    [java] recurse for 44
    [java] recurse for 43
    [java] recurse for 42
    [java] recurse for 41
    [java] recurse for 40
    [java] recurse for 39
    [java] recurse for 38
    [java] recurse for 37
    [java] recurse for 36
    [java] recurse for 35
    [java] recurse for 34
    [java] recurse for 33
    [java] recurse for 32
    [java] recurse for 31
    [java] recurse for 30
    [java] recurse for 29
    [java] recurse for 28
    [java] recurse for 27
    [java] recurse for 26
    [java] recurse for 25
    [java] recurse for 24
    [java] recurse for 23
    [java] recurse for 22
    [java] recurse for 21
    [java] recurse for 20
    [java] recurse for 19
    [java] recurse for 18
    [java] recurse for 17
    [java] recurse for 16
    [java] recurse for 15
    [java] recurse for 14
    [java] recurse for 13
    [java] recurse for 12
    [java] recurse for 11
    [java] recurse for 10
    [java] recurse for 9
    [java] recurse for 8
    [java] recurse for 7
    [java] recurse for 6
    [java] recurse for 5
    [java] recurse for 4
    [java] recurse for 3
    [java] recurse for 2
    [java] 1 == 1
    [java] 2 == 1
    [java] 3 == 2
    [java] 4 == 3
    [java] 5 == 5
    [java] 6 == 8
    [java] 7 == 13
    [java] 8 == 21
    [java] 9 == 34
    [java] 10 == 55
    [java] 11 == 89
    [java] 12 == 144
    [java] 13 == 233
    [java] 14 == 377
    [java] 15 == 610
    [java] 16 == 987
    [java] 17 == 1597
    [java] 18 == 2584
    [java] 19 == 4181
    [java] 20 == 6765
    [java] 21 == 10946
    [java] 22 == 17711
    [java] 23 == 28657
    [java] 24 == 46368
    [java] 25 == 75025
    [java] 26 == 121393
    [java] 27 == 196418
    [java] 28 == 317811
    [java] 29 == 514229
    [java] 30 == 832040
    [java] 31 == 1346269
    [java] 32 == 2178309
    [java] 33 == 3524578
    [java] 34 == 5702887
    [java] 35 == 9227465
    [java] 36 == 14930352
    [java] 37 == 24157817
    [java] 38 == 39088169
    [java] 39 == 63245986
    [java] 40 == 102334155
    [java] 41 == 165580141
    [java] 42 == 267914296
    [java] 43 == 433494437
    [java] 44 == 701408733
    [java] 45 == 1134903170
    [java] 46 == 1836311903
    [java] 47 == 2971215073
    [java] 48 == 4807526976
    [java] 49 == 7778742049
    [java] 50 == 12586269025
    [java] fibanacci(50) == 12586269025 took 130ms

BUILD SUCCESSFUL
Total time: 32 seconds
Finished at: Sun Jun 20 13:44:39 PDT 2004

Understanding the Fibonacci Example

We can simulate the Fibonacci invention in Drools and demonstrate conflict resolution on the way.

Our fibonacci number is represented by our Fibonacci Class, where sequence is the numbers position and value is the numbers value:

public class Fibonacci
{
    private int sequence;
    private long value;

    public Fibonacci(int sequence)
    {
        this.sequence = sequence;
        this.value    = -1;
    }

    public int getSequence()
    {
        return this.sequence;
    }

    public void setValue(long value)
    {
        this.value = value;
    }

    public long getValue()
    {
        return this.value;
    }

    public String toString()
    {
        return "Fibonacci(" + this.sequence + "/" + this.value + ")";
    }
}

We create a single Fibonacci object with a value of 50 which we then assert into the Working Memory and then call fireAllRules:

WorkingMemory workingMemory = ruleBase.newWorkingMemory();

Fibonacci fibonacci = new Fibonacci( 50 );

long start = System.currentTimeMillis();

workingMemory.assertObject( fibonacci );

workingMemory.fireAllRules();

long stop = System.currentTimeMillis();

System.err.println( "fibanacci(" + fibonacci.getSequence() + ") == " + 
fibonacci.getValue() + " took " + (stop-start) + "ms" );

The fibonacci.java.drl rule 'Recurse' then recurses backwards creating and asserting 50 objects into our Working Memory, notice we have assigned a salience value of '10' to this rule.

<rule name="Recurse" salience="10">
    <parameter identifier="f">
      <class>Fibonacci</class>
    </parameter>
    <java:condition>f.getValue() == -1</java:condition>
    <java:consequence>
      System.err.println( "recurse for " + f.getSequence() );
      drools.assertObject( new Fibonacci( f.getSequence() - 1 ) );
    </java:consequence>
  </rule>

We use two bootstraps, using the value field, to start our system counting back up again; calculating the fibonacci number. The first bootstrap is triggered when we assert a Fibonacci number fact into the Working Memory with a sequence of 2, this changes the value to 1 and then lets the Working Memory know the fact has changed:

<rule name="Bootstrap 2">
    <parameter identifier="f">
      <class>Fibonacci</class>
    </parameter>
    <java:condition>f.getSequence() == 2</java:condition>
    <java:condition>f.getValue() == -1</java:condition>
    <java:consequence>
      f.setValue( 1 );
      System.err.println( f.getSequence() + " == " + f.getValue() );
      drools.modifyObject( f );
    </java:consequence>
  </rule>

This means that when the Fibonacci fact with a sequence of 2 is first asserted into the Working Memory we have a conflict; our number currently has a value of -1, thus satisfying 'Recurse', but it also has a sequence of '2', satisfying 'Bootstrap 2'. If 'Bootstrap 2' was to fire first it would modify the facts value to 1, thus removing 'Recurse' from the Agenda as its conditions would no longer be satisfied. Without 'Recurse' firing, to assert a fact with a sequence of 1, our application would end. To overcome this we give 'Recurse' a salience value of 10, 'Bootstrap 2' would have a default of 0; this means that Recurse would fire first, asserting our object with a sequence of 1 into the Working Memory and then Bootstrap 2 would fire.

At this point we have another conflict resolution; the fibonacci fact with a sequence of 1 and a value of -1 satisfies both 'Recurse' and 'Bootstrap 1'.

<rule name="Bootstrap 1" salience="20">
    <parameter identifier="f">
      <class>Fibonacci</class>
    </parameter>

    <java:condition>f.getSequence() == 1</java:condition>
    <java:condition>f.getValue() == -1</java:condition>
    <java:consequence>
      f.setValue( 1 );
      System.err.println( f.getSequence() + " == " + f.getValue() );
      drools.modifyObject( f );
    </java:consequence>
  </rule>

If 'Recurse' was to fire then we would start adding objects with a negative sequence into the working memory, this is not desirable. Instead we give 'Bootstrap 1' a salience of 20, 'Recurse' is 10; this means that 'Bootstrap 1' fires first. 'Bootstrap 1' modifies the fact giving it a value of 1 which also causes 'Recurse' to be removed from the Agenda ; avoiding the negative sequence problem.

Once we have two facts with values that are not equal to -1 'Calculate' fires.

<rule name="Calculate">
    <parameter identifier="f1">
      <java:class>org.drools.examples.fibonacci.Fibonacci</java:class>
    </parameter>
    <parameter identifier="f2">
      <java:class>org.drools.examples.fibonacci.Fibonacci</java:class>
    </parameter>
    <parameter identifier="f3">
      <java:class>org.drools.examples.fibonacci.Fibonacci</java:class>
    </parameter>
    <java:condition>f2.getSequence() == (f1.getSequence() + 1)</java:condition>
    <java:condition>f3.getSequence() == (f2.getSequence() + 1)</java:condition>
    <java:condition>f1.getValue() != -1</java:condition>
    <java:condition>f2.getValue() != -1</java:condition>
    <java:condition>f3.getValue() == -1</java:condition>
    <java:consequence>
      f3.setValue( f1.getValue() + f2.getValue() );
      System.err.println( f3.getSequence() + " == " + f3.getValue() );
      drools.modifyObject( f3 );
      drools.retractObject( f1 );
    </java:consequence>
  </rule>

'Calculate' matches three Fibonacci facts and then uses the getSequence conditions to make sure we bind the write fact to the correct facthandle; f1, f2, f3. 'Calculate' calculates the new fibonacci number and assigns it to fact handle f3; drools.modifyObject( f3 ) is then called letting the Working Memory know that a fact has changed, f1 is removed from the Working Memory as it is no longer needed for any further calculations.