Prolog :- Mind = Blown.

About 7 years ago I wrote my first Hello World program. It’s been that long that I’ve been friends with programming but not a single programming language inspired me enough to write about it. Until today. Before judging me, know that I’ve been through a good chunk of languages – C, C++, Python, Java, Javascript, PHP, Ruby, Lisp, HTML5, CSS. And I like them, every single one of them (except Lisp, maybe). However, even after coding in all of these, nothing sparked a fire like Prolog did today.
So, what exactly does Prolog have which others don’t?
Brain. Prolog is a fast smartass shit.

I did AI course last semester and had to code AI programs in a language of my choice. Throughout the semester, I kept switching between Java and Python, writing programs to solve problems of graph coloring, of n-queens, of missionaries and cannibals, etc. We wrote a tic-tac-toe player which will always either win or draw the game, and some other puzzle/game solvers too that I don’t particularly remember right now.

Quick explanation : If I’m writing code for missionaries & cannibals problem, I don’t find out the logic myself and then write a program to perform those steps. That’s not an AI program. I write a search algorithm, which executes and tries to find what would be an optimum step to take at each step, then the algorithm takes that step, and proceeds, in search of the ‘solution’. So, what I used to do in such AI programs was define the whole problem using some data structures in the language, define initial and final states, and write a search algorithm that used to make(find) a path to go from initial to final state. I still remember how happy I was at seeing this :

Achievement unlocked. First AI program ran successfully. The missionaries and cannibals case solved. #Happy

A photo posted by Bhavul Gauri (@bhavul93) on

It was the simplest of all AI programs, but still this was a level up. My program was not dumb anymore. It was not just following some steps as I told it to, but was searching on its own and making its own path. Oh come on, don’t you feel great when you act as a mentor to someone and then they succeed on their own? It was a similar feeling, you can say. The program listened to my advice on living life, and it solved the freaking problem that was bugging it off in its life.
However, that was still not enough to blow my mind off.

So, let me tell you what happened today.

I was learning and practicing Prolog because I’m one of the guys handling labs of AI this semester, and my thesis revolves around ILP which again requires Prolog. In course of going through the easiest and kindest book for it, Learn Prolog Now, I reached exercise 6.6, which was apparently the last question of the last chapter I wanted to deal with for today.

Before I jump to that question, I should tell you a little about Prolog. Prolog is a different language than the standard ones. It was aimed to be a logic programming language, and it almost succeeds at its aim. What a complete logic programming language is supposed to have is the ability to insert the right logic for any sort of problem in any sort of world, to solve any solvable problem in that world. Prolog comes pretty close to that, as we’ll see.

What this means is, we don’t tell Prolog what to do. We just tell it about our world, and the question/problem. And, it answers on its own. It’s like that bright student in the class, who knows how to work things out inside his/her head without the teacher.

Here’s a very small glimpse.

big(bear).             % Tell Prolog that a bear is big
big(elephant).         % Tell Prolog an elephant is big
small(cat).            % Tell Prolog a cat is small
brown(bear).           % Tell Prolog a bear is brown
black(cat).            % Tell Prolog a cat is black
gray(elephant).        % Tell Prolog an elephant is gray
dark(X) :- black(X).   % Tell Prolog that anything is dark IF it is black
dark(X) :- brown(X).   % Tell Prolog that anything is dark IF it is brown

Hopefully, you should be able to understand the simple syntax given the comments with prefixed ‘%’. This, above, is my Prolog file, the program code.

Now, if I load this file and ask Prolog, “What is it that is dark and big?”
Prolog answers ‘elephant and bear’.
Tell me, What other language will do this given you just tell it about the ‘world’ and its ‘rules’?
Don’t be harsh, now! I know it looks simple to us. But, when a 2-3 year old baby, who has just started speaking and understanding the world is able to (logically) infer anything out of what all data it has learnt, you give him a pat on the back.

Prolog is able to figure out stuff, by itself. I don’t have to tell Prolog how to search for an answer or how to understand and apply the rules. Prolog has this capability built-in to understand any sort of ‘world'(facts) and its ‘laws’ (rules) and then solve any problem that can be solved with logic. Period.

Isn’t that the future for us? When computers will be intelligent in general, like humans, and we will be dumb (because relatively amazingly slow) people just telling computers about all that we have in our hands, and asking if ‘X’ problem can be solved with all the data and rules in place? Think about it.

Now, of course, even though I asked you not to be harsh, I was. I did like Prolog’s recursive ways to find out answers by matching facts and rules, but I was not impressed yet. Then, I came across the following question:

Exercise 6.6 Here is an exercise for those of you who like logic puzzles.

There is a street with three neighbouring houses that all have a different colour, namely red, blue, and green. People of different nationalities live in the different houses and they all have a different pet. Here are some more facts about them:

