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.

(Pastebin, Raw)

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!