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?
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.