CODEWITHSUNDEEP
prologlogicdatalog
J Bellamy
J Bellamy

Reputation: 159

Backwards Chaining With Variables

I have been reading up about inference in Prolog/Datalog and while forward chaining seems fairly simple to grasp, I have some issues with backward chaining with any sort of complex example which isn't simply propositional or used to determine a true or false value. I was reading an article the following example was given:

sg(X,X)
sg(X,Y) :- par(X, X1), par(Y,Y1), sg(X1,Y1)

Suppose we were to query sg(a,W) where a is a constant and W is a variable. This could be read as saying:

Give me all those who are in the same generation as a.

The article firstly states that these particular rules will result in an infinite loop in Prolog/Datalog, but can be fixed by changing the second rule to:

sg(X,Y) :- par(X, X1),  sg(X1,Y1), par(Y,Y1).

Why would the original result in a loop? Secondly, what would the execution of this kind of query look like? When do values get bound to these variables?

Upvotes: 1

Views: 727

Answers (1)

pasaba por aqui
pasaba por aqui

Reputation: 3529

The article seems not be very explicative. Assume the call is "sg(a,W)". Let analize first possibility:

sg(X,Y) :- par(X, X1), par(Y,Y1), sg(X1,Y1)

first "par" will be queried as "par(X=a,X1)", next as "par(Y=W,Y1)". This last query is a totally unbound query, and probably is what the article tries to skip.

Now, the second possibility:

 sg(X,Y) :- par(X, X1),  sg(X1,Y1), par(Y,Y1).

is executed as par(X=a,X1), sg(X1 /* bound in previous /, Y1), par(Y=W,Y1/ bound in previous */). As you can see, in all queries at least one of the arguments has been previously bound.

Upvotes: 1

Related Questions