Replacing parts of expression in prolog

Question

I need to simplify identities in prolog (e.g. x+0 = x, x-x=0, etc.). For this I need to replace parts of the expression (say x+0 by x).

Can you please help me in doing the replacement?

Answer 1

A neat thing about Prolog is that you can deconstruct an arithmetic expression pretty easily. Your basic template is going to look like this:

simplify(X, X)       :- number(X) ; atom(X) ; var(X).    
simplify(X+Y, X1+Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X-Y, X1-Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X*Y, X1*Y1) :- simplify(X, X1), simplify(Y, Y1).
simplify(X/Y, X1/Y1) :- simplify(X, X1), simplify(Y, Y1).

This doesn't really do anything except recursively walk the expression. We're recursively calling simplify on both sides of the operator so that the simplification patterns are matched regardless of where they occur in the expression. But for now it appears to do nothing:

?- simplify(3+X*y, Q).
Q = 3+X*y

Think of it as your empty loop. With this in hand, you can start dealing with your identities by putting "special cases" above this traversal. The identities are one thing you can handle this way:

simplify(1*X, X1) :- simplify(X, X1).
simplify(X*1, X1) :- simplify(X, X1).
simplify(0+X, X1) :- simplify(X, X1).
simplify(X+0, X1) :- simplify(X, X1).

Trying it out:

?- simplify(x*1+0, Q).
Q = x 

And you can see why we're using a recursive routine here:

?- simplify(x+(y+(z*43)+0)*1, Q).
Q = x+(y+z*43)

Even though the +0 is deeply nested within the structure, it is removed. We could do some more drastic simplifications too:

simplify(_*0, 0).
simplify(0*_, 0).

No need for recursion here, the whole subexpression is basically deleted:

?- simplify(x+(y+(z*43)+1)*0, Q).
Q = x+0 ;

You can do some more interesting things as well:

simplify(X*Y+Z*Y, Y1*(X1+Z1)) :- 
  simplify(X, X1), simplify(Y, Y1), simplify(Z, Z1).

Trying it out:

?- simplify(34*z+17*z, X).
X = z* (34+17) 

?- simplify(34*z+z*17, X).
X = 34*z+z*17 

This second example here reveals that there is a limitation to this type of processing. You don't want to have to give every permutation of your templates. If you want to make them more intelligent you're probably going to have to either adopt a more intelligent intermediate representation, or a more intelligent means of applying templates than simple unification. Unification is great, but it doesn't understand the commutative or associative properties.

To go further, you're probably going to want to dig a little deeper into Prolog. This type of problem is studied in most Prolog books; I'm partial to Programming Prolog and Art of Prolog but I hear Bratko's book is amazing. I'd recommend you get your hands on one of these and start digging through it. Don't hesitate to ask more questions though!

Answer 2

It is possible to replace subterms in an expression using =../2. Based on this predicate, I wrote a predicate that replaces all occurrences of a pattern in a term:

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :- Input=((X+0)=(Y+0)-(Z+0)),replace(A+0,A,Input,Output),writeln(Input),writeln(Output).

replace(Subterm0_, Subterm_, Term0, Term) :-
        copy_term([Subterm0_,Subterm_],[Subterm0,Subterm]),
        (   Term0=Subterm0 -> (Term = Subterm)
        ;   var(Term0) -> Term = Term0
        ;   Term0 =.. [F|Args0],
            maplist_(Args0, Args, replace(Subterm0,Subterm)),
            Term =.. [F|Args]
        ).

maplist_([], [], _).
maplist_([Elem1|Tail1], [Elem2|Tail2], replace(A,B)) :-
    copy_term([A,B],[A1,B1]),
    Goal=replace(A1,B1),
    writeln(Goal),
    call(Goal, Elem1, Elem2),
    maplist_(Tail1, Tail2, Goal).

In this case, the input is (X+0)=(Y+0)-(Z+0) and the output is X=Y-Z.