“Logic: The art of thinking and reasoning in strict accordance with the limitations and incapacities of the human misunderstanding.” Ambrose Bierce
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.
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.
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. 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
- X is instantiated with the value
- Then PROLOG will check, if the second clausel is also
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
X != food.
- The first clause is instantiated with
- 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!