The Englishman lives in the red house.
The jaguar is the pet of the Spanish family.
The Japanese lives to the right of the snail keeper.
The snail keeper lives to the left of the blue house.
Who keeps the zebra? Don’t work it out for yourself: define a predicate zebra/1 that tells you the nationality of the owner of the zebra!

(Hint: Think of a representation for the houses and the street. Code the four constraints in Prolog. You may find member/2 and sublist/2 useful.)

This is a basic first-order logic problem. A bigger problem of the same form exists which is famously called Einstein Puzzle and rumoured to be solved by just 2% (mostly a false rumour) human population.

You pick up a pen, try to work it out, and you’ll come at the solution in a few minutes if not less. However, solving this requires intelligence, because not everything is provided here. I tried writing a Prolog code for this but failed. To tell you the truth, our minds work just like Prolog’s, we think procedurally. We get so good at logic, that we are better at solving the problem than being able to present the problem to someone very gracefully.

So, I looked up the code someone else had written. If you know Prolog, or have started learning it, I urge you to first try to code solution for this before looking at the code below. And Those who have no idea about Prolog can skip trying to bang their heads over understanding the following small obscure code.

zebra(X) :- %% zebra(X,[H0,H1,H2]) :-
member(house(red, english, _), [H0,H1,H2]),
member(house(_, spanish, jaguar), [H0,H1,H2]),
sublist([house(_, _, snail), house(_, japanese, _)], [H0,H1,H2]),
sublist([house(_, _, snail), house(blue, _, _)], [H0,H1,H2]),
member(house(_, X, zebra), [H0,H1,H2]).

Here’s the translation of above code in pure english.
Line 1: Zebra is owned by X IF (all of what I tell henceforth satisfy)
Line 2: a red colored house owned by Englishman having i-don’t-know-and-don’t-care pet is one of the houses on the street.
Line 3: an i-don’t-know-and-don’t-care colored house owned by spanish guy having a jaguar pet is one of the houses on the street.
Line 4: Whichever way these houses are present on the street, a house with i-don’t-know-and-don’t-care color and i-don’t-know-and-don’t-care owner having snail as a pet appears just before (read left of) the house with i-don’t-know-and-don’t-care color but japanese owner having i-don’t-know-and-don’t-care pet.
Line 5: Whichever way these houses are present on the street, a house with i-don’t-know-and-don’t-care color and i-don’t-know-and-don’t-care owner having snail as a pet appears just before (read left of) the house with blue color and i-don’t-know-and-don’t-care owner having i-don’t-know-and-don’t-care pet.
Line 6: a i-don’t-know-and-don’t-care colored house with owner X having zebra as a pet is one of the houses on the street. Find X.

That is all I did in the code.
Read the question again, and read these 6 translated lines.
I have exactly framed the problem to the language, not written any sort of algorithm. If I was using Java/C++/Python, and I would write a translation of my program to solve the same question, the translation would be including loops, functions, stacks, queues and god knows what not. But, nope. Prolog doesn’t ask for any of that.
And yet, as soon as I ask Prolog, who owns the zebra?
It answers – japanese owns it. In milliseconds! Compare that to yourself. Isn’t this a thing for which Prolog deserves a round of applause?

This is a new level up for me. Till last semester when I was writing small AI codes, my code was intelligent. Now, my language itself is intelligent. I love logic and I was startled at the logical capabilities of Prolog (so far what I’ve been referring to as its intelligence). That is why this post took birth.


If this post or some other thing has made you interested in Prolog and you wish to learn more, I’ve just now written down a quick summary of all I learnt about Prolog. I think this would be the shortest (and one of the fastest) introduction to Prolog you can find on the internet right now. You can download that here.

However, if you wish to go for more standard and beautifully written sources, Learn Prolog Now and the book by Ivan Bratko will suit your needs.

* Intelligence has been defined in many different ways such as in terms of one’s capacity for logic, abstract thought, understanding, self-awareness, communication, learning, emotional knowledge, memory, planning, creativity and problem solving. The post above primarily talks of intelligence in terms of one’s capacity for logic and abstract thought (and maybe understanding). When you add ‘learning’ to that, you approach Inductive logic programming. We’ll cover more on that as I start working on my thesis. Thanks for reading. Hope you liked it.

bhavul

Tech always fascinates me. And sometimes, I'm able to find time to share that with you all. I'm a software developer working at Endurance International Group. Learning and teaching as I walk. Hope you find something cool here.

3 Comments

  1. You have a flair for making these topics seem reachable for programmophobic people like me. And your own interest seeps through the post as well. Good job!

Leave a Reply

Your email address will not be published. Required fields are marked *