Adventures in Prolog - Simplify Sum (3)

In an earlier installment the simplify_sum predicate was discussed. However it was not really a feature complete solution to the initially motivated problem. For this, this post is concerned with providing a newer version, which actually solves the following problem.

Given some additive formulae, such as:
1
a
1 + a
a + a
1 + a + 9 + b + a + b + c
we wish to obtain the following results:

1
1*a (or a)
1*a + 1 (or a + 1)
2*a
2*a + 2*b + 1*c + 10 (or 2*a + 2*b + c + 10)

The proposed solution will consist of three parts:

1.
order all parts of an additive equation according to letters and numbers.
place letters in order of the alphabet and summarize numbers, such that at most one number is present.

2.
summarize all variables. this leads to the transformation of x into 1*x

3.
reduce all variables from 1*x to x.

Translating the above sequence of steps into a Prolog program, leads to the following definition of the simplify_sum predicate:

simplify_sum(In, Final) :-
  sort_sum(In, SortedOut),
  simplify(SortedOut, Result),
  strip_sum(Result, Final), !.

A first naive implementation of sort_sum, checks whether some parameter is an atom or a number and arranges the output accordingly. The high level predicate sort_sum makes use of the acutal predicate called sort_sum_t. sort_sum_t implements a bubble sort approach to arrange numbers and atoms. If two numbers are encountered they are reduced to their sum.Elementary cases are only one number, one atom, two atoms, two numbers and atom and number. Compound cases split the input argument into simpler forms until input is elementary.

%sort_sum_t
sort_sum_t(X + Y, X + Y) :-
  atom(X),
  number(Y), !.

sort_sum_t(X + Y, X + Y) :-
  atom(X),
  atom(Y),
  char_code(X, CX),
  char_code(Y, CY),
  CX =< CY, !.

sort_sum_t(X + Y, Y + X) :-
  atom(X),
  atom(Y), !.

sort_sum_t(X + Y, Y + X) :-
  number(X),
  atom(Y), !.

sort_sum_t(X + Y, Res) :-
  number(X),
  number(Y),
  Res is X + Y, !.

%compounds
sort_sum_t(C + X, Res) :-
  sort_sum_t(C, R1),
  number(R1),
  number(X),
  Res is X + R1, !.

sort_sum_t(C + X, X + R1) :-
  sort_sum_t(C, R1),
  number(R1),
  atom(X), !.

sort_sum_t(C + X, A + Res) :-
  sort_sum_t(C, A + B),
  number(B),
  number(X),
  Res is B + X, !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  number(X), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  number(B),
  atom(X),
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, Res + B) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X),
  char_code(B, CB),
  char_code(X, CX),
  CX =< CB,
  sort_sum_t(A + X, Res), !.

sort_sum_t(C + X, A + B + X) :-
  sort_sum_t(C, A + B),
  atom(B),
  atom(X), !.

sort_sum(X, X) :- atom(X), !.
sort_sum(X, X) :- number(X), !.

sort_sum(In, Out) :- sort_sum_t(In, Out), !.

sort_sum(_, _).

Now that an input additive term is sorted according to variables and numbers, it may be processed. This processing, i.e. summing equal atoms and numbers is handled by the simplify predicate, which in turn calls simplify_t to summarize some additive input term. special cases correspond to those identified for the sort_sum predicate. However, simplify_t can make use of the following: (1) there is only one number in the input term, which is at the right most position and (2) an atom follows another atom which is either equal to itself (only having higher quantity) or is a smaller atom.

simplify_t(X, 1*X) :- atom(X), !.

simplify_t(A*X, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X*A, A*X) :-
  atom(X),
  number(A), !.

simplify_t(X, X) :- number(X), !.

simplify_t(X + Y, 1*X + Y) :-
  atom(X),
  number(Y), !.

simplify_t(X + Y, 1*X + 1*Y) :-
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(X + X, 2*X) :- atom(X), !.

simplify_t(X + I*X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X + X*I, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(I*X + X, J*X) :-
  atom(X),
  number(I),
  J is I + 1, !.

simplify_t(X*I + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(I*X + Y, I*X + Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + Y*I, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(X + I*Y, X + I*Y) :-
  atom(X),
  atom(Y),
  number(I), !.

simplify_t(A*X + B*X, C*X) :-
  atom(X),
  number(A),
  number(B),
  C is A + B, !.

simplify_t(X + Y, X + Y) :-
  atom(X),
  atom(Y), !.

simplify_t(A*X + B*Y, U + V) :-
  simplify_t(A*X, U),
  simplify_t(B*Y, V), !.

%compounds
simplify_t(C + X, R + X) :-
  number(X),
  simplify_t(C, R), !.

simplify_t(A + B, R*X) :-
  simplify_t(A, M*X),
  simplify_t(B, N*X),
  atom(X),
  R is M + N, !.

simplify_t(A + B, M*X + N*Y) :-
  simplify_t(A, M*X),
  simplify_t(B, N*Y),
  atom(X),
  atom(Y),
  X \= Y, !.

simplify_t(A + B, M + R*X) :-
  simplify_t(A, M + N*X),
  simplify_t(B, S*X),
  atom(X),
  R is N + S, !.

simplify_t(A + B, M + N + SX) :-
  simplify_t(A, M + N),
  simplify_t(B, SX), !.

simplify(In, Out) :- simplify_t(In, Out), !.

simplify(_, _).

Now that an additive term is transformed to its reduced form, the only thing left is to remove any unnecessary 1. That is reduce each 1*x to x. Again the compound case is reduced to atomic cases, which are 1*x = x, n*x = n*x, number = number.

strip_sum(X, X) :- number(X), !.

strip_sum(1*X, X) :- atom(X), !.

strip_sum(N*X, N*X) :-
  atom(X),
  number(N), !.

strip_sum(A + B, A1 + B1) :-
  strip_sum(A, A1),
  strip_sum(B, B1), !.

running the following example:

simplify_sum(a + b + c + d + a + c + 70 + a+ a + 50, X).
X = 4*a+b+2*c+d+120.

shows the correct working of simplify_sum.

As mentioned sort_sum makes use of a bubble sort approach, which clearly is less than optimal. For this, the next post is concerned with using a different sort_sum approach to speed simplify_sum up.