Advanced · Lesson 42 of 43

Symbolic computation

Differentiate and simplify expressions, programs as algebra.

Prolog treats expressions as plain data, so symbolic math falls out almost for free. An expression like x^3 + 2*x is just a term; x is an atom (not a variable!). We write rules mapping an expression to its derivative.

% d(Expr, Var, Derivative)
d(N, _, 0)          :- number(N).
d(X, X, 1)          :- atom(X).
d(Y, X, 0)          :- atom(Y), Y \== X.

d(U + V, X, DU + DV)   :- d(U, X, DU), d(V, X, DV).
d(U - V, X, DU - DV)   :- d(U, X, DU), d(V, X, DV).
d(U * V, X, U*DV + DU*V) :- d(U, X, DU), d(V, X, DV).
d(U ^ N, X, N * U^N1 * DU) :- integer(N), N1 is N - 1, d(U, X, DU).

d(sin(U), X, cos(U) * DU)      :- d(U, X, DU).
d(cos(U), X, -(sin(U)) * DU)   :- d(U, X, DU).
d(exp(U), X, exp(U) * DU)      :- d(U, X, DU).

?- d(x^2, x, D)

?- d(3*x + 5, x, D)

?- d(sin(x*x), x, D)

Correct, but ugly: 2*x^1*1. A second pass simplifies, removing + 0, * 1, * 0, and evaluating constants:

simplify(E, E) :- atomic(E), !.
simplify(E, S) :-
    E =.. [Op, A, B], !,
    simplify(A, SA), simplify(B, SB),
    simp(Op, SA, SB, S).
simplify(E, S) :-
    E =.. [F, A],
    simplify(A, SA),
    S =.. [F, SA].

simp(+, 0, X, X) :- !.
simp(+, X, 0, X) :- !.
simp(-, X, 0, X) :- !.
simp(*, 0, _, 0) :- !.
simp(*, _, 0, 0) :- !.
simp(*, 1, X, X) :- !.
simp(*, X, 1, X) :- !.
simp(^, X, 1, X) :- !.
simp(Op, A, B, V) :- number(A), number(B), !, E =.. [Op, A, B], V is E.
simp(Op, A, B, E) :- E =.. [Op, A, B].

derivative(Expr, Var, Simple) :- d(Expr, Var, D), simplify(D, Simple).

?- derivative(x^2, x, D)

?- derivative(x^3 + 2*x + 1, x, D)

?- derivative(sin(x*x), x, D)

?- derivative(exp(2*x), x, D)

Run derivative(x^4, x, D) and then differentiate the result by feeding it back in, you get the second derivative. The rules are tiny because each one follows the shape of the expression.

Defining your own operators

Prolog's syntax is extensible. op(Priority, Type, Name) teaches the reader a new operator. Lower priority binds tighter; xfx means "infix, non-associative". This is only notation, the term underneath is the same:

:- op(700, xfx, ===>).
:- op(200, xfy, and).

rewrite(X and true ===> X).
rewrite(X and false ===> false).

?- rewrite(foo and true ===> Result)

?- X = (a ===> b), X =.. Parts

?- X = (a and b and c), X = (First and Rest)

That's how Prolog can express DSLs: rules for a type checker, a rewrite engine, a configuration language, written directly in the host syntax.

Exercise: Derivative of a logarithm

The differentiation rules (without simplify) are loaded. Add a rule for the natural logarithm: the derivative of log(U) is DU / U, where DU is the derivative of U.