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.

Does this answer your question? [I'm curious if Logic Programs can do algebra](https://stackoverflow.com/questions/13690136/im-curious-if-logic-programs-can-do-algebra) — Guy Coder, Nov 09 '21 at 18:43
@GuyCoder it doesn't look at all like this answers OP's question. This is not about finding solutions this is about symbolic manipulation. — TA_intern, Nov 10 '21 at 06:41
If you want to get this done first try and find an algorithm for doing this, independently of the programming language. Then you can try and code it in Prolog. What you have already is maybe a good start but I don't know if you need to re-discover _the algorithm_, it is probably easier to just look it up. — TA_intern, Nov 10 '21 at 06:43
Well that's the problem that I tried to search how can I resolve this problem but didn't found anything. — Erik, Nov 11 '21 at 12:33

score 1 · Accepted Answer · answered Nov 11 '21 at 22:28

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 :-)

Simplify Expressions in Prolog With unknown variables

1 Answers1