Logic: The art of thinking and reasoning in strict accordance with the limitations and incapacities of the human misunderstanding. Ambrose Bierce

Power PROLOG \o/

In my last post we finally wrote our “Hello World!” in PROLOG. I hope you all bare with me, so we can finally start to explore the fun and powerful features of PROLOG. In this post, I am going to write about Backtracking.

Backtracking

When PROLOG is looking for instances that satisfies a clause, it will, whenever it is needed, perform what we call Backtrack. This is an automated concept which makes PROLOG a powerful language, as the programmer doesn’t need to implement it. Warning: the use of backtracking without understanding the internals of PROLOG can cost lots of resources and make the code inefficient.

Example:

Let’s create a new file called relationships.pl with the following facts like this:

like(maria, food).
like(maria, wine).
like(john, wein).
like(john, maria).

and then we do the following query:

?- consult("relationships.pl").
true.

?- like(maria,X), like(john, X).
X = wine ;
false.

How does PROLOG check it? To better understand backtracking - and also the data flow for the query - you can use the command trace:

?- trace.
true.
[trace]  ?-

Now we have the new command line inside the trace environment. Just do the same query again:

[trace]  ?- like(maria,X), like(john, X).
   Call: (9) like(maria, _7168) ? creep
   Exit: (9) like(maria, food) ? creep
   Call: (9) like(john, food) ? creep
   Fail: (9) like(john, food) ? creep
   Redo: (9) like(maria, _7168) ? creep
   Exit: (9) like(maria, wine) ? creep
   Call: (9) like(john, wine) ? creep
   Exit: (9) like(john, wine) ? creep
X = wine ;
   Redo: (9) like(john, wine) ? creep
   Fail: (9) like(john, wine) ? creep
false.
  • As we can see, first like(maria,X).was checked;
  • X is instantiated with the value food.
  • Then PROLOG will check, if the second clausel is also true for X = food.
  • As there is no clause like(john,food). this instance for X will fail.
  • In this moment, backtracking happens and X is un instantiated.
  • PROLOG will try to find an instance of like(maria,X) where X != food.
  • The first clause is instantiated with wein.
  • PROLOG will check, if the second clause is also true for X = wein.
  • As there is the clause like(john, wine).in our file, the user (we!) are notified.
  • We want to see other possibilities - we type ;

Always when a clause fails, backtrack will happen and the instantiated variables in that clause will be cleared, but the variables instantiated before that clause will be kept. Also when a solution is found and the user (we again!) wants to see another solution, the variables that were instantiated in the last clause will be freed and the proofing process will be restarted after the actual situation.

As one can see, this can become a really expensive process. In order to control the data flow, there is a special mechanism called cut. This is going to be my next post!