Adventures in Prolog - Simplify Sum (1)

Today's post is concerned with (the first part of) an example task from the book "Prolog Programming For Artificial Intelligence" - it is a about the simplification of additive terms using Prolog's facilities to reason about the type of some symbol.

For example, Prolog offers the following (and more) built-in predicates:

• number/1 - is the argumet passed, a number, e.g. number(1) returns true
• atom/1 - is the passed argument an atom, e.g. atom(x) returns true
• compound/1 - is the passed argument a compound term, e.g. compound(X+Y) returns true

Now, that we know how to inspect the type of some Prolog symbol, we may take a look onto today's task. Given some summation, the task is to simplify this summation, using some predicate called simplify_sum or simp_sum (for short).

For example:

• 1 +2 +3 = 6
• 1 +a = a +1
• a + b + 1 + c = a+ b +c + 1
• a + 1 +2 + b = a + b + 3

So in short, the summation should be ordered with atoms first and aggregated numbers last. The original task by Bratko is concerned with the aggration of atoms as well, such as x +x = 2*x, but I will keep this for the next post.

So based on the above statement of the problem, we must consider some elementary cases, such as:

• number + atom = atom + number
• number + number = number
• atom1 + atom2 = atom1 + atom2
• atom + number = atom + number

These cases will act as the recursion anchor in our simp_sum clauses. Based on this reduction to the simplest form of the problem (please note, that we do not consider a case where only one atom or one number is passed to simp_sum), we identify more advanced incarnations of the problem.

We must consider the following:

• some compound term + number
• some compound term + atom

cases as well. The reason for compound term occuring only on the left-hand side is the associativity of the + operator. For example. 3 + 4 + 5 is (3 + 4) + 5 and consuequently we have 3+ 4 +5 = compound + number where compound = number + number.

Putting together all this information we might come up with the following ...

simp_sum(X + Y, R) :- number(X), number(Y), R is X + Y.
simp_sum(X + Y, X + Y) :- atom(X), number(Y).
simp_sum(X + Y, Y + X) :- atom(Y), number(X).
simp_sum(X + Y, X + Y) :- atom(X), atom(Y), X \== Y.

%Result of simpsum is not compound
simp_sum(X + Y, Z) :-
simp_sum(X, X0), number(X0), number(Y), Z is X0 + Y.
simp_sum(X + Y, Y + X0) :-
simp_sum(X, X0), number(X0), atom(Y).

%Result of simpsum is compound
simp_sum(X + Y, A + Y0) :-
simp_sum(X, X0), number(Y), X0 = A + B,
number(B), simp_sum(B+Y, Y0).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), number(Y), X0 = A + B, atom(B).

simp_sum(X + Y, A + Y + B) :-
simp_sum(X, X0), atom(Y), X0 = A + B, number(B).

simp_sum(X + Y, A + B + Y) :-
simp_sum(X, X0), atom(Y), X0 = A + B, atom(B).

When Prolog is asked:

simp_sum(1 + b + 2 + c + a + 4 + d + 39 + e+ f + 122, X).

It answers correctly:

X = b+c+a+d+e+f+168 .