A friend of mine, perhaps now an ex-friend, was recently looking at my site when he started laughing. The reason for his mirth was my previous article on Prolog. He didn’t think any real programmer would go anywhere near Prolog. But he is a project manager, so what would he know?

I thought that this time I might demonstrate the power of Prolog through a simple piece of code. If you have learnt C, or C++ you will be aware of the ubiquitous program Hello, world!. A completely useless piece of code if ever there was. You wouldn’t use a computer language to say "Hello, world!", you would use a microphone and maybe a radio transmitter.

In Prolog we don’t bother with such idiocies. The first program that a would-be Prolog coder learns is something useful. Prolog, like its poor cousin Lisp, is built on lists. And one of the most important things you can do is determine if an object is a member of a given list. Now if you want to do that in C you have to learn about Null terminated strings and Char* and pointers and memory allocation. You don’t remember how to use malloc, no worry, you start counting the characters in "Hello, World!" get to three and think "this is too hard I’ll just set aside 1k, that should be enough."

And once you’ve done that and filled your screen up with enough { and } to cover all eventualities you come across the first law of programming:

Beware of any language that uses semi-colons

So how would we do it in Prolog? Prolog is made up of rules, or clauses. The clauses to determine membership could be written like this

     member(X,[X|Tail]).
     member(X,[Head|Tail]):-
        member(X,Tail).

First a couple of syntax rules.

• Clauses start with a lower case letter, in this case – member
• Clauses are terminated with a period .
• Variables start with an upper case letter or the underscore character. Here we have X, Head, Tail
• A list can be written within square brackets
• A list written [A|B] means that A is the first element of the list, and B is the rest of the list
• The colon followed by a dash, :- means if
• Commas mean and, although there aren’t any here they are quite useful
• In violation of the First Rule of Programming you can use semi-colons. A semi-colon ; means or, but fortunately you rarely have to use it. Some Prolog programmers never use it. I get quite stressed even contemplating using a semi-colon.

All fairly straight forward so far? Before we delve too deeply into our member snippet of code we should probably look at how it is called. Prolog is a goal oriented language. You tell Prolog what you want done and it does it. This is the nature of a declarative language. In a procedural language, like C, you tell the program how to do it. Prolog programmers have more important things to do than tell a program how to do its job.
So then, we give Prolog a goal, say we tell it that the goal is

member(b,[a,b,c]).

A goal is a clause and so it ends in a period. That makes sense, satisfy the goal then stop. What we are asking is “is b a member of the list [a,b,c]? If it is then Prolog will answer True, otherwise it will answer False. Now, even a C programmer can tell, with or without a header file, that the answer should be True. So let’s look at what Prolog does.

Prolog works by matching. In this case it matches our goal with the member rules. So that X is, in Prolog geek-speak, instantiated to b. Remember that a list [A|B] means that A is the first element, or head, of the list, and B is the rest, or the tail. So the first member rule says that b is a member of the list if b is the first element of the list. That is not true, because the first element of the list is a.

Since that rule fails Prolog tries the next rule. This is a little more complicated because it is a recursive rule. Prolog is full of recursion. The rule says that b is a member of the list which is split into a Head and a Tail if b is a member of the Tail. That sounds reasonable. But Prolog cannot evaluate that immediately. It takes the second part of the rule
member(X,Tail)
and applies it to the member rule as a whole. So it goes back to the start and so now we have

member(b,[b,c]).
because Tail was what was left over after we removed the first element, a. Now there is a match and Prolog returns True.

That is our first Prolog program. Isn’t it fun? we might do some more another time. Who knows, we may even write “Hullo, World!”