# Working with Prolog

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 **.

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 .
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 -th prime, but takes a bit of time to finish.