Developer

Bootstrap Series: Learn Prolog (Part 1)

Bootstrap Series: Learn how to use the declarative language Prolog. This tutorial utilises a Web based Prolog interpreter, so no messing around with installation is necessary.

This is to be the first of several articles introducing languages that are not the most common topic of conversation around Joe Average's work-place water-cooler.

This week we're looking at Prolog — a declarative language. It's interesting because the way it functions is entirely different to the most popular programming languages out there. To catergorise some of the common languages:

Procedural:
C
VB 6.0

Object-Oriented:
C# .Net
VB .Net
Java
Python

Functional:
Haskell

Declarative:
Prolog

A declarative language is one in which you state facts, and how these facts relate to one another. Prolog is modelled closely on the structure of Formal Logic. Those who have seen FOL before may feel more comfortable with the syntax. Programmers will find it easier to move between languages in the same bracket (e.g. VB .Net and C# .Net — which are practically identical), but harder to jump across categories. This is why the movement to a functional language is difficult for the legions of people who are strictly Procedural or Object-Oriented.

dog(rover).

This is an example of a statement in Prolog. To most people, it will look a lot like a half-baked function declaration. Well, you're partly right. It is a declaration — but not of a function — of a fact. In this case, "dog" is a relation, and "rover" is an atom. An atom is little more than a name. It is not an integer, a string or a class. It has no properties, and no type. It is just a name with no substance. This is the most important thing to get your mind around. The important thing is how these atoms relate to each other.

N.B. It's useful to note that all atoms in Prolog must start with a lower-case letter.

An atom has no real worth in this language without being meaningfully related to something. In the above example, the relationship "dog" is wrapped around the atom "rover". This can be read as "rover is a dog", much like a predicate in Formal Logic. Prolog is now aware that there is something called "rover" and that it's a "dog". It has no idea what a dog is, and really doesn't care — as long as you, the programmer, are happy it means something.

parent(john, kate).
parent(joan, kate).

female(joan).
female(kate).
male(john).

This code introduces another relationship, this time with two arguments. This means the relationship has an arity of two (two arguments - simple, no?). Relationships have no code behind them apart from what's seen above. Most programmers would be clambering to find the definition of "parent", but you will not find one. It doesn't need a definition. It is a perfectly complete prolog application as it stands above.

How then, you may well be asking, does the interpreter know whether john is kate's parent, or kate is john's parent?
It doesn't — and it doesn't matter as long as the relationship makes sense to you. We will choose to say that parent(X, Y) means that "X is a parent of Y". This way kate has two parents - john and joan. Now the fun starts...

parent(john, kate).
parent(joan, kate).

female(joan).
female(kate).
male(john).

mother(X, Y) :- female(X), parent(X, Y).

This is where we start to see the power of the language. The new statement "mother(X,Y)" introduces two new concepts:
1) Variables — Variables in Prolog are considered to be any word that starts with an uppercase letter — in this case X and Y. By contrast, as mentioned before, atoms start with a lowercase letter ("kate", "joan", "john"). A variable can be subsituted by any atom that exists in the program.
2) Conditions — The initial statement made, "mother(X, Y)", is followed by a colon and a dash ":-". This is followed by the conditions under which the initial statement is true. In English, it can be read as "X is the mother of Y, IF X is female and X is the parent of Y".

It's pointless going any further without explaining the other side of Prolog — Querying. The only thing you've seen so far is how to declare "facts". Querying allows us to ask questions to the Prolog interpreter about what it knows. A simple way to see Prolog in action is to go here. You can copy the code above into the top text area and type queries into the text box beneath it.

Try the following questions in the query box:
female(joan).
This will return "Yes" indicating that joan is a girl.
parent(joan, kate).
This will also return "Yes" because joan is a parent of kate.

This next one is interesting and will tell you more than what you've directly typed in. If you use a variable in a query (symbolised by starting with (or being) a capital letter) Prolog will figure out all of the possible values for the variable that still agree with all the facts. So, if you run the query:
parent(X, kate).
Prolog returns the following (plus some timing information I've stripped out):

X=john
yes

X=joan
yes

The Prolog engine determined that the query is true if it substitutes "john" in for X, or "joan" in for X. Try the query:
mother(X, kate).
Prolog will determine from the definition above, that in order for X to be the "mother" of kate, X must be the "parent" of kate and X must also be "female". The only atom that satisfies those two criteria is joan.

Have a play adding new facts to the program, and even try coming up with a few more statements with conditions attached (like the "mother" one above). Next week, this tutorial will be continued and we'll delve further into the guts of the language.

Editor's Picks

Free Newsletters, In your Inbox