Learning Prolog: Lab Session #5 - Backtracking

The new learning prolog banner!

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:


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

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

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!

Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blender blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing dns docker documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions freeside future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro minetest network networking nibriboard node.js open source operating systems optimisation own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference release releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg systemquery talks technical terminal textures thoughts three thing game three.js tool tutorial tutorials twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 worldeditadditions xmpp xslt


Art by Mythdael