Learning Prolog: Lab Session #5 - Backtracking
The next lab in the series introduces the idea of backtracking. Apparently Prolog is somewhat persistent in its attempts to prove things that you ask it, leading it to go back to where it last had a choice and try a different route when faced with failure.
Let's take this dataset (or knowledge base) for example:
food(apple,fruit). food(tomato,fruit). food(lettuce,salad). food(beef,meat). food(cucumber,salad).
This is a simple set of foods, along with their types.
What if we were lazy and wanted to get Prolog to output all the different salad foods in the above dataset? It's too much work for us to us (there might be thousands of lines to search in future), so let's insert the following lines:
display_salad_food :- food(Food,salad), write(Food), write(' is a salad'), nl, fail.
The above is a rule that can be satisfied by fetching a food of type salad. It then writes out the food to the console, then a new line, and then hits
fail - a brick wall that tells Prolog that it, well, erm... failed. This causes Prolog to backtrack to the last choice it made (in this case
food(Food,salad)) and try finding a different route. Here's some example output from the above:
?- display_salad_food. lettuce is a salad cucumber is a salad false
This construct is called a failure driven loop. This is because it gets Prolog to try all possibilities by backtracking - causing it to fail over and over again while it searches out alternative routes.
The other thing this lab introduced was
repeat predicate. This acts as a 'checkpoint', so to speak, which lets Prolog continue from this point, even if it doesn't find any path to take. Here's an example, though I should warn you that running it will crash Prolog! (unless you are using the web based editor or course - then you can just hit the abort button)
hello_world :- write('Hello '), repeat, write('World'), nl, fail.
And here's some example output:
Hello World World World World World World World World World World ...
The reason it crashes is because it contains an infinite loop. Prolog writes out
Hello,, and writes out
World and a new line, and then hits
fail. Going back, it spots a repeat statement, which allows it to continue. It then writes out
World again, hits the
fail, and so on and on and on.....
That concludes this post about lab #5. If you found it helpful, please comment (I love reading comments)! Suggestions and constructive criticism are always welcome too!