Today we’ll look at Prolog which is the most prominent representant of logical programming languages. It was already developed in the 1970s and is not really relevant anymore today. But it still influences a few other languages used today, especially in the context of graph databases. The database query language Datalog (used for example by Datamic) is a subset of it.

The Prolog syntax is rather simple. You can define some facts and later check if they apply to certain data. Let’s have a look at some examples.

loves(william, kate).
loves(harry, meghan).
loves(kate, william).
loves(meghan, harry).
loves(peter, kate).

We now defined some fact so loves who. When you read in a file with facts in Prolog, these facts are inserted to a in-memory knowledge base and you can query them later on.

Note that words starting with lower case are atoms in Prolog. They cannot be bind to any other value. For variables you have to use upper case characters. Don’t forget this as you may wonder why your queries don’t return anything, just because you forgot to hold the Shift key for a second.

Now that we have this, I’ll show you how we can work with these facts. First install Prolog on your machine. You’ll have the choice between a few Prolog implementations for your installation (e.g. GNU Prolog, JProlog, SWI Prolog), but in this article we’ll always use SWI Prolog. So download and install it, if you want to try the examples yourself.

After the installation of SWI Prolog, you can create a file with the facts from above and store it with the name “love.pl”.

Then you can query them in the Prolog console. You can start it either bei calling the command line tool swipl or by double clicking on your “.pl” file. By double clicking, you already load the file into the knowledge base.

You can now check if some facts apply:

?- loves(kate, william).
true.

?- loves(kate, harry).
false.

Here we check some facts by directly setting some atoms as parameters. The outcome is as expected: kate loves william, but not harry.

Next, lets see what we can do with variables:

?- loves(kate, X).
X = william.

Here we can bind X to all possible values that make the statement true. In this case, there is only one possibility. If there are more, you won’t get to the next line (starting with ?-), but your cursor will stay at the end of the line:

?- loves(Y, kate).
Y = william %cursor is here

Now, if we only wanted to get one answer (or if we are satisfied with the current answer), we can type the ENTER key or the “.” key. If we want more possibilities, we can type “;” and we get the next one (until there aren’t any other anymore).

?- loves(Y, kate).
Y = william ;
Y = peter.

Now if we want all possible combinations, we can use variables for both parameters:

?- loves(X, Y).
X = william,
Y = kate ;
X = harry,
Y = meghan ;
X = kate,
Y = william ;
X = meghan,
Y = harry ;
X = peter,
Y = kate.

What we can also do, is combine two facts, e.g. to find out reciprocal lovers:

?- loves(X,Y),loves(Y,X).
X = william,
Y = kate ;
X = harry,
Y = meghan ;
X = kate,
Y = william ;
X = meghan,
Y = harry ;
false.

Here we get a false in the end, because there are not further matches, but more facts.

Of course, only having facts is not so interesting, so we can also define rules which are derived from facts.

Example:

lovers(X,Y) :- loves(X,Y),loves(Y,X).

So now our query for reciprocal lovers is easier:

?- lovers(X,Y).
X = william,
Y = kate ;
X = harry,
Y = meghan ;
X = kate,
Y = william ;
X = meghan,
Y = harry ;
false.

But of course, we can not only query our fact tables in Prolog, but also do some regular calculations.

First, a very simple program, that just calculates the sum of two numbers:

add(A, B, Sum) :-
    Sum is A + B.

This was pretty simple. Note that you cannot use the = operator here, but have to use “is” when you have an operation on the right hand side of the assignment.

?- add(9, 5, X).
X = 14.

?- add(1,2,3).
true.

?- add(4,5,10).
false.

As expected, you can calculate the sum of two elements like this and check if two numbers added equals a third one, but unfortunately, you cannot bind a variable to one of the first two arguments:

?- add(9, X, 12).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] 12 is 9+_5544
ERROR:    [7] <user>
ERROR: 
ERROR: Note: some frames are missing due to last-call optimization.
ERROR: Re-run your program in debug mode (:- debug.) to get more detail.

The reason is that Prolog does not know how to invert an operation like “+”. So you cannot bind variables that are on the right hand side of a “is” instruction.

Now let’s move to a slightly more complex function that calculates the sum of a list:

list_sum([], 0).
list_sum([Head|Tail], Sum) :-
    list_sum(Tail, SumTail),
    Sum is SumTail + Head.

This is slightly more complex, so I’ll explain what happens here:

First, we do not have loops in Prolog, so we have to work with recursion for functions based on lists. In recursions, we always have to provide a base case, otherwise we’ll end up in endless recursion. In the case of lists, the base case is usually the empty list and the sum of an empty list is 0.

In Prolog functions you can define multiple clauses for the same function and Prolog will use the function definition that matches the clause. In our case, we have to possibilites for the first argument: either it is an empty list that matches “[]” or it is a non-empty list that matches “[Head|Tail]”. The latter one is a so-called list decomposition which breaks down a list in its first element (here Head) and the rest of the list. You can check this behaviour in your Prolog prompt:

?- [Head|Tail] = [1,2,3].
Head = 1,
Tail = [2, 3].

?- [Head|Tail] = [1].
Head = 1,
Tail = [].

?- [Head|Tail] = [].
false.

Back to our example: we always add the first element of the list to the sum of the remaining list and obtain the correct result like this.

Now, you’ve seen how to use Prolog in a nutshell. The real power of Prolog, is that it can find solutions to problems only by describing the problem and without the need to describe how to solve it.