Prolog is often overlooked as a language, there are probably lots of reasons for this. Prolog is a (mostly) declarative language which can mean quite a mind shift if you’re coming from a procedural background. Prolog implementations are somewhat fragmented, so can be hard to know where to start

Prolog was originally designed at the University of Aix-Marseille in the early 1970 (later further developed at the University of Edinburgh) as a language for use in natural language processing research. It is however an excellent, general purpose, first-order logic programming language with uses far beyond NLP. It has application for many symbolic type problems, be it theorem solvers, planning applications or inference engines.

A common misconception is that you need to be a logician with a background in formal logic to work with Prolog. While an understanding of how problems can be represented logically is useful, you don’t need any understanding of formal logic to get started with Prolog.

Perhaps I can convince you to give it a go.

Getting Started

There are several free implementations of Prolog many of which have support for subsets of all the major standards. I use the popular SWI-Prolog implementation. This brings a full Edinburgh compliant Prolog, along with excellent support for multi-threading and fast C and C++ interfaces so we can use our code in the real world.

SWI-Prolog is easy to get started with, just download the release for your platform and off you go.

Being a declarative language you don’t write functions and control flow in Prolog. Instead your program consists of a set of facts and rules. It can help to think of logic programming as describing the shape of the problem then asking prolog to solve it for you. You execute your program by presenting Prolog with a query to run.

Facts are simple, to tell Prolog about a person called Jim we use:

person(jim).

Note the full stop at the end - that’s important, like a semi-colon in C.

To run a program we pose a query. To query what Prolog knows about people we simply use:

person(X).

We’d expect to get the response back:

X = jim.

Rules are also simple. To take the classic modus ponens rule from propositional logic let’s say we wanted to express that ‘All people are mortal’. We write this as:

mortal(X) :- person(X).

Rules can get quite complex, but always take the form head :- body

Now if we query:

mortal(X).

we get

X = jim.

A query in Prolog essentially works by pattern matching, where the query is called the goal and the process of pattern matching is called unification.

When Prolog finds a solution to a goal any logic variables (X in the example above) become ‘bound’ to the value of the term it matches with. If it matches more than one term Prolog will provide multiple answers.

For example, given the following program:

person(john).
person(jim).
mortal(X) :- person(X).

posing the query:

mortal(X).

presents:

X = john;
X = jim;
no.

In SWI-Prolog the user enters the ; character to indicate they want Prolog to search for more answers. The ‘no’ at the end indicates that there are no more answers to be found.

The process of searching for more answers is called backtracking, in this case the X is unbound and a new solution sought. Backtracking also happens if unification fails but there are other routes to a solution.

Recursion is a very common pattern in Prolog, here’s an example program to calculate factorials:

factorial(0,1).
factorial(A,B) :-  
       A > 0,
       C is A-1,
       factorial(C,D),
       B is A*D.

Two things to note here. Firstly it’s recursive, secondly the program consists of two clauses. The first clause is a fact, the second is a rule with a head and a body.

If we query prolog with:

factorial(0,1).

We get back:

true

If we query prolog with:

factorial(3, X).

We get back:

X = 6.

When executing this program Prolog recurses, matching clauses as it goes. Eventually Prolog needs to match factorial(0,X) so we match the first clause and not the second (because A > 0 doesn’t match), at which point we’re done recursing, unwind and have the answer.

When to use Prolog

Choosing one language over another is a matter of picking the right tool for the job. Prolog is a language designed for symbolic reasoning. Sure there are people who’ve build ray-tracers in Prolog, and SWI-Prolog includes and extensive HTTP / web application layer. But at it’s heart Prolog is a good tool to understand when faced with symbolic problems.

Prolog programs are concise and lack the verbosity some other languages would suffer when representing this class of problem.

If you have a problem that involves reasoning over some kind of data, Prolog could be a good fit. In Prolog your data is your program.