4

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?

MWB
  • 11,740
  • 6
  • 46
  • 91
  • If I understand your notation correctly, then yes, the Drools engine does allow for function evaluation within both conditions and consequences. I can't speak for other engines, though. – Roddy of the Frozen Peas Jan 04 '21 at 13:17
  • The same for CLIPS – Gary Riley Jan 05 '21 at 18:23
  • @RoddyoftheFrozenPeas *"function symbols"* in logic might not be the same thing as *"functions"* elsewhere. Here's a litmus test: Can you use a logical variable as an argument given to those *"functions"* when you are stating the rules? (See the second example in the Q) – MWB Jan 06 '21 at 17:35
  • @GaryRiley Please see my reply to *Roddy*. – MWB Jan 06 '21 at 17:37
  • @MaxB The concept of a function symbol is not clear to me. – Gary Riley Jan 07 '21 at 17:43
  • @GaryRiley They let you say things like "If someone's father is rich then he/she is rich too": `rich(father(X)) → rich(X)`. Here `father` is a function symbol. – MWB Jan 07 '21 at 17:50
  • @MaxB What is the difference between your first and second examples in a language such as Prolog? – Gary Riley Jan 07 '21 at 19:10
  • @GaryRiley Can you ask in the *prolog* tag instead of commenting here? – MWB Jan 07 '21 at 21:12
  • 1
    @MaxB I just mentioned Prolog because you did. If there's no easy way to explain function args or why you'd want to use them, it's going to be hard for someone to answer your question.Your examples don't shed any light on what function args do. – Gary Riley Jan 07 '21 at 21:35
  • @GaryRiley Function symbols (sic) are a part of first-order logic definition. I'd say try stating `rich(father(X)) → rich(X)` in CLIPS. You could (sort of) state it like this `rich(X) ^ father(X, Y) -> rich(Y)`, but it's different, because function symbols imply existence and uniqueness of `father` of someone. In Prolog, function symbols are used to define all data structures. – MWB Jan 07 '21 at 23:37
  • @GaryRiley BTW, they are optional in FOL, not so in Prolog: https://math.stackexchange.com/questions/125818/first-order-logic-why-do-we-need-function-symbols – MWB Jan 07 '21 at 23:42
  • At this point is question is too broad. There's not going to be one person who can write one answer for every rule engine under the sun. If you want to know about Drools, and can formulate a plain-english "rule" psuedo code, then someone like me can answer whether it's possible or supported. If you want to know about CLIPs, someone like Gary could do the same. – Roddy of the Frozen Peas Jan 08 '21 at 16:47
  • @RoddyoftheFrozenPeas Was my example not "plain English" enough? Let me try again: *"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"* . If you are a drools expert and don't even understand the concept of function symbols, it sounds like drools doesn't have them. – MWB Jan 08 '21 at 17:18
  • Jeez no need to be rude. I haven't done formal logic since I was 12, @MaxB. Excuse me for not remembering my elementary school fundamentals that I've never had need for professionally. The problem with your example is there's no consequence. If I meet your conditions, then what? You only have half a rule there. I can write you a rule that detects when your conditions are violated, or I can write you a rule for when when your conditions are met. You haven't indicated which of those you're interested in, or what is supposed to _happen_ in that event. – Roddy of the Frozen Peas Jan 08 '21 at 23:59
  • My point is that your question is too broad because there's no _one_ answer. – Roddy of the Frozen Peas Jan 08 '21 at 23:59
  • @RoddyoftheFrozenPeas The Q is for people who understand FOL. If you don't, that doesn't make it a problem with the Q. (BTW, I very much doubt that FOL is part of any elementary school curriculum) – MWB Jan 15 '21 at 17:53
  • Doubt what you'd like about curricula, but it's still too broad a question because there cannot be a single answer. – Roddy of the Frozen Peas Jan 15 '21 at 18:06
  • Also it's worth pointing out that Drools is now based on phreak, not rete. Drools 5 (I think) was the last that was pure rete. Phreak is similar but based on collections rather than tuples. – Roddy of the Frozen Peas Jan 15 '21 at 18:11

2 Answers2

2

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)))
Gary Riley
  • 10,130
  • 2
  • 19
  • 34
  • There are really two rules. The first one ( *"For every person, there exists one and only one father of said person"* ) needs to state an existence. I don't see it in your code. – MWB Jan 15 '21 at 18:01
  • That's what the forall statement does. – Gary Riley Jan 15 '21 at 18:39
  • Why do you even need forall? Even without the wrapping it around forall this rule executes the same way, doesn't it? – Akaedintov Jan 16 '21 at 16:15
  • @Akaedintov No, it won't. The forall is shorthand for (not (person ?p) (not (and (father ?p ?f) (not (father ?p ~?f)))). It's necessary to guarantee that every person has one and only one father. – Gary Riley Jan 16 '21 at 21:22
0

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.

Roddy of the Frozen Peas
  • 14,380
  • 9
  • 49
  • 99
  • The rule should **state** "for every person, there exists one and only one father ...". Instead, you are using his existence as a condition. In your interpretation, the `father` field should never be null. Is Drools unable to state it unconditionally? – MWB Jan 15 '21 at 17:48
  • In a world of conditions and consequences, what is a statement? I've treated it like a condition. Since a statement can be true or it can be false, it seemed like an appropriate way to model it. If the statement is true, the rule evaluates; if the statement is false, it does not (unless you invert the condition.) – Roddy of the Frozen Peas Jan 15 '21 at 18:06
  • Drools is a _business rules language_. It's not intended for modeling abstract logical constructs. If you have temperature sensors and the statement "if any sensor reports > 120 degrees continuously for 3 minutes, then turn on the fire alarm" ... we can do that with drools. Your rich man/poor man example half translates _if_ you treat it like a conditional -- but your rules care whether you want to know if it holds true or if it holds false and that will change how you write your rule. – Roddy of the Frozen Peas Jan 15 '21 at 18:07