Simplify Expressions in Prolog With unknown variables

Question

I want to simplify expressions like:

2+x+3 = 5+x

I managed to write this code:

simplify(K, K):-
    atomic(K),!.
simplify(_ * 0, 0).
simplify(0 * _, 0).
simplify(0 + X, X).
simplify(0 + X, X).
simplify(X - 0, X).
simplify(X - 0, X).
simplify(0 / _, 0).
simplify(K + 0, E):-
    simplify(K, E).
simplify(K - 0, E):-
    simplify(K, E).
simplify(K1 + K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_addition(E1 + E2, R).
simplify(K1 - K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_substraction(E1 - E2, R).
simplify(K1 * K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_multiplication(E1 * E2, R).
simplify(K1 / K2, R):-
    simplify(K1, E1),
    simplify(K2, E2),
    simplify_division(E1 / E2, R).

simplify_addition(K1 + K2, R):-
    number(K1),
    number(K2),
    R is K1 + K2.
simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_substraction(K1 - K2, R):-
    number(K1),
    number(K2),
    R is K1 - K2.
simplify_substraction(K1 - K2, K1 - K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_multiplication(K1 * K2, R):-
    number(K1),
    number(K2),
    R is K1 * K2.
simplify_multiplication(K1 * K2, K1 * K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

simplify_division(K1 / K2, R):-
    number(K1),
    number(K2),
    R is K1 / K2.
simplify_division(K1 / K2, K1 / K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).
simplify_division(K / K, 1):-
    number(K).

Now the problem that I ran into is that I don't know how to resolve stuff like x+3 for example because in the current state if I run the code simplify(2+x+3,R). for example it will get to a stage where K1 = 2+x and K2 = 3 and it will try to get the sum of this two in simplify_addition.

Answer 1

This isn't really a Prolog question (maybe see if a tag like algorithm is appropriate, even though it's very general?), but there is a Prolog angle here. Specifically, this:

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2);
    atom(K2),
    number(K1).

is very very bad Prolog code that should not be written this way. The normal, expected way of terminating goals on a line is the comma ,. The disjunction ; has a drastically different meaning. And it looks much too similar to the comma and is much too easy to miss!

If you use ; (and you shouldn't necessarily do it), you must format your code in a way that really really makes the ; stick out. Just from looking at the shape of the code it must be clear that something different than linear conjunctions is going on. If I had to write this using ;, it would look like this:

simplify_addition(K1 + K2, K1 + K2):-
    (   atom(K1),
        number(K2)
    ;   atom(K2),
        number(K1) ).

Note that the ; is at the beginning of a line where no , usually goes. Indentation makes clear that the ; is the top-level operation, and that the two , are subordinate. The parentheses make clear where the disjunction starts and ends. There could be even more spacing (a line break after the ; rather than continuing on the same line), but I find this is explicit enough.

However, this should never be written using ; in the first place. It's much clearer using separate clauses to express the disjunction:

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2).
simplify_addition(K1 + K2, K1 + K2):-
    atom(K2),
    number(K1).

And at this point we can start on the algorithmic part. Compilers often use the term "canonicalization" for transformations of expressions that don't necessarily simplify them but get them into a more "standard" or "canonical" shape.

A very typical canonicalization is one that moves constants (in your case, represented directly as numbers) from the left to the right of a commutative operator. So x + 2 is in canonical form, but 2 + x is not; it should be canonicalized to x + 2. We're almost there, but the second rule needs to do this swapping of operands:

simplify_addition(K1 + K2, K1 + K2):-
    atom(K1),
    number(K2).
simplify_addition(K1 + K2, K2 + K1):-
    atom(K2),
    number(K1).

This way, when you try to simplify 2 + x + 3, which really is (2 + x) + 3, this will still fail. But it will fail after having internally transformed (2 + x) + 3 to (x + 2) + 3. Progress!

Another canonicalization you can do is to move parentheses in associative operations in a well-defined direction:

simplify_addition((K1 + K2) + K3, K1 + (K2 + K3)).

With this the above expression then canonicalizes as follows:

?- simplify(2 + x + 3, R).
R = x+(2+3) ;
false.

You are not done! And even after you've done some more recursive simplification, there is the fundamental problem that simplify_addition/2 shouldn't fail if it cannot simplify an addition further. But I think I've stretched this prolog answer far enough :-)