Having some fun with Prolog

It’s been a while since I wrote anything here, but now that my reading activities expanded again since I got my new Kindle I guess it’s time to share again.

I started looking over 7 Languages in 7 seven weeks by Bruce A. Tate. It’s a book presenting 7 different programming languages starting from their typing model, their programming model (OO, functional, procedural or some hybrid) to what are the core unique features of the language that make it so special. It’s a very well structured book that will enlighten the way you look and approach the learning of a new programming language. I highly recommend it.

One of the languages presented here is Prolog. I remember studying Prolog in university but to be honest it didn’t really got my attention back then. But now at a second look, after 6 years of OOP, functional and structured programming looking at Prolog is quite interesting. I consider having a completely different mindset when looking over a programming language really broadens your horizon and gives you unique new view in problems solving.

Prolog is a logic declarative programming language.Most of the languages we use day by day are imperative – you describe the data structures and the instructions step by step and the computer executes them. Nothing is inferred for you by the computer, he just does what it’s told to. In Prolog, being a declarative language, you declare some facts and inferences and the language does the reasoning for you. These are the main data building blocks:

• Facts: an assertions about something – for example: Vadim is a programmer; programmers like to code.
• Rules: a rule is a reasoning about the given facts – for example: A person likes to code if it’s a programmer.
• Query: a question about the given facts: Does Vadim like to code?

This should be enough for background, let’s get a grasp of some code examples. I’ll use GNU Prolog for the examples. Let’s state some facts – in a file called prefs.pl:

likes(paul, programming).
likes(vadim, programming).
likes(ian, fishing).
friend(X, Y) :- \+(X  = Y), likes(X, Z), likes(Y, Z).

The first 3 lines represent facts. The word “likes” can be replaced with any other word of our choice. So vadim and paul like programming and ian likes fishing. Don’t be afraid of the last line, it’s quite easy in the end. Notice the use of capitalisation in the last line, in Prolog capitalised words are variables and others are atoms that have a fixed value that can’t be changed. The last line is a rule and it describes our preferred rudimentary friendship relation: X and Y are friends if X is not equal to Y [ \+(X = Y) ] and if both X and Y like the same Z. Now let’s load this file into the Prolog interpreter (launching gprolog binary from the same dir where we saved prefs.pl) and see what’s going on.

| ?- ['prefs'].
compiling /Users/vadim/mycode/prolog/prefs.pl for byte code...
/Users/vadim/mycode/prolog/prefs.pl compiled, 
5 lines read - 947 bytes written, 4 ms

(1 ms) yes
| ?- likes(vadim, fishing).
no
| ?- likes(vadim, programming).
yes
| ?- friend(vadim, vadim).
no
| ?- friend(vadim, ian).
no
| ?- friend(vadim, paul).
yes

The responses about the given facts are quite intuitive. What’s interesting are the responses using the friend rule: vadim is not a friend with vadim because they are the same person, vadim is not a friend with ian because they don’t like the same activity but vadim is a friend with paul as they are both into programming. It’s not a bug, Prolog actually answers with yes and no – this is something new from what we’ve seen before, clearly.

Let’s try an example a little more complex, map colouring. The idea is to color a map so that two adjacent regions do not have the same color. The image below represents the map.

Let’s see how the code looks like. First we define 4 colours (it’s the minimum number of colours we can use for this map):

different(red,green). different(red,blue). different(red,yellow).
different(green,red). different(green, blue). different(green, yellow).
different(blue,red). different(blue, green). different(blue, yellow).
different(yellow, red). different(yellow, green). different(yellow, blue).

Now that we have the colours let’s state the rule that defines which squares on the map are adjacent:

coloring(One, Two, Three, Four, Five) :-
different(One, Two),
different(One, Three),
different(One, Four),
different(One, Five),
different(Two, One),
different(Two, Three),
different(Two, Four),
different(Three, One),
different(Three, Two),
different(Three, Four),
different(Four, One),
different(Four, Two),
different(Four, Three),
different(Four, Five),
different(Five, One),
different(Five, Four).

Now let’s run the code in the Prolog interpreter and see what’s going on. All the code was defined in a file called map.pl like in the previous example. Here is the result:

| ?- ['map'].
compiling /Users/vadim/mycode/prolog/map.pl for byte code...
/Users/vadim/mycode/prolog/map.pl compiled, 
20 lines read - 3017 bytes written, 7 ms

(1 ms) yes
| ?- coloring(One, Two, Three, Four, Five).

Five = green
Four = yellow
One = red
Three = blue
Two = green ? 

yes

Now the result and the code is quite amazing. We have a solution and is absolutely correct. The complexity of the code is very low, and what strucks me the most is the fact that the algorithm does not even exist. Imagine solving a problem like this in an imperative language. Illustrate your problem so that Prolog understands it and it will solve it for you. Now this raises interesting questions and deep thoughts. Are we using the computer at his full potential? Wouldn’t it be nice to have the computer solve our day to day problems without telling him exactly what to do? Delegating to a computer not to someone else … interesting. What do you think?