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 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.
Let’s create a new file called
relationships.pl with the following facts like this:
and then we do the following query:
How does PROLOG check it? To better understand backtracking - and also the data flow for the query - you can use the command
Now we have the new command line inside the trace environment. Just do the same query again:
[trace] ?- like(maria,X), like(john, X).
- 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 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
X != food.
- The first clausel is instantiated with
- 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!