Forward chaining like Rete algorithm in rule engine?

I don’t know why RETE (OPS5) still keeps showing up – its flagship example was the XCON (R1) configurator that had a few hundred rules and was almost impossible to maintain (I remember having a conversation with someone at DEC; as I recall they had a full-time team of ~5 people for maintaining it). RETE/OPS5 suffers from two problems: a global store where values can be changed (which trigger other changes) and no backtracking.

A configurator in Prolog for the same domain would be easier to both write and maintain, especially if it took advantage of the the more modern support for constraint solving.


How similar is the Soar cognitive architecture to Rete … both seem to be sophisticated forward chaining systems …

Also … can you give a few hints how you see modern constraint solving contribute …

@peter.ludemann @ @grossdan , I’m only familiar with RETE because of NRules, a popular open-source c# rule engine. If there were a popular and complete c# Prolog implementation, I’d use it. However, I’ve run into problems with asking questions on this forum and then trying to implement in csprolog . There is no table function for example. So, my choice seems to be using SWI-Prolog through some kind of server architecture or switching to a rule engine. One of the many nice things about Prolog is that it handles the facts and the rules. The rule engine is designed to apply rules to c# objects (the “facts”).

@peter.ludemann , I’m not sure exactly what you mean by “configurator”, but Microsoft recently made Guan available, in part to support “configuration-as-logic”. Guan uses Prolog syntax.

This seems to be a better showcase for Guan than the examples shown. While it has the basics, there is still much missing.

Here are pointers to the DEC configurator: Xcon - Wikipedia
It could handle things such as "customer has ordered a VAX-11/780 with 6 SCSI disks, so that requires 2 SCSI controllers; the disks will be in 1 rack, which will also require 2 3meter cables plus 4 1meter cables (daisy-chained). [SCSI cables were quite expensive, so optimizing the cabling was beneficial]

(I was asked to implement something similar for Intergraph … the project never happened for a number of reasons; one of them being that my recommendation that before starting the project, two departments at Intergraph should coordinate with each other, so that I could figure out the requirements; another suggestion was that instead of figuring out the ideal SCSI cables, the customer engineers could just take a few extra cables with them when they did the initial setup – neither of these suggestions were popular with the feuding managers at Intergraph … ahh, the life of an honest consultant.)

1 Like

First, note I don’t have answers for your questions.

(1) But as I just skimmed through the Wikipedia entry about Rete, now I wonder what do you mean by ‘… to see where they lead like the Rete algorithm does …’. I guess that Jan’s suggestion about tabling was a bit provocatory, as I expected more an hint to s(CASP), where forward chaining and explanations are more focused.

(2) RDF is a really low level representation, RDFs is the immediate upper level, and you should try to express your (Rete?) rules in it. If I were you, I would study this post from Jan. Done that, start looking into OWL. Note that I’m suggesting resources that AFAIK were not available when I had to attempt to grasp these arguments. But I feel that you can’t go wrong with Cambridge univ :slight_smile:

1 Like

Thanks @CapelliC . Please note that Cambridge Semantics is a software company.

RDF & OWL keep coming up both in this forum and in my own research. For some reason, every fact needing to be a URL annoys me. But, the general idea of triples (or quads) is attractive. As an alternative, I also really like the property graph concept.

Tabling and s(CASP) are quite different beasts. They both address reasoning in cyclic domains including negation. Tabling provides Well Founded Semantics where s(CASP) provides Stable Model Semantics. s(CASP) stresses creating an explanation. Tabling does not. Tabling scales a lot better than s(CASP). It all depends …


I’m curious about one thing. CHR was mentioned above, and it is a derivative of RETE, having the same performance profile and support for rules with multiple heads. But the conversation continued just ignoring that language. What issues do people have that the search for a good tool continues?

CHR has a decent implementation in SWI. It supports backtracking via prolog choicepoints.

It does feature a global store so it does present difficulties managing scope, but you can split the store across modules. Though you can’t write a rule that depends on facts in separate modules, one module can easily add facts in another, triggering rules in that other. You can also introduce unique ids to your constraints to have execution particular to a cluster of facts created around a particular id.

It’s easy to work with in the small. In the large, it’s a new paradigm requiring new skills just as getting into Prolog required new skills. But it exists here and does RETE style forward chaining.


That’s why I don’t like RETE – it doesn’t have backtracking.

