PROLOG - Part 6


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 clausel, 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 indiscriminated use of backtracking without understanding the internals of PROLOG can cost lots of resources and make the code ineficient.

Example:

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

1
2
3
4
like(maria, food).
like(maria, wine).
like(john, wein).
like(john, maria).

and then we do the following query:

1
2
3
4
5
6
?- 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:

1
2
3
?- trace.
true.
[trace] ?-

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

1
2
3
4
5
6
7
8
9
10
11
12
13
[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 clausel like(john,food). this instance for X will fail.
  • In this moment, backtracking happens and X is deinstantiated.
  • PROLOG will try to find an instance of like(maria,X) where X != food.
  • The first clausel is instantiated with wein.
  • PROLOG will check, if the second clausel is also true for X = wein.
  • As there is the clausel like(john, wine).in our file, the user (we!) are notified.
  • We want to see other possibilities - we type ;

Always when a clausel fails, backtrack will happen and the instantiated variables in that clausel will be cleared, but the variables instantiated before that clausel 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 clausel will be fred and the proofing proccess 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!