A practical introduction to backtracking in Prolog

Madeleine Malmsten
4 min readSep 3, 2018

--

Prolog (“Programming in Logic”) is, in my opinion, with no doubt the most forgotten and underestimated programming language there is. It was developed at the University of Marseilles in 1972 and was intended to be a tool for working with natural languages, before turning out to be a quite popular and commercially successful language during the late seventies.

A characteristic for Prolog is that logical rules are applied to the knowledge base to retrieve new information (a semantic inference engine), which means that Prolog counts as classic Artificial Intelligence.

So, if you’re lazy enough to appreciate a programming language that’s solving the problems for you instead of following your instructions of what to do, Prolog is your language. Prolog is with its beautiful syntax very simple and concrete; the only tricky thing is to know what to ask for to get what you want.

Some terminology (because why not make this more confusing)

In Prolog you don’t have functions, but the closest to these are predicates. The program and the database are build up by one or more predicates, and each predicate is one, or a set of, clauses. A clause can only return true; otherwise it fails. Two clauses belong to the same predicate if they have the same name and the same number of arguments. If you want something to be globally accessible, you can assert it to the internal database.

A small prerequisite

If you haven’t already, and if you want to follow along trying some coding yourself, install SWI Prolog and run swipl. The installation page is found here: http://www.swi-prolog.org/download/stable

Let’s go!

So let’s say I just got found a few pokemons, and to keep track of their colours and traits, I assert them to the database:

asserta(pokemon(charizard,orange,strong)),
asserta(pokemon(pikachu,yellow,electric)),
asserta(pokemon(gyarados,blue,destructive)),
asserta(pokemon(lugia,purple,telepathic)),
asserta(pokemon(mew,pink,cute)),
asserta(pokemon(mewtwo,pink,telepathic)),
asserta(pokemon(gengar,purple,ghost)),
asserta(pokemon(eevee,brown,cute)),
asserta(pokemon(jigglypuff,pink,cute)),
asserta(pokemon(squirtle,blue,cute)).

I can confirm that they’re asserted by running the following:

?- listing(pokemon).
:- dynamic pokemon/3.
pokemon(squirtle, blue, cute).
pokemon(jigglypuff, pink, cute).
pokemon(eevee, brown, cute).
pokemon(gengar, purpule, ghost).
pokemon(mewtwo, pink, telepathic).
pokemon(mew, pink, cute).
pokemon(lugia, purpule, telepathic).
pokemon(gyarados, blue, destructive).
pokemon(pikachu, yellow, electric).
pokemon(charizard, orange, strong).
true.

Perfect!

Prolog will always try to return true, so let’s say that I want to find a purple pokemon:

?- pokemon(Pokemon,purple,Trait).Pokemon = gengar,
Trait = ghost .

As you see I add a clause with only one declared argument. Prolog will then try to find the first pokemon in the list above that has the color purple. I can do it again, and this time I’m trying to find a telepathic pokemon:

?- pokemon(Pokemon,Color,telepathic).Pokemon = mewtwo,
Color = pink .

I can also combine these ones, and search for a pokemon that is both purple and telepathic:

?- pokemon(Pokemon,purple,telepathic).Pokemon = lugia.

Demonstrated above is a typical example of logic programming and backtracking.

Easy peasy?

Well, then let’s make this slightly more complex. Say that I want to have two different pokemons which are of the same color. Here, I’d like to ask for Pokemon1 and Pokemon2 of the same color (remember, variables/ arguments are immutable). Also, Pokemon1 and Pokemon2 shouldn’t be the same one. Prolog uses backtracking to find the combination of the two pokemons.

?- pokemon(Pokemon1,Color,_),
| pokemon(Pokemon2,Color,_),
| \+ Pokemon1 = Pokemon2.
Pokemon1 = squirtle,
Color = blue,
Pokemon2 = gyarados

So let’s crank it up a bit — this is when it starts to become more interesting! Say that I want a predicate where the first argument declares how many pokemons I want, and the second argument is a list of the pokemons most similar to each other regarding color and traits. The best scenario would be if the pokemons are of matching color and traits, the second best scenario is matching traits, and the third-best scenario is a matching color. The set of pokemons should be unique; there shouldn’t be another pokemon in the database equally matching the criteria!

find_pokemons(Pokemons,Length) :-
clause(pokemon(_,Color,Trait), _),
findall({Pokemon,Color,Trait},
pokemon(Pokemon,Color,Trait), Pokemons),
length(Pokemons, Length).
find_pokemons(Pokemons,Length) :-
clause(pokemon(_,_,Trait), _),
findall({Pokemon,Color,Trait},
pokemon(Pokemon,Color,Trait), Pokemons),
length(Pokemons, Length).
find_pokemons(Pokemons,Length) :-
clause(pokemon(_,Color,_), _),
findall({Pokemon,Color,Trait},
pokemon(Pokemon,Color,Trait), Pokemons),
length(Pokemons, Length).

Let’s start by requesting a list of exactly two pokemons. As you can see, the pokemons are of matching color and trait.

?- find_pokemons(Pokemons, 2).
Pokemons = [{jigglypuff, pink, cute}, {mew, pink, cute}]

When asking for three pokemons

?- find_pokemons(Pokemons, 3).
Pokemons = [{jigglypuff, pink, cute}, {mewtwo, pink, telepathic}, {mew, pink, cute}]

Moreover, when asking for four pokemons

?- find_pokemons(Pokemons, 4).
Pokemons = [{squirtle, blue, cute}, {jigglypuff, pink, cute}, {eevee, brown, cute}, {mew, pink, cute}]

Also, when asking for five pokemons, there is no good match to be found after trying all combinations. Returning false. If this happens, Prolog starts backtracking the predicate calling find_pokemons/2, if possible.

?- find_pokemons(Pokemons, 5).
false.

And when asking for N pokemons, prolog will find the first pokemon(s) in the database that has a unique set of color and trait.

?- find_pokemons(Pokemons, N).
Pokemons = [{squirtle, blue, cute}],
N = 1

This seems amazing, how do I get started?

SWI Prolog has the most amazing documentation I’ve ever seen.
http://www.swi-prolog.org/pldoc/

Anne Ogborn has published a bunch of very nice and useful examples on her Github.
https://github.com/Anniepoo/prolog-examples

SWI Prolog regularly announces courses and resources on their Twitter account.
https://twitter.com/SWI_Prolog

Here is a nice introduction to Prolog, step by step
https://www2.cs.arizona.edu/classes/cs372/fall06/prolog.sli.pdf

--

--

Madeleine Malmsten
Madeleine Malmsten

Written by Madeleine Malmsten

Developer / Staff Engineer with a soft spot for functional and logic programming.