In the end, it doesn’t matter whether you use forward-chaining or backwards-chaining; just as it doesn’t matter whether you use bottom-up or top-down execution (e.g., datalog can be implemented bottom-up, using magic sets). It’s simply a matter of efficiency and completeness.

RETE was a “nice try”; as was PLANNER; and I think their good ideas have been absorbed into things like CHR and Prolog. I suppose some people prefer procedural thinking to logical thinking (and assignment to unification), which is why RETE keeps on resurfacing (but nobody seems to revisit PLANNER, CONNIVER, etc.).

1 Like

I’m still a bit confused about CHR. It seems to have only operational semantics, right? The nice thing about Prolog+Tabling, Datalog, ASP and s(CASP) is that they have a well understood logical semantics. I never cared too much, but a recent project made me appreciate logical semantics. It notably seems easier to explain to non-programmer that the formalization of some text as a (logic) program is correct.

Of course, CHR has proved to be an elegant language for many problems.

1 Like

I’m always fascinated by the conversations my naive questions trigger. I learn so much just by lurking. Thanks everyone.


Thomas Frühwirth, who authored CHR, proposed a declarative semantics.


I have the CHR book, in which is described all the sorts of semantics one might hope to find in a logical language. You can take a simple program and prove consistency, correctness, completeness, etc. without necessarily looking at the operations, provided you code within certain boundaries. (Pretty much you could make the same statement regarding Prolog code.) In practice in either language I tend to think operationally in constructing a predicate, and declaratively in using it.


CHR has two kinds of declarative semantics: First-order logic declarative semantics and Linear logic declarative semantics.

Because CHR can model changes by removing and adding constraints, not each CHR program has First-order logic semantics, but it has linear logic semantics.

For example,

duplicate @ X leq Y \ X leq Y <=> true.
reflexivity @ X leq X <=> true.
antisymmetry @ X leq Y , Y leq X <=> X=Y.
transitivity @ X leq Y , Y leq Z ==> X leq Z.

This CHR program has First-order logic reading:

∀ X,Y (X≤Y ∧ X≤Y ⇔ X≤Y)  ∧ 
∀X (X≤X ⇔ true)  ∧ 
∀ X,Y (X≤Y ∧ Y≤X ⇔ X=Y)  ∧ 
∀ X,Y,Z (X≤Y ∧ Y≤Z ⇒ X≤Z)

However, the following CHR program has no First-order logic reading:

throw(Coin) <=> Coin = head
throw(Coin) <=> Coin = tail

If you insist on First-order logic reading, it will be

∀Coin.(throw(Coin) ⇔ (Coin=head)) ∧ 
∀Coin.(throw(Coin) ⇔ (Coin=tail))

This is obvious wrong.

But it has linear logic reading:

!∀Coin.(throw(Coin) ⊸ !(Coin=head)) ⊗
!∀Coin.(throw(Coin) ⊸ !(Coin=tail))

which logically equivalent to:

!∀Coin.(throw(Coin) ⊸ !(Coin=head)) ⊗
        (throw(Coin) ⊸ !(Coin=tail))

which logically equivalent to:

!∀Coin.(throw(Coin) ⊸ !(Coin=head) & !(Coin=tail))

This formula reads as “Of course, consuming throw(Coin) produces: choose from Coin=head and Coin=tail”. In other words, we can replace throw(Coin) with either Coin=head or Coin=tail but not both at the same time, i.e. a committed choice takes place.

Note that the penultimate logical equivalence uses “universal quantifiers distribution over ⊗”, I haven’t see this theorem on the internet, but intuitively it ought to be the same as “universal quantifiers distribution over ∧” in first order logic.

1 Like

Perhaps this next question deserves (or has already received?) its own thread. Can anyone familiar with Prolog and Datalog explain their differences? I ask because I notice that the Clojure JVM language has been used to develop many datalog implementations. EDIT: found a partial answer here: What's the difference between Prolog and Datalog?

In the current implementation, the second rule tends to be moot, and in general it is advised not to write this pair of rules, because programs including them often don’t have clear semantics.


When discussing declarative semantics, they (CHR book and lots of CHR papers) just use abstract operational semantics, not concrete implementation.

Here the 2nd rule will never be fired.

However, from wikipedia:

Additive conjunction (A & B) represents alternative occurrence of resources, the choice of which the consumer controls.

So from consumer’s perspective, we can make a choice by reordering the rule.