CODEWITHSUNDEEP
artificial-intelligencerule-enginefirst-order-logicrete
MWB
MWB

Reputation: 12617

Are function symbols allowed in rule engines / Rete algorithm?

AI: A Modern Approach brings up the Rete algorithm when discussing inference in first-order logic.

However, all descriptions of the Rete algorithm I found seem to use rules free of function symbols. In other words, rules look like

a(X) ∧ b(X, Y) → c(Y)

but not

a(f(X)) ∧ b(X, Y) → c(f(Y))

(The difference can be fundamental, as it is the difference between Prolog and Datalog, only one of which is Turing-complete)

Is the Rete algorithm limited to rules free of function symbols? Do modern rule engines like Drools and CLIPS handle function symbols?

Upvotes: 4

Views: 302

Answers (2)

Roddy of the Frozen Peas
Roddy of the Frozen Peas

Reputation: 15219

The problem with your example is that Drools works against Java objects. The conditional "every person has exactly one father" is taken care of by defining the Father variable as an instance and not as a List. That simplifies the check to just being a null check.

In Drools, this is how you'd implement this plain English use case:

For every person, there exists one and only one father of said person, and if a person's father is rich, then so is he/she.

rule "A person has a rich father and is rich"
when
  not( Person(father == null ))

  $person: Person( $father: father,
                            isRich == true )
  Person( isRich == true ) from $father
then
  // Insert consequences here
end

The right hand side of this rule (the consequence) will trigger for each person who is rich, and whose father is rich. The not clause at the beginning verifies that all Person instances in your working memory have father's. Each person passed into working memory is evaluated on their individual merits, even if multiple persons are passed in.

Basically how you'd read it would be: "All persons have a father. Every rich person has a rich father." If you inert the design of the object and check children you could assert something like "if person is rich then all children are rich".

For completeness' sake, the Java class modelled here looks like this:

public class Person {
  private Person father;
  private boolean isRich;
  public Person getFather() { return this.father; }
  public Person getIsRich() { return this.isRich; }
  // Setter methods omitted for brevity
}

Of course, if instead you're trying to test for situations you don't meet this condition, you could of course invert it:

rule "A person exists without a father"
when
  exists( Person( father == null) )
then
  // Do something for situation if there's a father-less person
end

rule "A person is rich and their father is not rich"
when
  Person( $father: father != null, 
                   isRich == true )
  Person( isRich == false ) from $father
then
  // Do something for the poor father
end

... where of course you could combine them into a single rule but it's considered bad rule design.

Drools is a business rules language. It's intended to use on combinations of conditions and consequences -- "if these conditions are true, then do this". Your scenario is a simple statement instead of a conditional+consequence, so it's a little hard to model here since it lacks consequences.

It does have the benefit of implicitly being applied against every input without having to specify loops or recursive functions, however. The way the above (both the positive and negative cases) would be invoked, would be to create a collection of Person instances and pass them in all at once into the session. Drools will evaluate each Person instance on its own merits against the inputs. Any changes to these instances without calling one of the special Drools 'refresh' functions (update, insert, modify, retract) will be ignored in terms of evaluating if the rule is valid. So for example, if I pass in a father-less Person instance, and then in one of my rules add a Person, from the "when" clause perspective my Person is still fatherless; the rules are evaluated against the immaculate inputs unless I specifically inform Drools otherwise using the above-mentioned functions.

Upvotes: 0

Gary Riley
Gary Riley

Reputation: 10757

In CLIPS, this is how you'd implement the rule "For every person, there exists one and only one father of said person, and if a person's father is rich, then so is he/she":

(defrule inherited-wealth
   (forall (person ?p)
           (father ?p ?f)
           (not (father ?p ~?f)))
   (person ?p)
   (father ?p ?f)
   (rich ?f)
   =>
   (assert (rich ?p)))

Upvotes: 2

Related Questions