Why does Prolog automatically backtrack in one case but not in another?

I have a Prolog program with two predicates, rr and p, each with its own set of rules and facts. When querying these predicates with specific inputs, I noticed that Prolog automatically backtracks in one case but not in the other.

rr(f(X,Y),g(Z)) :- rr(Y,Z).
rr(a,a).

p(X,Y,f(a)) :- p(X,X,Y).
p(X,X,X).

Queries:

?- rr(f(a,f(b,a)),X).
X = g(g(a)).
?- p(X,a,f(X)).
X = a ;
false.

As you can see, the first query doesn't perform any backtracking, while the second one automatically lets you choose between the first solution or perform backtracking manually.

[trace]  ?- rr(f(a,f(b,a)),X).
   Call: (10) rr(f(a, f(b, a)), _27336) ? creep
   Call: (11) rr(f(b, a), _28554) ? creep
   Call: (12) rr(a, _29312) ? creep
   Exit: (12) rr(a, a) ? creep
   Exit: (11) rr(f(b, a), g(a)) ? creep
   Exit: (10) rr(f(a, f(b, a)), g(g(a))) ? creep
X = g(g(a)).

[trace]  ?- p(X,a,f(X)).
   Call: (10) p(_33908, a, f(_33908)) ? creep
   Call: (11) p(a, a, a) ? creep
   Exit: (11) p(a, a, a) ? creep
   Exit: (10) p(a, a, f(a)) ? creep
X = a ;
   Redo: (10) p(_33908, a, f(_33908)) ? creep
   Fail: (10) p(_33908, a, f(_33908)) ? creep
false.

When printing the trace, both programs chose a path that ends at an empty statement, but the second one automatically detects backtracking, why does Prolog behave this way? Is it able to detect in the first case that the other possible solution is not valid beforehand?

Solution

Backtracking happens when the Prolog engine chooses a path through your code, and leaves a choicepoint to return and try the other possible paths. If the system can quickly tell that one path cannot lead to answers, it can ignore that path and never come back to try it. This does not change the answers (a backtracking prompt is not itself an answer), it is a performance optimisation - doing less work means finishing sooner. It would be valid to leave a choicepoint on rr/2, but not useful.

One strategy for this is first argument indexing: in rr/2 the shape of the first argument is different:

rr(f(X,Y), ...
rr(     a, ...

The query ?- rr(f(..,..), .. cannot unify the first argument with a and that can be identified quickly before leaving a choicepoint and backtracking to try the full call later on. In p/2:

p(X, ...
p(X, ...

Both first arguments are the same, there's no quick way to rule one out, so it leaves a choicepoint and tries the first one, and can go back and try the second clause later if needed.

SWI Prolog does several kinds of indexing, described here:

Just In Time (JIT) Indexing
- Static code with a choice between [_|_] and [] for quickly recursing over a list to the end.
- Linear scan on first argument, looking for a deterministic (no choicepoints) result.
- Hashtable lookup of predicates satisfying some non-trivial conditions.
Indexing Databases
- using term_hash/2 and term_hash/4 to customise indexes on some of your predicates.

Other Prolog systems have other strategies which may lead to performance strengths and weaknesses in different types of code; I think first argument indexing is implemented in many systems.