CODEWITHSUNDEEP
prolog
zer0kai
zer0kai

Reputation: 259

Simplify Expressions in Prolog

I wanted to ask how I can simplify expressions like:

1+2+a*5+0/b-c*0
= 3+a*5

And especially how can I separate such expressions in lists.

Upvotes: 2

Views: 3794

Answers (2)

Anderson Green
Anderson Green

Reputation: 31850

It's possible to simplify expressions in Prolog using unification, but this sometimes leads to unexpected results. In this example, two different variables in an expression are unified when "matching" a pattern, even if they were intended to be distinct:

:- initialization(main).

simplify(A+A,2*A).

main :-
    simplify(A+B,C),
    writeln(C).

In this case, simplify(A+B,C) would unify A with B.

To solve this problem, I use subsumes_term/2 to match a pattern without unifying the variables in an expression. subsumes_term(A+A,Input) will not match A+B unless A is already unified with B:

simplify(Input,2*A) :-
    subsumes_term(A+A,Input).

This subsumes_term/2 predicate is often useful for metaprogramming: I used it to write a Prolog-to-Minizinc compiler.

Upvotes: 2

Daniel Lyons
Daniel Lyons

Reputation: 22803

It's actually kind of fun in Prolog, because you don't need to do anything too magical to make it work.

?- X-Y = 1+2+a*5+0/b-c*0.
X = 1+2+a*5+0/b,
Y = c*0.

So you could start by doing something like this:

simplify(C, C) :- atom(C) ; number(C).
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 is an identity transform: it doesn't do anything.

?- simplify(1+2+a*5+0/b-c*0, Result).
Result = 1+2+a*5+0/b-c*0.

Now you can add rules for specific cases:

simplify(X*0, 0).
simplify(0*X, 0).

Now you get multiple results:

?- simplify(1+2+a*5+0/b-c*0, Result).
Result = 1+2+a*5+0/b-c*0 ;
Result = 1+2+a*5+0/b-0 ;

You could add a rule for constant folding:

simplify(X+Y, C)     :- number(X), number(Y), C is X+Y.

You know, just have fun with it.

Lists aren't really any easier to work with, but you can make them using the "univ" operator: =..:

?- 1+2+a*5+0/b-c*0 =.. R.
R = [-, 1+2+a*5+0/b, c*0].

Upvotes: 2

Related Questions