From time to time, I’d like to learn a new language, to see what it offers, and to broaden my mind. Intrigued by a chapter on predicate logic in Russell Norvig’s book Artificial Intelligence, I had a look at Prolog.

Let’s start with the example:

We want to compute the sum of integers up to a certain number \(n\).

Admeditly, I cannot imagine anyone using predicates in Prolog to solve this. In–let’s say–Python you could do this simply with sum(range(n + 1)) or with a bit of reshuffling, we see that the solution is \(n \cdot (n+1)/2\). However, this example is perfect to illustrate how to work with Prolog.

Consider this snippet.

% sum_integers.pl
sum_integers(1, 1).
sum_integers(N, Sum) :-
  N > 1,
  Prev is N - 1,
  sum_integers(Prev, PrevSum),
  Sum is N + PrevSum.

You can load the snippet with $ prolog sum_integers.pl. If you see the ?-, you can ask the system to do inferences. For example, type sum_integers(10, Sum).. The result should be Sum = 55 . which is the correct sum of all integers from 1 up to 10. But how did this work?

Consider this slightly modified version of the snippet.

% sum_integers2.pl
?- op(150, xfy, is_sum_of_integers_upto).

1 is_sum_of_integers_upto 1.

Sum is_sum_of_integers_upto N :-
  N > 1,
  Prev is N - 1,
  PrevSum is_sum_of_integers_upto Prev,
  Sum is N + PrevSum.

The first line tells Prolog to treat is_sum_of_integers_upto as an operator instead of a regular predicate. In our case, this is just a bit of syntactical sugar to make the code resemble natural language.

On a superficial level, Prolog works with truthful expressions. In sum_integers2.pl, we tell the system that 1 is the correct sum of all integers up to 1. So far so good. The next step generalizes this. Translated to plain English, we specify that some value Sum is the sum of integers up to N if a couple of conditions are satisfied:

  • N is greater than one. This makes sure that for N=1 only the first rule is used.
  • A new variable Prev is equal to N - 1. This looks weird at first. What is Prev? We use this construction to define a new variable. Prolog tries hard to satisfy our conditions. The only way to satisfy Prev is N -1 is by setting Prev to N - 1. So for the rest of this query, Prev is equal to N - 1.
  • Another new variable PrevSum is the sum of all integers up to Prev. In other programming languages, we would call this technique recursion. The condition can only be true if PrevSum is the sum of all integers up to N - 1. Again, since PrevSum is a variable, Prolog will satisfy the condition by setting PrevSum to the correct value.
  • Finally, the initial argument Sum must be the sum of all integers up to PrevSum (i.e. N - 1) and N.

Querying for Sum is_sum_of_integers_upto 10. will give us all possible values for Sum to make our query a truthful statement.

?- Sum is_sum_of_integers_upto 10.
Sum = 55 .

You can take this even to more complex levels and solve Project Euler with Prolog. My solution to problem 7 returns the correct values for the \(n\)-th prime, but takes a bit of time to finish.