Prolog - simplify derivative

Question

so I just got started with Prolog this semester, and got the homework to implement a pretty basic d(function, variable, derivative) which I did like this:

d(X,X,1) :- !.
d(C,X,0) :- atomic(C). %, (C \= X).
d(X**E,X,E*X**(E-1)).
d(U+V,X,A+B) :- d(U,X,A), d(V,X,B).
d(U-V,X,A-B) :- d(U,X,A), d(V,X,B).
d(U*V,X,DU*V+U*DV) :- d(U,X,DU), d(V,X,DV).
d(U/V,X,(DU*V-U*DV)/(V*V)) :- d(U,X,DU), d(V,X,DV).

I know this is not complete, but it covers all the tasks required in the exercise.

However, ?- d((x*x+2*x+3)/(3*x),x,R). leads to

R = ((1*x+x*1+ (0*x+2*1)+0)* (3*x)- (x*x+2*x+3)* (0*x+3*1))/ (3*x* (3*x)). which doesn't look pretty at all. is/2 unfortunately doesn't like my x as it is not a number...

Is there a simple solution to achieve a cleaner result?

`is/2` is specifically for arithmetic evaluation where you know what your variables are numerically instantiated to, so it's not appropriate for this purpose. If you want it more pretty, you're going to have to create a predicate to simplify expressions. — lurker, May 13 '15 at 20:44

repeat · Accepted Answer · 2019-02-20T23:10:24.097

I would rather see this as two separate problems:

First, get derivation right (you're probably getting close, depending on your concrete requirements).

Then, work on simplifying expressions on an algebraic level. Exploit algebraic identities, see if applying the laws of commutativity / associativity / distributivity on some subexpressions enable their rewriting into something equivalent (but simpler / more compact).

As a starting point, you may want to look at the somewhat related question "Replacing parts of expression in prolog".

Here's a simplistic sketch how you could do the simplification—using iwhen/2 to safeguard against insufficient instantiation:

expr_simplified(A, B) :-
   iwhen(ground(A), xpr_simplr(A,B)).

xpr_simplr(A, B) :-
   (  atomic(A)
   -> A = B
   ;  ( A = X+0 ; A = 0+X ; A = 1*X ; A = X*1 )
   -> xpr_simplr(X, B)
   ;  ( A = 0*_ ; A = _*0 )
   -> B = 0
   ;  A = X+X
   -> B = X*2
   ;  A = X*X
   -> B = X**2
   ;  A = X**1
   -> B = X
   ;  A =.. [F|Xs0],                          % defaulty catch-all
      maplist(xpr_simplr, Xs0, Xs),
      B =.. [F|Xs]
   ).

Let's see what it does with the expression you gave. We apply expr_simplified/2 until we reach a fixed point:

?- A = ((1*x+x*1+(0*x+2*1)+0)*(3*x)-(x*x+2*x+3)*(0*x+3*1))/(3*x*(3*x)),
   expr_simplified(A,B),
   expr_simplified(B,C),
   expr_simplified(C,D).
A = ((1*x+x*1+(0*x+2*1)+0)*(3*x)-(x*x+2*x+3)*(0*x+3*1))/(3*x*(3*x)),
B = ((x+x+(0+2))*(3*x)-(x**2+2*x+3)*(0+3))/(3*x)**2,
C = ((x*2+2)*(3*x)-(x**2+2*x+3)*3)/(3*x)**2,
D = C.                                        % fixed point reached

As imperfect as the simplifier is, the expression got a lot more readable.

Thank you! This indeed looks way better than before! – 4cello May 14 '15 at 09:23 — 4cello, May 14 '15 at 09:23

CapelliC · Answer 2 · 2015-05-14T06:12:53.000

a possibility to get a number is to replace each instance of variable x with a value, visiting the derived tree. You should do writing a clause to match each binary operator, or use a generic visit, like

set_vars(E, Vs, Ev) :-
    E =.. [F,L,R],
    set_vars(L, Vs, Lv),
    set_vars(R, Vs, Rv),
    Ev =.. [F,Lv,Rv].
set_vars(V, Vs, N) :- memberchk(V=N, Vs).
set_vars(V, _, V).

that yields

?- d((x*x+2*x+3)/(3*x),x,R), set_vars(R,[x=5],E), T is E.
R = ((1*x+x*1+ (0*x+2*1)+0)* (3*x)- (x*x+2*x+3)* (0*x+3*1))/ (3*x* (3*x)),
E = ((1*5+5*1+ (0*5+2*1)+0)* (3*5)- (5*5+2*5+3)* (0*5+3*1))/ (3*5* (3*5)),
T = 0.29333333333333333

but, there is a bug in your first clause, that once corrected, will allow to evaluate directly the derived expression:

d(X,V,1) :- X == V, !.
...

now, we can throw away the utility set_vars/3, so

?- d((T*T+2*T+3)/(3*T),T,R), T=8, V is R.
T = 8,
R = ((1*8+8*1+ (0*8+2*1)+0)* (3*8)- (8*8+2*8+3)* (0*8+3*1))/ (3*8* (3*8)),
V = 0.3177083333333333.

Prolog - simplify derivative

2 Answers2

Linked