Prolog backtracking VS Rete backtracking

Question

In my class I have been taught the Prolog backtracking algorithm and the Rete forprop algorithm, but I have also been told that Rete can be used to do backprop.

How does that work? In which ways is it similar / different to Prolog backtracking?

For example, this is one of the exercises I have been given:

(R1) 24fingers and antennas => origin(mars)
(R2) shy and 5feet => origin(mars)
(R3) shy and 4arms => origin(venus)
(R4) looksDownWhenTalking => shy
(R5) fleesWhenSeen => shy

The goal is given the following facts find the origin of the alien:

(F1) fleesWhenSeen
(F2) 4arms

In Prolog, we would solve it by pattern matching the goal origin(X) against the RHS of the rules. The rule matches against R1, R2 and R3, so first R1 will be triggered, and we would try to resolve the subgoals 24fingers and antennas which would fail.

Then we would go backtrack to the beginning and trigger R2, which eventually will fail, and finally backtrack and trigger R3, which succeeds.

So X ends up binded to venus in a successful query, and the algorithm ends.

Now, how would we solve the same exercise using the rete backprop algorithm?

I naively assume that we would use a list of subgoals, starting with origin(X), to start triggering rules whose RHS matches the subgoals.

But it isn't clear to me how the Rete algorithm would take care of backtracking when some subgoals fail, or how would it know that it has succeed once it resolves a certain subset of goals.

The rete algorithm is strictly forward-chaining. Maybe some engines primarily based on rete, do also support backward-chaining, yet the used algorithm cannot be the rete algorithm. Can you add some links to resources that claim to use rete and backward chaining? — CoronA
@CoronA this was in my college exercises, when I asked my teacher how to the exercises she went on to resolve them using Prolog-like backtracking, which only confused me further. If you are confident backtracking with rete is not a thing that is an answer I am satisfied with. — Jsevillamol
@Jsevillamol: I think that most RETE-based systems support queries that are backward chaining, but these queries are not processed with the RETE-Algorithm, but others (SLD-Resolution as in Prolog, Semi-Naive-Bottom-Up-Evaluation or Magic-Sets-Evaluation like in Deductive Databases) — CoronA
@G_V: The RETE-Algorithm and SLD-Resolution both are deductive algorithms. Backward-Chaining and Forward-Chaining are both deductive. Inductive reasoning is a subject beyond Rete and Prolog. All facts derived with inductive reasoning may be wrong (which is not the case for deductive reasoning). — CoronA
@G_V: Forward chaining allows you to derive facts from other facts. Inductive reasoning allows you to guess facts. Thats completely different. A rule frog => green means that all frogs are green. In this world there are no brown frogs. Inductive reasoning on this rule would propose that a given object that is green may (!) be a frog. Yet in this world there may be also other objects that are green and a green object that is not a frog is perfectly consistent with a world based on this rule. — CoronA

Gary Riley Gary Riley · Accepted Answer · 2018-02-12T19:47:42

There is no standard implementation for supporting backward chaining in a forward chaining system. Hybrid tools have implemented this functionality using different techniques. One technique, data-driven backward chaining, is described here: http://haleyai.com/wordpress/2008/03/11/goals-and-backward-chaining-using-the-rete-algorithm/. Some additional information: JESS vs DROOLS : Backward chaining and http://herzberg.ca.sandia.gov/docs/70/rules.html.

Prolog backtracking VS Rete backtracking

2 Answers